【操作系统】吸烟者问题、读者-写着问题、哲学家进餐问题、管程

1. 吸烟者问题

1. 问题描述

假设一个系统有三个抽烟者进程和一个供应者进程。每个抽烟者不停地卷烟并抽掉它，但是要卷起并抽掉一支烟，抽烟者需要有三种材料:烟草、纸和胶水。三个抽烟者中，第一个拥有烟草、第二个拥有纸、第三个拥有胶水。供应者进程无限地提供三种材料，供应者每次将两种材料放桌子上，拥有剩下那种材料的抽烟者卷一根烟并抽掉它，并给供应者进程一个信号告诉完成了，供应者就会放另外两种材料再桌上，这个过程一直重复(让三个抽烟者轮流地抽烟)

2. 问题分析

本质上也属于“生产者——消费者”问题，更详细说应该是“可生产多种产品的单生产者——多消费者”。

1. 关系分析。找出描述的各个进程，分析他们之间的同步、互斥关系。
2. 整理思路。根据各进程的操作流程确定P、V操作的大致顺序。
3. 设置信号量。设置需要的信号量，并根据题目条件确定信号量初值。（互斥信号量初值一般为1，同步信号量的初始值要看对应资源的初始值是多少）。

组合一：纸+胶水。组合二：烟草+胶水。组合三：烟草+纸。

同步关系（从事件的角度来分析）：

1. 桌上有组合一 -> 第一个抽烟者取走东西。
2. 桌上有组合二 -> 第二个抽烟者取走东西。
3. 桌上有组合三 -> 第三个抽烟者取走东西。

3. 如何实现

semaphore offer1 = 0; //桌上组合一的数量
semaphore offer2 = 0; //桌上组合二的数量
semaphore offer3 = 0; //桌上组合三的数量
semaphore finish = 0; //抽烟是否完成
inti=0; //用于实现“三个抽烟者轮流抽烟”

provider(){
  while (1) {
    if(i==0) {
      将组合一放桌上;
      V(offer1) ;
    } else if (i==1) {
      将组合二放桌上;
      V(offer2) ;
    } else if(i==2) {
      将组合三放桌上;
      V(offer3) ;
    }
    i=(i+1)%3;
    P(finish) ;
  }
}

smoker1 () {
  while (1) {
    P(offer1) ;
    从桌上拿走组合一;卷烟;抽掉;
    V(finish) ;
  }
}

smoker2 () {
  while (1) {
    P(offer2) ;
    从桌上拿走组合二;卷烟;抽掉;
    V(finish) ;
  }
}

smoker3 () {
  while (1) {
    P(offer3) ;
    从桌上拿走组合三;卷烟;抽掉;
    V(finish) ;
  }
}

2. 读者—写者问题

1. 问题描述

有读者和写者两组并发进程，共享一个文件，当两个或两个以上的读进程同时访问共享数据时不会产生副作用，但若某个写进程和其他进程(读进程或写进程)同时访问共享数据时则可能导致数据不一致的错误。因此要求:①允许多个读者可以同时对文件执行读操作;②只允许一个写者往文件中写信息;③任一写者在完成写操作之前不允许其他读者或写者工作;④写者执行写操作前，应让已有的读者和写者全部退出。

2. 问题分析

两类进程:写进程、读进程。

互斥关系:写进程—写进程、写进程—读进程。读进程与读进程不存在互斥问题。

3. 如何实现

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) ;
    if (count==0)
      P(rw) ;
    count++ ;
    V(mutex) ;
    V(w) ;
    读文件...
    P(mutex) ;
    count-- ;
    if (count==0)
      V(rw) ;
    V(mutex) ;
  }
}

3. 哲学家进餐问题

1. 问题描述

一张圆桌上坐着5名哲学家，每两个哲学家之间的桌上摆一根筷子，桌子的中间是一碗米饭。哲学家们倾注毕生的精力用于思考和进餐，哲学家在思考时，并不影响他人。只有当哲学家饥饿时，才试图拿起左、右两根筷子(一根一根地拿起)。如果筷子已在他人手上，则需等待。饥饿的哲学家只有同时拿起两根筷子才可以开始进餐，当进餐完毕后，放下筷子继续思考。

2. 问题分析

1. 关系分析。系统中有5个哲学家进程，5位哲学家与左右邻居对其中间筷子的访问是互斥关系。
2. 整理思路。这个问题中只有互斥关系，但与之前遇到的问题不同的是，每个哲学家进程需要同时持有两种临界资源才能开始吃饭。所以要避免临界资源分配不当造成的死锁现象。
3. 信号量设置。定义互斥信号量数组chopstick[5]={1,1,1,1,1}，用于实现对5个筷子的互斥访问。并对哲学家按0~4编号，哲学家i左边的筷子编号为i，右边的筷子编号为(i+1)%5。

如何防止死锁的发生？

1. 可以对哲学家进程施加一些限制条件，比如最多允许四个哲学家同时进餐。这样可以保证至少有一个哲学家是可以拿到左右两只筷子的。
2. 要求奇数号的哲学家先拿左边的筷子，然后再拿右边的筷子，而偶数号哲学家刚好相反。用这种方法可以保证如果相邻的两个奇偶号哲学家都想吃饭，那么只会有其中一个可以拿起第一只筷子，另一个会直接阻塞。这就避免了占有一支后再等待另一支的情况，
3. 仅当一个哲学家左右两支筷子都可用时才允许他抓起筷子。

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]);  //放右
    思考...
  }
}

4. 管程

1. 为什么要引入管程

1. 信号量机制存在的问题:编写程序困难、易出错
2. 能不能设计一种机制，让程序员写程序时不需要再关注复杂的PV操作，让写代码更轻松呢?
3. 1973年，Brinch Hansen首次在程序设计语言(Pascal)中引入了“管程”成分—一种高级同步机制。

2. 管程的定义和基本特征

管程是一种特殊的软件模块，由这些部分组成：

1. 局部于管程的共享数据结构说明；
2. 对该数据结构进行操作的一组过程；
3. 对局部于管程的共享数据设置初始值的语句；
4. 管程有一个名字。

管程的基本特征：

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

1. 扩展1：解决生产者消费者问题

2. 扩展2：Java中类似于管程的机制

Java中，如果用关键字synchronized来描述一个函数， 那么这个函数同一时间段内只能被一个线程调用。

5. 小结

引入管程的目的无非就是要更方便地实现进程互斥和同步。

1. 需要在管程中定义共享数据(如生产者消费者问题的缓冲区)
2. 需要在管程中定义用于访问这些共享数据的“入口”—其实就是一些函数(如生产者消费者问题中，可以定义一个函数用于将产品放入缓冲区，再定义一个函数用于从缓冲区取出产品)。
3. 只有通过这些特定的“入口”才能访问共享数据。
4. 管程中有很多“入口”，但是每次只能开放其中一个“入口”，并且只能让一个进程或线程进入(如生产者消费者问题中，各进程需要互斥地访问共享缓冲区。管程的这种特性即可保证一个时间段内最多只会有一个进程在访问缓冲区。**注意:这种互斥特性是由编译器负责实现的，程序员不用关心)**。
5. 可在管程中设置条件变量及等待/唤醒操作以解决同步问题。可以让一个进程或线程在条件变量上等待(此时，该进程应先释放管程的使用权，也就是让出“入口”);可以通过唤醒操作将等待在条件变量上的进程或线程唤醒。

其实就是“封装”的思想。