第一章

概念

控制和管理整个计算机系统的硬件和软件资源，并且合理的组织调度计算机的工作和资源的分配，以提供给用户和其他软件方便的接口和环境，是计算机系统中最基本的系统软件。

功能与目标

进程管理、存储管理、设备管理、文件管理、网络通信与服务、安全与保护

程序接口

• 命令接口

  • 联机命令接口 win+r（交互式命令接口）

  • 脱机命令接口

  • 批处理的命令接口

• 程序接口

• 图形用户界面（GUI） 只需要形象的图形操作，不用记忆复杂的系统指令。

操作系统四个特征

• 并发：宏观上同时发生，微观上交替发生；并行：宏观和微观都是同一时刻发生的。

  操作系统的并发性指的是计算机中有多个正在执行的程序。一个单核处理机同一时刻只能执行一个程序。操作系统会协调他们交替执行。当今计算机大部分是多核CPU，虽然看起来可以处理很多进程，但是还是不够进程足以让我们快乐使用，所有操作系统的并发性是必不可少的。

• 共享：系统中的资源可以供给内存中多个并发执行的进程共同使用。

  • 互斥共享：一个时间段只允许一个进程访问这个资源（摄像头、打印机）

  • 同时共享：允许“同时”使用 ( QQ 发送文件A，微信发送文件B。看上去是同时执行，实际上他们是交替着访问硬盘资源的）

    • 并发和共享的关系：如果系统失去了并发性，一个时间段只有一个进程，那么共享性就失去了意义。如果失去共享性，一个资源不能被两个进程访问，那么并发性也无法实现。

  • 虚拟：程序执行需要放入内存并且分配CPU才能执行。看起来我们正在使用的进程很大，实际上存在着虚拟存储技术。空分复用技术。

    比如说，单核CPU可以运行多个程序。处理机交替为各个进程服务。时分复用技术。（如果没有并发性，时分复用和空分复用技术也无意义）

  • 异步性：操作系统允许多个程序并发执行，但是不能贯彻到底，是走走停停的，以不可预知的速度推进。（没有并发性那么异步性也没啥意义）

发展与分类

1. 手工操作阶段：计算机处理速度快，输入输出慢
2. 单道批处理系统：脱机输入输出，监督程序（操作系统雏形）同一时刻只能有一道程序，只能串行执行。
3. 多道批处理系统：每次往内存中输入多道程序，引入中断技术，各个程序并发执行。操作系统正式诞生。共享计算机资源。没有人机交互。中间不能控制作业执行。效率大大提高了。
4. 分时操作系统：计算机以时间片为单位为各个用户服务，解决了人机交互问题。循环的为各个用户服务，完全公平的。没有优先级。
5. 实时操作系统：能够优先响应一些紧急的任务，要在严格的时间以内完成任务。及时性和可靠性。
6. 其他操作系统：网络操作系统、分布式操作系统、个人计算机操作系统

运行机制和体系结构

• 运行机制
  • 机器语言指令，一行代码可以对应很多个指令，指令是CPU能识别的最基本的操作。要限制用户对危险指令的使用。分为特权指令和非特权指令。两种处理器状态：用户态和核心态。用 PSW 来标志其状态。内核程序和普通程序。内核程序在和心态，可以执行特权指令和非特权指令。普通程序只能执行非特权指令，且在用户态。哪些是内核程序呢？
• 内核
  • 操作系统最接近硬件的是内核。时钟处理、中断处理。原语。运行具有原子性。要么不执行，要么执行了不能被中断。内核是计算机上面配置的底层软件，最基本最核心的部分。实现操作系统内核功能的那些程序就是内核程序。
  • 与硬件系统关系很紧密的：时钟管理（计时功能）、中断处理（中断机制）、原语（特殊程序，原子性，运行时间短，调用频繁)
• 体系结构
  • 大内核和微内核
  • 大内核就是操作系统的主要功能模块，运行在核心态。代码庞大。
  • 微内核只有基本的功能。代码小，性能低。
  • 大内核包括微内核。

中断和异常

• 早期的计算机只能串行执行程序，等待IO操作才能进入和离开程序，资源利用率低。操作系统作为计算机管理者，发生中断意味着操作系统介入，开展管理工作。比如一个程序正在运行，CPU收到计时部件发出的中断信号，切换为核心态，操作系统开始对中断信号处理。进程1的时间片已经用完，换进程2运行。

• 当中断发生时，CPU进入核心态。中断发生后，当前运行的程序会暂停，并且 由操作系统内核对中断进行处理。发生了中断，意味着操作系统就要介入。需要使用特权指令。所有CPU从用户态切换为核心态。有了中断，所以可以多道程序并发执行。

• 用户态到核心态->中断机制

• 区分用户态和核心态：PSW

• 内中断外中断：内中断（异常）信号来源是CPU内部，与当前的指令有关。外中断的信号来源是CPU外部，与当前执行的指令无关。

• 外中断比如I/O操作和人工干预。

• 外中断过程：

  • 执行完每条指令之后，CPU要检查当前是否有外部中断信号
  • 如果检测到外部中断信号，要保护被中断进程的CPU环境
  • 根据中断信号类型转入相应的中断处理程序
  • 恢复原来进程的CPU环境并且退出中断，返回原来的程序并且往下执行。

系统调用

• 操作系统需要为用户提供服务。命令接口面向用户，程序接口面向应用。（由系统调用组成）
• 应用程序通过系统调用向操作系统请求服务，凡是和资源相关的请求（I/O操作、存储分配、文件管理）通过系统调用的方式和操作系统发出请求。由操作系统代为完成。保证系统的稳定性
• 系统调用：
  • 设备管理
  • 文件管理
  • 进程控制
  • 进程通信
  • 内存管理
• 库函数：应用程序可以通过汇编语言使用系统调用，但是现在软件都是高级语言，使用高级语言提供的库函数，库函数也是封装在系统调用里面。不需要那么复杂的方式。
• 编程语言向上提供库函数，间接使用操作系统的系统调用。不是所有库函数使用系统调用功能（取绝对值)
• 库函数内部封装了系统调用内部好多细节。
• 系统调用会使得CPU从用户态转入核心态。
• 凡是与资源相关的操作，会影响其他进程的操作，要加入操作系统。系统调用。

第二章

进程定义

1. 程序：指令序列。程序的代码放在程序段，还有数据段。程序段和数据段都放入内存中。多道程序技术中，内存中有很多程序段和数据段，要记录程序段的位置和要使用的IO设备。要用PCB存放描述进程的全部信息（程序代码存放的位置）创建进程创建PCB。
2. 进程是一个动态过程，运行的过程。PCB是进程的唯一标志。进程实体是静态的，进程是动态的。一般不区分。
3. 进程（进程实体）组成：程序段、数据段、PCB（操作系统用于管理的数据结构）
4. PCB：
   • 进程描述信息（进程标识符，用户标识符）
   • 进程控制和管理信息
   • 资源分配清单
   • 处理机相关信息-各种寄存器值（进程切换的时候保存在里面）
5. 进程当中有很多PCB，操作系统要对其组织管理。进程组织讨论的是多个进程之间的组织方式。链接方式和索引方式。
6. 链接方式：执行指针，执行队列，就绪队列，阻塞队列。执行指针指向一个进程PCB。就绪指针指向一个就绪队列，把优先级高的放在队头。索引方式就是改成索引表的方式。
7. 进程：动态性，并发性，独立性，异步性，结构性。进程是接受资源分配调度的基本单位。

进程的状态与转换

1. 三种基本状态：运行态、就绪态、阻塞态。

   另外两种状态：创建状态、终止状态

   • 运行态：占用CPU，并在CPU下运行。单核处理机每个时刻最多一个进程处于运行态。
   • 就绪态：已经具备运行条件，拥有除了处理机以外的所有资源。没有空闲的CPU。
   • 等待态：因等待某一件事情而不能运行。请求I/O操作之类，进程从运行态到阻塞态等待IO操作完成。
   • 创建态：新建进程，分配存放的空间，新建PCB。
   • 终止态：出现错误或者进程完成。要回收资源。内存区域也要回收，要删除PCB。

2. 进程状态的转换：

   • 创建态—>就绪态：系统完成了创建进程的一系列工作。

   • 就绪态—>运行态：进程被调度；

   • 运行态—>就绪态：时间片到或者处理机被抢夺；

   • 运行态—>阻塞态：进程用系统调用的方式申请某种资源，或者请求等待某个事件发生。运行态到阻塞态是进程自身做出的主动行为。

   • 阻塞态—>就绪态：申请的资源被分配，或者等待的事情得到了发生。

   • 不能从阻塞态到进行态，也不能从就绪态到阻塞态（因为进入阻塞态是被分配到处理机的进程的主动行为）

   • 运行态—>终止态：进程运行结束，或者运行过程中遇到了不可修复的错误。

进程控制

1. 进程控制的概念：对系统中的所有进程实施有效的管理。创建进程、撤销已有集成，实现进程转换

2. 进程从创建态到就绪态，修改PCB相应的内容，进入就绪队列；就绪态到运行态，恢复进程运行环境，修改PCB内容和相应队列；完成/异常结束，就会到终止态。运行态到阻塞态，要保存已经处理的结果，PCB放入阻塞队列；类似阻塞态到就绪态，放入就绪队列，分配除了处理机以外的资源。如果不及时修改状态，会导致系统错误。

3. 用原语实现进程控制，原语的特点是不允许中断。原语采用关中断指令和开中断指令实现。只能在核心态下面的特权指令。

4. 原语要做的事情：

   1. 更新PCB中的信息
   2. 将PCB插入合适的队列
   3. 分配/回收资源
   • 创建原语：
     • 申请空白PCB
     • 为新的进程分配资源
     • 初始化PCB
     • 将PCB 插入就绪队列
   • 撤销原语
     • 从PCB集合中找到终止进程的PCB
     • 立刻剥夺CPU，分配给其他进程
     • 终止子进程
     • 删除PCB
   • 阻塞原语
     • 找到要阻塞进程PCB
     • 保护进程运行现场
     • 插入等待队列
   • 唤醒原语
     • 在等待队列中找到PCB
     • 进程设置为就绪态，并且从等待队列移除
     • 将PCB插入就绪队列，等待被调度
   • 切换原语
     • 保存信息
     • 移入相应队列
     • 选择另一个进程，更新PCB

进程通信

进程通信指的是进程之间的信息传递，各个进程的内存地址空间相互独立，进程2的内存地址空间不能被另一个地址访问。直接访问太危险，但是必须实现这种信息之间的交换。下面是一些安全的办法。

• 共享存储

  两个进程之间有一个共享空间，这两个进程对于共享空间的访问必须是互斥的。使用操作系统的同步互斥工具，PV操作

• 消息传递

  格式化的消息。消息头，消息体。进程通过发送消息/接受消息两个原语实现数据交换。

  直接通信方式/间接（信箱）

• 管道通信

  管道是内存中开辟的一个缓冲区，管道只能实现单向的传输，如果要设置两个管道，那么就需要设置两个管道。两个进程互斥访问管道。用字符流的形式，没有写满就不允许阅读，没有读空就不允许写入。数据一旦被读出就会被抛弃。

线程

1. 在没有引入进程之前，系统中各个程序串行执行。进程是程序的一次执行，没有线程，不可能同时发生。有的进程要同时做很多事情，为此，引入了线程，来增加并发度。传统的进程是程序执行流的最小单位，引入线程之后，每个进程当中包括很多线程，CPU为线程服务，想要并发执行的话，就放在一个进程的不同线程之下。引入线程后，线程成为了程序执行的最小单位。
2. 线程是基本的CPU执行单元，也是程序执行流最小单位。进程不是调度单位，变成了系统资源的分配单元。增加并发度。
3. 传统的进程并发，需要切换进程运行的环境，系统开销很大。线程间并发，如果是同一进程内的线程切换，不需要切换进程环境，开销会减小。
4. 多核CPU，各个线程占用不同CPU。每个线程有线程ID,线程控制块TCB。也有就绪阻塞运行三种基本状态。系统资源在进程那里，同一进程的不同线程共享进程的系统资源，同一进程中线程通信不需要操作系统干预，共享内存地址空间。不同进程之间的线程，系统开销会很大。
5. 线程实现方式：用户级线程（应用程序，不需要操作系统的干预，调度的时候是不考虑的）、内核级线程在核心态完成，是操作系统内核完成的。
   1. 将n个用户及线程映射到m个内核级线程，操作系统只看得见内核级线程，内核级线程才是处理机分配的单位分配多少个核就只看内核级线程几个线程。
   2. 多线程模型：多对一（并发性不高），一对一（成本高），多对多（√）。

处理机调度

1. 调度的概念：按照某种规则处理；处理机调度：进程数量多于处理机数量，怎么分配处理机给进程。

2. 作业调度（高级调度）：由于内存空间不够，按一定的原则从后备队列挑选作业，给他们分配内存等资源，并建立相应的进程，使他们获得竞争处理机的权利。作业调度是内存与外存之间的调度，作业调入的时候会建立相应的PCB，作业调出的时候撤销PCB。每个作业只调入一次，调出一次。外存和内存之间，无->创建态->就绪态，面向作业。

3. 中级调度：操作系统会将暂时不能运行的内存调至外存，挂起状态。PCB还在内存当中。建立挂起队列，存放PCB。中级调度就是从挂起队列中选择进程放入内存。中级调度可以发生很多次。外存和内存之间，挂起态->就绪态、阻塞挂起->阻塞态

   七状态模型 挂起 阻塞挂起

4. 进程调度（低级调度）：按照某种方法或者策略从就绪队列当中选择一个进程，将处理机分配给他。是操作系统中最基本的一种调度，进程调度的频率很高。发生在内存和CPU之间。就绪态->运行态

进程调度

1. 就是按照某种算法从就绪队列选择。
2. 进程调度时机：进程正常终止或者发生异常终止或者发出IO请求进入阻塞，分给进程的时间片用完，有更加紧急的事情，优先级更高的进程进入就绪队列
3. 不能进程调度：中断处理、进程在操作系统内核临界区中、在原语操作中。
4. 进程调度方式：抢占式（对应正常终止的情况）和非抢占式（对应有更加紧急的事情的情况）
5. 进程切换就是一个进程让出处理及，让另一个进程占用处理机的过程；对原来数据保存，对新的进程数据恢复。进程切换是有代价的。**广义的进程调度包括了选择一个进程和进程切换两个过程。

调度算法

1. CPU利用率：cpu忙碌时间占总时间的比例。

2. 系统吞吐量：单位时间完成的作业数。

   某计算机系统处理完十道作业，共花费了1000秒，则系统吞吐量为

   10/1000=0.1道/秒

3. 周转时间：从提交（外存）到完成花了多少时间。

   作业在外存后备队列中等待作业调度的时间，进程在就绪队列等待进程调度的时间，进程在CPU执行的时间，进程等待IO操作的时间。

   平均周转时间=各作业周转时间和/作业数

   带权周转时间=作业周转时间/作业实际运行时间>=1

   平均带权周转时间=各个作业周转时间之和/作业数

   进程等待时间：作业刚刚提交是放在后备队列之中，作业被调度之后，放入内存之中，并且建立起相应的进程，等待时间指的是进程被建立之后等待被服务的时间。对于作业来说，

   作业等待时间：不仅要考虑建立进程之后的等待时间，还要考虑作业在后备队列中外存中的时间。周转时间-运行时间

   调度算法只会影响作业/进程的等待时间。

   响应时间：从提交请求到首次产生响应的时间。

调度算法——先来先服务、短作业优先、高响应比优先

1. FCFS——先来先服务

   按照作业/进程到达的先后顺序进行服务，用于作业调度的时候，考虑的是哪个作业先进入后备队列；用于进程调度时，考虑的是哪个进程先到达就绪队列。

   非抢占式算法

   优点和缺点：公平；但是对于排在长进程后面的短作业不利。

   不会出现饥饿现象

2. SJF——短作业优先，SPF——短进程优先

   最短的进程/作业优先调度

   每次选择已经到达而且运行时间最短的作业/进程

   非抢占式算法，但是SRTN——最短剩余时间优先是抢占式算法

   SRTN是抢占式；到达的新的进程的剩余时间如果比当前运行进程剩余时间更短的话，那么新的进程就会抢占处理机。

   优点和缺点：不公平，对长作业不利

   会出现饥饿现象

3. HRRN——高响应比优先算法

   选择响应比最高的

   响应比：（等待时间+要求服务时间）/要求服务时间

   非抢占式算法

   进程	到达时间	运行时间
   P1	0	7
   P2	2	4
   P3	4	1
   P4	5	4

   0时刻，只有P1到达就绪队列，P1上处理机；7时刻，放弃CPU，P234都到达了；P2=（5+4）/4=2.25;P3=(3+1)/1=4;P4=(2+4)/4=1.5。所以选P3。继续按照这种方式去计算······P1->P3->P2->P4。

   等待时间相同时候，要求服务时间短的优先；要求服务时间相同的时候，等待长的时间优先。对前面两个算法进行了结合。

   不会导致饥饿。

4. RR——时间片轮转调度算法

   按照进程到达就绪队列的顺序，轮流让各个进程执行一个时间片。若进程未在一个时间片里面处理完，则剥夺处理机，将进程重新放到就绪队列队尾重新排队。

   只能用于进程调度。处理机只有进程调度才有。

   抢占式算法

   如果时间片太大，会退化成先来先服务算法。因此时间片不能太大。时间片太小，进程切换过于频繁，消耗系统。

   不会导致饥饿

5. 优先级调度算法

   每个作业进程有一个优先级，调度的时候选择优先级最高的进程/作业。

   抢占/非抢占都有

   非抢占式只看已经到达的且优先级最高的算法，当前面的进程主动放弃处理机的时候才去调度。

   抢占式每次调度选择已经到达而且优先级最高的，调度有两种情况，一是前进程主动放弃处理机，二是就绪队列发生了改变。优先级一样高的时候看谁先进入就绪队列。

   还有动态优先级······

   灵活

   有可能饥饿

6. 综合前面的——多级反馈队列调度算法

   抢占式算法

   设计多级优先队列，各级队列优先级从高到低，时间片从小到大。

   设置多级就绪队列，各级队列优先级从高到低，时间片从小到大。

   新进程到达先进入一级队列，按照FCFS原则排队等待被分配时间片。若时间片用完进程还没有结束，那么进程进入下一级队尾。如果已经在最下级队列，那重新放回最下级队列队尾。

   只有第K级队列为空，才会为第K+1级进程分配时间片

   被抢占处理机的会放回原队列队尾。

进程同步、进程互斥

1. 进程同步：同步也叫做直接制约关系，指为了完成某个人物而建立的两个或者多个进程，这些进程因为需要在某些位置上协调它们的工作次序而产生的制约关系。进程间的直接制约关系就是源于它们之间的相互合作。

2. 进程互斥：各个并发的进程需要共享一些资源。互斥共享方式和同时共享方式；对于互斥共享方式，也就是一段时间只允许一个进程使用的资源称之为临界资源。对于临界资源的访问，必须要互斥的进行。互斥，简称间接制约关系。进程互斥指的是当一个进程访问某临界资源的时候，另一个想要访问临界资源的进程必须等待。当前访问临界资源的进程访问结束，释放掉该资源以后，另一个进程才能去访问临界资源。

3. 对临界资源的访问，分为以下四个部分：

   do{
   entry section;//进入工作区
   critical section;//临界区
   exit sectio;//退出区
   remainder section;//剩余区
   }while (true)
   

   进入区负责检查是否可以进入临界区，若可以进入，那么应该设置正在访问临界资源的标志（可理解为上锁），以阻止其他进程同时进入临界区。

   临界区是实际访问临界资源的代码。

   退出区是负责接触正在访问临界资源的标志（可理解为解锁）。

   剩余区做其他处理。进入区和互斥区负责的是互斥的代码。

   空闲让进 忙则等待 有限等待 让权等待

进程互斥的软件实现方法

• 单标志法

  • 两个进程交替使用临界区，一个进程访问完临界区以后会把权限给另一个进程。

    int turn=0;//turn表示当前允许进入临界区的进程号

    P0 进程： P1进程：

    while(turn!=0); while (turn!=1);

    critical section; critical section;

    turn =1; turn=0;

    remainder section; remainder section;

    turn初值为0，即刚开始是P0进入临界区。

    若P1先上处理机，会卡在while，直到时间片用完，发生调度，P0运行。

    P0可以正常访问临界区，在P0进入临界区的期间即时切换回P1，P1还是卡在while。

    一直到P0结束访问，到了退出区，turn修改为1，把进入临界区的权限给P1，P1才能进入临界区。

    P1再进入退出区，改变turn。把权限给P0。

    同一时刻，就只能一个进程进入临界区，实现了互斥

    对于临界区的访问一直是P0->P1->P0->P1······这样轮流访问，那么如果P0不访问临界区，P1就不能进入临界区。不能实现空闲让进。

• 双标志先检查

  • 设置一个布尔型数组flag[],数组中各个元素用来标记各个进程想进入临界区的意愿，比如flag[0]=ture 意味着0号进程要进入临界区。每个进程在进入临界区之前先检查当前有没有别的进程想进入临界区，如果没有，则把自身的标志flag[i]设置为ture，之后开始访问临界区。

    bool flag[2];//表示想要进入临界区的数组

    flag[0]=false;

    flag[1]=false;//刚开始两个进程都不想进入临界区

    P0进程： P1进程：

    while (flag[1]); ① while(flag[0]); ⑤ //检查别的进程想不想进入临界区

    flag[0]=true; ② flag[1]=true; ⑥ //标记自己想要进入临界区

    critical section; ③ critical section; ⑦

    flag[0]=false; ④ flag[0]=false; ⑧ //访问完临界区，修改标记表示自己不想进入临界区

    remainder section; remainder section;

    如果说按照15263748的顺序执行，那么P0和P1会同时进入临界区。违反了忙则等待原则

    原因在于，进入区的检查和上锁并不是一气呵成的，检查后，在上锁之前可能发生进程切换

    改成原子操作！

• 双标志后检查

  • 双标志先检查的改版

    bool flag[2];//表示想要进入临界区的数组

    flag[0]=false;

    flag[1]=false;//刚开始两个进程都不想进入临界区

    P0进程： P1进程：

    flag[0]=true; ① flag[1]=true; ⑤ //检查别的进程想不想进入临界区

    while(flag[1]); ② while (flag[0]) ; ⑥ //标记自己想要进入临界区

    critical section; ③ critical section; ⑦

    flag[0]=false; ④ flag[0]=false; ⑧ //访问完临界区，修改标记表示自己不想进入临界区

    remainder section; remainder section;

  • 先上锁后检查，按照1526，会一直循环检查，无法进入临界区，违背了空闲让进和有限等待，产生了饥饿的现象。

• PETERSON算法

  • 如果双方都争着想进入临界区，可以让进程试着孔融让梨，主动让对方进入临界区。

    bool flag[2];//表示进入临界区意愿的数组，初始都是false
    int turn=0;//turn表示优先让哪个进程进入临界区
    P0进程:
    flag[0]=true;
    turn=1;
    while(flag[1]&&turn==1);
    critical section;
    flag[0]=false;
    remainder section;
    P1进程:
    flag[1]=true;//表示自己想进入临界区
    turn=0;//表示愿意让对方先进入临界区
    while(flag[0]&&turn==0);//对方想进且是最后一次让梨子，那自己就循环等待咯
    critical section;
    flag[1]=false;//访问完了临界区，表示自己已经不想进入临界区了
    remainder section;
    

    自己试试两个进程交替，会发现算法没啥大问题。但是他还是不够好。

进程互斥的硬件实现方法

• 中断屏蔽方法
  • 利用开中断关中断指令实现，关中断以后不允许进程被中断，直到当前进程访问完毕临界区，再执行开中断指令，才有可能有别的指令上处理机并且访问临界区。
  • 不适用于用户态，只能运行在内核态。这种指令要用户使用很危险。
• TS指令
  • TSL指令是他另一个名字
  • 用硬件实现，给临界区上锁。*lock=true。
  • TSL指令类似双标志，但是他把上锁和检查弄成了一气呵成的效果，不存在他们那种进程切换的问题。也会导致“忙等”。
• Swap指令
  • exchange指令。

信号量互斥

• 在双标志先检查法中，进入区的检查与上锁无法一气呵成的完成，从而导致了两个进程同时进入临界区的情况。

• 硬件的办法无法实现让权等待。（当进程不能进入自己的临界区时，应立即释放处理机，以免进程陷入“忙等”状态。

• 所以，迪基斯特拉提出了信号量机制。

• 用户进程可以通过使用操作系统原语来对信号量进行操作，从而很方便的实现了进程互斥进程同步。信号量其实就是一个变量，可以用一个信号量来表示系统中某种资源的数量。比如，系统中只有一台打印机，那么就可以设置一个初值为1的信号量。

• 原语是一种特殊的程序段，其执行只能一气呵成不能中断。原语是由开中断关中断指令实现的。软件很多方法不好就是因为进入的时候不能一气呵成，如果能把进入退出都用原语来实现就好了。

  • P/V操作可以理解成我们自己写的函数。（wait原语：进入区和signal原语：退出区）

  • 记录型信号量

    • 整型信号量会导致忙等

    • 记录性信号量用记录性数据结构，某进程要申请资源，用wait，value值-1，有等待队列；如果剩余资源数不够，block操作；进程使用完毕以后，通过signal短语释放，使用wakeup原语唤醒等待队列中的一个进程，该进程从阻塞态变为就绪态。

      typedef struct semaphore{
      int value;//信号量值
      struct pcb* list;//阻塞进程队列指针
      };
      void P=(semahore &s){
      s.value--;
      if(s.value<0) block(s.list);//阻塞本进程并进入s信号量队列
      }
      void V(semaphore &s){
      s.value++;//++以后如果value<0，说明阻塞队列还有东西，有进程在等待资源。
      if(s.value<=0)	wakeup(s.list);//唤醒s信号量队列中的一个进程进入就绪队列
      }
      

    • 用来表示系统中某种资源的数量

    • P(S):将信号量的值-1，若结果小于0，那么调用P(S)进程被阻塞，并进入信号量s的阻塞队列；若结果大于0，那么调用P(S)的进程就继续运行

      V(S)：将信号量s的值+1，若结果不大于0，那么调用V(S)的进程从该信号量在阻塞队列中释放。、唤醒一个处于等待状态的进程，将其转换为就绪状态，调用V(S)的进程将继续运行，如果小于零那么调用的进程继续运行。

    • 对信号量S的一次P操作意味着进程请求一个单位的该类资源，因此需要执行S.VALUE--,表示资源数-1，当S.value<0时表示该类资源已经分配完毕，因此进程应当调用block原语进行自我阻塞（当前运行的进程从运行态->阻塞态），主动放弃处理机，并且插入该类资源的等待队列S.L中。可见，该机制遵循了“让权等待”原则，不会出现“忙等”现象。

    • 对信号量的一次V操作意味着进程释放一个单位的该类资源，因此需要执行S.value++，表示资源数+1，若+1以后仍然S.value<=0，表示依然有进程在等待该类资源，因此调用wakeup原语唤醒等待队列中的第一个进程（被唤醒进程从阻塞态->就绪态）

用信号量实现进程互斥、同步前驱关系

• 分析并发进程的关键活动，划定临界区。
• 设置互斥信号量mutex，初值为1。表示资源数量，临界区一段时间只能分配给一个进程，所以是1。
• 在临界区之前执行P操作。
• 在临界区之后执行V操作。
• 对于不同的临界资源需要设置不同的互斥信号量。

semaphore mutex=1；//要会自己定义记录型信号量，但如果题目中没用特别说明，可以声明成这种形式
cobegin
Process Pi()//i=1,2,3····N
{
P(mutex);
临界区
V(mutex);
}
coend;

• 代码的先后顺序无法预知，可能是交替进行的，信号量机制可以让代码按照我们想要的顺序执行。让本来异步并发的进程互相配合，有序推进。即必须保证一前一后执行的两个操作。

  • 设置同步信号量S，初值设置为0；
  • 在前操作之后执行V(S);
  • 在后操作之前执行P(S)；
  • 1->2->4······

  P1(){        P2(){
  代码1；       P(S);
  代码2；       代码4;
  V(S);        代码5;
  代码3;        代码6;
  }            }
  

• 有前驱关系的代码：要保证一前一后的操作；为每一对一前一后地操作设置一个同步变量；在前操作之后对相对应地同步变量执行V操作，在后操作之前对相应地同步变量执行P操作。（前V后P)

• 有多少资源就把系统资源信号量设置为几。

生产者消费者问题

系统中有一组生产者进程和一组消费者进程，生产者进程每次生产一个产品放入缓冲区，消费者进程每次从缓冲区取走一个产品并且使用。生产者和消费者共享一个初始为空、大小为n的缓冲区。

缓冲区满时，生产者必须等待；缓冲区空时，消费者必须等待。

缓冲区是临界资源，必须互斥访问。

1. 设置一个初值为1的互斥信号量

2. 设置一个初值为0 的同步信号量（实现一前一后操作）

3. 设置一个信号量，初始值即为资源的数量，若无空闲资源，那么申请资源的进程要等待别的进程释放资源。

   • 缓冲区是互斥访问的，一个互斥信号量。
   • 缓冲区满时，生产者要等待消费者取走商品。一前一后！
   • 缓冲区空时，消费者要等待生产者放入商品。一前一后！
   • 生产者消耗缓冲区，P操作；消费者消耗缓冲区，V操作。生产者生产一个产品，V操作；消费者消耗一个产品,P操作。
   • 设置信号量。互斥信号量（1）、同步信号量（empty、full）
   • 互斥的P操作一定要放在同步的P操作之后。
   • V操作不会导致进程阻塞，两个V操作可以交换。

   semaphore mutex=1;//互斥信号量，表示对缓冲区地互斥访问；
   semaphore empty=n;//同步信号量，表示空闲缓冲区数量；
   semaphore full=0;//同步信号量，表示产品数量，也就是非空缓冲区数量；
   producer(){
   while(1){
   生产一个产品；
   P(empty);
   P(mutex);
   把产品放入缓冲区;
   V(mutex);
   V(full);
   }
   }
   consumer(){
   while(1){
   P(full);
   P(mutex);
   从缓冲区取走一个商品；
   V(mutex);
   V(empty)；
   使用产品；
   }
   }
   

多生产者、多消费者问题

桌子上有一个盘子，每次只能向其中放入一个水果。爸爸专向盘子中放苹果，妈妈专向盘子中放橘子。儿子专等吃盘子中的橘子，女儿专等吃盘子中的苹果。只有盘子空时，爸爸或妈妈才可向盘子中放入一个水果。仅当盘子中有自己需要的水果时，儿子或女儿才可以从盘子中取出水果。

• 对盘子（缓冲区）的访问是互斥的；

• 女儿和父亲之间一前一后；

• 儿子和女儿之间一前一后；

• 盘子为空，父母才能放入水果；

  • 互斥关系设置一个互斥信号量，在临界区前后；
  • 女儿和父亲之间同步信号量apple；apple=0
  • 儿子和母亲之间同步信号量orange；orange=0
  • 盘子是否为空plate

  semaphore mutex=1;
  semaphore apple=0;
  semaphore orange=0;
  semapohore plate=1;//盘子中还可以放多少个水果
  dad(){
  准备一个苹果；
  P(plate);
  P(mutex);
  往盘子中放入一个苹果；
  V(mutex);
  V(plate);
  }
  mom(){
  准备一个橘子；
  P(plate);
  P(mutex);
  往盘子中放入一个橘子；
  V(mutex);
  V(plate)；
  }
  son(){
  P(orange);
  P(mutex);
  从盘子中取出橘子；
  V(mutex);
  V(plate);
  吃掉橘子；
  }
  daughter(){
  P(apple);
  P(mutex);
  从盘子中取出苹果；
  V(mutex);
  V(plate);
  吃掉苹果；
  }
  

读者写者问题

有读者写者两组并发进程，他们共享一个文件，当两个或两个以上的都进程同时访问贡献数据时不会产生副作用，但若某个写进程和其他进程同时访问共享数据的时候则可能导致数据不一致的错误。因此要求：

允许多个读者可以同时对文件进行操作；

只允许一个写着往文件中些信息

任一写着在完成写操作之前不允许其他读者或者写者工作

写者执行写操作前，应让已有的读者和写者全部退出。

• 互斥关系：写进程——写进程、写进程——读进程。

  semaphore rw=1;//实现文件的互斥访问，表示现在是否有进程在访问共享文件
  int count=0;//记录当前有几个读进程；
  semaphore mutex=1;//用于保证对count变量的互斥访问；
  wirter(){
  while(1){
  P(rw);//写之前枷锁
  写文件;
  V(rw);//写之后解锁
  }
  }
  reader(){
  while(1){
  P(mutex);//互斥访问count
  if(count==0) P(rw);//第一个读进程枷锁
  count++;
  V(mutex);
  读文件；
  P(mutex);
  count--;
  if(count==0)V(rw);
  V(mutex);//最后一个都进程解锁；
  }
  }
  

  以上这种算法是读者优先。

  semaphore rw=1;//实现文件的互斥访问，表示现在是否有进程在访问共享文件
  int count=0;//记录当前有几个读进程；
  semaphore mutex=1;//用于保证对count变量的互斥访问；
  wirter(){
  while(1){
  P(w);
  P(rw);//写之前枷锁
  写文件;
  V(rw);//写之后解锁
  V(w);
  }
  }
  reader(){
  while(1){
  P(w);
  P(mutex);//互斥访问count
  if(count==0) P(rw);//第一个读进程枷锁
  count++;
  V(mutex);
  V(w);
  读文件；
  P(mutex);
  count--;
  if(count==0)V(rw);
  V(mutex);//最后一个都进程解锁；
  }
  }
  

  以上算法是读写公平法。

哲学家进餐问题

一个圆桌上坐了五位哲学家，每两个哲学家之间的桌子上摆了一根筷子，桌子中间是一碗白米饭。哲学家倾注毕生精力用于思考和进餐。思考不影响他人。哲学家饥饿的时候，试图拿起左右筷子（一根一根拿起），如果筷子已经在他人手中，则需要等待。

• 五位哲学家对左右邻居对筷子访问互斥。

• 要有两个临界资源才能吃饭。

• 信号量设置，定义互斥信号量数组chopstick[5]={1,1,1,1,1}用于对五只筷子互斥访问，并对哲学家0-4编号，哲学家i左边筷子编号为i，右边筷子编号（i+1）%5。

• 限制条件，最多四个哲学家同时进餐，这样保证至少一个哲学家有饭吃。

• 奇数号拿左边，偶数号拿右边。这样可以没筷子阻塞。不会占有资源阻塞。

• 仅当一个哲学家左右两只筷子都可用才允许他拿筷子。(还是有问题)--------应该这么说：各个哲学家拿筷子这件事必须互斥的进行。即使一个哲学家在拿筷子一半被阻塞，也不会有别的哲学家试图拿筷子。这样的话，当前吃饭的哲学家放下筷子，被阻塞的哲学家就可以获得等待的筷子了。

  semaphore chopstick[5]={1,1,1,1,1};
  semaphore token=4;
  pi(){
  while(1){
  think();
  P(token);
  P(chopstick[i]);//拿左
  P(chopstick[(i+1)%5]);//拿右
  eat();
  V(chopstick[i]);//放左；
  V(chopstick[(i+1)%5]);//放右
  V(token);
  }
  }
  

管程

信号量机制存在的问题：编写程序困难、易出错；

管程——高级同步机制；

管程包括哪些模块：

1. 局部于管程的共享数据结构说明；
2. 对该数据结构进行操作的一组过程；
3. 对局部于管程的共享数据结构设置初值的语句；
4. 管程有一个名字。
5. 局部于管程的数据只能被局部于管程的过程所访问；
6. 一个进程只有通过调用管程内的过程才能进入管程访问共享数据
7. 每次仅允许一个进程在管城内执行某个内部过程。

死锁

在并发环境下，各个进程竞争资源而造成的一种互相等待对方手里的资源，导致各个进程都阻塞，都无法向前推进的现象，就是死锁，发生死锁以后如果没有外力干涉，这些进程都无法向前推进。

饥饿不是死锁，饥饿是进程长期无法得到资源无法向前推进。死循环也不是死锁，是进程执行过程中一直跳不出循环的现象。（代码逻辑导致的）

死锁产生的必要条件：互斥使用的资源争抢、资源不能被抢夺，只能自己释放、进程已经保持了至少一个资源，同时请求新的资源、资源循环等待链。

发生死锁一定有循环等待链，但是发生循环等待不一定是死锁。

预防策略：预防死锁、避免死锁、死锁的检测于解除

• 预防死锁

  • 破坏以上四个死锁产生的必要条件：
    • 破坏互斥条件：把资源改成可以同时使用的资源而不再是互斥资源。spooling技术改成共享设备！
    • 破坏不能剥夺条件：进程还没使用完资源，可以强行剥夺资源。看情况！实现起来很复杂而且只适用于易保存的。而且系统开销很大。
    • 破坏请求和保持条件：静态分配方法；在进程运行前一次申请完他要的全部资源，资源不满足就不运行。这样他就不会请求了。不过很浪费而且饥饿现象。
    • 破环循环等待：给系统资源编号，每个进程必须按照编号递增的顺序请求资源。（一个进程已经拥有了小资源才能申请大资源，而且大编号进程不可能逆向申请小编号资源，所以不能循环起来）不过增加设备很麻烦。。。而且有可能进程使用资源顺序和资源编号递增顺序不一致。

• 避免死锁

  • 安全序列：如果系统按照这种序列分配资源，则每个进程都能顺利完成，只要找出一个安全序列，那么系统就是安全状态。安全序列可能很多个。

  • 系统处于安全状态一定不会死锁，但是在不安全状态可能死锁；发生死锁一定是不安全状态。

  • 找安全序列：

    • 把单维数字拓展为多维向量，初始（10，5，7）

      进程	最大需求（max矩阵）	已分配（allocation矩阵）	最多还需要（need矩阵）
      P0	(7,5,3)	(0,1,0)	(7,4,3)
      P1	(3,2,2)	(2,0,0)	(1,2,2)
      P2	(9,0,2)	(3,0,2)	(6,0,0)
      P3	(2,2,2)	(2,1,1)	(0,1,1)
      P4	(4,3,3)	(0,0,2)	(4,3,1)

      此时总共分配（7，2，5）还剩（3，3，2）

      把各个进程最多需要的和还剩余的对比，找到可以执行的，然后等待他归还。

      把P1加入安全序列，可用资源增加到（5，3，2）

      继续检查；P3加入安全序列，（7，4，3）

      ······

      最终得到安全序列。

      试试写代码：假设一共n个进程，m种资源。用一个n*m矩阵代表各个进程需要的最大资源数。MAX[i,j]表示进程Pi最多需要k个资源Rj。还有一个已经分配的矩阵allocation，max-allocation=need，表示改=该进程还需要多少资源。在设置一个一维数组表示剩余资源。request数组表示进程申请多少资源。

      王道：银行家算法步骤：

      检查此次申请是否超过了之前申明的最大需求数

      检查系统剩余可用资源是否满足此次请求

      试着分配，更改数据结构

      用安全性算法检查此次分配是否会导致系统进入不安全状态

      安全性算法步骤：

      检查当前的剩余可用资源是否能满足某个进程的最大需求，如果可以的话，就把该进程加入安全序列，并把该进程持有的资源回收。不断重复上述过程，看最终是否能让所有进程加入安全序列。

• 检测和解除

  • 死锁的检测：

    • 进程结点：每个节点对应一个进程，圆形表示

    • 资源节点：每个节点对应一类资源，一类资源里面可能有多个，矩形表示资源节点，矩形中的小圆代表该类资源的数量

    • 两种边：进程节点->资源节点：表示进程想请求几个资源，每条边代表一个

      ​ 资源节点->进程节点：表示已经为进程分配了几个资源，每条边代表一个

    • 如果系统中剩余的可用资源数足够满足进程的需求，那么这个进程暂时不会阻塞，可以顺利执行下去。

      如果这个进程执行结束了把资源归还给系统，就可能使得某些正在等待资源的进程被激活，并且顺利的执行下去。

      相应的，这些被激活的进程执行完了之后又会归还一些资源，这样又会激活另外一些阻塞的进程。

      如果按照上述过程分析，最终可以消除所有边，就说这个图是可以简化的，此时一定没发生死锁。（相当于可以找到一个安全序列）如果不能消除所有边，那么此时就是发生了死锁。最终还连这边的那些进程就是处于死锁状态的进程。

    • 检测死锁的算法：

      在资源分配图中，找到既不阻塞也不孤立的进程，消去他的所有分配边和请求边，使之成为孤立的节点。该进程释放的资源，可以唤醒某些因为等待这些资源而阻塞的进程，原来的阻塞的进程变成了非阻塞的进程。若能消去所有的边，那么这个图就是可以简化的。

      死锁定理：如果某时刻系统资源分配图是不可完全简化的，那么此时系统完全死锁。

  • 死锁的解除

    • 并不是系统中所有进程都是死锁的状态，用死锁检测算法化简资源分配图之后，还连这边的那些进程就是死锁进程。

    • 解决的办法主要有：

      • 资源剥夺法：挂起某些死锁进程，并且抢占他的资源，将这些资源分配给其他死锁进程。但是应该防止被挂起进程长期得不到资源而饥饿。
      • 撤销进程（终止进程）：强制撤销部分、甚至全部死锁进程，并且剥夺这些进程资源。不过代价很大，功亏一篑啊。
      • 进程回退：让一个进程回退到足以避免死锁的状态。要记录历史信息，设置还原点。

    • 牺牲谁？

      • 进程优先级（干掉低的）
      • 已经执行多长时间（干掉少的）
      • 还要多久完成（干掉晚的）
      • 已经使用多少资源（干掉多的）
      • 进程是交互的还是批处理（干掉批处理的，因为用户要交互的）