CIS 415 Operating Systems - Spring 2003

Discussion: Week 10 session 2

Solutions

Banker's Algorithm

P4 completes - 0 1 1 1 2 1
P5 completes - 1 2 2 2 2 1
P3 completes - 1 2 3 4 5 6
P1 completes - 1 3 3 6 5 7
P2 completes - 1 3 3 7 5 8
P6 completes - 1 3 4 7 5 8

Can we safely allocate 1ŚR3 to P2? Why or why not?
No - P4 and P5 can execute, but none of the others can run now that there aren't enough of R3 to run P3.

Virtual memory

• Memory capacity: 8 frames
• Process P1: 3 pages, initially loaded in frames 0..2
• Process P2: 5 pages, initially loaded in frames 3..7
• Process P3: 4 pages, completely swapped out for now.

Trace the references using the LRU, CLOCK and OPT policies, indicating each reference with a checkmark and each page fault with a star at the top of the column and the new page number in the correct frame beneath. Use the lowest frame number to break a tie. The CLOCK pointer starts at frame 5.

LRU (a '#' means recently used - assume higher frame numbers are more recent):
I will use an X to show a memory reference.

            *        *    *    *    *
0 P1.0#             P3.1
1 P1.1     P3.0
2 P1.2#                  P1.1
3 P2.0          X
4 P2.1   X                              X
5 P2.2#                       P1.2
6 P2.3#           X
7 P2.4#                            P2.2
Page fault rate: 5/9 = 56%

                *           *     *        *
  0 P1.0#         O               ->     P2.2#
  1 P1.1      P3.0#                        ->
  2 P1.2#       ->            O       X#
  3 P2.0            X#        O
  4 P2.1   X#                 O                X#
->5 P2.2#         O       P3.1#
  6 P2.3#         O    X#   ->      O
  7 P2.4#         O             P1.1#
Page fault rate: 4/9 = 44%

           *        *
0 P1.0    P3.0     P3.1
1 P1.1                  X
2 P1.2                    X
3 P2.0         X
4 P2.1  X                     X
5 P2.2                      X
6 P2.3           X
7 P2.4
Page fault rate: 2/9 = 22%

DMA

1. DMA, CPU and I/O devices are on the same bus
2. I/O devices are each attached to one of n DMA controllers, which are attached to the CPU/memory bus. One DMA controller may serve more than one device.
3. There are two buses - one for I/O devices, and one for the CPU and memory. A single DMA controller bridges the buses.

Which style is best for multiple I/O devices that may transfer large blocks at the same time?
Style 2, with its multiple independent controllers, can handle multiple transfers at once with a minimum number of cycles per word transferred.

Buffering

What advantage does single buffering have over unbuffered I/O?
This is where DMA comes in. Single buffering allows a transfer to be done by the DMA controller rather than the CPU, freeing the CPU to service other processes during the period where the I/O is progressing.
Example: Any data transfer to/from disk.

What advantage does double buffering have over single buffering?
The program can be processing the data at the same time as more is coming in. This is generally done with applications that transfer a stream of data rather than a fixed-length block, so there is no blocking request.
Examples: Computer games (drawing one frame while displaying another), sound mixers (mixing one buffer while playing another), sound recorders (saving one buffer while sampling another).

What advantage does circular buffering have over double buffering?
Circular buffering does not speed up transfers per se, because it still takes the same amount of time to read/process data. The attraction is that circular buffers can handle bursts, where the I/O momentarily comes faster than the program can handle and overruns the current buffer. The more buffers available, the larger the burst that can be handled.
Example: Network drivers (sort of) - packets can come in bursts.

File Storage