=========================preview======================
(COMP252)Final_07f_Solution.pdf
Back to COMP252 Login to download
======================================================
COMP 252 Operating Systems
Fall Semester 2007
Final Examination Solution
Time/Date: 8:30 C 10:30 am Dec 12, 2007 (Wednesday)
Name: ____________________ Student ID: __________________
Email: ____________________ Lecture Section: ______________
Question Points Score
1 15
2 25
3 25
4 10
5 20
6 5
Total 100
1. (15 pts) Deadlocks
1.1 (5 pts) List and briefly describe the four necessary conditions for deadlocks.
Answer:
1.
Mutual exclusion: at least one resource must be held in a non-sharable mode.
2.
Hold and wait: a process must be holding at least one resource and waiting to acquire additional resources that are currently being held by other processes.
3.
No preemption: a resource can be released only voluntarily by the process holding it.
4.
Circular wait: A set {P0, P1, , Pn} of waiting process must exist such that P0 is waiting for a resource held by P1, P1 is waiting for a resource held by P2, Pn-1 is waiting for a resource held by Pn, and Pn is waiting for a resource held by P0.
Correct answers without explanation (2.5 points)
1.2 (10 pts) Consider the following snapshot of a system:
Allocation Max Available
A B C D A B C D A B C D
P0 0 0 1 2 0 0 3 2 2 1 2 0
P1 2 0 0 0 2 7 5 0
P2 0 0 3 4 6 6 5 6
P3 2 3 5 4 4 3 5 6
P4 0 3 3 2 0 6 5 2
Answer the following questions using the bankers algorithm:
a.
(2 pts) What is the content of the matrix Need denoting the number of resources needed by each process?
b.
(4 pts) Is the system in a safe state? Why?
Answer: Need = Max C Allocation
Need
A B C D
P0 0 0 2 0
P1 0 7 5 0
P2 6 6 2 2
P3 2 0 0 2
P4 0 3 2 0
The allocation should be safe right now, with a sequence of process execution.
Answer: Yes (1 point), with <P0, P3, P4, P1, P2> (3 points)
Resources available after each process finished
A B C D
P0 2 1 3 2
P3 4 4 8 6
P4 4 7 11 8
P1 6 7 11 8
P2 6 7 14 12
c. (2 pts) If a request from process P1 arrives for (2, 1, 0, 0), can the request be granted immediately? Why?
Answer: No, the request is invalid or can not be granted since this is more than the maximum request that the process 1 can have
d. (2 pts) If a request from process P2 arrives for (0, 1, 2, 0), can the requested be granted immediately? Why?
Answer: No, this can not be allocated. If this is allocated, the resulting Available is (2, 0, 0, 0), there is no sequence of the process execution order that lead to the completion of all processes. This is an unsafe state.
(25 pts) Memory management
2.1 (2 pts) Consider a paging scheme, with the page table stored in the main memory. If each memory reference takes 250 nanoseconds, what is the effective memory-access time (average time to access any memory location)?
Answer: 250ns to access the page table + 250ns to ac