Test 1 - Processes

CS 505, Operating Systems Concepts

  1. Give an example of a problem that could occur when a semaphore has a passive wait operation.

    A semaphore implementing a passive wait doesn't cause a context switch when a process signals the semaphore, which means any waiters on the semaphore won't have an immediate chance to try for the now free semaphore.

    The two main problems with passive semaphores are fairness and timeliness. A signalling process that isn't booted from the cpu after a signal doesn't give the waiting process a chance to signal the semaphore. In stead, the signalling process can re-lock the semaphore, monopolizing whatever it is the semaphore's protecting.

    The timliness problem occurs when semaphores are used for pure synchronization. If a semaphore is unlocked when a particular condition occurs (for example, the buffer is full, the critical region is empty) and waiting processes aren't woken up when the signal occurs, the condition may no longer be true once the waiter does wake up.

  2. The tree batch disk contains a program that forks two copies of itself, which fork two copies of themselves, and so on, until some number of copies have been forked. If the program is n blocks long and User space is m blocks long, what is the maximum number of copies of the program that can be forked? Assume all process are long-lived; don't bother accounting for exiting processes. (Think carefully before answering.)

    At first glance, the answer seems obvious: if each procss uses n blocks of storage and User Space contains a total of m storage blocks, then at most floor(m/n) process can fit in User Space at the same time.

    There is, however, a less obvious answer based on an important observation: the program used for each process is identical and unchanging, which means the processes can all share the same copy of the program. Because only one copy of the program needs to be in User Space, the maximum number of processes using that program is limited to the amount of space un the operating system avaiable for representing the process control blocks.

  3. A system uses time-slicing to eject processes from the cpu. Processes on the system are either batch or interactive. Characterize the quanta most appropriate for each process class.

    Interactive processes can be characterized as computations that do a lot of I-O and don't do a lot of work between I-O events. The second fact suggests that the quantum be small, because the interactive process likely won't need to much computing. The first fact suggests that the quantum size doesn't matter: once the process starts an I-O operation, it will be ejected from the cpu.

    Batch processes have characteristics opposite of those for interactive processes: relatively little I-O and lots of computation. This suggests the quantum size should be larger than that for interactive processes; the less often a processes is moved out of the cpu when its quantum is expired, the lower the context-switch overhead.

  4. Explain why shortest-job first scheduling produces the optimum average wait time.

    Suppose the ready queue contains n processes and process P,i requires time(Pi) units of execution time to complete.

    The wait time for Pi, wait(Pi), is the sum of all the execution times of the processes ahead of it in the ready queue:

    wait(Pi = sum j = 0 to i - 1 : time(Pj)

    Now supposet that Pi - 1 has a longer execution time than does Pi (that is, the ready queue isn't in shortest-job next order). Every process behind Pi has the same wait time, as does every process ahead of Pi - 1. However, Pi has a longer wait time then it normally would because time(Pi - 1) is longer than it normally would be. This leads to a longer wait time than if the two processes were switched in the ready queue.

This page last modified on 20 June 2002.