操作系统笔记（七）进程同步-白红宇

操作系统笔记（七）进程同步

阅读量：5307 次

发布时间：2019-06-14

本文共 2903 字，大约阅读时间需要 9 分钟。

资源竞争

概念：不同进程并发操作同一资源，操作结果受进程执行顺序影响。

解决方案：保证某一时刻只有一个进程读写，即保证操作串行。

critical section: 访问共享数据的代码

判断是否解决的标准：
- 相互隔绝：两个进程不会同时进入critical section
- progress: critical section之外的进程不会阻止其他进程进入他们的critical section
- bounded waiting: 每个进程等待有限时间即可进入critical section
- speed: 解决方案不包括对cpu数量和速度的设定

两个进程的peterson 算法：

1 int turn = 0; 2 bool flag[2] = {
     false, false}; 3  4 do { 5      6     flag[i] = true; 7     turn = j; 8     while(flag[j] && turn == j);// j未执行完临界区 且 j不准备进入临界区 ==》 j在临界区 9 10     CRITICAL SECTION11     12     flag[i] = false;13 } while(1);

多个进程的bakry 算法：

1 bool choosing[n] = {
     false, ..., false}; 2 int number[n] = {
     0,...0}; 3 do{ 4     choosing[i] = true; 5     number[i] = max(number[0],..,number[n-1]) + 1; // large number 6     choosing[i] = false; // number settled 7     for(int j = 0; j < n; j++){ 8         while(choosing[j]); // j have not settled number  9         while( (number[j] != 0) && ( (number[j] < number[i]) || (number[j] == number[i] && j < i) ));10         // j 未离开临界区，number[j] 小于 number[i] 或者number[j] = number[i] 但j < i。11     }12     13     CRITICAL SECTION14     15     number[i] = 0;16 }while(1);

硬件同步：

关闭中断：进程关闭中断，仅受时钟周期影响。缺点：用户进程不应该关中断；无法适应多核情况。

特殊指令：TSL（Test and Set Lock设置为true，返回旧值），SWAP。原子操作。缺点：忙等待，自旋锁，进入临界区之前一直处于检查阶段；仅适合于多核（context switch 少）。

信号量

本质：整型变量，只有P，V两个原子操作

实现：value 表示可用的资源数（>0）等待的进程数（<0）

1 typedef struct{ 2     int value;  3     struct PCB* L; // blocked processes        4 } semaphore; 5  6 void P(semaphor* S) 7 { 8     S -> value --; 9     if( S -> value < 0)10     {11           add currProc to S -> L;12           currProc -> state = WAITING;13           scheduler();   14      }       15 }16 17 void V(semaphor* S)18 {19      S -> value ++;20      if(S -> value <= 0)21      {22            get procA from S -> L;23            procA -> state = READY; 24      }25 }

信号量解决同步问题

生产者和消费者问题：empty（BSIZE）， full（0）同步生产者和消费者；mutex控制临界区（1）。

1 // producer 2 do { 3   ...produce an item 4   P(&empty); // < 0 -> 没资源，满，等待 5   P(&mutex); // < 0 -> 没资源，在临界区，等待 6  ... 7   add item to buffer 8  ... 9   V(&mutex);// <= 0 -> 有等待，叫醒10   V(&full);// <=0 -> 有等待，  叫醒11 }12 13 // consumer14 do {15   P(&full); // < 0 -> 没资源，空，等待16   P(&mutex); // < 0 -> 没资源，在临界区，等待17  ...18   consume an item from buffer19  ...20   V(&mutex);// <= 0 -> 有等待，叫醒21   V(&empty);// <=0 -> 有等待，  叫醒22 }

读写问题： wrt保护共享对象（1），整数readcount（0）记录读者数目，mutext（1）保护readcount。

1 // writer loop 2 do  3 { 4    P(&wrt); 5    ... 6    writing is performed 7    ... 8    V(&wrt);  9 } while(1)10 11 // reader loop12 do 13 {14    P(&mutex);15    readcount++;16    if (readcount == 1)17         P(&wrt); // can not write18    V(&mutex);19 20     ...21     reading is performed22     ...23    24     P(&mutex);25     readcount--;26     if (readcount == 0)27         V(&wrt);28     V(&mutex);29 }while(1);