恶补《操作系统》2_3——王道学习笔记

2.3_1 进程同步、进程互斥

1、进程同步

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

2、进程互斥

把一个时间段内只允许一个进程使用的资源称为临界资源。

对临界资源的互斥访问，可以在逻辑上分为四个部分：

do{
 
  entry section;  //进入区  对访问的资源检查或进行上锁
 
  critical section; //临界区(段) 访问临界资源的那部分代码
 
  exit section;   //退出区  负责解锁
 
  remainder section; //剩余区  其它处理
 
} while(true)

需要遵循的原则：

（1）空闲让进。 空的可以直接进去

（2）忙则等待。 繁忙不能进去

（3）有限等待。 不能让进程等待无限长时间

（4）让权等待。 不能进去，不要堵着

2.3_2 进程互斥的软件实现方法（重点）

1、单标志法

两个进程在访问完临界区后会把使用临界区的权限教给另一个进程。也就是说每个进程进入临界区的权限只能被另一个进程赋予

int turn =0;
 
//p0进程
 
while(turn!=0);
 
critical section;
 
turn = 1;
 
remainder section;
 
//p1进程
 
while(turn!=1);
 
critical section;
 
turn = 0;
 
remainder section;

可以实现互斥

存在的问题：p1要访问的话，必须p0先访问，违背：空闲让进原则

2、双标志先检查

算法思想:设置一个bool数组flag[]来标记自己是否想要进入临界区的意愿，先检查后上锁。

bool flag[2]={false,false};
 
//p1进程
 
while(flag[1]);
 
flag[0]=true;
 
critical section;
 
flag[0]=false;
 
remainder section;
 
//p2进程
 
while(flag[0]);
 
flag[0]=true;
 
critical section;
 
flag[1]=false;
 
remainder section;

主要问题：由于进程是并发进行的，可能会违背 忙则等待 的原则；“检查”和“上锁”并不能一气呵成。

3、双标志后检查

算法思想:设置一个bool数组flag[]来标记自己是否想要进入临界区的意愿,不过是先上锁后检查。

bool flag[2]={false,false};
 
//p1进程
 
flag[0]=true;
 
while(flag[1]);
 
critical section;
 
flag[0]=false;
 
remainder section;
 
//p2进程
 
flag[0]=true;
 
while(flag[0]);
 
critical section;
 
flag[1]=false;
 
remainder section;

主要问题：由于进程是并发进行的，可能会两个同时上锁，都进不去，违反 空闲让进 和 有限等待 原则，从而会饥饿。

4、Peterson 算法

主动让对方先使用处理器（孔融让梨）

bool flag[2]={false,false};
 
int turn=0;
 
//p1进程
 
flag[0]=true;
 
turn=1;
 
while(flag[1]&&turn==1);
 
critical section;
 
flag[0]=false;
 
remainder section;
 
//p2进程
 
flag[1]=true;
 
turn=0;
 
while(flag[0]&&turn==0);
 
critical section;
 
flag[1]=false;
 
remainder section;

遵循空闲让进、忙则等待、有限等待三个原则，但是未遵循 让权等待（卡在while循环）的原则。

2.3_3 进程互斥的硬件实现方法

1、中断屏蔽方法

简单、高校

多处理机，可能会同时访问临界资源

使用OS内核进程

2、TestAndSet（TSL指令）

TSL是用硬件实现的，上锁、检查一气呵成

不满足让权等待，会盲等

C语言描述逻辑：

//true表示已经上锁
 
bool TestAndSet(bool *lock){
 
  bool old;
 
  old=*lock;
 
  *lock=true;
 
  return old;
 
}
 
​
 
//以下是使用TSL指令实现互斥的算法逻辑
 
while(TestAndSet (&lock));//上锁并检查
 
临界区代码段
 
lock=false; //解锁
 
​

3、Swap指令

别称：Exchange指令、XCHG指令

Swap指令是用硬件实现的

//true表示已经上锁
 
void Swap(bool *a,bool *b){
 
  bool temp;
 
  temp=*a;
 
  *a=*b;
 
  *b=temp;
 
}
 
​
 
//以下是使用Swap指令实现互斥的算法逻辑
 
bool old=true;
 
while(old=true)
 
  Swap(&lock,&old);
 
临界区代码段
 
lock=false; //解锁
 
//剩余代码段

简单；适用多处理机；不能让权等待

2.3_4 信号量机制

信号量：信号量是一种变量，表示系统中某种资源的数量；

一对原语：wait（S）原语和signal（S）原语，分别简称P（S）、V（S），这一对原语可以对信号量进行操作。

1、整形信号量

用一个整数表示系统资源的变量，用来表示系统中某种资源的数量

int S=1;
 
void wait(int S){ //wait原语，相当于：“进入区”（检查和上锁一气呵成）
 
  while(S<=0); //如果资源数不够，就意志循环等待
 
  S=S-1;    //如果资源数够，则占用一个资源
 
}
void signal(int S){//signal原语，相当于“退出区”
 
  S=S+1;    //使用完资源后，在退出区释放资源
 
}

​

可能会出现盲等

2、记录型信号量（重点）

记录型数据结构表示的信号量

//记录型信号量的定义
 
typedef struct{
 
  int value;
 
  struct process *L;
 
} semaphore;
 
//某进程需要使用资源时，通过wait原语申请
 
void wait (semaphore S){
 
  S.value--;
 
  if(S.value<0){
 
    block (S.L);//将该进程加入到消息队列中
 
 }
 
}
 
//进程使用完资源后，通过signal原语释放
 
void signal (semaphore S){
 
  S.value++;
 
  if(S.valie<=0){
 
    wakeup(S.L);
 
 }
 
}

除非特别说明，否则默认S为记录型信号量

2.3_5 用信号量机制实现进程互斥、同步、前驱关系（重点）

1、实现进程互斥

设置互斥信号量mutex，初值为1，mutex表示 “进入临界区的名额”

对不同的临界资源需要设置不同的互斥信号量（只有1个名额）

PV必须成对出现，P申请，V释放

2、实现进程同步

（1）保证一前一后的操作顺序

（2）设置同步信号量S，初始为0

（3）前V后P：在“前操作”之后执行V（S）；在“后操作”之后执行P（S）

3、实现进程的前驱关系（多级同步）

（1）要为每一对前驱关系各设置一个同步变量

（2）在“前操作”之后对相应的同步变量执行V操作

（3）在“后操作”之前对相应的同步变量执行P操作

———————————下面介绍几个经典进程同步/互斥问题——————————

2.3_6 生产者-消费者问题（互斥、同步综合问题）

1. 只有缓冲区没满时，生产者才能把产品放入缓冲区，否则必须等待；
2. 只有缓冲区不空时，消费者才能从中取出产品，否则必须等待；
3. 缓冲区是临界资源，各个进程互斥访问；（如果同时访问，可能会产生数据覆盖的问题）
4. 实现互斥的P操作要放在实现同步的P操作之后，不能交换顺序，不然会发生死锁；（V操作可以交换）
5. V操作不会导致进程发生阻塞的状态，所以可以交换；
6. 相同的操作不要放在临界区，不然并发度会降低；

2.3_7 多生产者-多消费者模型

在生产-消费者问题中，如果缓冲区大小为1，那么有可能不需要设置互斥信号量就可以实现互斥访问缓冲区；分析同步问题是，应该从“事件”的角度来考虑。

PV操作：

互斥：在临界区前后分别PV；

同步：前V后P。

2.3_8 吸烟者问题

解决“可以让生产多个产品的单生产者”问题提供一个思路；

若一个生产者要生产多种产品（或者说会引发多种前驱事件），那么各个V操作应该放在各自对应的“事件”发生之后的位置。

2.3_9 读者-写者问题

1、允许多个读者同时对文件执行读操作

2、只允许一个写者往文件中写信息

3、任一写者在完成写操作之前不允许其他读者或写者工作

4、写者执行写操作前，应让已有的读者和写者全部退出

semaphore rw=1;//用于实现对文件的互斥访问。表示当前是否有进程在访问共享文件
 
int count=0;//记录当前有几个读进程在访问文件
 
semaphore mutex=1;//用于保证对count变量的互斥访问
 
semaphore w=1; //用于实现“写优先”
 
  
 
writer(){
 
  while(1){
 
    P（w）;
 
    P(rw); //写之前“加锁”
 
    写文件。。。
 
    V（rw);//写之后“解锁”
 
  V(w);
 
 }
 
}
 
​
 
reader(){
 
  while(1){
 
    P(w);
 
   P(mutex); //各读进程互斥访问count
 
    if(count==0)
 
      P(rw); //第一个读进程的读进程数+1
 
    count++; //访问文件的读进程数+1
 
    V(mutex);
 
    V(w);
 
    读文件...
 
    P(mutex); //各读进程互斥访问count
 
    count--; //访问文件的读进程数-1
 
    if(count==0)
 
      V(rw); //最后一个读进程负责“解锁”
 
    V(mutex);
 
 }
 
}

2.3_10 哲学家进餐问题

五个人，必须拿左右的筷子才能吃饭

避免死锁发生

解决方案：

1、可以对哲学家进程施加一些限制条件，比如最多允许四个哲学家同时进餐，这样可以保证至少有一个哲学家是可以拿到左右两只筷子的。

2、要求奇数号哲学家先拿左边的筷子，然后再拿右边的筷子，而偶数号哲学家刚好相反。用这种方法可以保证如果相邻的两个奇偶号哲学家都想吃饭，那么只会有其中一个可以拿起第一只筷子，另一个会直接阻塞。这就避免了占有一只后再等待另一只的情况。

3、仅当一个哲学家左右两只筷子都可用时才允许他抓起筷子。

semaphore chopstick[5]={1,1,1,1,1};
 
semaphore mutex = 1; //互斥地取筷子
 
Pi(){     //i号哲学家的进程
 
  while(1){
 
    P(mutex);
 
    p(chopstick[i]);   //拿右
 
    p(chopstick[(i+1)%5]);//拿左
 
    V(mutex);
 
    吃饭...
 
    V(chopstick[i]);
 
    V(chopstick[(i+1)%5]);
 
    思考...
 
 }
 
}

2.3_11 管程

1、为什么要引入管程？

PV操作容易出错、困难

2、管程的定义和基本特征（重点）

定义：管程是一种特殊的软件模块

• 局部于管程的共享数据结构说明
• 对该数据结构进程操作的一组过程（函数）
• 对局部于管程的共享数据设置初始值的语句
• 管程有一个名字

基本特征：

• 局部于管程数据结构只能被局部于管程的过程所访问
• 一个进程只有通过调用管程内的过程才能进入管程访问共享数据
• 每次仅允许一个进程在管程内执行某个内部过程

心得：相当于C++的类，管程是数据放在private中，函数放在public中

拓展：用管程解决生产者消费者问题

monitor producerconsumer
 
  condition full,empty;
 
  int count = 0;
 
  void insert(Item item){ //产品放入缓冲区
 
    if(count == N)
 
      wait(full);
 
    count++;
 
    insert_item (item);
 
    if(count == 1)
 
      signal(empty);
 
 }
 
  Item remove(){ //从缓冲区取出一个产品
 
    if(count == 0)
 
      wait(empty);
 
    count--;
 
    if(count == N-1)
 
      signal(full);
 
    return remove_item();
 
 }
 
  end monitor;
 
​
 
//生产者进程
 
producer(){
 
  while(1){
 
    item = 生产一个产品;
 
    producerconsumer.insert(item);
 
 }
 
}
 
​//消费者进程
 
consumer(){
 
  while(1){
 
    item = producerconsumer.remove();
 
    消费产品 item;
 
 }
 
}

2.4_1 死锁的概念

1、什么是死锁

各进程互相等待对方手里的资源，导致各进程都阻塞，无法向前推进的现象。

2、进程死锁、饥饿、死循环的区别（重点）

（1）死锁：

1. 定义：各进程互相等待对方手里的资源，导致各进程都阻塞，无法向前推进的现象。
2. 区别：至少两个或两个的进程同时发生死锁

（2）饥饿：

1. 定义：由于长期得不到想要的资源，某进程无法向前推进的现象。
2. 区别：可能只有一个进程发生饥饿

（3）死循环：

1. 定义：某进程执行过程中一直跳不出某个循环的现象。
2. 区别：死循环是程序员的问题

饥饿、死锁都是堵塞态；死循环可能会是运行态

3、死锁产生的必要条件

• 互斥条件：多个进程争夺资源发生死锁
• 不剥夺条件：进程获得的资源不能由其它进程强行抢夺
• 请求和保持条件：某个进程有了资源，还在请求资源
• 循环等待条件：存在资源的循环等待链

发生死锁一定有循环等待；发生循环等待不一定死锁

4、什么时候会发生死锁

• 对系统资源的竞争
• 进程推进顺序非法
• 信号量的使用不当也会造成死锁

5、死锁的处理策略

• 预防死锁
• 避免死锁
• 死锁的检测和解除

2.4_2 死锁的处理策略——预防死锁

1、不允许死锁发生

• （1）静态策略：预防死锁
  • 破坏互斥条件（有些不能破坏）
  • 把互斥的资源改造为共享资源
  • 破坏不剥夺条件（复杂，造成之前工作失效，降低系统开销，会全部放弃、导致饥饿）
    • 方案1：当请求得不到满足的时候，立即释放手里的资源
    • 方案2：由系统介入，强行帮助剥夺
  • 破坏请求和保持条件（资源利用率极低，可能会导致某些进程饥饿）
    • 采用静态分配方法，一次性全部申请，如果申请不到，不要允许
  • 破坏循环等待条件（不方便增加新的设备，实际使用与递增顺序不一致，会导致资源的浪费，必须按规定次序申请资源）
  • 顺序资源分配法：对资源编号，进程按编号递增顺序请求资源
• （2）动态检测：避免死锁

2、允许死锁发生

• 死锁的检测和解除

2.4_3 死锁的处理策略——避免死锁

动态检测：避免死锁

• 什么是安全序列
• 进行后面的某些情况，不会使系统发生死锁
• 什么是系统的不安全状态，与死锁有何联系
• 如果系统处于安全状态，就一定不会发生死锁。如果系统进入不安全状态，就可能发生死锁（处于不安全状态未必就是发生了死锁，但发生死锁时一定时在不安全状态）
• 如何避免系统进入不安全状态——银行家算法
• 初始分配完成后，优先全部分配给最少的，并且拿回资源

步骤：

1、检查此次申请是否超过了之前声明的最大需求数

2、检查此时系统剩余的可用资源是否还能满足这次请求

3、试探着分配，更改各数据结构

4、用安全性算法检查此次所分配是否会导致系统进入不安全状态

2.4_4 死锁的处理策略——检测和解除

1、死锁的检测

（1）用某种数据结构来保存资源的请求和分配信息

（2）提供一种算法，利用上述信息来检测系统是否已进入死锁状态。

2、死锁的解除3种方法

（1）资源剥夺法：挂起某些死锁进程，并抢占它的资源，将这些资源分配给其他的死锁进程。

（2）撤销进程法/终止进程法：强制撤销部分，甚至全部死锁进程，并剥夺这些进程的资源。（代价大）

（3）进程回退法：让一个或多个死锁进程回退到足以避免死锁的地步。