CS 438 Test 1

Test 1 - Processes

CS 438, Operating Systems Analysis

Explain how an interrupt vector improves over an interrupt signal.
An interrupt signal indicates only that a device has raised a signal; it does not indicate which device raised the signal. After receiving an interrupt signal, the CPU has to poll the devices to determine which one raised the interrupt.
An interrupt vector essentially represents multiple, different interrupt signals. By assigning each device its own interrupt signal, the CPU can learn from the signal itself which device raised the interrupt. In fact, most CPUs use the signal to index the interrupt vector and jump directly to the appropriate device handler.
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.
Given functions
```
put_message(tag, data)
data = get_message(tag)
```
having the same behavior as the associated system calls you implemented, describe a pseudo-code implementation of the synchronization needed to share an n-slot buffer, n > 1, between producers and consumers.
Perhaps the easiest way to solve this problem is to have a message per slot in the message pool. Each message would have one of two distinguished tags, either empty or full. The message data would be a slot number. The pool would start out with n messages, all with the empty tag.
Producers would execute the following code to place items in the buffer:
```
  while (true) 
    slot_no = get_msg(empty)
    buffer[slot_no] = produce()
    put_msg(full, slot_no)
```
Consumers would execute the following code to retrieve items from the buffer:
```
  while (true) 
    slot_no = get_msg(full)
    consume(buffer[slot_no])
    put_msg(empty, slot_no)
```

This page last modified on 11 October 2001.