操作系统笔记（王道考研） 第二章：进程管理（2）

大部分内容基于中国大学MOOC的2021考研数据结构课程所做的笔记，后续又根据2023年考研的大纲增加了一些内容，主要有操作系统引导、虚拟机、多级队列调度算法、互斥锁、调度器和闲逛进程、内存映射文件、文件系统的全局结构、虚拟文件系统、固态硬盘SSD、输入输出应用程序接口 、驱动程序接口等等。

感谢我的室友HXN，他帮我写了一部分第五章的内容。

课程内容和西电平时讲课的内容大致重合，西电可能每章会多讲一点UNIX系统的实例，可以听完这课再快速过一遍老师的课件防止漏掉什么内容。

这门课讲的其实不算特别硬核，没怎么涉及具体的代码。不过我其实感觉操作系统是个大无底洞，能学到多深基本取决于愿意花多少时间和精力。如果有闲心，推荐看下南大蒋炎岩老师的《操作系统：设计与实现》和哈工大李治军老师的《操作系统》，讲的更深入，当然难度也相应的大的多。

 

其他各章节的链接如下：

操作系统笔记（王道考研） 第一章：计算机系统概述

操作系统笔记（王道考研） 第二章：进程管理（1）

操作系统笔记（王道考研） 第二章：进程管理（2）

操作系统笔记（王道考研） 第三章：内存管理

操作系统笔记（王道考研） 第四章：文件管理

操作系统笔记（王道考研） 第五章：输入输出（I/O）管理

其他各科笔记汇总

进程同步，进程互斥

“同时”指的是宏观上的同时，微观上可能这些进程是交替地在访问这些共享资源的

 

忙等待：这个进程暂时没办法往下推进了，但是这个进程还一直占用着处理机，使处理机一直处于忙碌的状态，没有办法给别的进程进行服务

 

进程互斥的软件实现方式

单标志法

双标志先检查法

双标志后检查法

Peterson 算法

Swap指令

 

之前学习的那些进程互斥的解决方案分别存在哪些问题/p>

进程互斥的四种软件实现方式（单标志法，双标志先检查，双标志后检查，Peterson算法）

进程互斥的三种硬件实现方式（中断屏蔽方法，TS/TSL指令，Swap/XCHG指令）

1.在双标志先检查法中，进去区的”检查“，”上锁“操作无法一气呵成，中间有可能先执行了检查就进行了进程切换，从而导致了两个进程有可能同时进入临界区的问题；

2.所有的解决方案都无法实现”让权等待“

其中单标志法，双标志先检查，双标志后检查都存在着比较严重的一些问题的隐患。Peterson算法还有后面的三种硬件实现方式其实问题都不大，但是这些方式也都无法解决”让权等待“原则

 

1965年，荷兰学者Dijkstra提出了一种有效的实现进程互斥，同步的方法 —— 信号量机制

信号量机制

用原语来实现“检查”和“上锁”，避免了双标志先检查法那种两个进程同时进入临界区的问题

如果一个进程暂时进不了临界区，它会一直占用处理机循环检查从而导致忙等

信号量机制 —— 记录型信号

可以把信号量的初始值设置为2，刚开始等待这个打印机资源的等待队列肯定是空的（null）。各个进程在使用打印机之前需要先用wait原语来申请打印机资源，在使用完之后又需要执行signal原语来释放一个打印机资源

对这个例子的具体讲解略过不记，应该不难理解，不懂自己去看下视频

S.value+1后>0说明已没有进程在等待该资源

S.value=0，资源恰好分配完

 

一个信号量对应一种资源

信号量的值 = 这种资源的剩余数量（信号量的值如果小于0，说明此时有进程在等待这种资源）

 

P(S) —— 申请一个资源S，如果资源不够进程就执行block原语主动阻塞等待

V(S) —— 释放一个资源S，如果有进程在等待该资源，则用wakeup原语唤醒一个正在等待的阻塞进程

信号量机制实现进程互斥

在这个前驱图当中包含了很多对的进程同步关系，每一条线其实就是代表一个一前一后的同步问题

 

生产者消费者问题

缓冲区是用来存放数据的一片区域。大小为n表示有n个小格子，可以放n个产品

如果各个进程同时访问缓冲区的话有可能会出现一系列的问题，比如说数据覆盖

 

通过以上分析找出了这个问题里面所隐含的一系列同步和互斥关系

问题分析

根据各进程的操作流程确定P，V操作的大致顺序：前V后P

只有当缓冲区里有产品的时候，消费者进程才可以消费；只有缓冲区没满的时候，生产者进程才可以生产。这样的两对一前一后的同步关系，需要给它们分别设置一个同步信号量，并且在前面这个动作完成之后需要对这个同步信号量执行一个V操作，在后面这个动作开始之前需要对这个同步信号量执行一个P操作

对缓冲区临界资源的互斥访问只需要设置一个互斥信号量，并且让它的初值为1然后在临界区的前后分别对互斥信号量执行PV操作就可以了

如何实现

生产者生产一个产品和消费者使用一个产品是否可以放到PV操作之间/p>

逻辑上可以放到PV操作这里边，但是如果我们把这两部分的处理都放到PV操作里边就会导致临界区代码变得更长，也就是说一个进程对临界区上锁的时间会增长，这样肯定不利于各个进程交替地使用临界区资源

 

多生产者-多消费者问题

把进程同步问题理解为某一个事件一定要求发生在另一个事件之前，而不是某一个进程的行为要发生在另一个进程的行为之前

问题描述

关系分析。找出题目中描述的各个进程，分析它们之间的同步，互斥关系。

实现互斥很简单，无非就是在访问临界资源之前和访问临界资源之后分别对互斥变量实行一个P操作和一个V操作

而实现同步关系，只需要遵循前V后P原则。也就是前面的这个事件发生了之后需要执行一个V操作，而后面的这个事件发生之前需要执行一个P操作

如何实现

分析：刚开始，儿子女儿进程即使上处理机运行也会被阻塞（apple和orange这两个信号量的数量都为0）。如果刚开始是父亲进程先上处理机运行，则：

父亲P(plate)，可以访问盘子 → to →母亲P(plate)，阻塞等待盘子 → to →父亲放入苹果V(apple)，女儿进程被唤醒，其他进程即使运行也都会被阻塞，暂时不可能访问临界资源（盘子） → to →女儿P(apple)，访问盘子，V(plate)，等待盘子的母亲进程被唤醒 → to →母亲进程访问盘子（其他进程暂时都无法进入临界区） → to →…

结论：即使不设置专门的互斥变量mutex，也不会出现多个进程同时访问盘子的现象

原因在于：本题中的缓冲区大小为1，在任何时刻，apple，orange，plate三个同步信号量中最多只有一个是1。而这几个进程刚开始都需要对其中的某一个信号量执行P操作，因此在任何时刻，最多只有一个进程的P操作不会被阻塞，并顺利地进入临界区

 

如果盘子（缓冲区）容量为2

“每次随机地让一个吸烟者吸烟”：可设置一个random随机数变量

前驱事件：这个事件发生了之后，另一个事件才可以发生

问题描述

由于供应者进程每次只能往桌子上放一种材料的组合，所以可以把桌子看作是一种容量为1初始为空的缓冲区，而对缓冲区的访问需要互斥地进行

为什么说它的容量为1呢是说桌子上每次会放两种材料吗/p>

这个题目当中不能把两种材料看作是两种独立的物品，我们应该把它看作是一种组合。比如说把“纸+胶水”的组合看作一个整体称为组合一，组合一是抽烟者一需要使用的。不应该说这个桌子上可以同时放两种材料，而应该说这个桌子上同一时刻只能放其中某一种组合

只有“桌子上有组合一”这个事件发生的时候，才可以发生“第一个抽烟者取走东西”这个事件，其他同理。对于这三对一前一后的这种同步关系来说，我们需要对这些关系各自设置一个同步变量

设置一个整型变量 i i i，并且让其按照0，1，2，0，1，2，…这样的顺序循环地改变其值，这样就实现了“轮流让各个吸烟者吸烟”这个需求

当供应者在桌上放入了某一种组合之后，它需要对这个组合对应的同步信号量执行一个V操作用来通知等待这种组合的吸烟者。另外供应者把材料放到桌上之后需要等待吸烟者向他发出完成吸烟的信号，所以在这个地方我们又需要执行P(finish)

而各个吸烟者在从桌子上拿走材料之前，需要检查此时桌子上放的是不是自己所需要的材料。当把这些材料拿走并且卷烟抽掉之后，又需要向供应者发出一个完成信号来通知供应者可以开始放下一个材料了

 

读者-写者问题

当一个写者进程正在对文件进行写操作的时候，其他进程是不能访问这个文件的。或者说当一个写进程想要写这个共享文件的时候，它必须先等到其他进程对这个文件的操作结束之后

问题分析

 

为了解决“潜在的问题”，可以再设置一个互斥信号量w

问题描述

但是这么做的问题在于假如说此时是5个哲学家都并发地执行“吃饭”，第一个哲学家拿起它左边的筷子之后，又切换回第二个哲学家也拿起左边的筷子，接下来又切换回第三个哲学家也拿起左边的筷子…当每个哲学家在尝试拿自己右边的筷子时会发现自己右边的筷子已经被别人占用，所以所有的哲学家进程都会被阻塞，它们会循环地等待自己右边的那个人放下自己想要的那只筷子，出现“死锁”现象。每一个哲学家进程都阻塞地互相等待对方来释放资源但是又不主动释放自己手里的资源，导致所有的哲学家进程都无法往下推进。所以这种解决方案是不合理的

 

为什么要引入管程

局部于管程的共享数据结构说明：生产者消费者问题当中，生产者和消费者都需要共享访问的那个缓冲区可以用一种数据结构来表示，对缓冲区进行管理。所以在管程当中需要定义一种和这种共享资源相对应的共享数据结构

对局部于管程的共享数据结构设置初始值的语句：对这个数据结构要进行初始化的一些语句也需要在管程当中说明

局部于管程的数据只能被局部于管程的过程所访问，一个进程只有通过调用管程内的过程才能进入管程访问共享数据：管程当中定义的这些共享的数据结构只能被管程当中定义的这些函数所修改，所以如果我们想要修改管程当中的这些共享数据结构只能通过调用管程提供的这些函数来间接地修改

每次仅允许一个进程在管程内执行某个内部过程：管程当中虽然定义了许多函数，但是同一时刻肯定只有一个进程在使用管程当中的某一个函数，每一次对共享数据结构的访问肯定只有一个进程正在进行

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

此处并没有按照某一种严格的语法规则来进行表述，只是为了方便理解所以用了类C语言的伪代码来表示管程当中的这一系列逻辑

可以用程序设计语言当中提供的某一种特殊的语法，比如说monitor, end monitor这样一对关键字来定义一个管程，中间的部分是管程的内容，管程的名字叫ProducerConsumer

另外可以定义一些条件变量来实现同步，还可以定义一些普通变量用来表示我们想要记录的信息，比如缓冲区中的产品数

除此之外还需要定义对缓冲区进行描述的一些数据结构，只不过为了方便，这里就省去了

生产者进程想要往缓冲区里放入一个新生产的产品可以直接调用管程当中定义的insert函数，同样消费者进程也可以调用管程当中定义的remove函数实现从缓冲区当中取出一个产品，而从缓冲区当中取出一个产品时缓冲区空了怎么办，还有对缓冲区的互斥怎么办这些消费者进程都不需要关心，剩下的都是管程会负责解决的问题

来源：CS_Lee_