3120 Take-home Midterm
Posted 25 June 2010
Due 2 July 2010
- As mentioned in class, many early operating systems regarded processes as different timesharing users. The process abstraction is a popular way to organize concurrent programs, but it is not the only choice. In order to build an editing system for multiple users, a traditional organization would be that each user runs as a separate process, all those processes executing the same code, which is shared among them. An alternative organization would be for each user to send a request to a single editing server process. This corresponds to a process abstraction with a single server process that maintains queues of work to do: this process never blocks as long as there is work to do, but completes (natural break), each work item it starts then switches to working on another pending work item. In particular, the application does not block awaiting input but instead polls to find if input from another client is available: processing requests are typically divided into several work items, that may be immediately queued for work to be done, Requests may be delayed pending completion of other work requests. The server process opens, modifies, and saves files on behalf of any of its clients. Discuss this alternative vis-à-vis implementing the program as per user processes coordinated by a general-purpose operating system.
- Most process abstractions support processes being destroyed when the program terminates, or in response to a specific kill directive. There are two common implementations, one a “poison pill” where the process is sent a command to kill itself, and the other where the system itself kills the process, not permitting the process to execute further at all. What actions need to be taken when a program terminates or a process is killed? What if that process destruction is not the consequence of normal process termination, but rather is the consequence of software failure?
- The standard way for debuggers to plant interactive breakpoints in a program in RAM (whatever the processor instruction set) is to save the breakpointed instruction and replace it by a jump to the breakpoint handling code. After the breakpoint is triggered, the saved instruction is restored in its original place in the code. If the interactive dialogue with the debugger during the breakpoint handling indicates that that the triggered breakpoint is to be removed, execution of the program can be resumed simply by jumping to the instruction that had been breakponted. However, if the dialogue with the debugger indicates that the breakpoint is to remain in place when execution of the program is resumed, implementation is more complicated. Execution of the saved instruction could be emulated, but this is difficult to do, ensuring all side effects such as condition code setting and exception triggering are performed correctly, as well as correctly simulating all addressing modes, such as PC relative. It is much easier simply to execute the breakpointed instruction in place, but to plant another breakpoint on a subsequent instruction in the same basic block, usually the immediate successor to the original breakpoint, so that the breakpoint handler can regain control in order to replant the original breakpoint and remove the secondary one. This obviously has some challenges if the successor of the breakpointed instruction cannot be statically predicted, for instance if the breakpointed instruction is a conditional jump, but a common solution is simply to ban planting breakpoints on such instructions.
Identify the critical races that exist with this scheme if the program is executed by multiple threads, possibly multiple cores or multiple processors. Use pseudo-code to illustrate how you would resolve these issues. - With software algorithms for mutual exclusion, such as Dekker’s algorithm, Peterson’s algorithm, or Lamport’s bakery algorithm, note that optimizing compilers and out-of-order execution by processors could invalidate most of these algorithms because such “optimization” does not take into account that the value of a shared variable can be changed by something other than the immediately evident code. This overly-simplistic characterization also happens with I/O devices, especially simple programmed I/O where data or control register contents changes as a result of the state of the device, not as a consequence of execution of processor instructions, as well as with clocks where the current time register changes continually. It also happens when DMA is used to input blocks of data, which is slightly more complex because the addresses whose value changes are not evident literally. What does this imply about device drivers?
- Priority Scheduling leads to the risk of starvation: a process is ready, but never is given the processor. Some preemptive priority schedulers therefore reserve a fraction of the processor cycles for use on lower priority queues, some others implement priority aging whereby the priority of a process increases the longer it has been waiting. Discuss the relative advantages and disadvantages of these schedulers versus a preemptive priority scheduler where priorities are fixed, and the analysis of response time of a process needonly consider processes at the same and higher priorities (assuming priority inversion is ignored), and where also a process can guarantee that no higher priority process can be pending when this process is executing (i.e. higher priority process execution is atomic with respect to this process.).