Chapter 10

11.Reduce by p4, then by p2, and then by p1 and p3 in either order. The graph is completely reducible, thus the state is not deadlocked. Here is a postscript version of this picture.

Chapter 11

10.The load instruction overwrites a value 1000 into the code segment register. The next instruction will not be the call instruction, but will be an instruction at physical 01000+0104 = 01104.

11. Here is a solution:

Chapter 12

11. The page reference stream is 3 2 4 3 4 2 2 3 4 5 6 7 7 6 5 4 5 6 7 2 1.

Belady’s optimal algorithm incurs 10 faults.

Frame 3 2 4 3 4 2 2 3 4 5 6 7 7 6 5 4 5 6 7 2 1

0	3	3	3	3	3	3	3	3	3	5	5	5	5	5	5	5	5	5	7	7	7
1		2	2	2	2	2	2	2	2	2	6	6	6	6	6	6	6	6	6	2	2
2			4	4	4	4	4	4	4	4	4	7	7	7	7	4	4	4	4	4	1

The LRU algorithm incurs 10 faults.

Frame 3 2 4 3 4 2 2 3 4 5 6 7 7 6 5 4 5 6 7 2 1

0	3	3	3	3	3	3	3	3	3	3	6	6	6	6	6	6	6	6	6	6	1
1		2	2	2	2	2	2	2	2	5	5	5	5	5	5	5	5	5	5	2	2
2			4	4	4	4	4	4	4	4	4	7	7	7	7	4	4	4	7	7	7

The FIFO algorithm incurs 9 faults.

Frame 3 2 4 3 4 2 2 3 4 5 6 7 7 6 5 4 5 6 7 2 1

0	3	3	3	3	3	3	3	3	3	5	5	5	5	5	5	4	4	4	7	6	6
1		2	2	2	2	2	2	2	2	2	6	6	6	6	6	6	5	5	5	2	2
2			4	4	4	4	4	4	4	4	4	7	7	7	7	7	7	6	7	7	1

The working set algorithm with window size 6 incurs 9 faults.

Frame 3 2 4 3 4 2 2 3 4 5 6 7 7 6 5 4 5 6 7 2 1

0	3	3	3	3	3	3	3	3	3	3	3	3	3								1
1		2	2	2	2	2	2	2	2	2	2	2								2	2
2			4	4	4	4	4	4	4	4	4	4	4	4		4	4	4	4	4	4
3										5	5	5	5	5	5	5	5	5	5	5	5
4											6	6	6	6	6	6	6	6	6	6	6
5												7	7	7	7	7	7	7	7	7	7
alloc	1	2	3	3	3	3	3	3	3	4	5	6	5	4	3	4	4	4	4	5	6

The working set algorithm page frame allocation is shown as the last row in the table above.

A program would have a small code locality and a small data locality if it was designed with a small loop that consistently changed a small set of data. For example, a program to solve for the roots of a polynomial by estimating the roots, computing the solution, correcting the estimation, and then iterating (such as one solver in the SOR problem).

A program would have a small code locality and a large data locality if it was designed with a small loop that touched large amounts of date, e.g., a transaction processing system (like an automatic teller machine).

This one is not a common class of programs/processes. A program would have a large code locality and a small data locality if it applied many different functions to a small amount of data. This could happen if a large program were applied to a small amount of input, e.g, a text formatter (like latex) or a compiler working on a small input stream.

A program would have a large code locality and a large data locality if it were like the previous example with a large input file.

13. 32 MB of file space is referenced from a FAT with one entry per block. The problem is to try to rationalize the size of disk block pointers and the size of disk blocks. The original DOS FAT used 12-bit pointers, meaning that the file system could have 4,096 blocks; each black was 4K KB for a maximum of 32 MB. For the disk to be bigger, the FAT space would have to be increased -- more addresses and/or each block could be bigger. The solution used in FAT file systems is to effectively increase the size of a block by defining clusters of blocks; the file system reads and writes all the blocks in a cluster as if they were a block.

Chapter 13

12.If the device directory contains 64K (16-bit) block addresses, then to directly address blocks in a 512 MB disk would mean that each block would have to be 8KB. However, since each disk sector is only 512 bytes, then somehow each FAT entry must reference a cluster of 16 contiguous blocks. Thus files are allocated clusters of contiguous blocks even though the hardware reads and writes 512-byte sectors.

13. The protection state for a particular process's memory relocation is the contents of the base and limit register for that process. The operating system can make this state be secure by only changing the contents of the hardware base and limit registers with privileged instructions (as part of a context switch).

Chapter 15

8.The addresses in the figure are not really realistic, since networks B and C both use "30". However, this doesn't change the answers to the questions:

Host X: [20, 4, 1333]
Host R: [20, 35, 1444] and [30, 15, 1666]
Host S: [30, 25, 1555] and [30, 40, 1777]
Host Y[30, 40, 1888]

DLL frame from 0x1826543  0x1834567
DLL frame from 0x1645673  0x1764321
DLL frame from 0x16701234  0x15465766

10. The accept() call is made by a server that is designed to wait for an arbitrarily long time -- until a client needs the services provided by the server. In the case of a connect request, the client is attempting to contact a server while it waits; therefore (to bound the time the client waits) a timeout interval is used.

2005-12-07T12:25:31