操作系统拾遗--进程同步、互斥

进程通信

进程通信--进程之间的信息交换，如同步、互斥。

进程通信分为：

• 低级通信方式：同步与互斥
• 高级通信方式：共享存储器系统、消息传递系统、管道通信系统。

进程同步与互斥

0. 概念

临界资源：同时只允许一个进程访问的资源。
临界区：进程中用于访问临界资源的代码段。
禁止同时进入临界区，四个原则：让权等待、空闲让进、忙则等待、有限等待。

1. 互斥

• 算法1. 使用公用整形变量

P0:
while(turn != 0){
     // critical section
     turn  = 1; // 退出区
     // remainder section
}

P1:
while(turn != 1){
     // critical section
     turn  = 0; // 退出区
     // remainder section
}

缺点：资源利用不充分，只能交替运行。违背了空闲让进原则。

• 算法2. 双标志法之先检查

boolean flag[] = {false, false}

P0： 
  while(flag[1]);
  flag[0] = true; 
  临界区
  flag[0] = false; 
  剩余区

P1：
  while(flag[0]);
  flag[1] = true;
  临界区
  flag[1] = false;
  剩余区

缺陷：同时未进入时，两个进程都想进入，同时进入。

• 双标志之后检查法

boolean flag[] = {false, false}

P0： 
  flag[0] = true; 
  while(flag[1]);
  
  临界区
  flag[0] = false; 
  剩余区

P1：
  flag[1] = true;
  while(flag[0]);
  临界区
  flag[1] = false;
  剩余区

缺点：同时未进入时，两个进程都想进入，判断对方为false，死锁。

• Peterson算法

P0：
  flag[0]=TURE; 
  turn=1;
  while(flag[1] && turn==1); 
  临界区
  flag[0]=false;
  剩余区

P1
  flag[1]=TURE; 
  turn=0;
  while(flag[0] && turn==0); 
  临界区
  flag[1]=false;
  剩余区

---

2. 信号量

二元组(s, q)：s表示资源数，q代表信号量所对应的队列。

• 整数型信号量--进行P操作时未遵循让权等待

P：wait(s){
  while (s<=0);
  s=s-1;
}

V：signal(s){
  s=s+1;
}
wait操作中，只要信号量S<=0，就会不断地测试。
因此，该机制并未遵循让权等待的原则。

• 记录型信号量--增加一个进程链表，用于存放所有等待该资源的进程

typedef struct{
    int value;
    struct process *linklist;
} semaphore;

wait(semaphore s) { 
    s.value--;
    if(s.value<0) {
        add this process to s.linklist;
        block(s.linklist);
    }
}

signal(semaphore s) {
    s.value++;
    if(s.value<=0){
        remove a process P from s.linklist;
        wakeup(P);
    }
}

• AND型信号量--当一段处理代码需要同时获取两个或多个临界资源时，就可能出现由于各进程分别获得部分临界资源并等待其余的临界资源的局面。各进程互不相让从而出现死锁。解决这个问题的一个思路是：在一个原语中申请整段代码需要的多个临界资源，要么全部分配给它，要么一个都不分配给它。也就是说，对若干个临界资源的分配，采取原子操作方式：要么把它所请求的资源全部分配到进程，要么一个也不分配。

---

3. 经典同步问题

3.1 生产者消费者问题

问题描述：生产者进程和消费者进程共享一块初始为空、有界的缓冲区。生产者往里放数据、消费者从中取数据。

条件：只有当缓冲区未满时，生产者进程才可以把数据放入缓冲区；只有缓存区不为空时，消费者进程才能从中取出数据。

一个有界缓冲区：生产者从中取数据，消费者往里放数据----互斥访问[信号量mutex.init=1]

semaphore mutex=1;     // 互斥访问缓冲区
semaphore full=0;          // 满缓冲区数值
semaphore empty=N;    // 空闲缓冲区数值

prodecer()
{
    while(true)
    {
          P(empty);   // P操作顺序不能颠倒       
          P(mutex);   // 多生产者模式下必须要有互斥访问量
          放入缓冲池;
          V(mutex);
          V(full);      
    }    
}        

consumer()
{
    while(true)
   {
         P(full);
         P(mutex);
         从缓冲区中取出一个元素;
         V(mutex);
         V(empty);     
    }    
}

Note：在有多个信号量同时存在的，P操作通常不能颠倒顺序。必须先对资源信号量进行P操作，再对互斥信号量进行P操作。

3.2 哲学家用餐

问题描述：假设有五位哲学家围坐在一张圆形餐桌旁，做以下两件事情之一：吃饭，或者思考。餐桌中间有一大碗米，每两个哲学家之间有一根筷子。他们只能使用自己左右手边的那两根筷子。

条件：吃东西的时候，他们就停止思考，思考的时候也停止吃东西。因为用一根筷子很难吃到米，所以假设哲学家必须用一双筷子吃东西。

奇数号哲学家先拿左筷子，再拿右边的筷子
偶数号哲学家相反。
semaphore Fork[5]={1,1,1,1,1}; // 5根筷子

philosopher(int i){
    while(true){
        思考
        饿了，去拿筷子
        if (i % 2 != 0){
            P(Fork[i]);
            P(Fork[(i+1) % 5]);
            吃饭; 
            V(Fork[i));
            V(Fork[(i+1) % 5]);
        }else{
            P(Fork[(i+1) % 5]);
            P(Fork[i]);
            吃饭; 
            V(Fork[i));
            V(Fork[(i+1) % 5]);
        }
    }
}

3.3 读者-写者问题

问题描述：有读者和写者两组并发进程，共享一个文件，当两个或以上的读进程同时访问共享数据时没有问题，但若某个写进程和其他进程（读进程或写进程）同时访问共享数据时则可能导致数据不一致的错误。

条件：
① 允许任意多个读者可以同时对文件执行读操作；
② 一次只允许一个写者往文件中写信息(写者必须互斥)；
③ 任一写者在完成写操作之前不允许其他读者或写者工作。

int readCount = 0;                  // 有多少读者在读读

Semaphore resourceAccess = 1;       // controls access (read/write) to the resource
Semaphore readCountAccess = 1;      // for syncing changes to shared variable readCount
Semaphore serviceQueue = 1;         // FAIRNESS: preserves ordering of requests (signaling must be FIFO)

void writer()
{
    serviceQueue.P();           // wait in line to be serviced
    // <ENTER>
    resourceAccess.P();         // request exclusive access to resource
    // </ENTER>
    serviceQueue.V();           // let next in line be serviced
    
    // <WRITE>
    writeResource();            // writing is performed
    // </WRITE>
    
    // <EXIT>
    resourceAccess.V();         // release resource access for next reader/writer
    // </EXIT>
}

void reader()
{
    serviceQueue.P();           // wait in line to be serviced
    readCountAccess.P();        // request exclusive access to readCount
    // <ENTER>
    if (readCount == 0)         // if there are no readers already reading:
        resourceAccess.P();     // request resource access for readers (writers blocked)
    readCount++;                // update count of active readers
    // </ENTER>
    serviceQueue.V();           // let next in line be serviced
    readCountAccess.V();        // release access to readCount
    
    // <READ>
    readResource();             // reading is performed
    // </READ>
    
    readCountAccess.P();        // request exclusive access to readCount
    // <EXIT>
    readCount--;                // update count of active readers
    if (readCount == 0)         // if there are no readers left:
        resourceAccess.V();     // release resource access for all
    // </EXIT>
    readCountAccess.V();        // release access to readCount
}

读者写者问题参考