注：有没有大佬能帮忙看一下管程程序是否正确呀，多谢了~~

文章目录

• 1背景
• 2信号量（semaphore）
• • 概念
  • 2.1信号量数据类型
  • 2.2信号量操作
  • 2.3信号量实现代码
  • 2.4信号量使用
  • • 2.4.1信号量分类
    • 2.4.2信号量使用
    • • 1互斥访问：临界区互斥访问控制
      • 2条件同步：线程时间等待，等待条件是独立的互斥
    • 2.4.3生产者消费者问题
    • • 1有界缓冲区的生产者-消费者问题
      • 2问题分析
      • 3用信号量约束
      • 4实现
      • 5困难
• 3管程
• • 3.1原理
  • 3.2使用
  • 3.3组成
  • • 3.3.1Lock
    • 3.3.2条件变量（condition varible）
  • 3.4消费者生产者模型实现
• 4经典同步问题
• • 4.1哲学家就餐问题
  • • 问题描述
    • 思路
    • • 程序编写：
      • 思路优化：要不都拿，要不一把不拿
      • 程序编程方法
      • • 信号量
        • 管程
  • 4.2读者-写者问题
  • • 问题描述：
    • 思路
    • 方案一：信号量（写者优先不理解）
    • 方案二：管程
  • 4.3步骤

1背景

2信号量（semaphore）

概念

信号量是操作系统提供的一种协调共享资源访问的方法，表示系统资源的数量
软件同步是平等线程间的一种同步协商机制。
操作系统是管理者，地位高于进程

2.1信号量数据类型

• 一个整型（共享资源数目），两个原子操作
• P():申请资源使用，信号量减1，当sem<0，P操作进程需要睡眠，等待，否则继续。当sem>=0,P操作可以继续执行
• V():信号量加1，当sem<=0,当前有进程等在信号量上，唤醒一个等待的P

V：Verhoog P：Prolaag //荷兰语增加与减少

举例：2个站台的车站（对应两个资源的信号量）

2.2信号量操作

• 信号量是被保护的整数变量
• 初始化完成后，只能通过PV操作修改，操作系统保证PV操作是原子操作。
• P可能阻塞，V不会阻塞
• 公平性：假设是公平的，线程不会无限期阻塞在P操作，可以实现先进先服务（自旋锁不能，自旋锁是抢时间片）

2.3信号量实现代码

classSemaphore{int sem; WaitQueue q; (推荐FIFO)void P(){  //原子操作sem--;if(sem<0){//Add this thread t to qblock(q);}}void V(){  //原子操作++sem;if(sem<=0){//等待队列有线程等待执行，remove thread t from qwakeup(t);}}
}

2.4信号量使用

2.4.1信号量分类

1. 根据信号量数目
   二进制信号量：资源数目为0或1
   资源信号量：资源数目为任何非负值
   二者关系：二者等价
2. 根据信号量的使用
   互斥访问：临界区互斥访问控制
   条件同步：线程时间等待，等待条件是独立的互斥

2.4.2信号量使用

1互斥访问：临界区互斥访问控制

成对使用P和V操作，必须先P后V，P()保证互斥访问临界资源，V()保证使用后释放临界资源

mutex = new Semaphore(1);
mutex->P();
//临界区
mutex->V()

2条件同步：线程时间等待，等待条件是独立的互斥

condition = new Semaphore(0);
//thread B 执行完X，thread A才能执行N
//thread A //Mcondition->P();  //V未执行的话，sem 从0变为-1，P挂起.V已执行的话，sem 从1变为0，P执行。//N
//thread B//Xcondition->V(); //P未执行，sem 从0变1，表示有信号可以使用。P已执行，sem从-1变0，表示有信号等待，唤醒等待队列中线程t加入就绪队列。//Y

2.4.3生产者消费者问题

1有界缓冲区的生产者-消费者问题

• 一个或多个生产者在生成数据后放在一个缓冲区里
• 单个消费者从缓冲区取出数据处理
• 任何时刻只能有一个 生产者或消费者可访问缓冲区

2问题分析

• 任何时刻只能有一个线程操作缓冲区（互斥访问）
• 缓冲区空时，消费者必须等待生产者（条件同步）
• 缓冲区满时，生产者必须等待消费者（条件同步）

3用信号量约束

二进制信号量：mutex
资源信号量：fullBuffers
资源信号量：emptyBuffers

4实现

ps：感觉有点类似智能指针，可以类比一下

Class BoundedBuffer{mutex = new Semaphore(1);fullBuffers = new Semaphore(0);emptyBuffers = new Semaphore(n);//生产者消费者实现同步//生产者Deposit(c){//P判断和临界区不能交换，会死锁。emptyBuffers->P(); //空-1{mutex->P(); //临界区操作//Add c to the buffer；mutex->V();	}fullBuffers->V();	//满+1}//消费者Remove(c){fullBuffers->P(); //满-1{mutex->P(); //临界区操作//Remove c from buffer;mutex->V();}emptyBuffers->V(); //空+1}
}

5困难

1.读/开发代码困难

• 程序员需要能运用信号量机制

2.容易出错

• 使用信号量已经被另一个信号量占用
• 忘记释放信号量

3.不能避免死锁出现

3管程

改进信号量处理临界区时的麻烦，信号量PV操作困难，针对语言的并发机制。

3.1原理

管程：是一种用于多线程互斥访问共享资源的程序结构，是一个由过程、变量和数据结构组成的封装模块。

• 采用**面向对象（封装）**的方法，简化线程间的同步控制。
• 保证任一时刻只有一个线程执行管程代码
• 正在管程中的线程可临时放弃管程互斥访问，等待事件出现时恢复。

3.2使用

• 收集对象/模块中相关的共享数据
• 定义访问共享数据的方法

3.3组成

• 锁：控制管程代码的互斥访问
• 0或者多个条件变量：管理共享数据的并发访问，是进程无法执行时被阻塞
• 进入管程需要一个等待队列，进入临界区后，当进程中某个共享资源无法满足时，会挂到信号变量上，再释放lock。
  

3.3.1Lock

Lock::Acquire() //等待直到锁可用
Lock::Release() //释放锁，如果有等待队列存在线程，唤醒等待者

3.3.2条件变量（condition varible）

定义：是管程内部的等待机制，进入管程的线程因资源被占用而进入等待状态，每个条件变量表示一种等待原因，对应一个等待队列。
操作：

• wait()：将自己阻塞在条件变量等待队列中，解除管程的互斥访问，唤醒一个条件变量等待者或释放锁
• signal()：将条件变量等待队列中的一个线程唤醒，如果等待队列为空，则等同空操作

实现：

class condition{int numWaiting = 0; //等待队列中线程数目WaitQueue q;wait(lock){numWaiting++; //add this thread t to qrelease(lock); //释放锁，让当前生产者释放锁，其他线程执行schedule(); //选择下一个线程执行require(lock); //}signal(){if(numWaiting>0){//Remove a thread t from q;wakeup(t);//need mutex，放到就绪态numwaiting--;}}
}

管理条件变量的释放处理方式：（不理解）

• Hansen管程：当前执行线程优先（效率更高，真实OS/JAVA）
  

• Hoare管程：被阻塞线程优先（更容易证明确定性）
  

		//hansen写法，条件变量释放只是一个提示，需要重新检查条件，更高效while(count==n) notFull.wait(&lock);//hoare写法，条件变量释放同时表示放弃管程访问，释放后条件变量的状态可用if(count == n) notFull.wait(&lock);

3.4消费者生产者模型实现

• 管程锁不紧靠操作，信号量会紧靠操作。因为管程需要进入管程（临界区，而且每次只进入一个），才能使用管程的管理函数。

class condition{int numWaiting = 0; //等待队列中线程数目WaitQueue q;wait(lock){numWaiting++; //add this thread t to qrelease(lock); //当前生产者先释放锁，然后再睡眠，让其他线程执行schedule(); //选择下一个线程执行require(lock); //}signal(){if(numWaiting>0){//Remove a thread t from q;wakeup(t);//need mutex，放到就绪态numwaiting--;}}
}
//消费者生产者模型
class boundedbuffer{lock lock;int count; //记录buffer空闲情况，0为空，n为满condition notFull,notEmpty;//生产者Deposit(c){lock->Acquire();//进入临界区，如果buffer满，就去睡眠//hansen写法while(count==n) notFull.wait(&lock); //满了睡眠，在里面释放锁//hoare写法//if(count == n) notFull.wait(&lock);//add s to the buffercount++;notEmpty.signal();lock->Release();}//消费者Remove(c){lock->Acquire();while(count == 0) notEmpty.wait(&lock);//Remove c from buffer;count--;notFull.signal();  //消费了一个，可以再加一个进来，生产者被唤醒lock->Release();}
}

4经典同步问题

4.1哲学家就餐问题

问题描述

思路

1. data
2. 叉子数信号量=5

程序编写：

• 大家同时行动，五个人都拿左边，右边叉子拿不到

//出现死锁，大家同时行动，五个人都拿左边，右边叉子拿不到。
#define N 5
fork[N];
void philosopher(int i){while(1){think();take(fork[i]);take(fork[(i+1)%N]);eat();put(fork[i]);put(fork[(i+1)%N];}
}

• 改进，拿左边，判断右边叉子能不能拿到，能就拿，拿不到左边放回去，等待重复操作。
  大家同一步调，会同时执行，一起拿一起放，仍然不行

#define N 5
semaphore fork[N];
void philosopher(int i){while(1){think();take(fork[i]);if(take(fork[(i+1)%N])){take(fork[(i+1)%N]);eat();put(fork[i]);put(fork[(i+1)%N];}else{put(fork[i]);wait_some_time();}}
}

• 改成等随机时长，随机数取值导致有的哲学家可能会饥饿

#define N 5
semaphore fork[N];
void philosopher(int i){while(1){think();take(fork[i]);if(take(fork[(i+1)%N])){take(fork[(i+1)%N]);eat();put(fork[i]);put(fork[(i+1)%N];}else{put(fork[i]);wait_random_time();}}
}

• 把拿叉子过程互斥保护起来,不会死锁，但是每次只有一个进餐，造成资源浪费

#define N 5
fork[N];
semaphore mutex;
void philosopher(int i){while(1){think();P(mutex);take(fork[i]);take(fork[(i+1)%N]);eat();put(fork[i]);put(fork[(i+1)%N];V(mutex);}
}

思路优化：要不都拿，要不一把不拿

不能浪费CPU时间，进程间相互通信

哲学家操作：

1. 思考
2. 饥饿时，如果左右邻居在吃饭，等待。否则拿起两把叉子。
3. 吃
4. 吃完放下叉子。看左右是否在饥饿状态，在就唤醒左右。
5. 重复思考

程序编程方法

1. 必须有数据结构描述哲学家状态
2. 状态是一个临界资源，访问应该互斥进行
3. 进程之间存在同步关系

信号量

//哲学家状态
#define N 5
#define LEFT (i+N-1)%N //左叉子和哲学家一个号
#define RIGHT (i+1)%5 
#define THINKING 0
#define HUNGRY 1
#define EATING 2
int state[N];
//临界状态，访问互斥进行,其他哲学家也需要访问哲学家状态
semaphore mutex //互斥信号量，初值1
//唤醒同步关系,就餐同步关系，可以就餐->就餐->就餐结束
semaphore s[N]; //同步信号量，初值0//
void philosopher(int i){while(true){think();take_forks(i);eat();put_forks(i);}
}void take_forks(int i){P(mutex);state[i] = HUNGRY;test_take_left_right_forks(i);V(mutex);P(s[i]); //看V
}void test_take_left_right_forks(inr i){if(state[i]==HUNGRY&&state[LEFT]!=EATING&&state[RIGHT]!=EATING){state[i] == EATING;V(s[i]); //唤醒第i个人吃操作，同步信号量}
}void put_forks(int i){P(mutex);state[i] = THINKING;test_take_left_right_forks(LEFT);test_take_left_right_forks(RIGHT);V(mutex);
}

管程

//自己编的不确定正确与否，等待校验

#define N 5
#define LEFT (i+N-1)%N //左叉子和哲学家一个号
#define RIGHT (i+1)%5 
#define THINKING 0
#define HUNGRY 1
#define EATING 2class condition{int status;void wait(Lock lock); //阻塞void signal(); //唤醒
};class database(){
private:Lock lock;Condition condition[N];	void take_forks(){lock.acquire();condition[i].status = HUNGRY;while(condition[LEFT].status==EATING||condition[RIGHT].status==EATING){condition[i].wait();}condition[i].status = EATING;lock.release();}void put_forks(){lock.acquire();condition[i].status = THINKING;if(condition[LEFT].status==HUNGRY){condition[LEFT].signal(); }if(condition[RIGHT].status==HUNGRY){condition[RIGHT].signal(); }lock.release();}public:void philosopher(){while(true){thinking();take_forks();eating();put_forks();}}};

4.2读者-写者问题

问题描述：

对共同数据访问与修改

• 读者可以读数据，写者可以读或者修改数据。
• 允许同一时间有多个读者，但任意时刻只能有一个写者。
• 没有写者时读者才能访问数据，没有读者写者时写者才能访问数据。
• 任何时刻只能有一个线程操作共享数据。

思路

多并发进程的数据集共享。
分为三类

1. 读者优先：给读者优先权，写者没有进行写操作，读者就可以访问。比如图书馆参考数据库。
2. 写者优先：读者延迟到所有就绪队列以及运行的写者都写完为止，读者运行时，写者要等读者读完后再写，不会堵塞读者，比如机票预订系统。
3. 读写公平（先来先服务）

伪码写法：

//写者：
//wait until no readers/writers;
write;
//check out-wakeup waiting readers/writers//读者：
//wait until no writers;
read;
//check out-wakeup waiting writers

方案一：信号量（写者优先不理解）

• 共享数据：rcount、data

//读者优先：读者可以跳过写者先执行，写者始终阻塞mutex countmutex(1); //1为互斥锁，读者计数锁，操纵rcount时需要上锁mutex writemutex(1);//写者写数据锁，向data写数据时上锁int rcount = 0;//写者,只有一个写者sem_P(writemutex); //写数据上锁write;sem_V(writemutex);//读者sem_P(countmutex) //读者计数锁，防止多个读者线程对rcount进行操作if(Rcount==0) //没有读者，加写锁，不让进行写操作sem_P(writemutex);++Rcount; //读者+1sem_V(countmetux);read; //读操作不需要加锁，因为可以多个读者进行读sem_P(countmutex)--Rcount; //读完，读者-1if(Rcount == 0) //读者为0，解写锁，可以进行写操作sem_V(writemutex);sem_V(countmutex);

• 共享数据：rcount
• 读者要等两种写者：一种是正在进行、一种是在就绪队列里
• 写者只等正在读的读者

//写者优先：mutex rcountmutex(1);mutex writemutex(1);mutex wcountmutex(1);mutex wmutex;int rcount = 0;int wcount = 0;//写者,只有一个写者sem_P(wcountmutex);if(wcount == 0)sem_P(rcountmutex)++wcount;sem_V(wcountmutex);sem_P(writemutex);write;sem_V(writemutex);sem_p(wcountmutex);--wcount;if(wcount == 0)sem_V(rcountmutex)sem_V(wcountmutex);//读者sem_P(wmutex);//实现写优先，wmutex临界区里一次只会进来一个读者访问计数sem_P(rcountmutex); //读者锁，防止多个读者线程对Rcount进行操作if(Rcount==0) //没有读者，加写锁，不让进行写操作sem_P(writemutex);//加读者计数锁++Rcount; //读者+1sem_V(rcountmetux);sem_V(wmutex);read;sem_P(rcountmutex)--Rcount; //读完，读者-1if(Rcount == 0) //读者为0，解写锁，可以进行写操作sem_V(writemutex);sem_V(rcountmutex);

方案二：管程

• 写者优先

2个状态，4个变量

class database{
private: //变量AR = 0; //正在读个数AW = 0; //写者个数WR = 0; //等待读者WW = 0; //等待写者Condition okToRead;  //同步操作Condition okToWrite; Lock lock; //进临界区互斥//读者，写者优先体现在WW>0void startread{lock.acquire();while(AW+WW>0){WR++;okToRead.wait(&lock);WR--;}AR++;lock.release();}void doneread(){lock.acquire();AR--;if(AR==0&&ww>0){okToWrite.signal();}lock.release();}//写者void startwrite(){lock.acquire();while(AR+AW>0){ //有读者或者有写者，进入等待队列wW++;okToWrite.wait(&lock);WW--;}AW++;lock.release();}void donewrite(){lock.acquire();AW--;if(WW>0){okToWrite.signal();}else if(WR>0){okToRead.broadcast();//所有reader都被唤醒		}lock.release();}public://读void Read(){startread();read;doneread();}//写void Write(){startwrite();write;donewrite();}};

• 读者优先
  注：似乎可以改进，AR和WR写在一起

class database{
private: //变量AR = 0; //正在读个数AW = 0; //写者个数WR = 0; //等待读者WW = 0; //等待写者Condition okToRead;  //同步操作Condition okToWrite; Lock lock; //进临界区互斥//读者，写者优先体现在WW>0void startread{lock.acquire();while(AW>0){ //有人写，暂停WR++;okToRead.wait(&lock);WR--;}AR++;lock.release();}void doneread(){lock.acquire();AR--;if(AR+WR>0){  //没人读，可写okToWrite.signal();}lock.release();}//写者void startwrite(){lock.acquire();while(AR+WR>0){ //有人读wW++;okToWrite.wait(&lock);WW--;}AW++;lock.release();}void donewrite(){lock.acquire();AW--;if(WR>0){  //有人等读okToRead.broadcast();//所有reader都被唤醒		}lock.release();}public://读void Read(){//读优先于写startread();read;doneread();}//写void Write(){startwrite();write;donewrite();}};

4.3步骤

1. 每个人的状态变化——伪代码
2. 找状态与共享资源等临界资源——确定锁数和临界区
3. 确定锁的用法——同步还是互斥，同步信号量为0，互斥信号量为1
4. 函数细化
5. 注意不出现死锁、低效、饥饿问题