課程名稱︰作業系統
課程性質︰必修
課程教師︰郭大維
開課學院：電資學院
開課系所︰資工系
考試日期（年月日）︰2012.6.20
考試時限（分鐘）：150分鐘
是否需發放獎勵金：是
（如未明確表示，則不予發放）
試題：
The exam is 150 minutes long. The total score is 112pts. Please read the
questions carefully.
1. Terminologies (21pts).
a. Condition Variable (Hint: Monitor)
b. Stable Storage
c. 50-Percent Rule for the First-Fit Algorithm (Hint: Dynamic Partitioning)
d. Virtual Memory
e. Lazy Swapper
f. Network Information Service (NIS or Yellow Pages from SUN)
g. Scan (or Elevator) Algorithm (Hint: Disk Scheduling)
2. Please answer the following question on process synchronization: (18pts)
a. Synchronization hardware might make programming easier for process
synchronization. Please explain why interrupt disabling works for
uniprocessor environments to avoid the race condition. (6pts)
b. There are three requirements for a solution to critical section problem.
Please tell me which requirement might not be satisfied for solutions
based on semaphores with priority-waiting queues. You must provide your
arguments. (6pts)
c. When the Two-Phase Locking protocol (2PL) is adopted for process
synchronization, and there is only exclusive lock, can we have a
deadlock? You must provide your arguments. (6pts)
3. Given the following snapshot of the system: Please determine whether there
exists a safe sequence. (5pts)
┌─┬──────┬───────┬──────┐
│ │ Allocation │ Maximum Needs│ Available │
│ │ A B C │ A B C │ A B C │
├─┼──────┼───────┼──────┤
│P0│ 0 1 2 │ 2 2 2 │ 0 1 1 │
├─┼──────┼───────┼──────┤
│P1│ 2 1 0 │ 2 1 1 │ │
├─┼──────┼───────┼──────┤
│P2│ 1 0 0 │ 1 1 2 │ │
├─┼──────┼───────┼──────┤
│P3│ 0 1 0 │ 0 1 1 │ │
└─┴──────┴───────┴──────┘
4. With binding at the compiling time, is it appropriate to have Paging?
With binding at the loading time, is it appropriate to have Paging?
You must provide explanation. (6pts)
5. Given a computer system with 64-bit virtual address and 8 bytes per page
entry, let the physical address be of 48 bits, and the system is
byte-addressable. Assume that every page is of 4KB. Please answer the
following questions: (20pts).
a. What is the maximum number of frames? (5pts)
b. Suppose that we have multi-level paging. How many levels do we have in
multi-level paging? (5pts)
c. Suppose that TLB is adopted for paging, and multi-level page tables are
all in the main memory. Let the memory access time and TLB access time
be 100ns and 10ns, respectively. What the TLB hit ratio should be so
that the effective memory access time would be no more than 120ns?
(5pts)
d. Continued with the previous question, What is the maximum number of
entries for an inverted page table? (5pts)
6. Please answer the following questions for demand paging: (20pts)
a. What is the maximum number of pages needed for the following
instruction: Add (R1)+, -(R2), +(R3) (4pts)
b. The effective access time is defined as (1 - p) * ma + p * pft, where
p, ma, and pft are the probability of a page fault, the memory access
time for paging, and the page fault time, respectively. Please give me
two approaches to reduce the pft. Please give me two approaches to
reduce p. (16pts)
7. Given the following reference string, which reference causes a page fault
under the Second Chance (Clock) Algorithm. Please also show us which page
is replaced when a page replacement occurs? Suppose that we have 3
available frames with 0, 1, and 3 as shown in the following graph, all
reference bits are 0, and the selection pointer starts at Page 0. (10pts)
1 0 3 1 4 3 2 1 3 0 2 1 5
8. Modern operating system often only recognize few file types. Please give two
advantages why file types are usually supported by applications, instead of
the operating system. (8pts)
9. Give me one reason when we need scheduling in I/O subsystem, beside
performance improvement. (4pts)
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.230.115.230