CS 505 Test 1

Test 1 - Processes

CS 505, Operating Systems Concepts

Draw the process-state diagram for the operating system you've implemented. Make sure all nodes and edges are labeled.

If there's no matching message in the pool, then get_msg blocks the running process; otherwise, the process continues to run. Once blocked, a process remains blocked until a matching message appears in the pool, at which point the process (or one of the competing processes) becomes unblocked and ready to run. put_msg never blocks. The scheduler moves ready processes into the CPU, and because you weren't required to implement a pre-emptive scheduler, the process remains in the CPU until it blocks or exits. Processes entering the system are in the ready state.
Describe a set of jobs which, when scheduled by shortest-job next, produces the optimal (that is, minimal) average wait time, but which, when scheduled by nearest-deadline first, produces a non-optimal (that is, larger than minimum) average wait time.
Scheduling by shortest-job next produces minimum average wait times for any set of jobs. To create non-minimum average wait times under nearest-deadline first, assign deadlines inversely proportional to execution time; that is, longer executing jobs have closer deadlines. This deadline assignment inverts the job ordering produced by shortest-job next scheduling and results in non-minimal average wait times.
For example, consider three jobs with 1, 3, and 5 unit execution times. Under shortest-job next, the average wait time is
(0 + (1) + (1 + 3))/3 = 5/3 = 5/3 = 1.7 or so
Now assign deadlines based on execution time so that the job with the 5 unit execution time has the earliest deadline, the 3-unit job has the next deadline, and the 1-unit job has the last deadline. The average wait time is
(0 + (5) + (5 + 3))/3 = 13/3 = 4.3 or so
Explain the protection provided by the simulator's base and top registers.
The base and top registers protect storage from errant accesses. The contents of the base and top registers determine the range of Primary-Store addresses accessible to the executing user process. Any storage access outside the range defined by the base and top registers results in a illegal-address interrupt.
Show how an atomic increase-by-one instruction functionally equivalent to
```
int increase_by_one(mem) {
  return mem++
  }
```
can be used to provide mutual exclusion among any number of processes. Do not worry about overflow or fairness.
Give all competing processes access to the shared integer variable lock; initially, lock equals 0. A process wishing to establish mutual exclusion performs the following
```
while (increase_by_one(lock) != 0) {
  // sleep() or yield() or whatever.
  }
```
Once the process falls out of the loop, it has established mutual exclusion. To release mutual exclusion, the process executes
```
lock = 0
```
In this scheme, lock = 0 represents the stone in the bowl, and lock > 0 represents the empty bowl. The atomic increase_by_one() instruction lets a process grab the stone and empty the bowl un-interruptably, after which the bowl remains empty until the stone is returned to the bowl by assigning 0 to lock.

This page last modified on 11 October 2001.