大家好,又见面了,我是你们的朋友全栈君。
题目一:
如果将 peterson 算法中的 flag[i] = true 与 turn = j 两条语句交换顺序,会导致求解临界区问题所需三个要求(互斥、有空让进、有限等待)中的哪些要求得不到满足?请举例并分析说明得不到满足的情况
解答:
假设两个进程i和j:
进程i的进入区代码是这样的
flag[i] = TRUE;
turn = j;
while(flag[j] == TRUE && turn == j);
进程j的进入区代码是这样的:
flag[j] = TRUE;
turn = i;
while(flag[i] == TRUE && turn == i);
如果进程i和进程j已经在并发执行了,它们的调度顺序是未知的,假设程i先执行,那么它会先将turn“谦让”地设置为j,但接下来轮到进程j执行了,它也“谦让”地将turn设置为i。这时又轮到了进程i执行了,而且我们可以发现,while中第二个条件已经不满足了!这时进程i就进入了临界区!
如果顺序颠倒,总共会六种可能的语句组合情况:
如果仅仅从结果来看,似乎六种情况都满足三个条件:
但如果考虑中间能够进入临界区的情况,那么情况三和情况四将会不满足互斥条件,进程i与进程j将有可能同时进入临界区:
所以,会存在不满足互斥的情况,所以不可以。
题目二:
试分析说明为何自旋锁(spinlocks)不适合单处理器系统但却常用于多处理器系统。
解答:
在单处理机环境中可以使用硬件提供的swap指令或test_and_set指令实现进程互斥,这些指令涉及对同一存储单元的两次或两次以上操作,这些操作将在几个指令周期内完成,但由于中断只能发生在两条机器指令之间,而同一指令内的多个指令周期不可中断,从而保证swap指令或test_and_set指令的执行不会交叉进行。
但在多处理机环境中情况有所不同,例如test_and_set指令包括“取”、“送”两个指令周期,两个CPU执行test_and_set(lock)可能发生指令周期上的交叉,假如lock初始为0, CPU1和CPU2可能分别执行完前一个指令周期并通过检测(均为0),然后分别执行后一个指令周期将lock设置为1,结果都取回0作为判断临界区空闲的依据,从而不能实现互斥。
为在多CPU环境中利用test_and_set指令实现进程互斥,硬件需要提供进一步的支持,以保证test_and_set指令执行的原子性. 这种支持目前多以“锁总线”(bus locking)的形式提供的,由于test_and_set指令对内存的两次操作都需要经过总线,在执行test_and_set指令之前锁住总线,在执行test_and_set指令后开放总线,即可保证test_and_set指令执行的原子性。
题目三:
请用比较并交换指令(compare_and_swap())实现互斥锁机制。互斥锁包含的数据结构及函数如下所示,其中 available == 0 表示锁可用,available == 1 表示锁不可用。
typedef struct {
int available ;
} lock ;
void acquire ( lock *mutex ) ;
void release ( lock *mutex ) ;
解答:
互斥锁是指当一个线程尝试获取某个锁时,如果该锁已被其他线程占用,该线程挂起或睡眠。互斥锁适用于临界区持锁时间比较长的操作,比如下面这些情况都可以考虑:
·临界区有IO操作
·临界区代码复杂或者循环量大
·临界区竞争非常激烈
·单核处理器
CAS(compare and swap),它通过原子操作交换两个变量的值来达到对变量的修改。我们可以把它看作是 i = i+1 这个表达式的原子操作版本。它的实现类似如下:
int compare and swap(int *value, int expected, int new_value) {
int temp = *value;
if (*value == expected)
*value = new_value;
return temp;
}
在一些线程库里面,mutex 是最简单的一种锁,也是最常见的锁。它的作用主要是对一段临界区上锁,对其他试图访问已经上锁的资源禁止访问。因此 mutex 也叫互斥锁,它的是英文单词 mutual exclustion 的缩写。mutex 可以使用 SAS 或 CAS 来实现:
mutex 通过让试图获取的锁的执行单元进入到一个等待队列里排队,当锁用完了以后再把等待的执行单元拿出来获取锁并继续执行:
void acquire (){
if(lock->available){
//把当前的执行单元加入到等待队列
add_process_to_waitlist(current_pocess)
sleep()//休眠
}
}
void release (){
compare_and_swap(lock,1,0)
//唤醒休眠的线程
wakeup_process()
}
顺便,写一下自旋锁,自旋锁之所以被叫做自旋锁,就是因为他会在锁被其他占用的时候会一直循环,不断地询问锁是否打开,也就是所谓的轮询,即:如果一个执行单元锁住了一块资源,另一个执行单元试图进入会一直轮询知道获取到锁为止:
void acquire (){
while(lock->available)//轮询
;
}
void release (){
compare_and_swap(lock,1,0)
}
题目四:
理发师问题:理发店里有一位理发师、一把理发椅和 n 把供等候理发的顾客坐的椅子。如果没有顾客,理发师便在理发椅上睡觉。当一个顾客到来时,它必须叫醒理发师。如果理发师正在理发时又有顾客到来,如果有空椅子可坐,就坐下来等待,否则就离开。请用信号量机制(wait(),signal())来解决上述问题。
解答:
首先设置一个count表示等待的人数(包括理发椅上的那个人),初值为0,以供后来者判断是否应该离开。同时对count的访问要保证互斥,所以设置mutex信号量来保证互斥,初值为1。
临界资源:凳子,理发椅。 分别设置waitchair,barchair信号量,初值分别为n和1,表示临界资源数量。
同步关系:顾客和理发师之间有同步关系,用ready和done信号量来表示,初值均为0,ready表示顾客有没有准备好,done表示理发师是否完成一次理发。
注意:并非每一个进程都需要while(1)无限循环,比如此例,顾客剪完一次头发就走了,不可能马上再来剪,而以前的生产者-消费者不同,他们都是可以不断生产消费的。
Semaphore waitchair = n;
Semaphore barchair = 1;
Semaphore ready = done = 0;
int count = 0;
Semaphore mutex = 1;
barber:
while(1) {
wait(ready);
理发
signal(done);
}
consumer:
wait(mutex);
if(count <= n) {
count = count + 1;
signal(mutex);
}
else {
signal(mutex);
离开
}
wait(waitchair);
wait(barchair);
signal(waitchair); //离开等待椅去理发椅需要释放等待椅!
signal(ready); //准备好了
wait(done); //等待理发完成
signal(barchair);
wait(mutex);
count = count – 1;
signal(mutex);
离开
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/159080.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...