清华操作系统：计算机后端感兴趣的相关知识本文调度算法

关于作者：博主是机器人专业的研究生，目前在读研究生。对计算机后端感兴趣，喜欢c++、go、python，目前熟悉c++、go语言、数据库、网络编程，了解分布式等相关内容\textcolor{orange}{博主是机器人专业的研究生，是目前是一名研究生。对计算机后端感兴趣，喜欢c++，go，python，目前熟悉c++，go语言，数据库，网络编程，了解分布式等相关内容}博主是机器人专业的研究生，目前在读研究生。对计算机后端感兴趣，喜欢c++、go、python，目前熟悉c++、go语言、数据库、网络编程，了解分布式等相关内容

个人主页：\textcolor{gray}{个人主页：}个人主页：傻鸟_coding

支持：\textcolor{gray}{支持：}支持：如果觉得博主的文章不错或者可以用，可以免费关注博主。支持三连就更好了\textcolor{ green}{如果觉得博主的文章不错或者可以用，可以免费关注博主，支持就更好三连合}如果觉得博主的文章不错或者可以用，可以免费关注博主c#生产消费者问题，支持三连就更好了，也就是给我最大的支持！ \textcolor{green}{是给我最大的支持！ }是给我最大的支持！

本文总结

本专栏主要讲解操作系统的相关知识。本文主要讲解semaphore和monitor流程

文章目录

清华操作系统系列文章：可采访可复习

1. 操作系统——概述

2.操作系统——中断、异常、系统调用

3.操作系统——物理内存管理

4. 操作系统 - 非连续内存分配

5.虚拟内存管理

6.操作系统——虚拟内存管理技术页面替换算法

7.流程管理

8.调度算法

9.同步和互斥

10. 信号量和监视器

11.死锁和进程通信

12.文件系统管理信号量和监视器

使用信号量和监视器解决同步和互斥问题

❓0. 最后的概念 同步 很难确保同步正确吗？

❓1. 信号量

❓2.信号量使用

一般信号量初始设置为整数，且为大于0的整数，这样进程进入临界区时不会阻塞

P()可以阻塞，V()不会阻塞

我们假设信号量是公平的

问题：信号量可以通过FIFO队列唤醒进程，锁在忙等待时可以通过FIFO队列唤醒进程吗？

信号量设置

信号量有两种使用方式

二进制信号量可以实现互斥操作

二进制信号量可以实现同步操作

首先执行进程A。当进程A执行时，O操作会减1。此时信号量会变为-1，进程A会被挂起，然后进程B会被执行。执行过程 B 时，V 运算为 +1。当信号量为0时，唤醒进程A

计算信号量

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

每个约束都有一个单独的信号量

❗️2.1生产者和消费者模型（第一个经典问题）消费者

如果生产者速度很快，缓冲区已满，则执行emptybuffer->P()，阻塞操作。这时消费者需要执行emptybuffer->V()操作，使缓冲区的值+1，当缓冲区未满时，通知休眠生产者

class BoundedBuffer{
		mutex = new Semaphore(1);         //互斥操作，初始值设置为1（当第一个执行时，值-1，为0.此时第二个需要等待第一个锁释放）
		fullBuffers = new Semaphore(0);   //说明缓冲区初始为空
 		emptyBuffers = new Semaphore(n);  //生产者可以往缓冲区填充n个数据
};
BoundedBuffer::Deposit(c){
		emptyBuffers->P();
		mutex->P();
		Add c to the buffer;
		mutex->V();
		fullBuffers->V();
}
BoundedBuffer::Remove(c){
		fullBuffers->P();
		mutex->P();
		Remove c from buffer;
		mutex->V();
		emptyBuffers->V();
}

P 和 V 操作的顺序重要吗？

对于交换生产者一开始的P操作，对程序有影响❓3.信号量的实现代码难以阅读和开发，容易出错并且无法处理死锁问题

与锁的区别：

❓4.监控

monitor进程最初用于语言完成同步和互斥操作（语言的并发操作），后来用于操作系统

一般方法

传说

进入监控进程的队列条目是互斥的。首先要做的是去锁，获取锁进入监控进程。如果无法获取锁，则必须进入该队列中由锁管理的临界区，线程才能进行监视器维护。一系列函数，操作函数，这些函数有很多共享变量，可以对共享变量进行操作。如果无法满足共享资源的共享变量，则需要等待并将自己挂载到条件变量上。同时释放锁，让等待锁的其他线程在条件变量上执行自己。条件变量的等待队列挂载所有线程，有条件x和y，当条件满足时，会调用对应的进程

wait：线程在条件变量中等待

信号：唤醒条件变量，使挂载在条件变量上的线程可以继续执行

条件变量Wait()操作Signal()操作（或broadcast()操作）

实施

class Condition{
		int numWaiting = 0;
		WaitQueue q;
};
Condition::Wait(lock){
		numWaiting++;             //执行wait操作就是睡眠了，表明多了一个睡在条件变量上的进程。
		Add this thread t to q;
		release(lock);    //让生产者释放锁，让其他的进程进入管程执行
		schedule(); //need mutex,选择下一个线程执行，本身这个进程已经属于睡眠状态了
		require(lock);
}
Condition::Signal(){
		if(numWaiting > 0){   //说明有进程处于等待状态，如果有的活从等待队列唤醒进程
				Remove a thread t from q;
				wakeup(t); //need mutex
				numWaiting--;
		}
}
wake up与 schedule对应，schedule是进程睡眠了，他会取一个就绪态进程继续执行，完成线程切换，wake up 将睡眠进程重新置成就绪态

值得注意的是，如果这个等待队列中没有进程，这个操作什么也不做

信号中，信号量的个数为0，（他的P和V操作肯定会进行加减运算）这里是等待等待进程的num个为0（在Wait中，会进行加法运算，并且信号不一定会减少操作）。

监视器解决生产者-消费者问题

注意：与信号量互斥不同，信号量互斥只是靠近缓冲区，而监视器互斥是放在程序的头部和尾部（由监视器的定义决定，线程进入pipe 只有一个线程可以访问monitor管理的所有功能，所以进入monitor时需要互斥）

class BoundedBuffer{
		Lock lock;
		int count = 0;  //buffer 为空
		Condition notFull, notEmpty;
};
BoundedBuffer::Deposit(c){
		lock->Acquire();    //管程的定义:只有一个线程能够进入管程
		while(count == n)
				notFull.Wait(&lock); //与信号量不一样，notfull是条件变量，不需要初始化，表示当前已经满了，需要睡眠，释放前面的锁（释放管程的lock，因为睡眠了，释放锁后，可以让其他的进程进入管程执行，睡眠之前一定要释放锁， 不然会导致所有后面等待的进程都无法进入管程）
		Add c to the buffer;
		count++;
		notEmpty.Signal();  //buffer空与buffer满是一样的
		lock->Release();
}
BoundedBuffer::Remove(c){
		lock->Acquire();
		while(count == 0)
				notEmpty.Wait(&lock);
		Remove c from buffer;
		count--;
		notFull.Signal();    //对应生产者的notfull Wait，notfull.Signal是唤醒机制，如果notfill Signal中有等待的线程，那么就会唤醒（首先count --, buffer满，经过-- 后，会不满，此时可以使用notfull Signal操作唤醒，它里面等待的进程）
		lock->Release();
}

问题：

两种解决方案

一旦发出信号操作，让等待线程执行，它自己休眠。发出信号的线程可以继续执行，直到等待线程完成释放。发出信号操作时，不是立即放弃CPUc#生产消费者问题，让等待线程执行，而是等到发出信号的线程执行释放，再将控制权交给等待线程执行。

同步结构如何有效地使用这些结构

开发并遵循严格的编程风格、策略❓5.经典同步问题❗️5.1 读写器问题（第二个经典问题）两类用户：有问题的约束：

当读者正在阅读，作者进入时，等待读者阅读完毕。类似地，当 writer 执行时，reader 和 writer 都必须等待。等待当前 writer 完成写入。

共享数据

读者第一，作者第一

5.1.1 使用monitor实现writer-first，reader-writer问题（之前使用semaphore方法的reader-writer问题）⭐️5.1.1.1 个代码

初始化

阅读器代码

编写器代码

总码

//writer
Database::Write(){
		Wait until readers/writers;
		write database;
		check out - wake up waiting readers/writers;
}
//reader
Database::Read(){
		Wait until no writers;
		read database;
		check out - wake up waiting writers;
}
//管程实现
AR = 0; // # of active readers
AW = 0; // # of active writers
WR = 0; // # of waiting readers
WW = 0; // # of waiting writers
Condition okToRead;
Condition okToWrite;
Lock lock;
//writer
Public Database::Write(){
		//Wait until no readers/writers;
		StartWrite();
		write database;
		//check out - wake up waiting readers/writers;
		DoneWrite();
}
Private Database::StartWrite(){
		lock.Acquire();
		while((AW + AR) > 0){    //如果临界区里面的读者或者写者正在进行操作，那么写者等待(体现写者优先)
				WW++;
				okToWrite.wait(&lock);
				WW--;		
		}
		AW++;
		lock.Release();
}
Private Database::DoneWrite(){
		lock.Acquire();
		AW--;
		if(WW > 0){
				okToWrite.signal();
		}
		else if(WR > 0){
				okToRead.broadcast(); //唤醒所有reader,可能等待的没有写者，只有读者，就把读者全部唤醒，提高效率
		}
		lock.Release();
}
//reader
Public Database::Read(){
		//Wait until no writers;
		StartRead();
		read database;
		//check out - wake up waiting writers;
		DoneRead();
}
Private Database::StartRead(){
		lock.Acquire();
		while(AW + WW > 0){    //关注等待的writer,体现出写者优先
				WR++;
				okToRead.wait(&lock);
				WR--;
		}
		AR++;
		lock.Release();
}
private Database::DoneRead(){
		lock.Acquire();
		AR--;
		if(AR == 0 && WW > 0){  //只有读者全部没有了,才需要唤醒
				okToWrite.signal();
		}
		lock.Release();
}

❗️5.2餐饮哲学家问题（第三个经典问题）

思考一：

思考 2：

思考 3：

5.2.1个代码（用信号量实现，也可以用监视器+条件变量实现）

'用数据结构，来描述每个哲学家的当前状态'
#define N 5                  //哲学家个数
#define LEFT (i + N - 1) % N //第i个哲学家的左邻居
#define RIGHT (i + 1) % N    //第i个哲学家的右邻居
#define THINKING 0           //思考状态
#define HUNGRY   1           //饥饿状态
#define EATING   2           //进餐状态
typedef int semaphore;  
int state[N];                // 跟踪每个哲学家的状态
'该状态是一个临界资源，对它的访问应该互斥地进行'
semaphore mutex = 1;         // 临界区的互斥，临界区是 state 数组，对其修改需要互斥
'一个哲学家吃饱后，唤醒临界，存在同步关系'
semaphore s[N];              // 每个哲学家一个信号量(哲学家进行通信，看是否阻塞还是运行)
void philosopher(int i) {    //i的取指：0到N-1
    while(TRUE) {
        think(i);            //S1
        take_forks(i);       //S2-S4（拿到俩把叉子或被阻塞）
        eat(i);              //S5（吃面条）
        put_forks(i);        //S6-S7（把俩把叉子放回到原处）
    }
}
'要么拿到俩把叉子，要么被阻塞起来'
void take_forks(int i) {
    P(mutex);                  //hunger是需要保护的，这是写操作
    state[i] = HUNGRY;         //第i个哲学家，饿了！
    test_take_left_right_forks(i);//试图拿俩把叉子
    V(mutex);
    P(s[i]); // 只有收到通知之后才可以开始吃，否则会一直等下去（没有叉子便阻塞）
}
'把俩把叉子放回原处，并在需要的时候，去唤醒左邻右舍'
void put_forks(i) {
    P(mutex);                         //进入临界区
    state[i] = THINKING;              //思考状态，意味着把俩把叉子放回去
    test_take_left_right_forks(LEFT); // 尝试通知左右邻居，自己吃完了，你们可以开始吃了——看左邻居能否进餐
    test_take_left_right_forks(RIGHT); //看右邻居能否进餐（之前参数i是指的自身，看自身能不能进餐）
    V(mutex);                        //与take_forks的P[s[i]]是一对的，当这里执行了V操作后，P操作才不会阻塞（我先判断左/右邻居能不能拿到俩把叉子进餐，如果可以的话，执行V操作，在执行P操作就不会阻塞，如果不执行V操作，说明它拿不到叉子此时P操作需要一直等等待）
}
void think(int i){
	P(&mutex);
    state[i] = THINKING;
    V(&mutex);
}
void eat(int i) {
    P(&mutex);
    state[i] = EATING;
    V(&mutex);
}
// 检查两个邻居是否都没有用餐，如果是的话，就 V(s[i])，使得 P(s[i]) 能够得到通知并继续执行
void  test_take_left_right_forks(int i) {         
    if(state[i] == HUNGRY && state[LEFT] != EATING && state[RIGHT] !=EATING) {
        state[i] = EATING;         //俩把叉子到手(只要处于eat状态，证明俩把叉子到手)
'拿到俩把叉子，且通知自己可以吃饭了'
        V(s[i]);                   //通知第i人可以吃饭了,s[i]的初值为0（V操作后s[i]的值变为1），我自己可以吃饭（对自身状态做了设置），使得后面做P操作的时候不会阻塞。
    }
}

**总结**：