文章目录

• 一、背景
• 二、 临界区（Critical-Section）
• • 理论上的解决方案要满足（单核状态）：
  • Peterson's Solution
  • • 进程的情况
    • 简单的形式？
• 三、 硬件同步机制（Synchronization Hardware）
• • TestAndSet Instruction
  • Swap Instruction
• 四. 信号量（Semaphores）
• • Semaphore的版本
  • Semaphore Implementation
  • • busy waiting
    • no busy waiting
  • Deadlock & Starvation（死锁和饿死）
• 五. 经典同步问题（Classic Problems of Synchronization）
• • ！！Bouded Buffer Problem
  • ！！Readers-Writers Problem
  • dining philosophers problem
  • 其他同步问题
  • • 1. 使用二进制semaphore实现counting semaphore
    • 理发师问题
• 六、 管程（Monitor）
• • Semaphore的使用问题
  • monitor的提出
  • Condition Variable
  • monitor模式对dining philosopher问题解法的实现（使用CV）
  • ！！使用Semaphore实现monitor
  • • 不使用CV的实现方法
    • 使用CV时monitor的实现方法

一、背景

• 对共享数据的并发访问会导致数据不一致性（数据的处理结果与人规定的既定规则下的结果不同）

例子：在生产者和消费者体系中，二者修改一个count，但却在各自的进程空间进行，但是修改过程中可能会出现这种情况：

二、 临界区（Critical-Section）

上述对count的修改就是critical section

理论上的解决方案要满足（单核状态）：

1. Mutual Exclusion ：如果某个进程正在进行它的critical section，那么其他进程不能进行其critical section。
2. Process：如果没有进程处于critical section，且有进程想要进入critical section，需要选出一个不能被无限期推迟的进程进入critical section
3. Bounded Waiting ：当一个进程需要且已经被授权准入critical section时，它等待其他进程先进入critical section的时间应当是有限的。

另外：

• 假设每个进程都以非0速度执行
• 没有进程间相对执行速度相对执行速度的概念

Peterson’s Solution

进程的情况

代码情况：

while (true) {flag[i] = TRUE;turn = j;while ( flag[j] && turn == j);CRITICAL SECTIONflag[i] = FALSE;REMAINDER SECTION
}
// Pj代码完全对称
while (true) {flag[j] = TRUE;turn = i;while ( flag[i] && turn == i);CRITICAL SECTIONflag[j] = FALSE;REMAINDER SECTION
}

简单的形式？

当一个process的remainder section很长，难以结束，另一个就无法进入critical section。

三、 硬件同步机制（Synchronization Hardware）

很多系统提供对critical section code的硬件帮助

• 使用单处理器时，可以使处理器进入不可中断模式
• 处理器硬件提供原子性的操作，要么使用TestAndSet，要么使用Swap

TestAndSet Instruction

// 被共享的lock初始化为false// 指令描述
boolean TestAndSet (boolean *target){boolean rv = *target;*target = TRUE;return rv;
}// 使用
while (true) {while ( TestAndSet (&lock )); /* do nothing*/// critical sectionlock = FALSE;// remainder section
}

这种方法不能够满足Bounded waiting，之后的更新后的ppt有可以实现Bounded waitng的TestAndSet方法。

Swap Instruction

不满足Bounded Waiting

// Definition:
void Swap (boolean *a, boolean *b){boolean temp = *a;*a = *b;*b = temp:
}
// Solution:
while (true) {key = TRUE;while ( key == TRUE) Swap (&lock, &key );// critical sectionlock = FALSE;// remainder section
}

四. 信号量（Semaphores）

简单的同步化工具，通过两个原子化的标准操作修改一个integer值$S$ ：wait()和signal()（一开始也被称为P()和V()）

wait(S){while(S<=0) /*此处如果不空，则这个进程在忙等待*/;S--;
}
signal(S){S++;
}

显然S不应为负。

Semaphore的版本

• Counting Semaphore：S的值是不被约束的整数
• Binary Semaphore：S的值只能是0或1，也被成为mutex locks

简单的使用

上图S的值应当取1

上图中，S的初始值应当为0

Semaphore Implementation

• 应该确保任意两个进程不能在同一时刻分别对t同一个S运行wait()和signal()，也即wait和signal本身也是critical section。
• 有忙等待和非忙等待两种方法

busy waiting

（是自旋锁？）

no busy waiting

如果while中的时间不能被忽略，就需要把这些操作放在waiting queue，而不是放在wait操作中。
此时 Semaphore本身应该具有两个字段：

1. 值（以int形式存储）
2. 指向PCB链表（实际上就是waiting queue）的指针

使用2个系统内核和提供的系统调用

• block
• wakeup

这样的Semaphore的实现方法：

Implementation of wait:
wait (S){value--;if (value < 0) {// add this process to waiting queueblock(); }
}Implementation of signal:Signal (S){value++;if (value <= 0) {// remove a process P from the waiting queuewakeup(P); }
}

block是让自己睡觉，wakeup是把包括自己在内的 别人叫醒

当使用多处理器并且占用率较低时，busy waiting可以填充CPU时间

Deadlock & Starvation（死锁和饿死）

• 死锁：所有进程都在等待其他进程执行完成。
  
  在上图中，P0和P1在都执行完第一句后就会产生死锁

• starvation：

五. 经典同步问题（Classic Problems of Synchronization）

！！Bouded Buffer Problem

// producer的代码
BoundedBuffer::Producer(){while (true) {// produce an itemwait(empty);wait(mutex);// add the item to the buffersignal(mutex);signal(full);}
}// consumer的代码
BoundedBuffer::Consumer(){while (true) {wait(full);wait(mutex);// remove an item from buffersignal(mutex);signal(empty);// consume the removed item}
}

full和empty确定buffer产生和消费的串行化，而mutex确定从buffer中放入和放出item的critical section的原子性。

但是其实这个mutex对buffer的控制是粗粒度的。如果producer与consumer访问的item在buffer中的位置不相同，这显然不需要采用mutex确保串行化，可以并行访问。只有他们访问同一个item的时候，才需要保护。

！！Readers-Writers Problem

经典问题

• dataset被一些并发进程共享，readers只读取数据，writers既可以读，又可以写
• 应当允许多个readers可以一起读一个数据项，但不能允许多个writers（或者writers和readers）一起写（或有写有读）一个数据项。

解决方案：制定一些共享数据：

• dataset
• 一个Semaphore：mutex初始化为1，来确保mutual exclusion，其实也是对readcount的保护
• Semaphore：wrt初始化为1（也是binary的）
• readcount：integer值，初始化为0

DataBase{BinarySemaphore mutex=1,wrt=1;int readCount = 0;// writer进程的代码void writer(){while (true) {wait(wrt) ;OP_WRITE();// 执行写操作signal(wrt);}}// reader进程的代码void reader(){while (true) {wait(mutex); // 可以看到，上下两段wait(mutex)其实保护了readcount的操作readcount++ ;if (readcount == 1) wait(wrt) ;// 当只有一个reader时，应当把他当做writer对待// 但之后就不能这样做，否则wrt会一直阻塞（因为之后只会signal一次）//此时如果有writer，在这里就会阻塞住，直到没有writer（不论是真的还是假的）signal(mutex);OP_READ();// 执行读操作wait(mutex) ;readcount -- ;if (readcount == 0) signal(wrt) ;signal(mutex) ;}}
}

dining philosophers problem

五个人五根筷子，这是共享数据的情况。只有拿到2根筷子才能吃饭（data）
故：

• 米饭=>data set
• Semaphore chopstick[5] init to 1

此时，phil的代码（会产生死锁）

while(true){
wait( chopstick[i] );
wait( chopStick[ (i + 1) % 5] );OP_EAT();
signal( chopstick[i] );
signal(chopstick[ (i + 1) % 5] );OP_THINK();
}

在这样的情况下，如果每个phil都拿起左边的筷子，全局就会形成死锁

之后的monitor方法会防止死锁

其他同步问题

1. 使用二进制semaphore实现counting semaphore

struct S{int val;               // init kBinarySemaphore sem;   // init 0,用于对等待S时的排队同步int waitCount;         // init 0,表示在S上等待的进程的数量BinarySemaphore mutex; //init 1，用于保护对waitCount和val的更新
};// wait操作
void wait(struct S s){wait(s.mutex);// 保护val和waitCountif (s.val == 0){// 目前没有空闲，val=0s.waitCount++; // 等待的进程增加signal(s.mutex); // 退出临界区wait(s.sem); // 等待有进程完成了对S的操作，signal掉了sem}else{s.val--;// 还有剩下的val，所以根本不需要waitCountsignal(s.mutex); // 退出临界区}
}void signal(struct S s){wait(s.mutex);// 同样是保护两个数值if(s.waitCount>0){s.waitCount--;signal(s.sem); // 从相当于从等待sem的进程中挑一个执行}else{s.val--;// 这里根本就没有等待的进程，因此也不需要signal(s.sem)}signal(s.mutex);// 最终释放保护信号量
}

总结：

• 用整数表示计数的方法，用mutex保护操作的整数，但是这个mutex要在整数不使用后马上释放
• 对整数的判断和修改都需要加mutex锁

理发师问题

解法：

#define n 10
// 其中，costumers不是二进制信号量，因为可能有多个顾客
Semaphore mutex = 1, barber = 1, costumers = 0;
int freeChair = n;/*** 理发师进程 */
void Barber()
{while (1){wait(costumers); // 等待客人，如果没有就睡觉// 客人来到wait(mutex);    // 临界区保护freeChair++;    // barber起身，空出一个座位signal(mutex);  // 临界区结束signal(barber); // 理发师去剪发cutHair();      // 给顾客剪头}
}/*** 顾客进程 */
void Costomers()
{while (1){wait(mutex);// 对freeChair的判断值也可能因为多进程而不准确// 所以用mutex保护if (freeChair > 0){freeChair--;signal(mutex);     // 完成临界区signal(costumers); // 此时顾客已经到来wait(barber);      // 等待理发师剪头haveHairCut();     //顾客被剪头}else{signal(mutex); // 退出临界区，没空位走了}}
}

六、 管程（Monitor）

Semaphore的使用问题

• 顺序不能错
• 必须1对1对应

容易出错的原因是Semaphore的运行模式其实是与普通代码一样的。

monitor的提出

在一个时刻，1个condition variable只允许有1个process在monitor中处于active状态，但可以有多个process被挂起（也可以说sleeping）

monitor monitor-name{// shared variable declarationsprocedure P1(…) { …. }…procedure Pn(…) {……}Initialization code( ….) { … }…
}

整体结构:
在这里插入图片描述
其中椭圆内部的每个矩形对应着1个operation。

Condition Variable

CV允许为管程提出个性化的同步方案

这个变量允许的也是两个操作：wait和signal，但语义和Semaphore有区别
condition x;

• x.wait()：调用这个操作的process会被挂起
• x.signal()：从因为x挂起的process中选一个,但如果没有进程在这里等待，就什么也不做

所以condition variable具有一个waiting queue

condition variable的整体结构

从这个结构可以看到，condition variable时monitor的关键，它应当有：

• 一个指向被挂起进程（也就是PCB）队列的指针
• 一个用于实现同步的锁和对应的机制（下文使用的就是Semaphore）

monitor模式对dining philosopher问题解法的实现（使用CV）

monitor DP{enum { THINKING; HUNGRY, EATING) state[5] ;condition self[5]; //philosopher i can delay herself when unable to get chopsticksvoid pickup(int i) {state[i] = HUNGRY;test(i);if (state[i] != EATING) self[i].wait();}void putdown(int i) {state[i] = THINKING;// test left and right neighborstest((i + 4) % 5);test((i + 1) % 5);}void test(int i) {if ( (state[(i + 4) % 5] != EATING) &&(state[i] == HUNGRY) &&(state[(i + 1) % 5] != EATING) ) {state[i] = EATING ;self[i].signal() ;}
}initialization_code() {for (int i = 0; i < 5; i++)state[i] = THINKING;}
}

调用时，每个phil只需要如下的调用：

dp.pickup(phil_id);
OP_EAT();
dp.putdown(phil_id);

！！使用Semaphore实现monitor

不使用CV的实现方法

每一个管程都拥有如下的数据结构，它被所有procedure所共有

Semaphore mutex;// init = 1,保护next_count和过程体
Semaphore next;//init 0,把别的进程唤醒，自己等待？
int next_count = 0;// 让位等待的process数，也即在next上等待的进程数

不使用CV时，使用默认的同步方案，这样的方案也是通过Semaphore实现的

procedureF(){wait(mutex);// actual body of Fif(next_count>0) signal(next);// 优先调用让位给别人的processelse signal(mutex);
}

使用CV时monitor的实现方法

对每个condition variable，除了拥有上述3个属于整个管程的变量之外，用于进程同步的字段和方法有：

• 信号量 x_sem（init 0）：
• 整数值 x_count（init 0）：
• 成员wait操作
• 成员signal操作

它们的实现如下

struct ConditionVariable{// CV使用的，实现定制化同步的手段BinarySemaphore x_sem = 0;int x_count = 0;PCB wait_queue; // 指向进程的队列void wait(){// 其中的操作应当是原子性的x_count++;if(next_count>0){signal(next);}else{signal(mutex);}wait(x_sem);x_count--;}void signal(){if(x_count>0){next_count++;signal(x_sem);wait(next);next_count--;}}
};

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！