課程名稱︰作業系統
課程性質︰必修
課程教師︰郭大維
開課學院：電機資訊
開課系所︰資訊工程
考試日期（年月日）︰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