操作系统第六章作业进程同步¶

1. What is the meaning of the term busy waiting?¶

当一个进程位于临界区时，任何其它试图进入临界区的进程都必须在代码中不断地循环。

2. What is the meaning of the term spinlocks?¶

自旋锁是一种会造成忙等的信号量，在进程等待锁时还需不断运行，占用 cpu 资源。

3. Explain the deadlock and give an example¶

若干个进程竞争系统资源，最后每个进程都必须得在其它进程释放资源时才能改变状态，因而无法改变状态，造成死锁。如以下程序在 A，B 同时运行时造成死锁。 A:

wait(S)
wait(Q)
...
signal(S)
signal(Q)

B:

wait(Q)
wait(S)
...
signal(S)
signal(Q)

4¶

Servers can be designed to limit the number of open connections. For example, a server may wish to have only N socket connections at any point in time. As soon as N connections are made, the server will not accept another incoming connection until an existing connection is released. Explain how semaphores can be used by a server to limit the number of concurrent connections. (6.8)

初始化计数型信号量 connection=N

wait(connection)
//do something
signal(connection)

5. What operations can be performed on a semaphore? List them and explain the means of semaphore values¶

wait() 和 signal() 操作。信号量可分为计数信号量与二进制信号量。计数信号量值域不受限制，代表系统受限资源的数量。二进制信号量的值只能为 0 或 1，可表示对临界区的访问权（只能有一个进程位于临界区）。

6. How does the signal() operation associated with monitors differ from the corresponding operation defined for semaphores? (6.16)¶

当没有进程等待时，信号量的 signal() 会对信号量的值加一，而管程里的 signal() 则不会进行任何操作。

7¶

A uniprocessor system concurrently executes 2 processes ($ P_A, P_B $). Two Semaphores $ Mutex_R_a $ and $ Mutex_R_b $ are added in mutual accessing the critical section and synchronizing between $ P_A $ and $ P_B $ . Please read following program segment carefully and answer the questions:

(1) What are initial values for $ Mutex_R_a $ and $ Mutex_R_b $ . (2) Is it possible to cause deadlock? Please state your reason. Semaphore $ Mutex_R_a $, $ Mutex_R_b $ ;

Void P_A ( ){
    while(true){
        Wait(Mutex_Ra );
        ......
        Wait(Mutex_Rb );
        ......
        Signal(Mutex_Ra );
        ......
        Signal(Mutex_Rb );
    }
}

Void P_B ( ){
    while(true){
        Wait(Mutex_Rb );
        ......
        Wait(Mutex_Ra );
        ......
        Signal(Mutex_Rb );
        ......
        Signal(Mutex_Ra );
    }
}

答： (1) $ Mutex_R_a = Mutex_R_b = 1$ (2) 当 P_A 和 P_B 同时到达时，两个进程都会执行第一句，接着便会由于$ Mutex_R_a = Mutex_R_b = 0$而陷入死锁。

8¶

设有一个可以装 A、B 两种物品的仓库，其容量有限 (为 N),但要求仓库中 A、B 两种物品的数量满足下述不等式： $$ -M≤A 物品数量-B 物品数量≤N $$ 其中 M 和 N 为正整数。另外，还有一个进程消费 A 和 B，一次取一个 A 与 B 组装成 C。试用信号量和 P、V 操作描述 A、B 两种物品的入库和出库 (组装成 C) 过程。

答：设 nA, nB 分别为 A 物品，B 物品数量，二进制信号量 mutex，初始值为 1。

A 入库进程：

wait(mutex)
nA++
if(nA <= N && -M <= nA-nB <= N)
    A入库
else
    nA--
signal(mutex)

B 入库进程：

wait(mutex)
nB++
if(nB <= N && -M <= nA-nB <= N)
    B入库
else
    nB--
signal(mutex)

C 出库进程：

wait(mutex)
if(nA>0 && nB>0)
    nA--;nB--
    C出库
signal(mutex)

changed:

semaphore initiation:
    muxtex = 1
    empty  = N
    delta  = M
    nA = nB = 0
progress A:
do{
    P(empty)
    P(mutex)
        A in
    V(mutex)
    V(nA)
    V(delta)
}while(true)

progress B:
do{
    P(empty)
    P(delta)
    P(mutex)
        B in
    V(mutex)
    V(nB)
}while(true)

progress C:
do{
    P(nA)
    P(nB)
    P(mutex)
        C out
    V(mutex)
    V(empty)
    V(empty)
}while(true)

操作系统第六章作业 进程同步¶