Part 6. Implementing ps (30 points)

Click the link and read the description of ps as defined by the POSIX standard. (The Portable Operating System Interface, or POSIX, is a standard that various Unix-like operating systems including Linux distributions, BSD distributions, macOS, and others follow to a greater or lesser extent.)

There are many different versions of ps. Most support the options and output format specified in the POSIX standard as well as their own, nonstandard options. We’re going to restrict ourselves to a subset of POSIX.

Your task

Implement a subset of the ps utility functionality. In particular, your implementation needs to support the following command-line arguments.

  • -a Write information for all processes with controlling terminals. Omit processes for which is_session_leader() returns true.
  • -A/-e Write information for all processes.
  • -d Write information for all processes, except session leaders.
  • -f Generate a full listing.
  • -l Generate a long listing.

The -e option and the -A option are the same. You can support this in clap via

#[derive(Debug, Parser)]
#[command(author, version, about = "ps - report process status", long_about = None)]
struct Config 
    /// Write information for all processes.
    #[arg(short = 'A', short_alias = 'e')]
    all: bool,

    // ...
}

in your Config structure. (Review the Lab 4 for a refresher on how to parse command-line arguments with clap. Remember that you will need to run cargo add clap -F derive to add the clap crate with the derive feature.)

Notice that none of these options have equivalent long options. POSIX command line utilities tend not to.

The -a, -A, -d, and -e flags select which processes get displayed whereas the -f and -l options control what information about the selected processes to display.

Given a particular Process, you can decide if it should be printed by following this simple algorithm:

  1. If the -A or -e flag was passed, then print the process.
  2. If the -a flag was passed and the process has a controlling terminal and the process is not a session leader, then print the process.
  3. If the -d flag was passed and the process is not a session leader, then print the process.
  4. Otherwise if none of -a, -A, -d, and -e were passed and the process’s user ID is the same as the user ID of the ps process and the process’s controlling terminal is the same as the controlling terminal of the ps process, then print the process.

Remember that you can use Process::for_self() to get both the current user ID and controlling terminal.

I recommend implementing the algorithm to select the processes to print first and then print out the debug representation of the Process. Your printed output will differ, but the processes that you select for printing should match the behavior of the real ps when called with some of -a, -A, -d, and -e. Make sure you try combinations of arguments and none at all to make sure you’re getting the same number of processes.

Next, implement printing out the table that ps prints out. The spacing of the columns of output doesn’t need to match the spacing of the real system. So try to pick field widths large enough to contain the values in the table. (The real ps does a poor job of this because it expects some fields, like user IDs to be short.) See documentation here for how to print a field with a specific width.

There are 15 fields that ps will print about each process (subject to the -l and -f options). These are listed in the STDOUT section of the ps standard. We will only support a subset of these, namely

  • S,
  • UID,
  • PID,
  • PPID,
  • TTY,
  • TIME, and
  • CMD.

Look at the table in the man page to see which fields get printed when the -l and/or -f options are present.

You should print the fields in the same order as shown but only if the appropriate flag was passed as indicated in the middle column of the table in the STDOUT section of the ps standard. For example, the state field, S, is only displayed if -l is passed.

For this part, make sure you can print out the S, UID (as a number), PID, PPID, and CMD fields. We’ll tackle the TTY, TIME, and non-numeric UID in the next lab. In the mean time, print out the UID as numeric, even with -f, print out the process’s tty_nr field for TTY and print the total execution time as an integer for the time.

Here are some examples.

$ cargo run --quiet --
       PID TTY             TIME CMD
     11050 34816             32 ps
     29327 34816             55 bash

$ cargo run --quiet -- -l
S        UID        PID       PPID TTY             TIME CMD
R 1425750506      11135      29327 34816             29 ps
S 1425750506      29327      29326 34816             57 bash

$ cargo run --quiet -- -f
UID               PID       PPID TTY             TIME CMD
1425750506      11141      29327 34816             28 target/debug/ps -f
1425750506      29327      29326 34816             58 -bash

$ cargo run --quiet -- -fl
S UID               PID       PPID TTY             TIME CMD
R 1425750506      11155      29327 34816             28 target/debug/ps -fl
S 1425750506      29327      29326 34816             60 -bash

(You can see the execution time for that bash process creep up from 57 to 58 to 60 as I run commands because Bash has to wake up, process the command line, arrange for Linux to start running the command, and after the command runs, print a prompt and go back to sleep waiting for input. As you can see in the real output below, the actual execution time for bash after that last one is less than 1 second. In fact, it was about 0.6 seconds. We’ll see how to determine this in the next lab.)

For comparison, here’s the real output with those options.

$ ps
  PID TTY          TIME CMD
 8637 pts/0    00:00:00 ps
29327 pts/0    00:00:00 bash

$ ps -l
F S   UID   PID  PPID  C PRI  NI ADDR SZ WCHAN  TTY          TIME CMD
0 R 1425750506 8641 29327  0 80 0 - 7223 -      pts/0    00:00:00 ps
0 S 1425750506 29327 29326  0 80 0 - 9167 wait  pts/0    00:00:00 bash

$ ps -f
UID        PID  PPID  C STIME TTY          TIME CMD
steve     8645 29327  0 12:57 pts/0    00:00:00 ps -f
steve    29327 29326  0 Jul31 pts/0    00:00:00 -bash

$ ps -fl
F S UID        PID  PPID  C PRI  NI ADDR SZ WCHAN  STIME TTY          TIME CMD
0 R steve     8651 29327  0  80   0 -  9344 -      12:57 pts/0    00:00:00 ps -fl
0 S steve    29327 29326  0  80   0 -  9167 wait   Jul31 pts/0    00:00:00 -bash

Note that the CMD field displays the command_name unless -f was passed in which case it shows all of the command line arguments, if it can. If -f was passed but /proc/<pid>/cmdline was an empty file, your process.command_line field will be empty. In this case, the standard says to print the command name in brackets. You might want some code like this.

#![allow(unused)]
fn main() {
struct Config { full: bool }
struct Process { command_name: String, command_line: Vec<String> }
let config = Config { full: true };
let process = Process { command_name: String::new(), command_line: Vec::new() };
let cmd: String = if !config.full {
    process.command_name
} else if process.command_line.is_empty() {
    format!("[{}]", process.command_name)
} else {
    process.command_line.join(" ")
};
}

Info

If your code is working as described up to this point (congratulations!), you’re done and can submit it by following the instructions. You don’t need to keep reading.

However, I want to explain some of the terms you encountered regarding processes. Specifically, “session” and “controlling terminal.” What the heck are these? Read on!

In some of the early days of computing, a user would interact with a computer by sitting down at a computer terminal which consisted of a keyboard and a display. Earlier terminals contained a printer rather than a display and output was displayed to the user by printing it! Click on that link to look at some images of computer terminals on Wikipedia. Note in particular that a hard-copy terminal (one that printed the output) was called a teletypewriter or TTY. This terminology persists today. The TTY in the ps output refers to exactly this. But that’s getting ahead of our story here.

If you think about multiple users using hardware terminals to interact with the same computer, it’s clear that input from the keyboard in one terminal should only go to certain processes on the computer, namely the ones that particular user is running from that terminal. By the same token, any output from those processes should go back to the same terminal.

We no longer use hardware terminals any longer, of courrse. Instead, we use terminal emulation programs that are a software implementation of the hardware terminals.

The notion of sessions and controlling terminals arose out of the need to keep input/output associated with the correct processes. These concepts were standardized in the POSIX standard in the General Terminal Interface portion of the standard. Read that link if you want all of the details.

In fact, there’s a third concept, a process group, which is essential to understand for this as well. I’ll layout the terminology first and then explain what happens when a user interacts with the system.

  • Process – A running instance of a computer program. Every process has a process ID (PID), a parent process ID (PPID), a process group ID (PGID), and a session ID (SID), and a controlling terminal (TTY). All of these IDs are just integers and are present in the /proc/<pid>/stat file as you saw.
  • Process group – A group of related processes that share a PGID. A process group is usually created by the shell for each pipeline. E.g., if you run $ sort foo | uniq -c | sort -rn, bash will create a new process group containing 3 processes, the two sort processes and the uniq process.
  • Session – A set of process groups. Every process in each process group in a session has the same SID and the same TTY (or they all have none).
  • Controlling terminal – A controlling terminal is an abstraction. It’s just an integer that the operating system kernel, Linux in this case, uses to represent a hardware of software terminal. Every controlling terminal has a foreground process group.
  • Foreground process group – Definitionally, a foreground process group is just the process group that is the foreground process group for the controlling terminal of the process group’s member processes. But more importantly, only processes in the foreground process group of a controlling terminal can receive input from that terminal.
  • Process group leader – A process is the process group leader of its process if and only if its PID is equal to its PGID.
  • Session leader – A process is the session leader of its session if and only if its PID is equal to the SID. We saw this in the Process::is_session_leader() function in Part 4.

These all fit together roughly like this.

The user sits down at the terminal and logs in. The shell, let’s say bash, is started. Initially, the bash process is the only process in its process group and its process group will be the only process group in its session. Thus bash will be both its process group’s leader and its session’s leader. We can get the real ps to print out the various identifiers using the -o option.

Here’s the real output from ps showing bash as the process group leader and the session leader.

$ ps -o pid,pgid,sid,tname,command
  PID  PGID   SID TTY      COMMAND
29327 29327 29327 pts/0    -bash

(I removed the output for the ps process itself.) Notice that the PID, PGID, and SID are all the same.

Let’s run a pipeline and look at the output from ps. On one terminal, I’m going to run $ sort | uniq -c | sort -nr. The first sort will sleep waiting for input from the terminal. On a second terminal, I’m going to run ps and use one of the nonstandard options -s to select only the processes that match the SID of the bash process shown above and it’s also printing out the parent process ID (PPID).

$ ps -s 29327 -o pid,ppid,pgid,sid,tname,command
  PID  PPID  PGID   SID TTY      COMMAND
17314 29327 17314 29327 pts/0    sort
17315 29327 17314 29327 pts/0    uniq -c
17316 29327 17314 29327 pts/0    sort -nr
29327 29326 29327 29327 pts/0    -bash

The key things to notice are

  1. bash is the parent process of the other three (i.e., the PPID of the sort and uniq processes is the PID of bash);
  2. All three processes that were created for the pipeline have the same process group ID (PGID), 17314, which is different from the PGID of bash; and
  3. The first sort process is the process group leader of its group (i.e., its PID is equal to its PGID, 17314).
  4. All four processes have the same TTY (which we know they must because they all have the same SID).

I said above that only processes in the foreground process group of a controlling terminal are allowed to read input from the terminal. We can ask ps to display the process group ID of the foreground process group of the controlling terminal of each process, if any. (That’s a mouthful. I mean something like this pseudocode: process.controlling_terminal().foreground_process_group().id().)

$ ps -s 29327 -o pid,ppid,pgid,sid,tgid,tname,command
  PID  PPID  PGID   SID TPGID TTY      COMMAND
17314 29327 17314 29327 17314 pts/0    sort
17315 29327 17314 29327 17314 pts/0    uniq -c
17316 29327 17314 29327 17314 pts/0    sort -nr
29327 29326 29327 29327 17314 pts/0    -bash

The TPGID column holds the process group ID of the active foreground process group for the controlling TTY. All four processes have the same TTY, symbolic name pts/0, and thus all have the same TPGID. Since foreground process group of pts/0 has ID 17314, we can see that it’s only the sort | uniq | sort pipeline which is able to receive input from the terminal. In particular, bash cannot do so at this time.

I had to log in to use a second terminal to run these commands because, as we’ve just discussed, the process group for the pipeline is the only one that can receive input from its controlling terminal right now. If I print out all of the processes belonging to my user (using the nonstandard -u option) rather than just the processes associated with the session we’ve been looking at so far, I get this (I cut off the right side of ps’s output as it’s long and unimportant).

$ ps -u steve -o pid,ppid,pgid,sid,tpgid,tname,command
  PID  PPID  PGID   SID TPGID TTY      COMMAND
17314 29327 17314 29327 17314 pts/0    sort
17315 29327 17314 29327 17314 pts/0    uniq -c
17316 29327 17314 29327 17314 pts/0    sort -nr
18314 29326 18314 18314 18408 pts/5    -bash
18408 18314 18408 18314 18408 pts/5    ps -u steve -o pid,ppid,pgid,
23147     1 22908 22908    -1 ?        sh /usr/users/noquota/faculty
23157 23147 22908 22908    -1 ?        /net/storage/zfs/faculty/stev
23218 23157 22908 22908    -1 ?        /net/storage/zfs/faculty/stev
24880     1 24880 24880    -1 ?        /lib/systemd/systemd --user
24882 24880 24880 24880    -1 ?        (sd-pam)
29326 29306 29306 29306    -1 ?        sshd: steve@pts/0,pts/5
29327 29326 29327 29327 17314 pts/0    -bash
29401 29326 29401 29401    -1 ?        -bash
29477 29401 29401 29401    -1 ?        bash
29529 23157 22908 22908    -1 ?        /net/storage/zfs/faculty/stev
29540 23157 22908 22908    -1 ?        /net/storage/zfs/faculty/stev
29596 29529 22908 22908    -1 ?        /net/storage/zfs/faculty/stev
29604 23218 29604 29604 29604 pts/4    /bin/bash --init-file /net/st
29673 29529 22908 22908    -1 ?        /usr/users/noquota/faculty/st
29723 29673 22908 22908    -1 ?        /net/storage/zfs/faculty/stev

There’s a lot of output here, but some things to notice:

  1. I’m actually connected to 3 different TTYs, pts/0, pts/4, and pts/5. All three of these come from sshing into a Linux server. The processes on pts/4 are actually from Visual Studio Code on my Mac sshing to the server.
  2. Some of these processes don’t have a controlling terminal, it shows ? instead. These processes will never read or write to a terminal. Most of these were started by Visual Studio Code and are things like the rust-analyzer VS Code extension running in the background.

Once the pipeline ends (all of the processes in it have completed), bash will arrange for its process group to once again be the foreground process group for its controlling terminal so that it can print out the prompt and wait for the next line of input.

In the next lab, you will implement the kill command-line utility which can terminate individual processes by PID or entire process groups by PGID. For example, I can kill the entire sort | uniq | sort pipeline’s process group. To distinguish between a PID and a PGID, we use a negative value to indicate the PGID and a positive value to indicate the PID. This command kills every process in process group 17314, namely the pipeline.

$ kill -TERM -17314

For the final time, let’s print out details about the processes in that first session.

$ ps -s 29327 -o pid,ppid,pgid,sid,tgid,tname,command
  PID  PPID  PGID   SID  TGID TTY      COMMAND
29327 29326 29327 29327 29327 pts/0    -bash

And there we go. We’re back to a single process, bash, in a single process group in the session. This process group is the controlling terminal’s foreground process group.

I didn’t show an example, but bash can create background process groups, change up which group is the foreground process group and perform a wide variety of so-called “job control.” There’s a bunch of information in the Bash manual. I almost never avail myself of this functionality, but in specific circumstances, it can be useful.

Hopefully, you now have a better understanding of the somewhat unusual behavior of ps with respect to which processes it prints information about in response to -a/-A/-d/-e. To recap:

  • If none of those options are passed, ps prints out just the processes running in the current terminal. This makes historical sense: a user would typically only be logged in to a single terminal so it makes sense to show only those processes by default.
  • The -a and -d options show all processes except for session leaders (and -a also omits processes without a controlling terminal). Why not show session leaders? My best guess is because this is basically always going to be the shell and you’re not likely to want to see a bunch of bash instances and if you really want to, you can use -A or -e.

If you read this far, I’m impressed! I think understanding the low-level details of how systems work is really cool. This is one of those super important, but not well understood areas of computers. Now, having read this, you’re better informed about how processes and terminals work on Unix-like systems, including macOS and Linux, than almost every single computer programmer.