[考古] 作業系統(一)/林明言/97上期末
※ [本文轉錄自 FCU_Talk 看板]
作者: justforppt (洨麵人) 看板: FCU_Talk
標題: [考古][資訊][林明言][97年上期末][作業系統][OS(一)]
時間: Wed Jan 14 13:40:30 2009
考完時間太多..來打個考古題..順便練英打= =
PART 1.
1. Belady's Anomaly states that ______
(A)giving more memory to process will improve its performance.
(B)as the number of allocated frames increases,the page-fault rate may
decrease for all page replacement algorithms.
(C)for some page replacement algorithms,the page-fault rate may decrease
as the number of allocated frames increase.
(D)for some page replacement algorithms,the page-fault rate may increase
as the number of allocated frames increase.
2. Which of the following situation may indicate that the system is thrashing?
(A)CPU utilization 78%,Paging Disk utilization 78%
(B)CPU utilization 22%,Paging Disk utilization 78%
(C)CPU utilization 22%,Paging Disk utilization 22%
(D)CPU utilization 78%,Paging Disk utilization 22%
3. Which of the following dynamic storage-allocation algorithms in the
smallest leftover hole in memory?
(A)best-fit (B)worst-fit (C)first-fit (D)None
4. Which of the following binding schemes facilitates deadlocks?
(A)execution time (B)load time (C)assembly time (D)interrupt time
5. Which of the following is a way to deal with deadlocks?
(A)ensure that a system will never enter a deadlocked?
(B)allow the system to enter a deadlocked state and then detect and recover
(C)ignore the deadlock altogether
(D)all of the above
6. A cycle in a resource-allocation graph is_____
(A)a necessary and sufficient condition for deadlock in the case that each
resource has more than one instance.
(B)a necessary and sufficient condition for a deadlock in the case that each
resource exactly one instance.
(C)a sufficient condition for a deadlock in the case that each resource
has more than one instance.
(D)is neither necessary nor sufficient for indicating deadlock in the case
that each resource exactly one instance.
7. In a system resource-allocation graph,_____.
(A)a directed edge from a process to a resource is called an assignment
edge.
(B)a directed edge from a resource to a process is called a request edge.
(C)a directed edge from a process to a resource is called a request edge.
(D)none of the above.
8. A semaphore __.
(A)is essentially an integer variable.
(B)is accessed through only one standard operation.
(C)can be modified simultaneously by multiple threads.
(D)cannot be used to control access to a thread's critical sections.
9. The first readers-writers problem____.
(A) request that,once a writer is ready,that writer performs its write as
soon as possible.
(B) is not used to test synchronization primitives.
(C) request that no reader will be kept waiting unless a writer has already
obtained permission to use the shared database.
(D) request that no reader will be kept waiting unless a reader has already
obtained permission to use the shared database.
10. A transaction____
(A)performs multiple logical functions. (B)is a single instrutuon.
(C)is a single operation (D)performs a single logical function
PART II:short answers(簡答)
1. (a) List,except progress the other two criteria that a critical section
solution must satisfy.
(b) Briefly describe their meanings.
2. In Peterson's solution for two cooperating processes,
(a)what variable are shared between the two processes?
(b)what is the "entry code" before entering the critical section?
(c)what is the "exit code" before leaving the critical section?
3. If 3 processes P1,P2,and P3,are cooperating for a task.Function p1a()(P1),
function p2b(P2),and funtion p3c(P3) are tk be exechted in this order:
p1a() can be executed after p2b() has finished. p3c() can be executed
after p1a() has finished.
Present a pseudocode using semaphore to show these processes,indicate the
necessary semaphores and their initial values.
4.If a system prevents deadlock by guaranteeing the following constraint:
whenever a process requests a resource,it does not hold any other resource
(a)give two protocols to implement this provision
(b)name two disadvantages for these protocols.
5. There are two methods for a system to elimminat deadlocks by aborting a
process.
(a)briefly describe the two methods
(b) which method will invoke a deadlock-detection algorithm?
6.(a)Draw the resorce-allocation graph for the following situation:P = {P1,
P2,P3},R = {R1,R2,R3}, E = {P1→R1,R1→P2,R1→P3,P3→R2,R2→P1,R3→P3}
R1 has two instances,R2 has one instance,and R3 has one instance
(b)List the deadlocked processes if there is a deadlock OR describe how
the system can be free from a deadlock.
7. Consider a locgical address space of 16 pages of 2048 words each,mapped
onto a physical memory of 64 frames.
(a)How many bits are there in the logical address?
(b)How many bits are there in the physical address?
8. (a) Explain the difference between internal and external fragmentation.
(b) Withoust paging how do you reduce external fragmentation?
9. Consider a paging system with the page table stored in memory.
(a)If a memory reference takes 100 nanosecnds,how long does paged memory
referende take?
(b)if we add associative registers and finding a page-table entry in the
associative registers takes 20 nanoseconds, what is the minimum
hit-ratio for the TLB if effective memory accse time must be less than
140 nanoseconds?
10.(a)What are the three techniques for structuring the page tables?
(b)which technique needs a linked list and why?
11. Using demand paging,what benefits bo you have?
12. Describe the 6 steps to handle a page fault.
PART III:(計算/簡答)
1.Given 3 frams and the following referene string(4,3,2,1,4,3,5,4,3,2,1,5)
for page replacement.
(a)what is the minimum number of page faults?
(b)using LRU page-replacement scheme,how many page faults do you have?
(c)using FIFO page-replacement scheme,how many page faults do you have?
2.Use the banker's algorithm and consider the following snapashot 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 1 2 1 5 2 0
P1 1 0 0 0 1 7 5 0
P3 1 3 5 4 2 3 5 6
P4 0 6 3 2 0 6 5 2
P5 0 0 1 4 0 6 5 6
(a)what is the content of the matrix Need?
(b)Is the in a safe state,and why?
(c)if a request from process P1 arrives for(0,4,2,0),can the request be
granted immediately,and why?
3.A system uses demand-paging:its page fault rate is 0.005,memory access time
80 nanoseconds,a service to handling a page fault take 20 milliseconds in
average,swapping a page needs 2 milliseconds, the time to restart an
instruction can be ignored. Compute effecitve access time:
(a) if memory has free frame
(b) if memory has no free frame
4.Consider the bounded-buffer problem (size n) using semaphore solution.
Complete the following structures of producer/consumer processes.
Semaphores mutex,empty,full are used.
(a) producer process (b) consumer process
do{... do{...
___________ ___________
___________ ___________
.... // add to buf ...//remove item from buf
___________ ___________
___________ ___________
}while(true) }while(true)
(c)what are the initial values for mutex,empty,full?
5.Explain"two - phase locking protocol"
6.Compare "Buddy system" and "Slab allocation"
--
原po尬正妹，迸出新滋味，全新科科良品，復古味，新絕配！
http://www.wretch.cc/blog/lulu168
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.46.151.138
推
01/14 14:01,
01/14 14:01
推
01/14 14:08,
01/14 14:08
推
01/14 15:08,
01/14 15:08
推
01/14 15:35,
01/14 15:35
推
01/14 15:43,
01/14 15:43
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 220.132.214.27