Test 1 - Processes

CS 505, Operating Systems Concepts

  1. Explain how the scheduler can help turn a passive wait semaphore operation into an active wait operation.

    A semaphore implementing a passive wait doesn't cause a context switch when a process signals the semaphore; an active wait would context switch the signaling process to give a waiting process (if any) a chance to execute.

    The scheduler helps implement an active wait in two ways: it recognizes that the running process is signaling a semaphore, and so should move out of the cpu, and picks a waiting process to receive the cpu.

  2. A batch disk contains two programs. Program 0 is one block long and program 1 is two blocks long. If User Space is n blocks long, what is the maximum number of copies of program 1 that program 0 can fork? 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 forked process uses 2 blocks of storage and User Space contains a total of m storage blocks, then at most floor((n - 1)/2) 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 forked 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 in the operating system available for representing the process control blocks.

  3. A colleague of yours thinks it would be a good idea to change the join() system call so that any number of processes could join with a process, instead of having just one process join. Would you volunteer to implement this change in your operating system? Explain.

    Probably not. The difficulty with your colleague's idea is in determining when an exited process can be purged from the system. In the assignment, only one process can join with an exited process, so the joined process can be purged after a join. However, your colleague's idea prevents this because any number of processes could potentially join with the exited process.

  4. Shortest-job first scheduling produces the optimum average wait time under an important assumption. Explain the assumption.

    The important qualifier for shortest job first scheduling is that it be done with a fixed set of processes; processes that enter the system after a shorest job first schedule has been determined can result in larger than minimal average wait times. To see why this is a problem, imagine that a job with a long execution time enters the cpu and then a short execution time job enters the system. If the short job had been present from the start, it would have executed before the longer job, but as it is the wait time is now the length of the longer job rather than the shorter job.

This page last modified on 20 June 2002.