CIS 415 Operating Systems - Spring 2003

Navigate

Discussion: Week 10 session 2

Banker's Algorithm

Current Allocation:

	R1	R2	R3	R4	R5	R6
P1	0	1	0	2	0	1
P2	0	0	0	1	0	1
P3	0	0	1	2	3	5
P4	0	1	0	0	0	0
P5	1	1	1	1	0	0
P6	0	0	1	0	0	0

Maximum Request:

	R1	R2	R3	R4	R5	R6
P1	1	3	0	6	2	5
P2	0	3	3	7	2	5
P3	1	2	3	4	5	6
P4	0	1	0	1	0	0
P5	1	2	1	2	0	0
P6	0	2	2	5	0	0

Still needs:

	R1	R2	R3	R4	R5	R6
P1
P2
P3
P4
P5
P6

Total System Resources:

R1	R2	R3	R4	R5	R6
1	3	4	7	5	8

Available system resources:

R1 R2 R3 R4 R5 R6
0 0 1 1 2 1

Is this state safe? If so, give a possible safe execution order. If not, list the processes that deadlock.

Can we safely allocate 1舑3 to P2? Why or why not?

Virtual memory

Suppose we have the following memory and processes:

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.

Reference string (pages): P2.1 P3.0 P2.0 P2.3 P3.1 P1.1 P1.2 P2.2 P2.1

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):

0	P1.0#
1	P1.1
2	P1.2#
3	P2.0
4	P2.1
5	P2.2#
6	P2.3#
7	P2.4#
Page fault rate:

CLOCK ( a '#' means the use bit is set):

0	P1.0#
1	P1.1
2	P1.2#
3	P2.0
4	P2.1
5	P2.2#
6	P2.3#
7	P2.4#
Page fault rate:

OPT:

0	P1.0
1	P1.1
2	P1.2
3	P2.0
4	P2.1
5	P2.2
6	P2.3
7	P2.4
Page fault rate:

DMA

The slides showed three examples of DMA configurations:

DMA, CPU and I/O devices are on the same bus
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.
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 steals the most bus cycles from the CPU?

Which style is best for multiple I/O devices that may transfer large blocks at the same time?

Buffering

Can you think of an application for which unbuffered I/O makes sense?

What advantage does single buffering have over unbuffered I/O?

What advantage does double buffering have over single buffering?

What advantage does circular buffering have over double buffering?

File Storage

How many levels of indexing are required to store a 2GB file if blocks are 1K in length and block pointers are 4 bytes long? Use 1GB = 230 bytes and 1K = 210 bytes.