Processes

Due:

11:00pm, Friday February 4, 2022

Description

For this assignment we will run process related simulators from the textbook supplementary material (source) and answer related questions. A zip file with the simulator programs linked on the assignments page. The README files for each program are listed below that contain information on how to run each simulator program. Read these before answering the questions that follow.

process.py README

This program, called process-run.py, allows you to see how the state of a process state changes as it runs on a CPU. As described in the chapter, processes can be in a few different states:

RUNNING - the process is using the CPU right now
READY   - the process could be using the CPU right now
          but (alas) some other process is
WAITING - the process is waiting on I/O
          (e.g., it issued a request to a disk)
DONE    - the process is finished executing

In this homework, we’ll see how these process states change as a program runs, and thus learn a little bit better how these things work.

To run the program and get its options, do this:

prompt> ./process-run.py -h

If this doesn’t work, type python before the command, like this:

prompt> python process-run.py -h

What you should see is this:

Usage: process-run.py [options]

Options:
  -h, --help            show this help message and exit
  -s SEED, --seed=SEED  the random seed
  -l PROCESS_LIST, --processlist=PROCESS_LIST
                        a comma-separated list of processes to run, in the
                        form X1:Y1,X2:Y2,... where X is the number of
                        instructions that process should run, and Y the
                        chances (from 0 to 100) that an instruction will use
                        the CPU or issue an IO
  -L IO_LENGTH, --iolength=IO_LENGTH
                        how long an IO takes
  -S PROCESS_SWITCH_BEHAVIOR, --switch=PROCESS_SWITCH_BEHAVIOR
                        when to switch between processes: SWITCH_ON_IO,
                        SWITCH_ON_END
  -I IO_DONE_BEHAVIOR, --iodone=IO_DONE_BEHAVIOR
                        type of behavior when IO ends: IO_RUN_LATER,
                        IO_RUN_IMMEDIATE
  -c                    compute answers for me
  -p, --printstats      print statistics at end; only useful with -c flag
                        (otherwise stats are not printed)

The most important option to understand is the PROCESS_LIST (as specified by the -l or –processlist flags) which specifies exactly what each running program (or ‘process’) will do. A process consists of instructions, and each instruction can just do one of two things: - use the CPU - issue an IO (and wait for it to complete)

When a process uses the CPU (and does no IO at all), it should simply alternate between RUNNING on the CPU or being READY to run. For example, here is a simple run that just has one program being run, and that program only uses the CPU (it does no IO).

prompt> ./process-run.py -l 5:100 
Produce a trace of what would happen when you run these processes:
Process 0
  cpu
  cpu
  cpu
  cpu
  cpu

Important behaviors:
  System will switch when the current process is FINISHED or ISSUES AN IO
  After IOs, the process issuing the IO will run LATER (when it is its turn)

prompt> 

Here, the process we specified is “5:100” which means it should consist of 5 instructions, and the chances that each instruction is a CPU instruction are 100%.

You can see what happens to the process by using the -c flag, which computes the answers for you:

prompt> ./process-run.py -l 5:100 -c
Time     PID: 0        CPU        IOs
  1     RUN:cpu          1
  2     RUN:cpu          1
  3     RUN:cpu          1
  4     RUN:cpu          1
  5     RUN:cpu          1

This result is not too interesting: the process is simple in the RUN state and then finishes, using the CPU the whole time and thus keeping the CPU busy the entire run, and not doing any I/Os.

Let’s make it slightly more complex by running two processes:

prompt> ./process-run.py -l 5:100,5:100
Produce a trace of what would happen when you run these processes:
Process 0
  cpu
  cpu
  cpu
  cpu
  cpu

Process 1
  cpu
  cpu
  cpu
  cpu
  cpu

Important behaviors:
  Scheduler will switch when the current process is FINISHED or ISSUES AN IO
  After IOs, the process issuing the IO will run LATER (when it is its turn)

In this case, two different processes run, each again just using the CPU. What happens when the operating system runs them? Let’s find out:

prompt> ./process-run.py -l 5:100,5:100 -c
Time     PID: 0     PID: 1        CPU        IOs
  1     RUN:cpu      READY          1
  2     RUN:cpu      READY          1
  3     RUN:cpu      READY          1
  4     RUN:cpu      READY          1
  5     RUN:cpu      READY          1
  6        DONE    RUN:cpu          1
  7        DONE    RUN:cpu          1
  8        DONE    RUN:cpu          1
  9        DONE    RUN:cpu          1
 10        DONE    RUN:cpu          1

As you can see above, first the process with “process ID” (or “PID”) 0 runs, while process 1 is READY to run but just waits until 0 is done. When 0 is finished, it moves to the DONE state, while 1 runs. When 1 finishes, the trace is done.

Let’s look at one more example before getting to some questions. In this example, the process just issues I/O requests. We specify here that I/Os take 5 time units to complete with the flag -L.

prompt> ./process-run.py -l 3:0 -L 5
Produce a trace of what would happen when you run these processes:
Process 0
  io
  io_done
  io
  io_done
  io
  io_done

Important behaviors:
  System will switch when the current process is FINISHED or ISSUES AN IO
  After IOs, the process issuing the IO will run LATER (when it is its turn)

What do you think the execution trace will look like? Let’s find out:

prompt> ./process-run.py -l 3:0 -L 5 -c
Time        PID: 0           CPU           IOs
  1         RUN:io             1          
  2        WAITING                           1
  3        WAITING                           1
  4        WAITING                           1
  5        WAITING                           1
  6        WAITING                           1
  7*   RUN:io_done             1          
  8         RUN:io             1          
  9        WAITING                           1
 10        WAITING                           1
 11        WAITING                           1
 12        WAITING                           1
 13        WAITING                           1
 14*   RUN:io_done             1          
 15         RUN:io             1          
 16        WAITING                           1
 17        WAITING                           1
 18        WAITING                           1
 19        WAITING                           1
 20        WAITING                           1
 21*   RUN:io_done             1

As you can see, the program just issues three I/Os. When each I/O is issued, the process moves to a WAITING state, and while the device is busy servicing the I/O, the CPU is idle.

To handle the completion of the I/O, one more CPU action takes place. Note that a single instruction to handle I/O initiation and completion is not particularly realistic, but just used here for simplicity.

Let’s print some stats (run the same command as above, but with the -p flag) to see some overall behaviors:

Stats: Total Time 21
Stats: CPU Busy 6 (28.57%)
Stats: IO Busy  15 (71.43%)

As you can see, the trace took 21 clock ticks to run, but the CPU was busy less than 30% of the time. The I/O device, on the other hand, was quite busy. In general, we’d like to keep all the devices busy, as that is a better use of resources.

There are a few other important flags:

  -s SEED, --seed=SEED  the random seed  
    this gives you way to create a bunch of different jobs randomly

  -L IO_LENGTH, --iolength=IO_LENGTH
    this determines how long IOs take to complete (default is 5 ticks)

  -S PROCESS_SWITCH_BEHAVIOR, --switch=PROCESS_SWITCH_BEHAVIOR
                        when to switch between processes: SWITCH_ON_IO, SWITCH_ON_END
    this determines when we switch to another process:
    - SWITCH_ON_IO, the system will switch when a process issues an IO
    - SWITCH_ON_END, the system will only switch when the current process is done 

  -I IO_DONE_BEHAVIOR, --iodone=IO_DONE_BEHAVIOR
                        type of behavior when IO ends: IO_RUN_LATER, IO_RUN_IMMEDIATE
    this determines when a process runs after it issues an IO:
    - IO_RUN_IMMEDIATE: switch to this process right now
    - IO_RUN_LATER: switch to this process when it is natural to 
      (e.g., depending on process-switching behavior)

fork.py README

The simulator fork.py is a simple tool to show what a process tree looks like when processes are created and destroyed.

To run it, just:

prompt> ./fork.py

If this doesn’t work, type python before the command, like this:

prompt> python fork.py

What you’ll see then is a list of actions, such as whether a process calls fork to create another process, or whether a process calls exit to stop running.

Each process that is running can have multiple children (or none). Every process, except the initial process (which we call a here for simplicity), has a single parent. Thus, all processes are related in a tree, rooted at the initial process. We will call this tree the Process Tree and understanding what it looks like as processes are created and destroyed is the point of this simple homework.

Simple Example

Here is a simple example:

prompt> ./fork.py -s 4

                           Process Tree:
                               a
Action: a forks b
Process Tree?
Action: a forks c
Process Tree?
Action: b forks d
Process Tree?
Action: d EXITS
Process Tree?
Action: a forks e
Process Tree?

From the output, you can see two things. First, on the right, is the initial state of the system. As you can see, it contains one process, a. Operating systems often create one or a few initial processes to get things going; on Unix, for example, the initial process is called init which spawns other processes as the system runs.

Second, on the left, you can see a series of Action listings, in which various actions take place, and then a question is posed about the state of the process tree is at that point.

To solve, and show all outputs, use the -c flag, as follows:

prompt> ./fork.py -s 4 -c

                           Process Tree:
                               a

Action: a forks b
                               a
                               └── b
Action: a forks c
                               a
                               ├── b
                               └── c
Action: b forks d
                               a
                               ├── b
                               │   └── d
                               └── c
Action: d EXITS
                               a
                               ├── b
                               └── c
Action: a forks e
                               a
                               ├── b
                               ├── c
                               └── e
prompt>

As you can see, the expected tree that results (shown left-to-right) from a particular operation is shown now. After the first action, a forks b, you see a very simple tree, with a shown as b’s parent. After a few more forks, a call to exit is made by d, which reduces the tree. Finally, e is created, and the final tree, with a as parent of b, c, and e (which are considered “siblings”), as the final state.

In a simplified mode, you can just test yourself by trying to write down the final process tree, using the -F flag:

prompt> ./fork.py -s 4 -F
                           Process Tree:
                               a

Action: a forks b
Action: a forks c
Action: b forks d
Action: d EXITS
Action: a forks e

                        Final Process Tree?

Once again, you can use the -c flag to compute the answer and see if you were right (in this case, you should be, because it’s the same problem!)

Other Options

A number of other options exist with the fork simulator.

You can flip the question around with the -t flag, which allows you to view process tree states and then guess what action must have taken place.

You can use different random seeds (-s flag) or just don’t specify one to get different randomly generated sequences.

You can change what percent of actions are forks (vs exits) with the -f flag.

You can specify specific fork and exit sequences with the -A flag. For example, to have a fork b, b then fork c; c exit, and finally, a fork d, just type (we show -c here to solve the problem, too):

prompt> ./fork.py -A a+b,b+c,c-,a+d -c

                           Process Tree:
                               a

Action: a forks b
                               a
                               └── b
Action: b forks c
                               a
                               └── b
                                   └── c
Action: c EXITS
                               a
                               └── b
Action: a forks d
                               a
                               ├── b
                               └── d

You can only show the final output (and see if you can guess all the intermediates to get there) with the -F flag.

Finally, you can change the printing style of the tree with the -P flag.

Questions

1. Run the process.py program with two processes: the first process must have one instruction and a 0% chance of CPU and the second process must have four instructions with a 100% chance of CPU. What is the command that you entered?

2. Reverse the order of the processes from question 1. Does changing the order matter? Why?

3. Run the same processes as described in question 1, but with the -S flag set to SWITCH_ON_END. How does the result change?

4. Run the following command:

   ./process-run.py -l 3:0,5:100,5:100,5:100 -S SWITCH_ON_IO -I IO_RUN_LATER

   Are the system resources utilized effectively? Why?

5. Run the same processes as in question 4, but with the -I flag set to IO_RUN_IMMEDIATE. How does the behavior differ? Why might running a process that just completed an I/O operation be a good idea?

6. The fork.py program has a flag -f that controls the likelihood that the next action is a fork; the higher it is, the more likely the next action will be a fork. Run the fork.py program with various values between 0.1 to 0.9. What do the resulting process trees look like as the percentage changes?

7. Run the command:

   ./fork.py -A a+b,b+c,c+d,c+e,c- -c

   What does this command do?

8. Run the same command as in question 7, but add the -R flag. How does the behavior change compared to the result from question 7?

Turning in the Assignment

Create a text file named assignment1.txt containing your answers to the questions. Submit your solution to the appropriate folder on D2L.

Note that your answers must be correctly numbered and only the answers must be in your submission; any answer solution that does not satisfy these requirements will be marked as a zero.