The document provides a study guide for an operating systems final exam, including key concepts, sample exam questions, and answers to selected textbook questions. Many common OS topics are covered such as deadlock detection, memory management techniques, paging, virtual memory, scheduling policies, and file systems.
The document provides a study guide for an operating systems final exam, including key concepts, sample exam questions, and answers to selected textbook questions. Many common OS topics are covered such as deadlock detection, memory management techniques, paging, virtual memory, scheduling policies, and file systems.
The document provides a study guide for an operating systems final exam, including key concepts, sample exam questions, and answers to selected textbook questions. Many common OS topics are covered such as deadlock detection, memory management techniques, paging, virtual memory, scheduling policies, and file systems.
The document provides a study guide for an operating systems final exam, including key concepts, sample exam questions, and answers to selected textbook questions. Many common OS topics are covered such as deadlock detection, memory management techniques, paging, virtual memory, scheduling policies, and file systems.
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 bankers 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
Max Additional Resources Needed
Process
R0
R1
R2
R3
Process
R0
R1
R2
R3
P1
P1
P2
P2
P3
P3
P4
P4
P5
P5
2. Define or explain each of the following:
preemptible resources.
Priority preemption
non-preemptible resources
memory fragmentation
serially reusable resource
quantum preemption
Paging
Thrashing
virtual memory
Page Frame
working-set
page fault
3. Discuss at least 4 weaknesses in the Bankers Algorithm.
4. Compare and contrast what is meant by a process location space and its name space. 5. A memory management system must consider a number of problems, discuss code/data, fragmentation, memory partitioning, protection, and swapping.
6. Explain how a paging system works, be certain to include faults, thrashing, pages, frames, swapping, page replacement strategies, address translation, and anomalies.
12 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.)
13 Discuss deadlock; what is it. Provide an illustration, explain the necessary conditions for deadlock, and name the three basic approaches to handling deadlock.
14 Discuss/explain scheduling methodologies; include non-preemptive versus preemptive,
FCFS, SPN, RR, and multilevel feedback queues.
15. 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.
15 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
ABCD
ABCD
ABCD
1020 0312 2451 3006 4213
3242 3512 2775 5508 6214
22 32 03 25 20
1 2 3 4 5
Resources Available
Total Resources
A B C D
3 4 0 1
13 13 9 13
B C
2 0 2 0 0
2 0 4 2 1
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 overcommitted (i.e., too many processes)?
------- Skip these next questions --------
2. We discussed two memory models in class, strongly ordered and weakly ordered. Explain each model, and include how they can affect a programmers view of memory.
3. 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.
a. 011011110100 b. 011011100000 Question 7.7
a. Buddy k = x + 2K, if x mod 2(K+1) = 0.
b. Buddy k = x - 2K, if x mod 2(K+1) = 2K. Question 7.8
a. Yes, it is possible. b. 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.
2. Provide an overview of system protection mechanisms; include system access, software,
data, hardware (Authentication, memory access, files, and instruction levels).
