課程名稱︰作業系統
課程性質︰必修
課程教師︰郭大維
開課學院：電機資訊
開課系所︰資訊工程
考試日期（年月日）︰2014/6/18
考試時限（分鐘）：150
是否需發放獎勵金：是
（如未明確表示，則不予發放）
試題 :
The eaam is 150 minutes long. The total score is 105 pts. Please read the
questions carefully.
1. Terminologies (12pts).
a. The Second Reader-Writers Problem
Once a writer is ready, it performs its write asap!
b. Binary Semaphore
A semaphore is like a variable S being only accessible by two atomic
operations : wait() and signal(). For a binary semophore, no matter
how many times we signals it, the maximum value is 1.
c. Memory Transaction
A sequence of memory read-write operations that are atomic.
d. Absolute Code (Hint : Binding Time)
It refers to a program, where the binding times is at the compile
time.
2. Please provide answers to the following problem: You must provide
explanation to receive any credits. (8pts)
a. Please provide the reason for the existence of the critical section
problem. (Hint: Processes share variables.) (4pts)
b. Suppose that there is no critical section problem for a set of
processes. Is it possible to have a deadlock among the processes of
the set? (Assumption: The only thing shared among processes are
variables. No other resource sharing among the processes.) (4pts)
a. It is because processes might share variables (or cooperate) such
that some processes might update variables while others are reading
or updating some of the variables. As a result, the outcome of their
executions depends on the particular order of process scheduling.
b. No, it is because the processes of the set have no sharing of any
variables (and any resource) such that no locking-orientes behaviors
could result in hold-and-wait.
3. Please explain the difference between the following requirments to a
solution to the critical section problem: Progress and Bounded Waiting.
(8pts)
The progress requirement has two parts: (1) Only processes not in their
remainder section can decide which will enter its critical section. (2)
The section cannot be postponed indefinitely. The first part has
nothing to do with the Bounded Waiting requirement, but the difference
between the second part and the Bounded Waiting could be explained by
one of the Peterson solutions (i.e., the first solution in the class)
in which one process ends before the other such that the variable
"turn" is not switched to the right status.
4. Please revise the following solution to the first reader-writers problem
such that a writer only needs to wait for at most 5 readers. (8pts)
┌────────────┐ ┌────────────┐
│Writer: │ │Reader: │
│ wait(wrt); │ │ wait(mutex); │
│ ..... │ │ readcount++; │
│ writing is performed │ │ if(readcount == 1) │ ←≧5
│ ..... │ │ wait(wrt); │
│ signal(wrt); │ │ signal(mutex); │
└────────────┘ │ .....reading..... │
│ wait(mutex); │
│ readcount--; │
│ if(readcount == 0) │
│ signal(wrt); │
│ signal(mutex); │
└────────────┘
5. Why the existence of a cycle in the Resource Allocation Graph of a process
set denotes a deadlock, where each resource has one instatnce? (5pts)
It is because the cycle shows the circular wait of the processes in the
cycle.
6. Given the following snapshot of the system: Please determine whether there is
currently a deadlock. (5pts)
┌─┬─────┬─────┬─────┐
│ │Allocation│Requests │Available │
│ │ A B C│ A B C│ A B C│
├─┼─────┼─────┼─────┤
│P0│ 2 0 1│ 0 1 2│ 0 1 1│
├─┼─────┼─────┼─────┤
│P1│ 1 1 1│ 2 0 1│ │
├─┼─────┼─────┼─────┤
│P2│ 0 2 0│ 2 2 2│ │
├─┼─────┼─────┼─────┤
│P3│ 0 0 2│ 0 1 1│ │
└─┴─────┴─────┴─────┘
No, there is a sequence <P3, P0, P1, P2> such that Finish[i] = true.
7. Please answer these questions for memory managment. You must provide
explanation to receive any credits. (15pts)
a. The Memory Management Unit (MMU) is responsible to the translation
of a logical address into a physical address. Can MMU be implemented
as software? (5pts)
b. What is the advantage of Paging in terms of fragmentation, composed
to Dynamic Partitions with Contiguous Allocation? (5pts)
c. What is the advantage of Dynamic Partitions with Conguous Allocation
in terms of the effective memory access time, compared to Paging?
(5pts)
a. No, because if would be too slow
b. Paging can avoid external fragmentation and has only little internal
fragmentation problem.
c. The effective memory access time of Dynamic Partition is always the
memory access time, while paging is slowed down to 2*memory access
time without TLB.
8. Given the following reference string, which reference causes a page fault
under the LRU algorithm. Please also show us which page is replaced when a
page replacement occurs? Suppose that we have 3 available frames, which are
empty initially. (5pts)
3 1 0 2 3 0 4 5 0 6 0 6
┌──────┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┐
│ │ 3│ 1│ 0│ 2│ 3│ 0│ 4│ 5│ 0│ 6│ 0│ 6│
├──────┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
│ │ 3│ 3│ 3│ 2│ 2│ │ 4│ 4│ │ 6│ │ │
│frames │ │ 1│ 1│ 1│ 3│ h│ 3│ 5│ h│ 5│ h│ h│
│ │ │ │ 0│ 0│ 0│ │ 0│ 0│ │ 0│ │ │
├──────┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
│ │ │ │ │ 3│ 1│ │ 2│ 3│ │ 4│ │ │
│replacements│ │ │ │↓│↓│ │↓│↓│ │↓│ │ │
│ │ │ │ │ 2│ 3│ │ 4│ 5│ │ 6│ │ │
└──────┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┘
9. Given a computer system with a 52-bit virtual address, let the physical
address be of 64-bit, and the system is only word-addressable, and every
word is of 8 bytes. Assume that evrey page is of 8 KB with 8 bytes per page
entry in the page table. Please answer the following questions : (23pts)
a. What would be the maximum number of frames owned by a process? What
is the maximum logical address space for a process in terms of
bytes? (10pts)
b. Suppose that TLB is adopted for paging, and there is only one level
for paging. Let the memory access time and TLB access time be 100ns
and 10ns, respectively. When the TLB hit ratio is 98%, what is the
effective memory access time? (5pts)
c. Suppose that we have multi-level paging. How many levels do we have
in multi-level paging? What is the effective memory access time now
(continued from the above subproblem)? (8pts)
a. 2^42 pages ; 2^52 * 2^3 bytes
b. EMAT = 2% * 210 + 98% * 110 , unit = ns
c. 5 levels; EMAT = 2% * 610 + 98% * 110
10. For virtual memory management, the adopting of an inverted page table cane
avoid storing the page table of every process in the main memory. One
common way to eliminate lengthy table lookup time is to adopt the Hash
Table. (16pts)
a. Suppose that there is no page fault, no hash table miss or
collision, and no TLB implementation, and the Hash Table is in the
main memory. When the memory access time is 100ns, what is the
effective memory access time because of the adopting of an inverted
page table and the Hash Table? (6pts)
b. Suppose that a miss in the Hash Table lookup also means a page fault
(in memory access) and vice versa, and p is the probability of a
page fault. ma is memory access time (i.e., 100ns), and pft is the
page fault time for a page table retrieval OR a page retrieval
(including its memory access). Please define the effective access
time. (Hint: The effective memoy access time defined in the texbook
is equal to (1 - p) * ma + p * pft, when there is no inverted page
table). (10pts)
a. 200ns
b. (1 - p) * 2 * ma + p * (ma + 2 * pft)
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.217.52
※ 文章網址: http://www.ptt.cc/bbs/NTU-Exam/M.1403667958.A.FA7.html
※ w4a2y4:轉錄至看板 b04902xxx 06/16 20:26