Operating Systems / Chapter 5: Parallel Processes /

In this course, we learned how to interact with the computer and I/O devices using shell commands. Many commands, such as cd and cat, finish almost instantly. But other commands either take a long time or run indefinitely. For example, serve_http keeps running until the user manually terminates the process.

The shell does not display the prompt until the command is finished. Thus, we cannot issue any new commands while serve_http is running. But just because serve_http is running does not mean that the process is staying busy the entire time. serve_http is like a cashier at a grocery store: serve_http is busy when it is processing client requests but is idle when it is waiting for requests to come in. What if the operating system can utilize the downtime by running other commands?

Multiprocess operating systems (MPOS) increase computer utilization by allowing users to issue multiple commands in parallel. The Logicwalk MPOS still runs one process at a time, but when the running process makes an I/O operation request (such as receive_message), MPOS pauses the process and starts running another process that is ready to run. Later, when the I/O operation is complete, MPOS pauses the other process that was running and resumes the process that was waiting for the I/O operation.

The process of pausing one process and resuming another process is called a context switch.

So how do we issue commands in parallel? In Unix-like operating systems (including LWOS), when we append an ampersand (&) to a command, the shell executes the command in the background. Here is an example session:

> serve_http&
>

serve_http& asks the shell to start serve_http in the background. Background tasks do not block the shell, so the shell immediately prints another prompt instead of waiting for serve_http to finish.

Suppose that we next issue the following command:

> cat name.txt

Then LWOS is going to pause serve_http and start cat name.txt in the foreground. Foreground tasks block the shell, so we have to wait until the cat command terminates before issuing more commands.

To highlight the difference between foreground and background tasks, let's compare the shell to an employee at a coffee shop. Executing a command in the foreground is analogous to the employee taking your order, making the coffee and serving it to you. On the other hand, executing a command in the background is analogous to the employee taking your order and handing it off to a barista. While the barista is making your coffee, the employee can then take another order.

The cat command runs until one of the following events occur:

• The cat command makes a system call.
• An I/O device interrupts LWOS.
• The cat command terminates.

LWOS may switch between serve_http and cat multiple times before the cat command terminates. But the OS switches context so fast and frequently that users don't even notice. In fact, the two processes appear to run at the same time.

Suppose that we run more commands in the background after the cat command terminates as follows:

> python calculate_pi.py&

> web_browser&

> video_player&

Now 4 commands are running concurrently.

Try starting some background tasks in the simulator below:

How Multiprocessing Works

Let's convert LWOS to a MPOS. First, we add a stack called Processes to keep track of the processes in the system. Whenever a user issues a command in the shell, LWOS creates a process state map and appends it to the Processes stack. The process state contains properties that are necessary to run and pause a process, such as the command associated with the process and the process status.

Each process can now be identified by the index of the process state in the Processes stack. For example, the process ID of the first process is 0, since the process state associated with the first process is located at index 0 of the Processes stack.

Since each process is associated with its own command and status, we remove the Command and Status properties at the system level. Instead, we add a property called Current Process, which contains the index of the process that is currently running.

Finally, we add a property called Foreground Process, which contains the ID of the process that is running in the foreground (if any).

Here is an example of the updated LWOS state at startup (boot) time:

• Hostname: "a.com"
• Current Folder Index: 0
• Interrupts
  • Keyboard: false
• Tokens: [ ]
• Foreground Process: -1
• Current Process: -1,
• Processes: [ ]

Current Process is initially -1 which indicates that no process is currently running. Foreground Process is also -1 since no process is currently running in the foreground. Finally, the Processes stack is empty.

Suppose that the user executes:

> write name.txt JohnSmith

Then LWOS updates the state as follows:

• Hostname: "a.com"
• Current Folder Index: 0
• Interrupts
  • Keyboard: false
• Tokens: [ "name.txt", [ "JohnSmith", [ ] ] ],
• Processes:
  • 0
    • Command: "write"
    • Status: "WAITING_FOR_FS",
• Foreground Process: 0
• Current Process: 0
• File System:
  • Requests
    • 0
      • Mode: "WRITE"
      • Process: 0
      • Data: [ folders ]

LWOS creates a new process state and pushes it to the Processes stack. The ID of this process is the index of the process state in the Processes stack, which is 0. LWOS also updates Foreground Process to 0. If the process was started in the background, then the Foreground Process would remain at -1.

Changes to the File System Property

In MPOS, when a process makes a disk write request, the OS needs to record the ID of that process. Why? After the disk write operation is complete, the hard drive interrupts the OS. The OS then needs to notify and resume the process that made the disk request. Without the ID, the OS does not know which process to notify.

Let's record the process ID in a new property called File System -> Process. Then when the OS is interrupted by the hard drive, the OS can resume the process whose ID is File System -> Process.

Unfortunately, we have another problem. While one process, say A, is waiting for a file system operation, another process, say B, may overwrite the File System property with its own request. Then when the disk operation is complete, the OS may resume process B instead of A.

To prevent processes from overwriting requests, we replace the File System properties with a stack called Requests.

Under the new request system, when a process wants to perform a disk operation, it appends a new request, which consists of the operation mode, the process ID, and the data, to File System -> Requests.

When the length of File System -> Requests is greater than 0, the hard drive processes the request at the top of the stack. The hard drive then interrupts LWOS as before.

LWOS then pops the top element of Requests stack. The Process property of the popped element is the ID of the process that made the disk operation request. LWOS resets Interrupts -> File System and resumes this process.

If the length of File System -> Requests is still greater than 0, the hard drive performs another operation. But the hard drive will wait until Interrupts -> File System is false to give LWOS time to pop File System -> Requests.

Switching Processes

When LWOS is interrupted by the hard disk, LWOS resumes the process that made the disk request. But if another process was running, then LWOS needs to first pause the running process. The ID of the running process is stored in the Current Process property. LWOS locates this process in the Processes stack and updates the process status to READY. Then LWOS resumes the blocked process by updating Current Process to the Process property of the file system request and updating the status of the blocked process to RUNNING.

If the new process either blocks on a system call or terminates, LWOS needs to switch processes yet again. LWOS searches the Processes stack for a process whose status is READY. Then LWOS once again updates LWOS -> Current Process to the ID of the ready process and updates the status of the new process to RUNNING.

Previous Lesson Next Lesson