Computer Science | Binghamton University



Binghamton University - Watson School

CS 350 – Exam 2

11/21/03 – updated 11/24/03

Closed Book, Closed notes except one 1 ½ x 11 “cheat sheet” subject to the restrictions given in the “Coverage Document”.

This test is worth 23% of your grade

Note: Questions 1 through 6 should have short answers- suspect long answers of being incorrect. .

1. (4 points) In memory management, how come page sizes (in bytes) are always powers of two?

2. (4 points) Given a non-virtual memory system with multi-programming, process swapping, and single partition contiguous allocation. At some point there is 100K of unused memory. Explain why an 80K process may not be loadable into this memory (answer is very short). Briefly explain how this problem could be resolved while still using a non-virtual memory.

3. (4 points) True or False (T/F):

a. ____An unsafe resource allocation state is a sufficient condition for deadlock.

b. ____If deadlock does not occur, then the resource allocation state is safe.

c. ____If deadlock occurs, then the resource allocation state must be unsafe.

4. (4 points) What is the Principle of locality? Your answer should have two aspects of this principle. These two aspects were discussed in class and in the notes.

5. (4 points). A system has two processes and three identical resources. Each process needs a maximum of two resources to complete. Is deadlock possible? Explain your answer.

6. (4 points) How is thrashing related to the degree of multiprogramming (avoid long definitions – just give the relationship).

7. (15 points total) Assume we have a demand-paged virtual memory system consisting of a TLB with access time of 10 ns, a main memory having access time of 200 ns, and a disk backing store with an overall page transfer time of 8 ms.for a page read operation, and 20 ms for a page swap when a page is modified. Assume that the main memory hit ratio is 99.9999% (ie., fault rate is 1 out of a million references). The hit ratio for the TLB is 90%. 30% of page faults must replace a modified page thus requiring a page write back in addition to reading in a new page (page swap). The specification for this design is that the effective access time must not exceed the main memory access time by more than 25%.

Answer the following questions:

(a) (10 points) What is the average or effective access time of a reference. A formula or a detailed breakdown of the calculation may be more important than the numerical answer. Indicate any approximations you are making. Tip: convert all times to microseconds.

(b) (4 points) Does this design meet the specification? Justify your answer quantitatively using numbers.

(c) (1 point) Is the expectation of 99.9999% hit ratio a reasonable expectation? Looking for some intuitive insight here. Yes or no answer does not get credit.

.

8. (12 points total) Consider a virtual memory of 256 terabytes. The page size is 4K. This logical space is mapped into a physical memory of 256 megabytes.

Prefix meaning: 1K = 210, 1Meg = 220, 1Giga = 230 = 1Kx1Meg, 1 tera = 240 = 1Kx1Giga

a. (3 points) How many bits in a virtual address?, a physical address?

b. (3 points) How many pages are in the virtual memory?, the physical memory?, How many entries are in page table which is simply indexed by the page number? Will it fit into physical memory?

c. (3 points) How many bits are in a virtual page number? The page offset?

d. (3 points) Given the address: 0x034F48AC5345 what is the page number and offset (in hex).

9. (9 Points) A virtual memory system has a 32 bit virtual address with a 4K byte page size. Assuming no TLB, consider the following beginning of page table page table for process P with the first six entries in hex. The first column (V) is the validity bit and second column (PT Entry) is the data needed to do the address translation:

V PT Entry

|1 |3AC |

|0 |974 |

|1 |3B1 |

|1 |445 |

|1 |38D |

|1 |C34 |

| |… etc. |

For the following virtual addresses, determine the physical addresses, wherever possible. Explain if not possible:

0x0000112C

0x000035F9

0x000040A2

All addresses are hex, and are legal. (All accesses are within the address space of the process and will not cause addressing errors). Give your answers in hex.

10. Part a: (15 points) The following is a “reference string” (trace) of addresses in hexadecimal (with the “0x” prefix dropped for simplicity) from a demand paged virtual memory system:

3140, D3C2, 2157, 4250, D3F4, 215C, 31A8, D330, 3132, 465F, 46F1, 4256.

Note that these addresses point to single bytes of data in memory (not words or any other grouping of bytes). For these addresses the page size is 256 bytes. Assume that there is a fixed allocation of page frames for this process in physical memory of three (3) frames. Show the contents of memory in a series of “snapshots” (a “vertical” array of 3 page numbers per snapshot), as the references are being made for the FIFO, LRU, and Clock (second chance) replacement algorithms. The reference string should be of page numbers rather than byte addresses. Determine the total number of page faults and the hit ratio occurring in each case. The initial loading of pages will be counted as page faults. It is OK to display memory as some stack or queue representing the algorithm, if you so choose – the ordering of the pages numbers in the “vertical array” is not critical as long as the correct pages are displayed. In doing the Clock algorithm, indicate that the reference bit = 1 by an asterisk (*) next to the page number (in the queue or page list), and the “next page to be replaced” by the “>” symbol next to the page number (in the queue or page list). Hint: the pointer to the “next page to be replaced” will be advanced to the next entry in the circular queue from the one just replaced.

Part b: (5 points) For each page number reference derived from the address trace above, show the working set for a window size of ( = 3 references.

11. (20 points) Consider a system with the following current resource-allocation state:

There are five processes: p0, p1, p2, p3, p4

The system has three resources types: A, B, and C

The for each process, the current allocation and the maximum required allocation are given by the Allocation and MAX matrices below. The current available resources are given by the Available vector.

Allocation MAX Available

A B C A B C A B C

p0 1 1 2 4 3 3 2 1 0

p1 2 1 2 3 2 2

p2 4 0 1 9 0 2

p3 0 2 0 7 5 3

p4 1 1 2 11 2 3

(a) (2 points) Determine the total amount of resources of each type (installed on the system).

(b) (2 points) What is the “Need” matrix” (put it with the above given data)?

(c) (6 points) Determine if this state is “safe” using the “Safety Algorithm” using the approach given in the posted notes.

(d) (8 points) Starting with the allocation resource state given above, suppose the current requests for each process is given by the Request matrix below. Furthermore, assume that these requests are granted.

Request Matrix:

A B C

p0 3 3 1

p1 1 1 0

p2 6 0 1

p3 7 2 3

p4 0 1 1

Will the system be in a deadlocked state? Determine this using the deadlock detection algorithm as described in the posted notes.

(e) (2 points) What, if anything, does this problem demonstrate about the relationship between the “safeness” of an allocation state and deadlock itself.

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download