Operating Systems Concepts Review
Process State Transitions
In Figure below, three process states are shown. In theory, with three states, there could be six transitions, two out of each state. However, only four transitions are shown. Are there any circumstances in which either or both of the missing transitions might occur?
Figure: A process can be in a running, blocked, or ready state. Transitions between these states are as shown.
- Process blocks for input
- Scheduler picks another process
- Scheduler picks this process
- Input becomes available
The transition from blocked to running is conceivable. Suppose that a process is blocked on I/O and the I/O finishes. If the CPU is otherwise idle, the process could go directly from blocked to running.
The other missing transition, from ready to blocked, is impossible. A ready process cannot do I/O or anything else that might block it. Only a running process can block.
Multithreaded Web Server
In Figure below, a multithreaded Web server is shown. If the only way to read from a file is the normal blocking read system call, do you think user-level threads or kernel-level threads are being used for the Web server? Why?
A worker thread will block when it has to read a Web page from the disk. If user-level threads are being used, this action will block the entire process, destroying the value of multithreading. Thus, it is essential that kernel threads are used to permit some threads to block without affecting the others.
Per-Thread Register Set
In Figure below, the register set is listed as a per-thread rather than a per-process item. Why? After all, the machine has only one set of registers.
Figure: The first column lists some items shared by all threads in a process. The second column lists some items private to each thread.
When a thread is stopped, it has values in the registers. They must be saved, just as when the process is stopped, the registers must be saved. Multiprogramming threads are no different than multiprogramming processes, so each thread needs its own register save area.
Single-Threaded vs. Multithreaded File Server
In this problem, you are to compare reading a file using a single-threaded file server and a multithreaded server. It takes 15 msec to get a request for work, dispatch it, and do the rest of the necessary processing, assuming that the data needed are in the block cache. If a disk operation is needed, as is the case one-third of the time, an additional 75 msec is required, during which time the thread sleeps. How many requests/sec can the server handle if it is single-threaded? If it is multithreaded?
In the single-threaded case, the cache hits take 15 msec and cache misses take 90 msec. The weighted average is 2/3 x 15 + 1/3 x 90. Thus the mean request takes 40 msec, and the server can do 25 per second.
For a multithreaded server, all the waiting for the disk is overlapped, so every request takes 15 msec, and the server can handle 66 2/3 requests per second.
Peterson’s Solution and Process Scheduling
Does Peterson’s solution to the mutual exclusion problem shown in Figure below work when process scheduling is preemptive? How about when it is non-preemptive?
It certainly works with preemptive scheduling. In fact, it was designed for that case. When scheduling is non-preemptive, it might fail. Consider the case in which turn is initially 0 but process 1 runs first. It will just loop forever and never release the CPU.
Implementing a Semaphore with Interrupts
Give a sketch of how an operating system that can disable interrupts could implement a semaphore.
To do a semaphore operation, the operating system first disables interrupts. Then it reads the value of the semaphore. If it is doing a down and the semaphore is equal to zero, it puts the calling process on a list of blocked processes associated with the semaphore. If it is doing an up, it must check to see if any processes are blocked on the semaphore. If one or more processes are blocked, one of them is removed from the list of blocked processes and made runnable. When all these operations have been completed, interrupts can be enabled again.
Dining Philosophers Problem
In the solution to the dining philosophers problem (see Figure below), why is the state variable set to HUNGRY in the procedure take_forks?
Figure: A nonsolution to the dining philosophers problem.
The change would mean that after a philosopher stopped eating, neither of his neighbors could be chosen next. In fact, they would never be chosen. Suppose that philosopher 2 finished eating. He would run test for philosophers 1 and 3, and neither would be started, even though both were hungry and both forks were available. Similarly, if philosopher 4 finished eating, philosopher 3 would not be started. Nothing would start him.