Final Exam Study Guide

Concepts/Terms:

Banker's Algorithm, Deadlock detection (pg 268), reusable resource, consumable resource, memory managements requirements & Techniques, Fixed/dynamic partitioning, Simple paging/segmentation, virtual memory paging/segmentation, fragmentation (internal, external), placement/replacement, page table, segment table, logical-physical address translation (e.g., pg 308), thrashing (321), resident set, working set, principle of locality, Concepts that appear in table 8.3 (pg 340) and table 8.4 (pg 352), page fault, segment fault, modify bit, invalid bit, System Scheduling (types, criteria, policies), FCFS, RR, SPN, Feedback, Disk Scheduling Policies (SSTF, SCAN, FIFO)---pros/cons and algorithm.

Text Questions:

Chapter Questions
6 2, 3, 8, 9, 12.
7 4, 9.
8 1, 13(a)
9 10,  12, 13, 15
11 1

SAMPLE QUESTIONS (including some questions from the Ph.D. qualifying exam in OS) :

  1. Employing semaphores, Solve the reader/writer problem giving the writer priority. 

  2. Describe the deadlock detection algorithm found on pages 266-268.

  3. Considering the basic function of a page table, for example: the need to locate, replace, or swap pages to/from secondary storage; memory protection and sharing, explain what the fields of a page-table would be and the rational for each field. 

  4. Given a system that uses the bankerís algorithm for avoiding deadlock and the resource state shown below, explain why it is a safe or unsafe state. Assume that the total number of each system resource is <6, 4, 4, 2>, where <R0, R1, R2, R3> and Ri means the amount of resource i.

Current Allocations

Process

R0

R1

R2

R3

P1

2

0

1

1

P2

1

1

0

0

P3

1

1

0

0

P4

1

0

1

0

P5

0

1

0

1

 

Max Additional Resources Needed

Process

R0

R1

R2

R3

P1

1

2

0

0

P2

0

1

0

2

P3

0

0

2

0

P4

2

2

0

0

P5

2

0

0

1

  1. Define or explain each of the following:

    preemptible resources. 

    non-preemptible resources

    serially reusable resource

    Paging

    virtual memory 

    working-set

    Priority preemption 

    memory fragmentation 

    quantum preemption

    Thrashing 

    Page Frame 

    page fault

  2. Discuss at least 4 weaknesses in the Bankerís Algorithm.

  3. Compare and contrast what is meant by a processí location space and its name space.

  4. A memory management system must consider a number of problems, discuss code/data, fragmentation, memory partitioning, protection, and swapping.

  5. Explain how a paging system works, be certain to include faults, thrashing, pages, frames, swapping, page replacement strategies, address translation, and anomalies.

  1. Explain the mapping of a virtual address to a real address under a paging system, include faults, pages, page frames, swapping, page replacement (be sure you are clear, and use diagrams if necessary.)

  2. Discuss deadlock; what is it. Provide an illustration, explain the necessary conditions for deadlock, and name the three basic approaches to handling deadlock.

  3. Discuss/explain scheduling methodologies; include non-preemptive versus preemptive, FCFS, SPN, RR, and multilevel feedback queues.

  1. There are three basic issues in defining a paging policy: when to fetch a page, when to remove/replace a page, and where to place pages. Discuss one aspect of each issue.

  2. Consider the following experiment and explain the observations.

A program is run by itself on a paging machine. The program begins execution with its first procedure page. As it runs, the pages it needs are demand paged into available page frames. The number of available page frames is much much larger than the number of pages in the program. Also, there is a dial external to the computer that allows a person to set the maximum number of page frames the program may use.

Initially, the dial is set to 2 frames and the program is run to completion. The dial is then set at 3 frames and again the program is run to completion. This process is continued until the dial is eventually set to the number of available pages in real storage, and the program is run for the last time. For each run, the execution time of the program is recorded.

Observations:

As the dial is changed from 2, to 3, to 4, the execution time improves dramatically. From 4, 5, to 6, the execution time still improved each time, but less dramatically. With the setting of 7 and higher the execution time is essentially constant.

 

17. Assume a disk with 200 tracks and that the disk request queue has random requests in it. The requested tracks, in the order received are: 55, 58, 39, 18, 90, 160, 150, 38, and 184. Assuming that the disk head is a track 100, and is moving toward track 200, show the sequence that the requests will be serviced and the total track sequence traversed for each of the following scheduling policies: FCFS, SSTF, and SCAN. 

18. (Ph.D. exam) Semaphores: Using semaphores, implement a writer's priority solution to the readers/writes problem.

19. (Ph.D. exam) Deadlock: A system that uses the Banker's Algorithm deadlock avoidance has five (5) processes (1, 2, 3, 4, and 5) and four (4) types of resources (A, B, C, and D). There are multiple resources of each type. Is the following  state safe or not? If it is, show how the processes can complete. If not, show how they can deadlock.

Process

 

Current loan Max need Current claim
A B C D A B C D A B C D
1 1 0 2 0 3 2 4 2 2 2 2 2
2 0 3 1 2  3 5 1 2 3 2 0 0
3 2 4 5 1 2 7 7 5 0 3 2 4
4 3 0 0 6 5 5 0 8 2 5 0 2
5 4 2 1 3 6 2 1 4  2 0 0 1

 

Resources Available Total Resources
 A  B  C  D  A    B  C    D
 3   4  0  1  13  13  9  13

20. (Ph.D. exam) Virtual memory: Draw a picture showing how virtual memory addresses in a page system are translated to real addresses when using combined associative/direct mapping 

21. (Ph.D. exam) Virtual memory: Why is it generally more desirable to replace an unmodified page rather than a modified one?  In what circumstances might it be more desirable to replace a modified page?

22. (Ph.D. exam) Virtual memory: How might a storage manager determine if storage is over-committed (i.e., too many processes)?

 

------- Skip these next  questions --------

  1. We discussed two memory models in class, strongly ordered and weakly ordered. Explain each model, and include how they can affect a programmerís view of memory.

  2. A system is composed of 4 processes, { p1, p2, p3, p4 }and three types of serial reusable resources, {s1, s2, s3}. The number of units of the resources are t1=3, t2=2, and t3=2. Process p1 holds 1 unit of s1 and requests 1 unit of s2. P2 holds 2 units of s2 and requests 1 unit each of s1 and s3. P3 holds 1 unit of s1 and requests 1 unit of s2. P4 holds 2 units of s3 and requests 1 unit of s1. Show the serially reusable resource graph to represent this system state. Show the reduced form of the graph. Which, if any, of the processes are deadlocked in this state? 

23. (Ph.D. exam) In a file system: what is the difference between a queued access method and a basic access method?

24.  What would it mean to retain state information in a fileserver system? What are the pros and cons of either retaining state information or being a stateless fileserver?

Answers to selected text questions on the Buddy System.

Question 7.6.

  1. 011011110100
  2. 011011100000

Question 7.7

  1. Buddy k = x + 2K, if x mod 2(K+1) = 0.
  2. Buddy k = x - 2K, if x mod 2(K+1) = 2K.

Question 7.8

  1. Yes, it is possible.
  2. It provides a greater variety of block sizes (e.g., 5, 8, 13, 21) to choose from, so there is the potential to reduce internal fragmentation, but by the same token it can increase external fragmentation in that there may be many unusable blocks created. 

 

  1. Provide an overview of system protection mechanisms; include system access, software, data, hardware (Authentication, memory access, files, and instruction levels).