操作系统笔记6

操作系统笔记6

进程同步

背景

共享数据的并发访问可能会导致数据的不一致。进程同步即通过各种机制来解决这个问题。

临界区问题

一、临界资源：

• 一次只能被一个进程使用的资源，如：共享变量、共享数据结构、慢速设备（打印机等）

二、临界区：

• 进程中有一个代码段称为临界区，在该区中，进程可能改变公共变量等，当一个进程进入临界区，就没有其他进程允许在临界区中执行，即没有两个进程可以同时在临界区中执行。

• 每个进程必须请求允许进入临界区，实现这一请求的代码段称进入区，临界区之后有退出区，其他代码称为剩余区

• do{
  //进入区
  //临界区
  //退出区
  //剩余区
  }while(true)
  - **临界区的解答必须满足三点要求**：1.互斥 2.有限等待 3.前进
  
  - **临界区的使用原则：**1.空闲让进 2.忙则等待 3.有限等待(不能出现死循环) 3.让权等待(放弃CPU)
  
  
  
  ## Peterson算法：基于软件的临界区问题解答
  
  Peterson算法适用于**两个进程**在临界区与剩余区交替执行。
  
  **一、两个进程之间共享的数据项：**
  
  ```c
  int turn;//表示哪一个进程可以进入临界区，如果turn==i，则表示进程i允许在其临界区内执行
  bool flag[2];//表示哪一个进程想进入临界区。如果flag[i]==true,表示i想进入临界区
  
  

二、算法的描述：

do{
    flag[i]=true;//表示进程i想要进入临界区
    turn=j;//先将turn赋值给j，看看j进程是否想要进入临界区
    while(turn==j && flag[j]==true);//如果j想要进入临界区且turn等于j，则等待j进入临界区
    
    //等待结束后，进入临界区
    
    //退出区
    flag[i]=false;//表示已经使用完临界区，不想进入了
    
    //剩余区
}while(true)

while(turn==j && flag[j]==true);此语句存在忙等

硬件同步

硬件同步方法虽然比软件同步简单，但仍然未解决忙等。

一般来说，任何临界问题都要一个工具：锁。通过要求临界区用锁来防护，就可以避免竞争。

do{
    //请求锁
    //临界区
    //释放锁
    //剩余区
}while(true)

信号量机制：解决忙等

信号量：只能通过P、V操作来改变其值的整形变量称为信号量

信号量的分类：

1. 计数型信号量：值域不受限制
2. 二元信号量：只有0和1，也称互斥锁

两个标准操作：wait（）和signal（），也称p（）操作和v（）操作

wait（）操作：为了克服忙等，如果发现信号量不为正时，入waiting队列等待

1. wait(semaphore *s){
       s->value--;//首先s变量自减
       
       //如果发现s变量不为正，则表明没有s类资源了，入waiting等待
       if(s->value<0){
           //add this process to S ->list
           block();
       }
   }
   2. signal（）操作：
   
      ```c
      signal(semaphore *s){
          s->value++;//首先s变量自增
          
          //如果s变量小于等于0，说明waiting队列有在等待s的进程
          if(s->value<=0){
              //reomve a process from S->list
              wakeup(p);//唤醒p进程
          }
      }
   
   
   
   

经典同步问题

有限缓冲问题：

假设缓冲池有n个缓冲项：

• 信号量mutex提供对缓冲池访问的互斥需求
• empty，初值为n，表示空缓冲项的个数
• full，初值为0，表示满缓冲项的个数

生产者进程：

do{
    //生产一个数据
    
    wait(empty);//等待有空的缓冲才能放
    wait(mutex);//等待缓冲池互斥锁放行
    //add
    signal(mutex);//释放互斥
    signal(full);//满缓冲项加一
}while(true)

消费者进程：

do{
   wait(full);//等待缓冲中数据
   wait(mutex);//等待互斥锁
   //remove
   signal(mutex);//释放互斥锁
   signal(empty);//空缓冲加一
}while(true)