## Homework 5

Assigned: Mar. 18
Due: Mar. 25

### Problem 1

Note: I STRONGLY recommend that anyone who did not do well on problem 6 of the midterm should work through this problem:

Consider the following scenario: There are three processes, A, B, and C. The OS is running a round-robin scheduler. At time 0, process A is is beginning to run and the FIFO ready queue holds {B,C} in that order. The time for a context switch is 2 msec. The activities of the three processes are as follows:

A will run a CPU burst of 20 msecs. It then blocks for an I/O call which will take 60 msec to complete. It then runs for a CPU burst of 40 msec. It then terminates.

B will run a CPU burst of 10 msecs. It then blocks for an I/O call which will take 80 msec to complete. It then runs for a CPU burst of 20 msec. It then terminates.

C will run a CPU burst of 25 msec. It then blocks for an I/O call which will take 40 msec to complete. It then runs for a CPU burst of 50 msec. It then terminates.

Note:

• If process X is running, and all other processes are blocked, and X comes to the end of its time quantum, then X can proceed to the next time quantum without the need of a context switch.
• If all processes are blocked, and process X become ready, then the OS must carry out a context switch before X can run.
• If process X unblocks and there are already processes on the ready queue, then X is placed at the end of the ready queue.

Trace the evolution of the system, and compute the CPU efficiency, from T=0 until all three processes are complete, under each of the following assumptions:

• A. The time quantum is 15 msec. The different calls to I/O can all be handled concurrently; (e.g. each different process is using a different I/O device.) Thus, the clock time when a process unblocks is always the time when it blocks plus the time required for its I/O call.
• B. The time quantum is 30 msec. The different calls to I/O can all be handed concurrently, as in (A).
• C. The time quantum is 15 msec. The different calls to I/O must be handled sequentially; that is, they are all using the same device, which can only handle one request at a time. The I/O device handles its requests in first-come, first-served order.
• D. The time quantum is 30 msec. The different calls to I/O must be handled sequentially, as in (C).

### Problem 2

Suppose you have a multi-processing system using variable-length segments for memory management. The total size of memory is 128M. Jobs enter and exit the system as follows:
```At time 0, Process A, of size 36M, enters.
At time 1, Process B, of size 70M, enters.
At time 2, Process A terminates.
At time 3, Process C, of size 15M, enters.
At time 4, Process D, of size 20M, enters.
At time 5, Process E, of size 20M, enters.
At time 6, Process F, of size 15M, enters.
At time 7, Process B terminates.
At time 8, Process G, of size 50M, enters.
At time 9, Process D terminates.
At time 10, Process F terminates.
At time 11, Process E terminates.
```
Trace the evolution of the system -- that is, the placement of each process in memory -- (a) if the "first fit" algorithm is used; (b) if the "best fit" algorithm is used. Assume that
• A process is always placed at the bottom of the chosen empty segment.
• If a process cannot be placed in memory when it enters, it is placed at the end of a FIFO queue of waiting processes.
• When a process terminates, the scheduler goes down the FIFO queue in order, using the specified algorithm to pick an empty segment for each process in turn. If a process cannot fit, then it stays in its place in the queue, and the scheduler continues to look down the FIFO queue for some other job that may fit.