---
# System prepended metadata

title: 作業系統期中考

---

# **是非題**
## CH6
|||| T ||||1. In reader-writers problem, the reader will get starvation if the version of “no reader will be kept waiting unless a writer has already obtained permission to use the shared database” is used.

|||| F ||||2. A monitor consists of mutual exclusive operations that are pre-determined and do not require programmer’s definition.

|||| F ||||3. Under race condition, the final value of the shared data will be determined by the first process arrived.

|||| T ||||4. Critical sections should not be executed at the same time, even if these critical sections belong to the same process.

|||| F ||||5. The monitor is considered a lower level synchronization construct than semaphore.

|||| T ||||6. Based on Peterson’s solution, it is difficult to know, before execution, which process will enter the critical section first.

|||| T ||||7. In the solution of Dining Philosopher problem using monitor construct, both pickup( ) and putdown( ) procedures need to invoke the test( ) procedure.

|||| F ||||8. The test-and-set instruction returns the tested value and set it to false regardless the original value.

|||| T ||||9. It is possible to implement a semaphore using a monitor or implement a monitor using a semaphore.

## CH8
|||| F ||||10. If the processes in the system can be preempted, no deadlock can happen.

|||| T ||||11.When there are more than one instances for each type of resources, the appearing of cycles cannot determine the happening of deadlocks.

|||| F ||||12.The operating systems are very sophisticated, most of them has powerful deadlock manipulation schemes available.

|||| T ||||13.Mutual Exclusion is not required for sharable resources, but must hold for nonsharable resources.

|||| F ||||14.It is inevitable to abort at least one process when adopting deadlock recovering methods.

# **選擇題**
## CH6
|||| C ||||1.When processes are synchronized, they must _______ for each other.
 A.consistent

 B.in-line

 C.wait

 D.compete

|||| A ||||2.Consider test-and-set instructions used for process Pi to enforce mutual exclusiveness (as below), which of the following is true?
```
do{
    while(test_and_set(&lock));/*do nothing*/
        /*critical section*/
    lock = false;
        /*remainder section*/
}while(true);
```
 A.When the test-and-set returns false, it is successfully acquired the lock.

 B.Test-and-set instruction will be invoked only once.

 C.The lock equals to false when the critical section is being executed.

 D.When the lock is false, no process can get into critical sections

|||| E ||||3.(Multiple answers) Consider the monitor construct on the right. Which of the statements below is true?
![image](https://hackmd.io/_uploads/rycgLShkR.png)

 A.The shared data in the monitor can be accessed by outside processes.

 B.There can be only one process waiting inside the monitor.

 C.Processes within the monitor can work concurrently at the same time.

 D.Each process can call only one of the procedures in the monitor.

 E.Each condition variable has one queue for processes to get in-line.

|||| B ||||4.Which of the solution of the dining-philosophers problem is not placing restriction to the usual solution?
 A.Allow philosophers to pick up only when both chopsticks are available

 B.Put more chopsticks on the table.

 C.Giving different orders of picking up the chopsticks

 D.Allow smaller number of philosophers sit in the table

|||| A ||||5.In the dining-philosophers problem, if _____ philosopher can get both the left and right chopsticks at the same time, then no deadlock can happen.
 A.anyone

 B.all

 C.more than one

 D.no
 
|||| B ||||6.Encapsulation allows local-variables to be accessed only by operations _____ the monitor.
 A.named by

 B.within

 C.outside

 D.controlled by
 
|||| A ||||7.In Solaris, the readers-writers locks are used to protect data that are accessed frequently, but usually only in a _________ manner.
 A.read-only

 B.read or write

 C.(A)write-only

 D.read and write
 
|||| C ||||8.For thread synchronization outside the kernel, Windows XP provides a mechanism called
 A.turnstiles

 B.condition variables

 C.dispatcher objects 

 D.mutex locks

|||| A ||||9.Suppose process A has 2 critical sections and process B has 3 critical sections. How many critical sections can be executed at the same time?
 A.1

 B.3

 C.5 

 D.2
 
## CH8
|||| B ||||10.If there is one, which deadlock handling method can immune the system completely?
 A.deadlock avoidance

 B.deadlock prevention

 C.deadlock recovery

 D.deadlock detection

|||| D ||||11.Breaking the “Hold and wait” condition in a multi-threaded system may cause
 A.implementation problem 

 B.mutual exclusive

 C.deadlock

 D.starvation

|||| A ||||12.Reaching an unsafe state doesn’t mean that the system is going to be deadlocked. What kind of unfortunate situation will lead the system to deadlock? 
 A.all processes requests denied

 B.no safe sequence

 C.processes waiting

 D.resource not enough
答案解析：

||||  C  ||||13.A Claim edge Pi - - - - -> Rj used in a resource allocation graph algorithm indicates that process Pi may request resource Rj 
 A.all the time. 

 B.now

 C.some time in the future

 D.some time before

|||| B ||||14.A wait-for graph is obtained from the resource-allocation graph by removing the nodes of type ____________ and collapsing the appropriate edges.
 A.database

 B.resource

 C.class 

 D.document

# 手寫題
## CH6
![image](https://hackmd.io/_uploads/rkwEyiFgR.png)
Process 1 can’t go back to cs immediately because it needs to reset it’s flag and follow mutual exclusion protocol again before re-entering the critical section.

![image](https://hackmd.io/_uploads/rk_5yjte0.png)
In the `wait` operation:
If `S->value` becomes negative (`S->value < 0`), it means there aren‘t enough resources available, so the current process is blocked until resources become available.

In the `signal` operation:
If `S->value` is not greater than zero (`S->value <= 0`), it means there are processes waiting for resources. One waiting process is then woken up to proceed.

In essence, these `if` statements ensure proper coordination of processes accessing shared resources.

![image](https://hackmd.io/_uploads/ryelgsYe0.png)
when a process encountering x.wait，the process that invokes the operation is suspended and stored process within x，store the function within y

F1
```
S1;
done = true
x.signal();
```
F2
```
if(done = false)x.wait();
S2;
```
In this example，P1 and P2 respectively invoke F1 and F2 within the monitor. When executing F1，S1 is performed first，then done is set to true，at last，process possibly waiting on x are awakened through x.signal. When executing F2，if done is false，the process will wait on x until awakened by another process through x.signal(). Once done is true，the process executes S2. This ensures that S1 must be executed before S2 

## CH7
![image](https://hackmd.io/_uploads/HykmfoFgA.png)

![image](https://hackmd.io/_uploads/HySk7iYxR.png)
* During the pickup phase:
  * Using the test( ), you can check if the person next to you is eating. If they are eating, you will enter the waiting state; if not, you will start eating.
* During the putdown phase:
  * Using the test( ), you can check if the person next to you is waiting. If they are waiting, you need to wake them up so they can start eating.

Invoking test() in both pickup() and putdown() procedures ensures proper synchronization and avoids potential deadlocks in the solution to the Dining Philosopher problem using monitorsconstruct.
It helps prevent deadlocks, ensures fairness, and synchronizes access to shared resources.


## CH8
![image](https://hackmd.io/_uploads/r1rubjYlA.png)
1. If a safe sequence is available，then the system is in safe stage 
2. A state is safe if the system can allocate resources to each process in some order and still avoid a deadlock
3. In unsafe state，if OS cannot prevent processes from requesting more resources，it will cause deadlock.

![image](https://hackmd.io/_uploads/SJmi-jtgC.png)

![image](https://hackmd.io/_uploads/ryc2-sKlR.png)
Because there is no cycle in the graph，so there don't exist a deadlock