Learning Objectives

• exploration of a standard problem in Scala: edge reversal algorithm: converting a representation of a tree as a flat sequence of child-to-parent edges to one where each parent maps to a sequence of children
  • OO/imperative, with mutable data structures
  • functional, with immutable data structures
• software design principles
  • SoC (separation of concerns)
  • DRY (don't repeat yourself)
  • testcase superclass
• Scala programming techniques
  • console input
  • stackable traits
  • unit testing using ScalaTest
  • automated performance testing/microbenchmarking using ScalaMeter

Overview

This is a Scala-based solution to the process tree homework assignment from the course COMP 374/410: Introduction to Operating Systems.

In short, this program converts a flat list of current processes (showing process ID, parent process ID, etc.), as printed by the ps command

> ps -ef
  UID   PID  PPID   C STIME   TTY           TIME CMD
    0     1     0   0 24Aug23 ??        72:25.36 /sbin/launchd
    0   102     1   0 24Aug23 ??        26:34.38 /usr/libexec/logd
    0   103     1   0 24Aug23 ??         0:01.08 /usr/libexec/smd
...
  502   735     1   0 24Aug23 ??       659:59.66 /Applications/Microsoft Edge.app/...
...
  502 60704     1   0 10:53PM ??         1:17.05 /Applications/WhatsApp.app/...
...
  502 60706 60704   0 10:53PM ??         0:02.27 /Applications/WhatsApp.app/...
...
  502 65138   735   0 10:48AM ??         0:23.83 /Applications/Microsoft Edge.app/...
...

to a hierarchical process tree, as printed by the pstree command (you'd usually have to install this through your package manager).

> pstree
-+= 00001 root /sbin/launchd
 |--= 00102 root /usr/libexec/logd
 |--= 00103 root /usr/libexec/smd
 .
 .
 .
 |-+= 00735 laufer /Applications/Microsoft Edge.app/Contents/MacOS/Microsoft Edge
 | |--- 65138 laufer /Applications/Microsoft Edge.app/Contents/Frameworks/Microsoft Edge
 .
 .
 .
 |-+= 60704 laufer /Applications/WhatsApp.app/...
 | |--- 60706 laufer /Applications/WhatsApp.app/...
 .
 .
 .

Usage

To run the tests:

$ sbt test

To run the main methods, let's first generate the wrapper scripts:

$ sbt stage

Now we can run the various main methods:

$ ps -ef | ./target/universal/stage/bin/edu_luc_etl_osdi_processtree_scala_mutable_main
$ ps -ef | ./target/universal/stage/bin/edu_luc_etl_osdi_processtree_scala_groupby_main
$ ps -ef | ./target/universal/stage/bin/edu_luc_etl_osdi_processtree_scala_fold_main

To generate larger data sets for testing:

$ ./target/universal/stage/bin/edu_luc_etl_osdi_processtree_scala_fakeps_main 100000" > data.txt

On Windows, if you installed Git with the recommended third option, Use Git and optional Unix tools from the Windows Command Prompt, then you will have a ps command available.