程序并发执行时具有如下特征:
由于程序在并发执行时,可能会造成执行结果的不可再现,所以用 "程序" 这个概念已无法描述程序的并发执行,所以必须引入新的概念—进程来描述程序的并发执行,并要对进程进行必要的管理,以保证进程在并发执行时结果可再现。
进程 (Process) 定义:"可并发执行的程序在一个数据集合上的运行过程"。进程具有如下特征:
进程的三个基本状态
三个基本状态之间可能转换和转换原因如下:
一个问题:假设一个只有一个处理机的系统中,OS 的进程有运行、就绪、阻塞三个基本状态。假如某时刻该系统中有 10 个进程并发执行,在略去调度程序所占用时间情况下试问
这时刻系统中处于运行态的进程数最多几个?最少几个
这时刻系统中处于就绪态的进程数最多几个?最少几个
这时刻系统中处于阻塞态的进程数最多几个?最少几个?
解:因为系统中只有一个处理机,所以某时刻处于运行态的进程数最多只有一个。而最少可能为 0,此时其它 10 个进程一定全部排在各阻塞队列中,在就绪队列中没有进程。而某时刻处于就绪态的进程数最多只有 9 个,不可能出现 10 个情况,因为一旦 CPU 有空,调度程序马上调度,当然这是在略去调度程序调度时间时考虑。处于阻塞态的进程数最少是 0 个。
进程是由程序、数据和进程控制块组成。进程上下文实际上是执行活动全过程的静态描述。具体说,进程上下文包括系统中与执行该进程有关的各种寄存器(例如:通用寄存器、程序计数器 PC、程序状态寄存器 PS 等)的值,程序段在经编译之后形成的机器指令代码集(或称正文段)、数据集及各种堆栈值和 PCB 结构。一个进程的执行是在该进程的上下文中执行,而当系统调度新进程占有处理机时,新老进程的上下发生切换。UNIX 操作系统的进程上下文称为进程映象。
在多道程序环境下,系统中各进程以不可预测的速度向前推进,进程的异步性会造成了结果的不可再现性。为防止这种现象,异步的进程间推进受到二种限制:
进程之间竞争资源也面临三个控制问题:
进程在并发执行时为了保证结果的可再现性,各进程执行序列必须加以限制以保证互斥地使用临界资源,相互合作完成任务。多个相关进程在执行次序上的协调称为进程同步。用于保证多个进程在执行次序上的协调关系的相应机制称为进程同步机制。所有的进程同步机制应遵循下述四条准则:
1965 年,荷兰学者 Dijkstra 提出的信号量机制是一种卓有成效的进程同步工具,在长期广泛的应用中,信号量机制又得到了很大的发展,它从整型信号量机制发展到记录型信号量机制,进而发展为 "信号集" 机制。现在信号量机制已广泛应用于 OS 中。
信号量按联系进程的关系分成二类:
具体分类如下:
为使多个进程能互斥地访问某临界资源,只需为该资源设置一个互斥信号量 mutex, 并设其初值为 1,并规定每个进程在进入临界区 CS 前必须申请资源,即对互斥信号量 mutex 施加 P 操作,在退出临界区 CS 后必须释放资源,即对互斥信号量 mutex 施加 V 操作;即将各进程的临界区 CS 置于 P(mutex)和 V(mutex) 操作之间。
在多道程序环境下,进程同步是一个十分重要又令人感兴趣的问题,而生产者 - 消费者问题是其中一个有代表性的进程同步问题。下面我们给出了各种情况下的生产者 - 消费者问题。
(1)一个生产者,一个消费者,公用一个缓冲区。
定义两个同步信号量:
empty——表示缓冲区是否为空,初值为 1。
full——表示缓冲区中是否为满,初值为 0。
生产者进程
- while(TRUE){
- 生产一个产品;
- P(empty);
- 产品送往Buffer;
- V(full);
- }
消费者进程
- while(True){
- P(full);
- 从Buffer取出一个产品;
- V(empty);
- 消费该产品;
- }
(2)一个生产者,一个消费者,公用 n 个环形缓冲区。
定义两个同步信号量:
empty——表示缓冲区是否为空,初值为 n。
full——表示缓冲区中是否为满,初值为 0。
设缓冲区的编号为 0~n-1,定义两个指针 in 和 out,分别是生产者进程和消费者进程使用的指针,指向下一个可用的缓冲区。
生产者进程
- while(TRUE){
- 生产一个产品;
- P(empty);
- 产品送往buffer(in);
- in=(in+1)mod n;
- V(full);
- }
消费者进程
- while(TRUE){
- P(full);
- 从buffer(out)中取出产品;
- out=(out+1)mod n;
- V(empty);
- 消费该产品;
- }
(3)一组生产者,一组消费者,公用 n 个环形缓冲区
在这个问题中,不仅生产者与消费者之间要同步,而且各个生产者之间、各个消费者之间还必须互斥地访问缓冲区。
定义四个信号量:
empty——表示缓冲区是否为空,初值为 n。
full——表示缓冲区中是否为满,初值为 0。
mutex1——生产者之间的互斥信号量,初值为 1。
mutex2——消费者之间的互斥信号量,初值为 1。
设缓冲区的编号为 0~n-1,定义两个指针 in 和 out,分别是生产者进程和消费者进程使用的指针,指向下一个可用的缓冲区。
生产者进程
- while(TRUE){
- 生产一个产品;
- P(empty);
- P(mutex1);
- 产品送往buffer(in);
- in=(in+1)mod n;
- V(mutex1);
- V(full);
- }
消费者进程
- while(TRUE){
- P(full)
- P(mutex2);
- 从buffer(out)中取出产品;
- out=(out+1)mod n;
- V(mutex2);
- V(empty);
- 消费该产品;
- }
需要注意的是无论在生产者进程中还是在消费者进程中,两个 P 操作的次序不能颠倒。应先执行同步信号量的 P 操作,然后再执行互斥信号量的 P 操作,否则可能造成进程死锁。
下面给出一个 Java 描述代码:
- package com.kang;
- import java.util.concurrent.Semaphore;
- class Signs {
- static Semaphore empty = new Semaphore(10); // 信号量:表示仓库缓存区
- static Semaphore full = new Semaphore(0); // 信号量:表示仓库满的标志
- static Semaphore mutex = new Semaphore(1); // 临界区互斥访问信号量(二进制信号量),相当于互斥锁。
- }
- class Producer implements Runnable {
- // 生产者
- public void run() {
- try {
- while (true) {
- Signs.empty.acquire(); // 递减仓库缓存区信号量
- Signs.mutex.acquire(); // 进入临界区
- System.out.println("生成一个产品放入仓库");
- Signs.mutex.release(); // 离开临界区
- Signs.full.release(); // 递增仓库满信号量
- Thread.currentThread().sleep(100);
- }
- } catch (InterruptedException e) {
- e.printStackTrace();
- }
- }
- }
- class Consumer implements Runnable {
- // 消费者
- public void run() {
- try {
- while (true) {
- Signs.full.acquire(); // 递减仓库满信号量
- Signs.mutex.acquire(); // 进入临界区
- System.out.println("从仓库拿出一个产品消费");
- Signs.mutex.release(); // 离开临界区
- Signs.empty.release(); // 递增仓库缓存区信号量
- Thread.currentThread().sleep(1000);
- }
- } catch (InterruptedException e) {
- e.printStackTrace();
- }
- }
- }
- public class Test {
- public static void main(String[] args) {
- new Thread(new Producer()).start();
- new Thread(new Consumer()).start();
- }
- }
程序运行结果如下:
在 1965 年,Dijkstra 提出并解决了一个他称之为哲学家进餐的同步问题。从那时起,每个发明新的同步原语的人都希望通过解决哲学家进餐间题来展示其同步原语的精妙之处。这个问题可以简单地描述:五个哲学家围坐在一张圆桌周围,每个哲学家面前都有一碟通心面,由于面条很滑,所以要两把叉子才能夹住。相邻两个碟子之间有一把叉子。哲学家的生活包括两种活动: 即吃饭和思考。当一个哲学家觉得饿时,他就试图去取他左边和右边的叉子。如果成功地获得两把叉子,他就开始吃饭,吃完以后放下叉子继续思考。
约束条件:
(1) 只有拿到两只筷子时,哲学家才能吃饭。
(2) 如果筷子已被别人拿走,则必须等别人吃完之后才能拿到筷子。
(3) 任一哲学家在自己未拿到两只筷子吃饭前,不会放下手中拿到的筷子。
(4) 用完之后将筷子返回原处。
分析:筷子是临界资源,每次只被一个哲学家拿到,这是互斥关系。如果筷子被拿走,那么需要等待,这是同步关系。
在什么情况下 5 个哲学家全部吃不上饭?
考虑两种实现的方式,如下:
A、设置一个信号量表示一只筷子,有 5 只筷子,所以设置 5 个信号量,哲学家每次饥饿时先试图拿左边的筷子,再试图拿右边的筷子,拿不到则等待,拿到了就进餐,最后逐个放下筷子。这种情况可能会产生死锁,因为我们不知道进程何时切换(这也是很多 IPC 问题的根本原因),如果 5 个哲学家同时饥饿,同时试图拿起左边的筷子,也很幸运地都拿到了,那么他们拿右边的筷子的时候都会拿不到,而根据第三个约束条件,都不会放下筷子,这就产生了死锁。描述如下:
- void philosopher(int i)
- /*i:哲学家编号,从0 到4*/
- {
- while (TRUE) {
- think();
- /*哲学家正在思考*/
- take_fork(i);
- /*取左侧的筷子*/
- take_fork((i + 1) % N);
- /*取右侧筷子;%为取模运算*/
- eat();
- /*吃饭*/
- put_fork(i);
- /*把左侧筷子放回桌子*/
- put_fork((i + 1) % N);
- /*把右侧筷子放回桌子*/
- }
- }
B、规定在拿到左侧的筷子后,先检查右面的筷子是否可用。如果不可用,则先放下左侧筷子, 等一段时间再重复整个过程。
分析:当出现以下情形,在某一个瞬间,所有的哲学家都同时启动这个算法,拿起左侧的筷 子,而看到右侧筷子不可用,又都放下左侧筷子,等一会儿,又同时拿起左侧筷子…… 如此 这样永远重复下去。对于这种情况,所有的程序都在运行,但却无法取得进展,即出现饥饿, 所有的哲学家都吃不上饭。
描述一种没有人饿死(永远拿不到筷子)算法。
考虑了三种实现的方式(A、B、C):
A.原理:至多只允许四个哲学家同时进入房间进餐, 以保证至少有一个哲学家在任何情况下能够正常进餐, 最终总会释放出他所使用过的两支筷子, 从而可使更多的哲学家进餐。
以下将 room 作为信号量,只允许 4 个哲学家同时进入房间就餐,这样就能保证至少有一个哲学家可以就餐,而申请进入房间的哲学家进入 room 的等待队列,根据 FIFO 的原则,总会进入到房间就餐,因此不会 出现饿死和死锁的现象。
伪码:
- semaphore chopstick[5]={1,1,1,1,1}; //筷子信号量
- semaphore room=4;
- void philosopher(int i)
- {
- while(true)
- {
- think(); //思考
- wait(room); //请求进入房间进餐
- wait(chopstick[i]); //请求左手边的筷子
- wait(chopstick[(i+1)%5]); //请求右手边的筷子
- eat();
- signal(chopstick[(i+1)%5]); //释放右手边的筷子
- signal(chopstick[i]); //释放左手边的筷子
- signal(room); //退出房间释放信号量room
- }
- }
B.原理:仅当哲学家的左右两支筷子都可用时, 才允许他拿起筷子进餐。
方法 1:利用 AND 型信号量机制实现:在一个原语中,将一段代码同时需 要的多个临界资源,要么全部分配给它,要么一个都不分配,因此不会出现死锁的情形。当某些资源不够时阻塞调用进程; 由于等待队列的存在,使得对资源的请求满足 FIFO 的要求, 因此不会出现饥饿的情形。
伪码:
- semaphore chopstick[5]={1,1,1,1,1}; //筷子信号量
- void philosopher(int I)
- {
- while(true)
- {
- think(); //思考
- Swait(chopstick[(I+1)]%5,chopstick[I]); //同时获取左右筷子,是AND信号量
- eat(); //就餐
- Ssignal(chopstick[(I+1)]%5,chopstick[I]); //释放
- }
- }
方法 2:利用信号量的保护机制实现。通过信号量 mutex 对 eat()之前的取左侧和右侧筷 子的操作进行保护,使之成为一个原子操作,这样可以防止死锁的出现。
伪码:
- semaphore mutex = 1 ; //互斥信号量
- semaphore chopstick[5]={1,1,1,1,1};
- void philosopher(int I)
- {
- while(true)
- {
- think();
- wait(mutex); //进入互斥区
- wait(chopstick[(I+1)]%5); //获取右侧筷子
- wait(chopstick[I]); //获取左侧筷子
- signal(mutex); //离开互斥区
- eat();
- signal(chopstick[(I+1)]%5);
- signal(chopstick[I]);
- }
- }
C. 原理:规定奇数号的哲学家先拿起他左边的筷子, 然后再去拿他右边的筷子; 而偶数号 的哲学家则相反。按此规定, 将是 1,2 号哲学家竞争 1 号筷子, 3,4 号哲学家竞争 3 号筷子. 即五个哲学家都竞争奇数号筷子, 获得后, 再去竞争偶数号筷子, 最后总会有一个哲学家能获得两支筷子而进餐。而申请不到的哲学家进入阻塞等待队列,根 FIFO 原则,则先申请的哲学家会较先可以吃饭,因此不会出现饿死的哲学家。
伪码:
- semaphore chopstick[5]={1,1,1,1,1};
- void philosopher(int i)
- {
- while(true)
- {
- think();
- if(i%2 == 0) //偶数哲学家,先右后左。
- {
- wait (chopstick[ i + 1 ] mod 5) ;
- wait (chopstick[ i]) ;
- eat();
- signal (chopstick[ i + 1 ] mod 5) ;
- signal (chopstick[ i]) ;
- }
- Else //奇数哲学家,先左后右。
- {
- wait (chopstick[ i]) ;
- wait (chopstick[ i + 1 ] mod 5) ;
- eat();
- signal (chopstick[ i]) ;
- signal (chopstick[ i + 1 ] mod 5) ;
- }
- }
- }
解决哲学家进餐问题的一个 Java 描述:
- package com.kang;
- import java.util.Random;
- class Chopsticks {
- // 用 used[1]至 used[5]五个数组元素分别代表编号 1 至 5 的五支筷 子的状态
- // false 表示未被占用,true 表示已经被占用。 used[0]元素在本程序中未使用
- private boolean used[] = {
- true,
- false,
- false,
- false,
- false,
- false
- };
- // 拿起筷子的操作
- public synchronized void takeChopstick() {
- /* 取得该线程的名称并转化为整型,用此整数来判断该哲学家应该用哪两支筷子 */
- /* i 为左手边筷子编号,j 为右手边筷子编号 */
- String name = Thread.currentThread().getName();
- int i = Integer.parseInt(name);
- /*
- * 1~4 号哲学家使用的筷子编号是 i 和 i+1,5 号哲学家使用 的筷子编号是 5 和 1
- */
- int j = i == 5 ? 1 : i + 1;
- /* 将两边筷子的编号按奇偶顺序赋给 odd,even 两个变量 */
- int odd,
- even;
- if (i % 2 == 0) {
- even = i;
- odd = j;
- } else {
- odd = i;
- even = j;
- }
- /* 首先竞争奇数号筷子 */
- while (used[odd]) {
- try {
- wait();
- } catch(InterruptedException e) {}
- }
- used[odd] = true;
- /* 然后竞争偶数号筷子 */
- while (used[even]) {
- try {
- wait();
- } catch(InterruptedException e) {}
- }
- used[even] = true;
- }
- /* 放下筷子的操作 */
- public synchronized void putChopstick() {
- String name = Thread.currentThread().getName();
- int i = Integer.parseInt(name);
- int j = i == 5 ? 1 : i + 1;
- /*
- * 将相应筷子的标志置为 fasle 表示使用完毕, 并且通知其他等待线程来竞争
- */
- used[i] = false;
- used[j] = false;
- notifyAll();
- }
- }
- class Philosopher extends Thread {
- Random rand = new Random(); //用来进行随机延时
- Chopsticks chopsticks;
- public Philosopher(String name, Chopsticks chopsticks) {
- /* 在构造实例时将 name 参数传给 Thread 的构造函数作为线程的名称 */
- super(name);
- /* 所有哲学家线程共享同一个筷子类的实例 */
- this.chopsticks = chopsticks;
- }
- public void run() {
- /* 交替地思考、拿起筷子、进餐、放下筷子 */
- while (true) {
- thinking();
- chopsticks.takeChopstick();
- eating();
- chopsticks.putChopstick();
- }
- }
- public void thinking() {
- /* 显示字符串输出正在思考的哲学家,用线程休眠若干秒钟来模拟思考时间 */
- System.out.println("Philosopher " + Thread.currentThread().getName() + " is thinking.");
- try {
- Thread.sleep(1000 * rand.nextInt(5));
- } catch(InterruptedException e) {}
- }
- public void eating() {
- /* 显示字符串输出正在进餐的哲学家,并用线程休眠 若干 秒钟来模拟进餐时间 */
- System.out.println("Philosopher " + Thread.currentThread().getName() + " is eating.");
- try {
- Thread.sleep(1000 * rand.nextInt(5));
- } catch(InterruptedException e) {}
- }
- }
- public class Test {
- public static void main(String[] args) {
- {
- /* 产生筷子类的实例 chopsticks */
- Chopsticks chopsticks = new Chopsticks();
- /* 用筷子类的实例作为参数, 产生五个哲学家线程并启动 */
- /* 五个哲学家线程的名称为 1~5 */
- new Philosopher("1", chopsticks).start();
- new Philosopher("2", chopsticks).start();
- new Philosopher("3", chopsticks).start();
- new Philosopher("4", chopsticks).start();
- new Philosopher("5", chopsticks).start();
- }
- }
- }
读者一写者问题 (Courtois et al., 1971) 为数据库访问建立了一个模型。例如,设想一个飞机定票系统,其中有许多竞争的进程试图读写其中的数据。多个进程同时读是可以接受的,但如果一个进程正在写数据库、则所有的其他进程都不能访问数据库,即使读操作也不行。
我们来分析他们的关系,首先,这个问题没有明显的同步关系,因为在这个问题里,读和写并不要合作完成某些事情。但是是有互斥关系的,写者和写者,写者和读者是有互斥关系的,我们需要设置一个 mutex 来控制其访问,但是单纯一个信号量的话会出现读者和读者的互斥也出现了,因为我们可能有多个读者,所以我们设置一个变量 ReadCount 表示读者的数量,好,这个时候,对于 ReadCount 又要实现多个读者对他的互斥访问,所以还要设置一个 RC_mutex。这样就好了。然后是行为设计:
- void Reader() {
- while(1) {
- P(&RC_mutex);
- rc = rc + 1;
- if(rc == 1) P(&mutex); //如果是第一个读者,那么限制写者的访问
- V(&RC_mutex);
- //读数据
- P(&RC_mutex);
- rc = rc - 1;
- if(rc == 0) V(&mutex); //如果是最后一个读者,那么释放以供写者或读者访问
- V(&RC_mutex);
- }
- }
- void Writer() {
- while(1) {
- P(&mutex);
- //写数据
- V(&mutex);
- }
- }
这里给出 Java 描述:
- package com.kang;
- import java.util.concurrent.Semaphore;
- class Sign {
- static Semaphore db = new Semaphore(1); // 信号量:控制对数据库的访问
- static Semaphore mutex = new Semaphore(1); // 信号量:控制对临界区的访问
- static int rc = 0; // 记录正在读或者想要读的进程数
- }
- class Reader implements Runnable {
- public void run(){
- try {
- //互斥对rc的操作
- Sign.mutex.acquire();
- Sign.rc++; //又多了一个读线程
- if(Sign.rc==1) Sign.db.acquire(); //如果是第一个读进程开始读取DB,则请求一个许可,使得写进程无法操作 DB
- Sign.mutex.release();
- //无临界区控制,多个读线程都可以操作DB
- System.out.println("[R] "+Thread.currentThread().getName()+": read data....");
- Thread.sleep(100);
- //互斥对rc的操作
- Sign.mutex.acquire();
- Sign.rc--;
- if(Sign.rc==0) Sign.db.release(); //如果最后一个读进程读完了,则释放许可,让写进程有机会操作DB
- Sign.mutex.release();
- } catch (InterruptedException e) {
- e.printStackTrace();
- }
- }}
- class Writer implements Runnable {
- public void run() {
- try {
- // 与读操作互斥访问DB
- Sign.db.acquire();
- System.out.println("[W] " + Thread.currentThread().getName()
- + ": write data....");
- Thread.sleep(100);
- Sign.db.release();
- } catch (InterruptedException e) {
- e.printStackTrace();
- }
- }
- }
- public class Test {
- public static void main(String[] args) {
- new Thread(new Reader()).start();
- new Thread(new Reader()).start();
- new Thread(new Writer()).start();
- }
- }
其实,这个方法是有一定问题的,只要趁前面的读者还没读完的时候新一个读者进来,这样一直保持,那么写者会一直得不到机会,导致饿死。有一种解决方法就是在一个写者到达时,如果后面还有新的读者进来,那么先挂起那些读者,先执行写者,但是这样的话并发度和效率又会降到很低。
来源: http://blog.csdn.net/xiaokang123456kao/article/details/73773474