进程同步和互斥

什么是进程同步、互斥

异步：各并发执行的进程已各自独立、不可预知的速度向前推进

同步：直接制约关系，为完成某种任务而建立的两个或多个进程，这些进程因为需要在某些位置上协调他们的工作次序而产生的制约关系，进程间的直接制约关系就是源于他们的相互合作

互斥：间接制约关系，当一个进程访问某临界资源时，另一个想要访问该临界资源的进程必须等待，当前访问临界资源的进程访问结束，释放该资源之后，另一个进程才能去访问该临界资源

do{
    entry section;      // 进入区
    critical section;   // 临界区
    exit section;       // 退出区
    remain section;     // 剩余区
}while(true)

进入区：负责检查是否可进入临界区，若可进入，则应设置正在访问临界资源的标志（上锁），以阻止其他进程同时进入临界区
临界区：访问临界资源的代码
退出区：负责解除正在访问临界资源的标志（解锁）
剩余区：其他处理
进入区和退出区是负责实现互斥的代码段

互斥访问的原则

  1. 空闲让进：临界区空闲时，可以允许一个请求进入临界区的进程立即进入临界区
  2. 忙则等待：当已有进程进入临界区时，其他试图进入临界区的进程必须等待
  3. 有限等待：对请求访问的进程，应能保证在有限时间内进入临界区（不会饥饿）
  4. 让权等待：当进程不能进入临界区时，应立即释放CPU，防止进程忙等待

进程互斥的软件实现方法

单标志法
算法思想：两个进程在访问完临界区后，会把使用临界区的权限转交给另一个进程。即每个进程进入临界区的权限只能被另一个进程赋予

int turn; // turn表示当前允许进入临界区的进程号

// p0进程
while(turn != 0); // 1
critical section; // 2
turn = 1; // 3
remain section; // 4

// p1进程
while(turn != 1); // 5
critical section; // 6
turn = 0; // 7
remain section; // 8

可以实现互斥访问临界区，对临界区的访问是交替轮流的
如果p0一直不访问临界区的话，p1也访问不了临界区，因为turn要在p0退出区改变权限给p1，违背了空闲让进的原则

双标志先检查法
算法思想：设置一个布尔型数组flag[]，数组中各个元素用来标记各进程想进入临界区的意愿，比如flag[0] = true，表示p0现在想要进入临界区。每个进程在进入临界区前先检查当前有没有别的进程想进入临界区，如果没有，把自身对应标志flag[i] = true，之后开始访问临界区

// 初始化两个进程都不想进入临界区
bool flag[2];
flag[0] = false;
flag[1] = false;

// p0
while(flag[1]); // 1
flag[0] = true; // 2
critical section; // 3
flag[0] = false; // 4
remain section;

// p1
while(flag[0]); // 1
flag[1] = true; // 2
critical section; // 3
flag[1] = false; // 4
remain section;

某个时刻之前p0和p1都不想访问临界区，到了这个时刻p0和p1都想访问临界区，而且此时flag[0]和flag[1]都是false，所以两个进程可以同时进入临界区，不能实现互斥访问临界区，违背了忙则等待的原则。原因在于检查和上锁不是一气呵成的

双标志后检查法
算法思想：双标志先检查法的改版，前一个算法的问题在于先检查后上锁，但是这两个操作又无法一气呵成，因此导致两个进程同时进入临界区的问题，因此，人们想到先上锁后检查的方法来避免上述问题

// 初始化两个进程都不想进入临界区
bool flag[2];
flag[0] = false;
flag[1] = false;

// p0
flag[0] = true; // 1
while(flag[1]); // 2
critical section; // 3
flag[0] = false; // 4
remain section;

// p1
flag[1] = true; // 1
while(flag[0]); // 2
critical section; // 3
flag[1] = false; // 4
remain section;

某一时刻p0和p1都想进入临界区，他们的flag都为true，p0和p1进程就会一直处于while循环中等待，都无法进入临界区。违反了空闲让进和优先等待原则，会因各进程都长期无法访问临界资源产生饥饿现象

Peterson算法
算法思想：双标志后检查算法中，两个进程都争着想用临界区，但是谁也不让，最后谁都无法进入临界区。如果双方都想进入临界区，可以让进程主动让对方先使用临界区

// 初始化两个进程都不想进入临界区
bool flag[2];
int turn = 0;

// p0
flag[0] = true;
turn = 1;
while(flag[1] && turn = 1);
critical section;
flag[0] = false;
remain section;

// p1
flag[1] = true;
turn = 0;
while(flag[0] && turn = 0);
critical section;
flag[1] = false;
remain section;

解决了进程互斥问题，遵循了空闲让进、忙则等待、有限等待原则，但是没遵循让权等待原则，会发生忙等待

进程互斥的硬件实现方法

中断屏蔽方法
利用开/关中断实现（与原语的实现思想相同，即在某进程开始访问临界区到结束访问为止都不允许被中断，也就不能发生进程切换，因此也不可能发生两个进程同时访问临界区的情况）
关中断--临界区--开中断
优点：简单高效
缺点：不适用于多CPU（因为开关中断指令只对当前的CPU有用），只适用于操作系统内核进程，不适用于用户进程（因为开关中断指令只能在内核态运行，这组指令如果能让用户随意使用会很危险）

TestAndSet指令（TS、TSL）
执行的过程不能被中断

// c语言描述的一个逻辑，只是逻辑
// 布尔型共享变量lock表示当前临界区是否被加锁
// true表示已加锁，false表示未加锁
bool TestAndSet(bool* lock){
    bool old;
    old = *lock; // old用于存放lock原来的值
    *lock = true; // 无论之前是否已加锁，都将lock设为true
    return old; // 返回lock原来的值
}

// 以下是使用TSL指令实现互斥的算法逻辑
while(TestAndSet(&lock)); // 上锁并检查
critical section;
lock = false; // 解锁
remain section;

把上锁和检查操作用硬件的方式变成了原子操作
优点：实现简单，无需像软件实现方法那样严格检查是否会有逻辑漏洞，适用于多CPU环境
缺点：不满足让权等待原则，暂时无法进入临界区的进程会占用CPU并循环执行TSL指令，导致忙等

swap指令（exchange、xchg指令）
用硬件实现，一气呵成

//  用c语言描述的逻辑

// Swap用于交换两个变量的值
Swap(bool* a, bool* b){
    bool temp;
    temp = *a;
    *a = *b;
    *b = temp;
}

// 以下是使用Swap指令实现互斥的算法逻辑
// lock表示当前临界区是否被加锁
bool old = true;
while(old == true)
    Swap(&lock, &old);
critical section;
lock = false;
remain section;

和TSL差不多的逻辑，都是先记录下此时的临界区是否被上锁，记录在old中，再将lock设置为true，最后检查old，如果old为false说明之前没有别的进程对临界区上锁，可跳出循环进入临界区
优点：实现简单，无需像软件实现方法那样严格检查是否有逻辑漏洞；适用于多CPU环境
缺点：不满足让权等待原则，暂时无法进入临界区的进程会占用CPU并循环执行swap指令，导致忙等

信号量

用户进程可以通过使用操作系统提供的一对原语来对信号量进行操作，从而很方便的实现了进程互斥、进程同步。原语是通过开关中断来实现的

信号量：一个变量，可以是一个整数，也可以是更复杂的记录型变量，可以用一个信号量来表示系统中某种资源的数量。比如，系统中只有一台打印机，就可以设置一个初值为1的信号量

一对原语
wait(S)：P操作，申请
signal(S)：V操作，释放

整型信号量：表示系统中某种资源的数量，三种操作：初始化、P、V

// 有一台打印机
int S = 1; // 打印机资源数

void wait(int S){
    while(S <= 0); // 如果资源数不够，就一直循环等待
    S = S - 1; // 如果资源数够，则占用一个资源
}

void signal(int S){
    S = S + 1; // 使用资源后，在退出区释放资源
};

// 进程p0
...
wait(S);
critical section;
signal(S);
...

// 进程p1
...
wait(S);
critical section;
signal(S);
...

// 进程pn
...
wait(S);
critical section;
signal(S);
...

和双标志先检查后上锁逻辑一样，但是通过原语操作将检查上锁绑定在一起了
存在的问题：不满足让权等待原则，会发生忙等。一个进程暂时进不了临界区，卡在while循环

记录型信号量
用来解决忙等问题

// 记录型信号量的定义
typedef struct{
    int value; // 剩余资源数
    struct process* L; // 等待队列（阻塞队列）
}semaphore;

// 某进程需要使用资源时，通过wait原语申请
void wait(semaphore S){
    S.value--; // 某个进程需要使用资源，将资源数量减1
    if(S.value < 0){ // 检查value值，小于零说明在减1之前已经没有系统资源可以分配
        block(S.L); // 将进程阻塞，挂到信号量S的等待队列（阻塞队列）
    }
}

// 进程使用完资源，通过signal原语释放
void signal(semaphore S){
    S.value++; // 数量加1
    if(S.value <= 0){ // 资源释放后value仍然小于等于0，说明在释放资源之前，还有进程处于阻塞队列
        wakeup(S.L); // 调用wakeup原语从S的阻塞队列唤醒某一个进程，让他从阻塞态进入就绪态
    }
}

// 例子：有两台打印机
// 初始化：value为2，S.L为NULL
// 进程p0
...
wait(S);
critical section;
signal(S);
...

// 进程p1
...
wait(S);
critical section;
signal(S);
...

// 进程pn
...
wait(S);
critical section;
signal(S);
...

如果资源分配完会进行自我阻塞，不会出现忙等现象，遵循了让权等待现象

PV默认为记录型信号量

用信号量实现进程互斥

  1. 划分临界区
  2. 互斥信号量mutex，初值为1
  3. 在临界区前执行P
  4. 在临界区后执行V
semaphore mutex = 1;
p1(){
    ...
    p(mutex);
    critical section;
    V(mutex);
    ...
}
p2(){
    ...
    p(mutex);
    critical section;
    V(mutex);
    ...
}

对于不同的临界资源要设置不同的互斥信号量
PV必须成对出现

用信号量实现进程同步

要让各并发进程按要求有序推进

  1. 分析什么地方需要实现同步关系，必须保证一前一后执行的两个操作
  2. 设置同步信号量S，初始为0
  3. 在前操作之后执行V
  4. 在后操作之前执行P
semaphore S = 0;

p1(){
    code1;
    code2;
    V(S);
    code3;
}

p2(){
    P(S);
    code4;
    code5;
    code6;
}

要保证code2在code4之前执行
若先执行到V，S的value变为1，之后p2在执行的时候，将S的value变为0，继续执行code4
若先执行到P，S的value变为-1，p2陷入阻塞状态，p1执行到V操作，将value变为0，并将处于阻塞的p2唤醒，code4再执行

信号量机制实现前驱关系

每一对前驱关系都是一个进程同步问题

  1. 为每一对前驱关系设置一个同步变量
  2. 前操作之后进行V
  3. 后操作之前进行P
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 204,445评论 6赞 478
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 85,889评论 2赞 381
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 151,047评论 0赞 337
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 54,760评论 1赞 276
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 63,745评论 5赞 367
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 48,638评论 1赞 281
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 38,011评论 3赞 398
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 36,669评论 0赞 258
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 40,923评论 1赞 299
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,655评论 2赞 321
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,740评论 1赞 330
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 33,406评论 4赞 320
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 38,995评论 3赞 307
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,961评论 0赞 19
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,197评论 1赞 260
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 45,023评论 2赞 350
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 42,483评论 2赞 342