来都来了给我点个赞吧🌹🌹🌹🌹🌹
一、操作系统导论 1.简介什么是操作系统
操作系统（Operating Ststem， OS）是指控制和管理整个计算机系统的硬件和软件资源，并合理地组织调度计算机的工作和资源的分配，以提供给用户和其他软件方便的接口和环境，它是计算机系统中最基本的系统软件。
1.OS 作为用户与计算机硬件系统之间的接口
OS 作为用户与计算机硬件系统之间接口的含义是：OS 处于用户与计算机硬件系统之 间，用户通过 OS 来使用计算机系统。或者说，用户在 OS 帮助下，能够方便、快捷、安全、 可靠地操纵计算机硬件和运行自己的程序。应注意，OS 是一个系统软件，因而这种接口是软件接口。图 1-1 是 OS 作为接口的示意图。由图 可看出，用户可通过以下三种方式使用计算机。
(1) 命令方式。这是指由 OS 提供了一组联机 命令接口，以允许用户通过键盘输入有关命令来 取得操作系统的服务，并控制用户程序的运行。
(2) 系统调用方式。OS 提供了一组系统调用， 用户可在自己的应用程序中通过相应的系统调 用，来实现与操作系统的通信，并取得它的服务。
(3) 图形、窗口方式。这是当前使用最为方便、最为广泛的接口，它允许用户通过屏幕 上的窗口和图标来实现与操作系统的通信，并取得它的服务。
2.OS 作为计算机系统资源的管理者
在一个计算机系统中，通常都含有各种各样的硬件和软件资源。归纳起来可将资源分 为四类：处理器、存储器、I/O 设备以及信息(数据和程序)。相应地，OS 的主要功能也正是 针对这四类资源进行有效的管理，即：处理机管理，用于分配和控制处理机；存储器管理， 主要负责内存的分配与回收； I/O 设备管理，负责 I/O 设备的分配与操纵；文件管理，负责 文件的存取、共享和保护。可见，OS 的确是计算机系统资源的管理者。事实上，当今世界 上广为流行的一个关于 OS 作用的观点，正是把 OS 作为计算机系统的资源管理者。
值得进一步说明的是，当一个计算机系统同时供多个用户使用时，用户对系统中共享 资源的需求(包括数量和时间)可能发生冲突，为了管理好这些共享资源(包括硬件和信息)的 使用，操作系统必须记录下各种资源的使用情况，对使用资源的请求进行授权，协调诸用 户对共享资源的使用，避免发生冲突，并计算使用资源的费用等
3.OS 实现了对计算机资源的抽象
对于一个完全无软件的计算机系统(即裸机)，它向用户提供的是实际硬件接口(物理接 口)，用户必须对物理接口的实现细节有充分的了解，并利用机器指令进行编程，因此该物 理机器必定是难以使用的。为了方便用户使用 I/O 设备，人们在裸机上覆盖上一层 I/O 设备 管理软件，如图 1-2 所示，由它来实现对 I/O 设备操作的细节，并向上提供一组 I/O 操作命令，如 Read 和 Write 命令，用户可利用它来进行数据输入或输出，而无需关心 I/O 是如何 实现的。此时用户所看到的机器将是一台比裸机功能更强、使用更方便的机器。这就是说， 在裸机上铺设的 I/O 软件隐藏了对 I/O 设备操作的具体细节，向上提供了一组抽象的 I/O 设备.
4.用户和计算机硬件之间的接口
（1）人工操作方式
从第一台计算机诞生(1945 年)到 20 世纪 50 年代中期的计算机，属于第一代计算机。此 时的计算机是利用成千上万个真空管做成的，它的运行速度仅为每秒数千次，但体积却十 分庞大，且功耗也非常高。这时还未出现 OS。计算机操作是由用户(即程序员)采用人工操 作方式直接使用计算机硬件系统，即由程序员将事先已穿孔(对应于程序和数据)的纸带(或 卡片)装入纸带输入机(或卡片输入机)，再启动它们将程序和数据输入计算机，然后启动计 算机运行。当程序运行完毕并取走计算结果之后，才让下一个用户上机。这种人工操作方 式有以下两方面的缺点:
(1) 用户独占全机。此时，计算机及其全部资源只能由上机用户独占。
(2) CPU 等待人工操作。当用户进行装带(卡)、卸带(卡)等人工操作时，CPU 及内存等 资源是空闲的。
可见，人工操作方式严重降低了计算机资源的利用率，此即所谓的人机矛盾。随着 CPU 速度的提高和系统规模的扩大，人机矛盾变得日趋严重。
下面的作业也就是一个程序：
（2）脱机输入/输出方式
脱机也就是运用了io的方式让电脑操作不是只通过主机来操作数据，认识引进了磁盘的类似概念
为了解决人机矛盾及 CPU 和 I/O 设备之间速度不匹配的矛盾，20 世纪 50 年代末出现 了脱机输入/输出(Off-Line I/O)技术。该技术是事先将装有用户程序和数据的纸带(或卡片) 装入纸带输入机(或卡片机)，在一台外围机的控制下，把纸带(卡片)上的数据(程序)输入到 磁带上。当 CPU 需要这些程序和数据时，再从磁带上将其高速地调入内存。
脱机 I/O 方式的主要优点：
1.减少了 CPU的空闲时间。装带(卡)、 卸带(卡)以及将数据从低速 I/O 设备送到高 速磁带(或盘)上，都是在脱机情况下进行 的，并不占用主机时间，从而有效地减少了 CPU 的空闲时间，缓和了人机矛盾。
2.提高了 I/O 速度。当 CPU 在运行中需要数据时，是直接从高速的磁带或磁盘上将 数据调入内存的，不再是从低速 I/O 设备上输入，极大地提高了 I/O 速度，从而缓和了 CPU 和 I/O 设备速度不匹配的矛盾，进一步减少了 CPU 的空闲时间。
2.2单道批处理系统通常是把一批作业以脱机 方式输入到磁带上，并在系统中配上监督程序(Monitor)，在它的控制下使这批作业能一个 接一个地连续处理。其自动处理过程是：首先，由监督程序将磁带上的第一个作业装入内 存，并把运行控制权交给该作业。当该作业处理完成时，又把控制权交还给监督程序，再 由监督程序把磁带(盘)上的第二个作业调入内存。计算机系统就这样自动地一个作业一个作 业地进行处理，直至磁带(盘)上的所有作业全部完成，这样便形成了早期的批处理系统。由 于系统对作业的处理都是成批地进行的，且在内存中始终只保持一道作业，故称此系统为 单道批处理系统(Simple Batch Processing System)。
单道批处理系统的特征:
(1) 自动性。在顺利情况下，在磁带上的一批作业能自动地逐个地依次运行，而无需人 工干预。
(2) 顺序性。磁带上的各道作业是顺序地进入内存，各道作业的完成顺序与它们进入内 存的顺序，在正常情况下应完全相同，亦即先调入内存的作业先完成。
(3) 单道性。内存中仅有一道程序运行，即监督程序每次从磁带上只调入一道程序进入 内存运行，当该程序完成或发生异常情况时，才换入其后继程序进入内存运行。
2.3多道批处理系统多道程序设计的基本概念:
在该系统中，用户所提交的作业都先存放在外存上并排成一个队列，称为“后备 队列”；然后，由作业调度程序按一定的算法从后备队列中选择若干个作业调入内存，使它们共享 CPU 和系统中的各种资源。
多道批处理系统的优缺点
(1) 资源利用率高。由于在内存中驻留了多道程序，它们共享资源，可保持资源处于忙 碌状态，从而使各种资源得以充分利用。
(2) 系统吞吐量大。系统吞吐量是指系统在单位时间内所完成的总工作量。能提高系统吞吐量的主要原因可归结为：第一，CPU 和其它资源保持“忙碌”状态； 第二，仅当作业 完成时或运行不下去时才进行切换，系统开销小。
(3) 平均周转时间长。作业的周转时间是指从作业进入系统开始，直至其完成并退出系 统为止所经历的时间。在批处理系统中，由于作业要排队，依次进行处理，因而作业的周转时间较长，通常需几个小时，甚至几天。
(4) 无交互能力。用户一旦把作业提交给系统后，直至作业完成，用户都不能与自己的作业进行交互，这对修改和调试程序是极不方便的。
2.4分时系统分时系统(Time Sharing System)与多道批处理系统之间有着截然不同的性能差别，它能很好地将一台计算机提供给多个用户同时使用，提高计算机的利用率。它被经常应用于查询系统中，满足许多查询用户的需要。简单来说就是把一个系统再多用户访问的时候给每个用户分一段时间在一段时间没有做完这个任务，也把时间给下一位用户直到循环回来继续执行。
分时系统的特征
(1) 多路性。允许在一台主机上同时联接多台联机终端，系统按分时原则为每个用户服 务。宏观上，是多个用户同时工作，共享系统资源；而微观上，则是每个用户作业轮流运 行一个时间片。多路性即同时性，它提高了资源利用率，降低了使用费用，从而促进了计 算机更广泛的应用。
(2) 独立性。每个用户各占一个终端，彼此独立操作，互不干扰。因此，用户所感觉到 的，就像是他一人独占主机。
(3) 及时性。用户的请求能在很短的时间内获得响应。此时间间隔是以人们所能接受的 等待时间来确定的，通常仅为 1～3 秒钟。
(4) 交互性。用户可通过终端与系统进行广泛的人机对话。其广泛性表现在：用户可以 请求系统提供多方面的服务，如文件编辑、数据处理和资源共享等。
2.5 实时系统所谓“实时”，是表示“及时”，而实时系统(Real Time System)是指系统能及时(或即时) 响应外部事件的请求，在规定的时间内完成对该事件的处理，并控制所有实时任务协调一 致地运行。例如自动驾驶要在指定的时间内完成任务不然就会出问题
在实时系统中必然存在着若干个实时任务，这些任务通常与某个(些)外部设备相关，能 反应或控制相应的外部设备，因而带有某种程度的紧迫性。可从不同的角度对实时任务加 以分类。
1) 按任务执行时是否呈现周期性来划分
(1) 周期性实时任务。外部设备周期性地发出激励信号给计算机，要求它按指定周期循 环执行，以便周期性地控制某外部设备。
(2) 非周期性实时任务。外部设备所发出的激励信号并无明显的周期性，但都必须联系 着一个截止时间(Deadline)。它又可分为开始截止时间(某任务在某时间以前必须开始执行) 和完成截止时间(某任务在某时间以前必须完成)两部分。
2) 根据对截止时间的要求来划分
(1) 硬实时任务(Hard real-time Task)。系统必须满足任务对截止时间的要求，否则可能 出现难以预测的结果。
(2) 软实时任务(Soft real-time Task)。它也联系着一个截止时间，但并不严格，若偶尔 错过了任务的截止时间，对系统产生的影响也不会太大。
2.6微机操作系统1．单用户单任务操作系统
2．单用户多任务操作系统（windos）
3．多用户多任务操作系统（linux）
3.操作系统的基本特征 3.1、并发并发是指两个或多个事件在同一时间间隔内发生。这些事件在宏观上是同时发生的，在微观上是交替发生的。（把并发想成串行就好理解了）
易混淆的概念——并行：两个或多个事件在同一时刻同时发生
3.2、共享共享即资源共享，是指系统中的资源内存中多个并发执行的进程共同使用。
所谓的“同时”往往是宏观上的，而在微观上，这些进程可能是交替地对该资源进行访问的(即分时共享)
生活实例:
互斥共享方式:使用QQ和微信视频。同一时间段内摄像头只能分配给其中一个进程。
同时共享方式:使用QQ发送文件A，同时使用微信发送文件B。宏观上看，两边都在同时读取并发送文件，说明两个进程都在访问硬盘资源，从中读取数据。微观上看，两个进程是交替着访问硬盘的。
3.3、虚拟虚拟是指把一个物理上的实体变为若干个逻辑上的对应物。物理实体（前者）是实际存在的，而逻辑上对应物（后者）是用户感受到的。
异步是指，在多道程序环境下，允许多个程序并发执行，但由于资源有限，进程的执行不是一贯到底的，而是走走停停，以不可预知的速度向前推进，这就是进程的异步性。
只有系统拥有并发性，才有可能导致异步性。 4.操作系统的运行机制和体系结构指令
CPU 
操作系统的内核 由于内核划分功能的不同，内核分为大内核和微内核。
大内核和微内核的优缺点
类比:
操作系统的体系结构问题与企业的管理问题很相似。
内核就是企业的管理层，负责一些重要的工作。只有管理层才能执行特权指令，普通员工只能执行非特权指令。用户态、核心态之间的切换相当于普通员工和管理层之间的工作交接
大内核:企业初创时体量不大，管理层的人会负责大部分的事情。优点是效率高;缺点是组织结构混乱，难以维护。
微内核:随着企业体量越来越大，管理层只负责最核心的一些工作。优点是组织结构清晰，方便维护;缺点是效率低。
5.中断和异常1.概念和作用
中断是指计算机运行过程中，出现某些意外情况需主机干预时，机器能自动停止正在运行的程序并转入处理新情况的程序，处理完毕后又返回原被暂停的程序继续运行。
当中断发生时，CPU立即进入核心态
当中断发生后，当前运行的进程暂停运行，并由操作系统内核对中断进行处理。
对于不同的中断信号，会进行不同的处理。
有了中断，才能实现多道程序并发执行。
“用户态→核心态”是通过中断实现的，并且中断是唯一途径。“核心态→用户态”的切换是通过执行一个特权指令，将程序状态字（ PSW）的标志位设置为 “用户态”。
2.分类
中断信号的来源来自CPU内部称为内中断，外部称为外中断。
“系统调用”是操作系统提供给应用程序（程序员/编程人员）使用的接口，可以理解为一种可供应用程序调用的特殊函数，应用程序可以发出系统调用请求来获得操作系统的服务。
6.2.作用应用程序通过系统调用请求操作系统的服务。系统中的各种共享资源都由操作系统统一掌管，因此在用户程序中，凡是与资源有关的操作（如存储分配、I/o操作、文件管理等），都必须通过系统调用的方式向操作系统提出服务请求，由操作系统代为完成。这样可以保证系统的稳定性和安全性，防止用户进行非法操作。
6.3.系统调用和库函数的区别编程语言（c,java）中里边有很多库函数，其实它们（不是所有的库函数）就是将系统调用封装起来，隐藏一些细节，使上层进行系统调用更加方便。
6.4.其他系统调用发生在用户态，对系统调用的处理发生在核心态。
执行陷入指令（自陷指令或访管指令）会处理内中断，使处理器（CPU）从用户态进入核心态。
二、进程控制 1.进程的定义程序：是静态的，就是个存放在磁盘里的可执行文件，就是一系列的指令集合。 进程（Process）的概念：是动态的，是程序的一次执行过程。同一程序多次执行会对应多个进程。 进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位。进程是动态的，进程实体是静态的；进程实体反应了进程某一时刻的状态就像视频中的一帧。进程，’‘用进程实体（进程映像）更准确’‘：由PCB，程序段（代码：指令序列），数据段（运行过程中产生当各种数据）。其中PCB是给操作系统用的，程序段和数据段是给进程自己用的。操作系统对进程进行管理工作所需的信息都存在PCB中。PCB是进程存在的唯一标志，当进程被创建时，操作系统为其创建PCB，当进程结束时，会回收其PCB。进程控制块（PCB）：包括进程描述信息（PID，UID），进程控制和管理信息（CPU、磁盘、网络流量；进程当前状态：就绪态阻塞态/运行态），资源分配清单（正在使用哪些文件，I/O，内存），处理机相关信息（PSW各种寄存器用于实现进程切换）PID：当进程被创建时，操作系统会为该进程分配一个唯一的、不重复的“身份证号”。ID（UID）：基本的进程描述信息，可以让操作系统区分各个进程。通过任务管理器我们可以发现每个进程不仅仅只有cpu内存磁盘的占用率也是有唯一用来表示进程的PID（process id）
程序的运行过程：
进程特征：
总结：
进程是程序的一次执行。在这个执行中，进程的状态有各种变化。为了方便进程管理，把进程分为了，运行态，就绪态，阻塞态、创建态、终止态五种状态。
创建态：系统创建进程，操作系统给进程分配系统资源、pcb等等就绪态：已经具备运行条件，等待空闲的cpu，进行调用运行态：当cpu处于空闲阶段就会在就绪态的进程里面选择一个进行执行，，也就是把cpu占据进入了运行态，一核的cpu就只可以一次运行一个进程，多少核的cpu可以有多少个进程处于运行态阻塞态：因为某个事件而暂时不可用运行终止态：运行进程从cpu撤销，操作系统就会回收资源、撤销PCB 2.2转化
组织也就是调用的方式
链式
索引
进程控制的含义：进程控制就是要用来实现进程状态的转化的
进程控制的实现：进程控制由原语实现。所谓原语，一般是指由若干条指令组成的程序段，用来实现某个特定功能，在执行过程中不可被中断。原语采用 “关中断指令” 和 “开中断指令” 来实现。 注意： 原语运行在核心态。
那么原语是如何实现进程状态的转换呢？
更新PCB中的信息（如修改进程状态标志、将运行环境保存到PCB、从PCB恢复运行环境)所有的进程控制原语一定都会修改进程状态标志 剥夺当前运行进程的CPU使用权必然需要保存其运行环境 某进程开始运行前必然要恢复期运行环境 将PCB插入合适的队列 分配/回收资源
程序的运行
含义：进程通信就是进程之间的信息交换。
为了保证安全，一个进程不能直接访问另一个进程的地址空间。所以操作系统就提供了三种方法使得进程可以进行信息交换。
1.共享存储
2.消息传递
进程间的数据交换以格式化的消息为单位。进程通过操作系统提供的“发送消息/接收消息” 两个原语进行数据交换。
3.管道通信
1.管道只能采用半双工通信，某一时间段内只能实现单向的传输。如果要实现双向同时通信，则需要设置两个管道。
2.各进程要互斥地访问管道。
3.数据以字符流的形式写入管道，当管道写满时，写进程的write()系统调用将被阻塞，等待读进程将数据取走。当读进程将数据全部取后，管道变空，此时读进程的read()系统调用将被阻塞。
4.如果没写满，就不允许读。如果没读空，就不允许写。
5．数据一旦被读出，就从管道中被抛弃，这就意味着读进程最多只能有一个，否则可能会有读错数据的情况。
有的进程需要同时做很多事，例如用QQ来进行聊天，发送文件等，而传统的进程只能串行执行一系列程序。因此，引入“线程”，来增加并发度。
可以把线程理解为轻量级的进程。线程是一个基本的CPU执行单元，也是程序执行流的最小单位。引入线程后，进程作为除CPU之外的系统资源的分配单元。
内核级线程的管理工作由操作系统内核完成。线程调度、切换等工作都由内核负责，因此内核级线程的切换必然需要在核心态下才能完成。
可以这样理解，“内核级线程”就是“从操作系统内核视角看能看到的线程”。
操作系统只“看得见”内核级线程，因此只有内核级线程才是处理机分配的单位。
5.3.多线程模型线程模型分为三种：一对一、多对一、多对多
一对一模型
一对一模型:一个用户级线程映射到一个内核级线程。优点:当一个线程被阻塞后，别的线程还可以继续执行，并发能力强。多线程可在多核处理机上并行执行。缺点:一个用户进程会占用多个内核级线程，线程切换由操作系统内核完成，需要切换到核心态，因此线程管理的成本高，开销大。
多对一模型
多对一模型:多个用户及线程映射到一个内核级线程。每个用户进程只对应一个内核级线程。
优点:用户级线程的切换在用户空间即可完成，不需要切换到核心态，线程管理的系统开销小，效率高
缺点:当一个用户级线程被阻塞后，整个进程都会被阻塞，并发度不高。多个线程不可在多核处理机上并行运行
多对多模型
多对多模型:n用户级线程映射到m个内核级线程(n >=m)。每个用户进程对应m个内核级线程。克服了多对一模型并发度不高的缺点，又克服了一对一模型中一个用户进程占用太多内核级线程，开销太大的缺点。
首先我们需要认知的是作业和进程的区别是什么：
作业是用户需要计算机完成的某项任务。一个作业的完成要经过作业提交、作业收容、作业执行和作业完成四个阶段。而进程是对已提交完毕的程序所执行过程的描述。
1.作业是用户向计算机提交任务的任务实体。在用户向计算机提交作业作业后，系统将它放入外存中的作业等待队列中等待执行。而进程则是完成用户任务的执行实体，是向系统申请分配资源的基本单位。任一进程，只要它被创建，总有相应的部分存在于内存中。
2.一个作业可由多个进程组成，且必须至少由一个进程组成，反过来不成立。
3.作业的概念主要用在批处理系统中，像UNIX这样的分时系统中就没有作业的概念。而进程的概念则用在几乎所有的多道程序系统中。
在多道程序系统中，进程的数量往往是多于处理机的个数的，这样不可能同时并行地处理各个进程。处理机调度，就是从就绪队列中按照一定的算法选择一个进程并将处理机分配给它运行，以实现进程的并发执行。
调度分为三个层次，分别为高级调度，中级调度，初级调度。
高级调度 由于内存空间有限，有时无法将用户提交的作业全部放入内存，因此就需要确定某种规则来决定将作业调入内存的顺序。高级调度（作业调度)。按一定的原则从外存上处于后备队列的作业中挑选一个(或多个）作业，给他们分配内存等必要资源，并建立相应的进程（建立PCB)，以使它（们）获得竞争处理机的权利。高级调度是辅存（外存）与内存之间的调度。每个作业只调入一次，调出一次。作业调入时会建立相应的PCB，作业调出时才撤销PCB。高级调度主要是指调入的问题，因为只有调入的时机需要操作系统来确定，调出的时机必然是作业运行结束才调出。
临界资源： 一个时间段内只允许一个进程使用的资源。各进程需要互斥的访问临界资源。
临界区：访问临界资源的那段代码。
内核程序临界区一般是用来访问某种内核数据结构的，比如进程的就绪队列。
2.进程调度的方式 非剥夺调度方式，又称非抢占方式。即，只允许进程主动放弃处理机。在运行过程中即便有更紧迫的任务到达，当前进程依然会继续使用处理机，直到该进程终止或主动要求进入阻塞态。优点：实现简单,系统开销小但是无法及时处理紧急任务，适合于早期的批处理系统
剥夺调度方式，又称抢占方式。当一个进程正在处理机上执行时，如果有一个更重要或更紧迫的进程需要使用处理机，则立即暂停正在执行的进程，将处理机分配给更重要紧迫的那个进程。优点：可以优先处理更紧急的进程，也可实现让各进程按时间片轮流执行的功能（通过时钟中断）。适合于分时操作系统、实时操作系统
3.进程的切换与过程“狭义的进程调度”与“进程切换”的区别:
狭义的进程调度指的是从就绪队列中选中一个要运行的进程。(这个进程可以是刚刚被暂停执行的进程，也可能是另一个进程，后一种情况就需要进程切换）进程切换是指一个进程让出处理机，由另一个进程占用处理机的过程。广义的进程调度包含了选择一个进程和进程切换两个步骤。
进程切换的过程主要完成了:
1.对原来运行进程各种数据的保存2.对新的进程各种数据的恢复(如:程序计数器、程序状态字、各种数据寄存器等处理机现场信息，这些信息一般保存在进程控制块)注意 : 进程切换是有代价的，因此如果过于频繁的进行进程调度、切换，必然会使整个系统的效率降低，使系统大部分时间都花在了进程切换上，而真正用于执行进程的时间减少。
8.调度算法的评价指标可以看下面调度算法的例题来理解其中的含义是怎么算的
CPU利用率： CPU"忙碌"的时间占总时间的比例。系统吞吐量：单位时间内完成作业的数量。周转时间：是指从作业被提交给系统开始，到作业完成为止的时间间隔。周转时间=作业完成时的时间-作业提交时间平均周转时间=各作业周转时间之和/作业数带权周转时间=（作业完成时的时间-作业提交时间）/作业实际运行时间等待时间：指进程/作业处于等待处理机状态时间之和，等待时间越长，用户满意度越低。对于进程来说，等待时间就是指进程建立后等待被服务的时间之和，在等待I/O完成的期间其实进程也是在被服务的，所以不计入等待时间。
对于作业来说，不仅要考虑建立进程后的等待时间，还要加上作业在外存后备队列中等待的时间。
响应时间：指从用户提交请求到首次产生响应所用的时间。 9.调度算法 9.1.先来先服务（FCFS，First Come First Serve）
非抢占式的作业优先算法
抢占式的作业优先算法
例题：
时间片就是分配一段时间给进程运行时间到了就会主动的放弃处理机
非抢占式
抢占式
同步亦称直接制约关系，它是指为完成某种任务而建立的两个或多个进程，这些进程因为需要在某些位置上协调它们的工作次序而产生的制约关系。进程间的直接制约关系就是源于它们之间的相互合作。
通过进程通信——管道通信的例子来了解什么是进程同步。
读进程和写进程并发地运行，由于并发必然导致异步性，因此“写数据”和“读数据”两个操作执行的先后顺序是不确定的。而实际应用中，又必须按照“写数据→读数据”的顺序来执行的。如何解决这种异步问题，就是“进程同步”所讨论的内容。
10.2进程互斥 我们把一个时间段内只允许一个进程使用的资源称为临界资源。许多物理设备（比如摄像头、打印机）都属于临界资源。此外还有许多变量、数据、内存缓冲区等都属于临界资源。对临界资源的访问，必须互斥地进行。互斥，亦称间接制约关系。进程互斥指当一个进程访问某临界资源时，另一个想要访问该临界资源的进程必须等待。当前访问临界资源的进程访问结束，释放该资源之后，另一个进程才能去访问临界资源。
对临界资源的互斥访问，可以在逻辑上分为如下四个部分:
为了实现对临界资源的互斥访问，同时保证系统整体性能，需要遵循以下原则:
空闲让进。临界区空闲时，可以允许一个请求进入临界区的进程立即进入临界区; 忙则等待。当已有进程进入临界区时，其他试图进入临界区的进程必须等待; 有限等待。对请求访问的进程，应保证能在有限时间内进入临界区（保证不会饥饿) 让权等待。当进程不能进入临界区时，应立即释放处理机，防止进程忙等待。 11.进程互斥的软件实现方法 1.单标志法算法思想:每个进程在访问完临界区后会把使用临界区的权限转交给另一个进程。也就是说每个进程进入临界区的权限只能被另一个进程赋予。
代码实现
上面的代码如果用turn等于0开始，如果率先得到cpu的进程使p1进程，会使p1进程卡在代码5上，（while循环满足条件虽然没有要执行的语句但是会一直卡在里面），但是当p1的时间片到了，就会给p0进程执行代码，到了p0进入临界区了，又且回到p1进程但是还是继续卡住知道执行了代码3就可以执行进程p1了，但是我们可以发现一个很明显的问题就是，在p1想先访问的时候是不可以访问的，所以这是违法了空闲让进的原则。
2.双标志先检查法算法思想:设置一个布尔型数组flag[]，数组中各个元素用来标记各进程想进入临界区的意愿，比如“flag[0] =ture”意味着0号进程 P0现在想要进入临界区。每个进程在进入临界区之前先检查当前有没有别的进程想进入临界区，如果没有，则把自身对应的标志flag[li]设为true，之后开始访问临界区。
若按照①⑤②⑥③⑦…的顺序执行，P0和P1将会同时访问临界区。因此，双标志先检查法的主要问题是:违反“忙则等待”原则。
原因在于，进入区的“检查”和“上锁”两个处理不是一气呵成的。“检查”后，“上锁”前可能发生进程切换。
3.双标志后检查法算法思想:双标志先检查法的改版。前一个算法的问题是先“检查”后“上锁”,但是这两个操作又无法一气呵成,因此导致了两个进程同时进入临界区的问题。因此,人们又想到先“上锁”后“检查”的方法，来避免上述问题。
算法思想:双标志后检查法中，两个进程都争着想进入临界区，但是谁也不让谁，最后谁都无法进入临界区。Gary L.Peterson想到了一种方法，如果双方都争着想进入临界区，那可以让进程尝试“孔融让梨”，主动让对方先使用临界区。
用一个整数型的变量作为信号量，用来表示系统中某种资源的数量。
与普通整数变量的区别：对信号量的操作只有三种，初始化，P操作，V操作。
下面以打印机为例：
整型信号量的缺陷是存在“忙等”问题，因此人们又提出了“记录型信号量”，即用记录型数据结构表示的信号量。
先P后V
注意： 对不同的临界资源（如摄像头，打印机）需要设置不同的互斥信号量。
P、V操作必须成对出现。缺少P(mutex)就不能保证临界资源的互斥访问。缺少V(mutex)会导致资源永不被释放，等待进程永不被唤醒。
2.信号量机制实现进程同步进程同步：要让各并发进程按要求有序的进行。
那么如何实现呢？
分析什么地方需要实现“同步关系”，即必须保证“一前一后”执行的两个操作（或两句代码) 设置同步信号量s,初始为0 在“前操作”之后执行v(S) 在“后操作”之前执行P(S)下面通过一个例子来解释，要求：进程2的代码4必须在进程1的代码2之后执行。
进程P1中有句代码S1，P2中有句代码S2 …P… P6中有句代码S6。这些代码要求按如下前驱图所示的顺序来执行:
其实每一对前驱关系都是一个进程同步问题（需要保证一前一后的操作)，因此，
要为每一对前驱关系各设置一个同步变量 在“前操作”之后对相应的同步变量执行V操作 在“后操作”之前对相应的同步变量执行Р操作
系统中有一组生产者进程和一组消费者进程，生产者进程每次生产一个产品放入缓冲区，消费者进程每次从缓冲区中取出一个产品并使用。(注:这里的“产品”理解为某种数据)
生产者、消费者共享一个初始为空、大小为n的缓冲区。只有缓冲区没满时，生产者才能把产品放入缓冲区，否则必须等待。只有缓冲区不空时，消费者才能从中取出产品，否则必须等待。缓冲区是临界资源，各进程必须互斥地访问。
桌子上有一只盘子，每次只能向其中放入一个水果。爸爸专向盘子中放苹果，妈妈专向盘子中放橘子，儿子专等着吃盘子中的橘子，女儿专等着吃盘子中的苹果。只有盘子空时，爸爸或妈妈才可向盘子中放一个水果。仅当盘子中有自己需要的水果时，儿子或女儿可以从盘子中取出水果。用PV操作实现上述过程。
2.如何实现
问题：可不可以不使用问题信号量？
.结论:即使不设置专门的互斥变量mutex，也不会出现多个进程同时访问盘子的现象
原因在于:本题中的缓冲区大小为1，在任何时刻，apple、orange、plate三个同步信号量中最多只有一个是1。因此在任何时刻,最多只有一个进程的P操作不会被阻塞，并顺利地进入临界区…
如果盘子（缓冲区）数量为2，可能会出现两个进程同时访问缓冲区的情况，有可能导致两个进程写入缓冲区的数据相互覆盖的情况。
3.总结在生产者-消费者问题中，如果缓冲区大小为1，那么有可能不需要设置互斥信号量就可以实现互斥访问缓冲区的功能。当然，这不是绝对的，要具体问题具体分析。
建议:在考试中如果来不及仔细分析，可以加上互斥信号量，保证各进程一定会互斥地访问缓冲区。但需要注意的是，实现互斥的P操作一定要在实现同步的P操作之后，否则可能引起“死锁”。
17.吸烟者问题 1.问题描述假设一个系统有三个抽烟者进程和一个供应者进程。每个抽烟者不停地卷烟并抽掉它，但是要卷起并抽掉一支烟，抽烟者需要有三种材料:烟草、纸和胶水。三个抽烟者中，第一个拥有烟草、第二个拥有纸、第三个拥有胶水。供应者进程无限地提供三种材料，供应者每次将两种材料放桌子上，拥有剩下那种材料的抽烟者卷一根烟并抽掉它，并给供应者进程一个信号告诉完成了，供应者就会放另外两种材料再桌上，这个过程一直重复(让三个抽烟者轮流地抽烟)。
也就是先i=0的时候取出组合1放在桌子上然后就给finish加锁，生产者就被锁在了P（finish）处，在这之前要是有smokern在进程中了也会被P（offern）阻塞住，知道生产者告诉吸烟者才会把烟卷起来抽掉，再释放finish，生产者又可以继续的生成了就是这样的过程实现让三个抽烟者循环抽烟
有读者和写者两组并发进程，共享一个文件，当两个或两个以上的读进程同时访问共享数据时不会产生副作用，但若某个写进程和其他进程（读进程或写进程）同时访问共享数据时则可能导致数据不一致的错误。因此要求:
①允许多个读者可以同时对文件执行读操作;
②只允许一个写者往文件中写信息;
③任一写者在完成写操作之前不允许其他读者或写者工作;
④写者执行写操作前，应让已有的读者和写者全部退出。
潜在的问题：只要读进程还在读，写进程就要一直堵塞等待，可能会饿死。因此在这种算法中，读进程优先。下面来实现“ 先来先服务”算法，这样就不会导致写进程饿死。
读者-写者问题为我们解决复杂的互斥问题提供了一个参考思路。
其核心思想在于设置了一个计数器count用来记录当前正在访问共享文件的读进程数。我们可以用count的值来判断当前进入的进程是否是第一个/最后一个读进程，从而做出不同的处理。
另外，对count变量的检查和赋值不能一气呵成导致了一些错误，如果需要实现“一气呵成”，自然应该想到用互斥信号量。
最后，还要认真体会我们是如何解决“写进程饥饿”问题的。
19.哲学家吃饭 1.问题描述一张圆桌上坐着5名哲学家，每两个哲学家之间的桌上摆一根筷子，桌子的中间是一碗米饭。哲学家们倾注毕生的精力用于思考和进餐，哲学家在思考时，并不影响他人。只有当哲学家饥饿时，才试图拿起左、右两根筷子（一根一根地拿起)。如果筷子已在他人手上，则需等待。饥饿的哲学家只有同时拿起两根筷子才可以开始进餐，当进餐完毕后，放下筷子继续思考。
1.关系分析。系统中有5个哲学家进程，5位哲学家与左右邻居对其中间筷子的访问是互斥关系。
2.整理思路。这个问题中只有互斥关系，但与之前遇到的问题不同的是，每个哲学家进程需要同时持有两个临界资源才能开始吃饭。如何避免临界资源分配不当造成的死锁现象，是哲学家问题的精髓。
3.信号量设置。定义互斥信号量数组chopstick[5]={1,1,1,1,1}，用于实现对5个筷子的互斥访问。并对哲学家按0~4编号，哲学家i左边的筷子编号为i，右边的筷子编号为(i+1)%5。
3.如何实现如果使用下图所示的方法，图中方法也就是哲学家都先拿自己左边的筷子，然后等着拿自己右边的筷子，要是每个哲学家同时拿自己左边的筷子就会导致死锁问题。
那么如何解决呢？
①可以对哲学家进程施加一些限制条件，比如最多允许四个哲学家同时进餐。这样可以保证至少有一个哲学家是可以拿到左右两只筷子的
②要求奇数号哲学家先拿左边的筷子，然后再拿右边的筷子，而偶数号哲学家刚好相反。用这种方法可以保证如果相邻的两个奇偶号哲学家都想吃饭，那么只会有其中一个可以拿起第一只筷子，另一个会直接阻塞。这就避免了占有一支后再等待另一只的情况。
③仅当一个哲学家左右两支筷子都可用时才允许他抓起筷子。
下面用代码实现第三种方式。
1.为什么引入管程？
信号量机制存在的问题 : 编写程序困难、易出错。 因此人们想设计一种机制，让程序员写程序时不需要再关注复杂的PV操作，让写代码更轻松。1973年，Brinch Hansen首次在程序设计语言(Pascal)中引入了“管程”成分――一种高级同步机制。
2.管程的定义和基本特征管程相当于对临界区资源进行抽象而编写的一个类。
管程是一种特殊的软件模块，有这些部分组成:
局部于管程的共享数据结构说明; （一个类） 对该数据结构进行操作的一组过程; （类中的方法） 对局部于管程的共享数据设置初始值的语句; （类中的变量） 管程有一个名字。 （类名）管程的基本特征:
局部于管程的数据只能被局部于管程的过程所访问; （类中变量有自己的作用范围） 一个进程只有通过调用管程内的过程才能进入管程访问共享数据; ** 这种互斥特性是由编译器来实现的。 每次仅允许一个进程在管程内执行某个内部过程。 3.java中类似于管程的机制（单例模式）
在并发环境下，各进程因竞争资源而造成的一种互相等待对方手里的资源，导致各进程都阻塞，都无法向前推进的现象，就是“死锁“。
2.死锁，饥饿，死循环的区别 死锁:各进程互相等待对方手里的资源，导致各进程都阻塞，无法向前推进的现象。饥饿:由于长期得不到想要的资源，某进程无法向前推进的现象。比如:在短进程优先（SPF）算法中，若有源源不断的短进程到来，则长进程将一直得不到处理机，从而发生长进程“饥饿”。死循环:某进程执行过程中一直跳不出某个循环的现象。有时是因为程序逻辑bug 导致的，有时是程序员故意设计的。 3.死锁产生的必要条件产生死锁必须同时满足一下四个条件，只要其中任一条件不成立，死锁就不会发生。
互斥条件:只有对必须互斥使用的资源的争抢才会导致死锁(如哲学家的筷子、打印机设备）。像内存、扬声器这样可以同时让多个进程使用的资源是不会导致死锁的(因为进程不用阻塞等待这种资源）。不剥夺条件:进程所获得的资源在未使用完之前，不能由其他进程强行夺走，只能主动释放。请求 和 保持条件:进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源又被其他进程占有，此时请求进程被阻塞，但又对自己已有的资源保持不放。循环等待条件:存在一种进程资源的循环等待链，链中的每一个进程已获得的资源同时被下一个进程所请求。注意 : 发生死锁时一定有循环等待 , 但是发生循环等待时未必死锁（循环等待是死锁的必要不充分条件)
如果同类资源数大于1，则即使有循环等待，也未必发生死锁。但如果系统中每类资源都只有一个，那循环等待就是死锁的充分必要条件了。
4.什么时候会发生死锁对系统资源的竞争。各进程对不可剥夺的资源（如打印机）的竞争可能引起死锁，对可剥夺的资源(CPU)的竞争是不会引起死锁的 进程推进顺序非法。请求和释放资源的顺序不当，也同样会导致死锁。例如，并发执行的进程P1、P2分别申请并占有了资源R1、R2，之后进程p1又紧接着申请资源R2，而进程p2又申请资源R1,两者会因为申请的资源被对方占有而阻塞，从而发生死锁。 信号量的使用不当也会造成死锁。如生产者-消费者问题中，如果实现互斥的P操作在实现同步的P操作之前，就有可能导致死锁。(可以把互斥信号量、同步信号量也看做是一种抽象的系统资源) 5.死锁的处理策略预防死锁。破坏死锁产生的四个必要条件中的一个或几个。 避免死锁。用某种方法防止系统进入不安全状态，从而避免死锁（银行家算法) 死锁的检测和解除。允许死锁的发生，不过操作系统会负责检测出死锁的发生，然后采取某种措施解除死锁。 22.避免死锁1.什么是安全序列
2.银行家算法
数据结构:
长度为m的一维数组 Available表示还有多少可用资源
nm矩阵Max表示各进程对资源的最大需求数
nm矩阵Allocation表示已经给各进程分配了多少资源
Max - Allocation = Need矩阵表示各进程最多还需要多少资源
用长度为m的一位数组Request表示进程此次申请的各种资源数
银行家算法步骤:
①检查此次申请是否超过了之前