408操作系统笔记

一操作系统概述

1.操作系统的概念

考点：
1.单处理机系统：并行是指同时执行多个任务或者操作的方式，单处理机是一个计算机系统只包括一个运算处理器，同一时间只能处理一个任务，进程和进程之间在单处理机中无法并行。
2.操作系统提供给应用程序接口的是系统调用
3.RAM随机存储器(一般作为内存，断电后数据会消失)，ROM只读存储器(即使关闭电源数据也不会消失)，EPROM：电可擦除存储器；
4.操作系统最终会被加载到RAM
5.多道程序：早期多道程序并发执行，即使不支持虚拟存储管理，也可以实现多道并发，进程越多不意味着CPU利用率高，进程越多可能会因为资源竞争导致死锁现象，从而导致CPU利用率低
6.用户态执行的有：1.直接执行：命令解释程序 2.程序接口(也可以称为系统调用：允许用户通过程序间接使用，由一组系统调用组成)；用户态进入核心态通过陷入指令(也称为访管指令或trap指令)；执行系统调用，先传递系统调用的参数，然后由陷入指令将用户态转化为内核态；系统调用避免用户直接访问 外设
核心态执行的有：1.各种中断的处理，特权指令：2.进程的调度 3.整数除零 4.I/O指令 5.进程，内存管理
7.中断程序和子程序调用都需要保护现场，中断处理一定会保护而子程序调用不需要保护的内容是：程序状态字寄存器：因为子调用和当前进程有关，不需要保存程序状态字
8.中断时保存的数据：1.硬件保存：程序计数器PC，程序状态字PSW ，将CPU改为内核态 2.操作系统负责：其他有必要保存的信息，如某些通用寄存器，中断屏蔽字
9.有可能产生中断的操作：1.(R0)/(R1)->R0 有可能是除零操作 2.MOV RO ,addr 吧地址addr中的内存数据放入到寄存器R0中，可能会有缺页异常
中断：CPU执行指令外的事件发生 异常：内部的指令执行

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

2：操作系统的目标和功能

(1)操作系统四大管理功能：
进程管理：多道程序环境下，处理机的分配和运行都是以进程或线程为基本单位，对处理机的管理可以归结为对进程的管理。主要任务：进程控制，进程同步，死锁处理，处理机调度。
内存管理：主要是内存的分配和回收，地址映射，内存保护和共享和内存扩存
设备管理：主要任务是完成用户的I/O请求，提高设备的利用率，缓冲管理，设备处理(分配和回收)和虚拟设备等功能。
文件管理：主要包括文件存储空间的管理，目录管理以及文件读写管理和保护
(2)作为用户和硬件系统的接口
现在，主要通过GUI(图形用户界面)和操作系统交流，以前主要通过命令行(命令提示符)完成交互。这些都是操作系统提供的接口，操作系统提供的接口主要有两类，命令接口：用户利用这些操作命令组织和控制作业的执行，程序接口：编程人员可以使用它们来请求操作系统服务。
一：命令接口：
1.联机命令接口(一条命令一条命令执行)：
交互命令接口，适合分时或实时操作系统，用户通过控制台输入操作命令，向系统提出各种服务要求，每输入一条命令，控制权转给操作系统的命令解释程序，然后由命令解释程序解释并且执行输入的命令，完成功能后，之后的控制权转回控制台或者中断。
2.脱机命令接口(一批命令处理完后控制权才回到控制台)：
批处理命令接口，适合批处理系统，由一组作业控制命令完成，脱机用户不能直接干预作业的运行，事先相应的作业控制命令写出一份操作说明书，连同作业一起提交给操作系统。系统调度到该作业时，由系统中的命令解释程序逐条解释执行作业说明书上的命令。
二：程序接口
由一组系统调用组成，用户通过在程序中使用这些系统调用请求操作系统服务
例如：printf是向屏幕输出信息，需要操作系统完成，因为这是对硬件的控制，所以printf在底层会调用类似接口。
(3)需要实现对硬件机器的扩展
裸机：没有任何软件支持的计算机称为裸机，它构成了计算机系统的物质基础，
虚拟机或扩充机：操作系统覆盖在裸机上，提供资源管理和方便用户的各种服务功能，把裸机改造成为功能更强，使用更方便的机器。因此，把软件覆盖的机器称为虚拟机或扩充机

3：操作系统的四个特征

1.并发(区别并行和并发)
并发指的是两个或者多个事件在同一时间间隔内发生，这些事情在宏观上是同时发生的，在微观上是交替发生的。
操作系统的并发性：指的是操作系统在宏观上这些事件同时发生，微观上，这些事情是交替发生的。
单核CPU同一时刻只能执行一个程序，所以各个程序只能并发执行，多核CPU,同一时刻可以同时执行多个程序，多个程序可以并行执行。
2.共享
指的是系统中的资源可以供内存中多个并发执行的进程共同使用。分为互斥共享，同时共享。
a.互斥共享(在一个时间段内，只允许一个进程对它进行访问)
进程A访问某个资源时，若该资源空闲，则分配给进程A，若此后其他进程也要访问该资源时，若是A还没有用完该资源，则其余进程必须等待，这种资源称为临界资源，对于临界资源的访问各个进程之间是互斥的。
b.同时共享
同时共享：这里共享是宏观上的共享，其微观上也是交替对该资源进行访问

总结：并发和共享是操作系统两个最基本的特征，两者互为存在的前提，失去并发，共享失去存在的意义，失去共享，多个进程也无法进行
3.虚拟
是指把一个物理上的实体变为若干逻辑上的对应物。
应用：
虚拟处理机：利用多道程序设计技术把一个物理上的CPU虚拟为多个逻辑上的CPU，让每个终端用户都感觉有一个CPU在为它专门服务。
虚拟存储器：将一台机器的物理存储虚拟为虚拟存储器，以便从逻辑上扩充存储器的容量。

操作系统的虚拟技术：
时分复用：虚拟处理机的分时共享
空分复用：虚拟存储器
4.异步
在多道程序的环境下，允许多个程序并发执行，但是由于资源有限，程序的执行不能一气呵成，而是走走停停吗，程序以不可知的速度向前推进，这就是进程的异步性。

4：操作系统的发展历程

1.手工操作阶段
此阶段没有操作系统，所有工作需要人工干预，有两个显著缺点：用户独占全机，资源利用率很低，CPU等待手工操作，CPU利用很不充分

2.批处理阶段(操作系统开始出现)
一：单批道处理系统：引入了脱机输入输出技术，采用外围机+磁带完成，并且由监督程序负责控制作业的输入输出，这里的监督程序就是操作系统的雏形。
单批道处理系统的 特征：
自动性：磁带上的一批作业可以自动逐个运行，无需人工干预
顺序性：各道作业的完成顺序和他们进入内存的顺序在正常情况下完全一致
单道性：监督程序每次从磁道只调入一道程序进入内存运行
优缺点：
优点：缓解了一定程度的人机矛盾，资源利用率有所提升
缺点：单道性，内存中只有一道程序运行，CPU有大量时间等待I/O完成，资源利用率仍让很低

二：多批道处理系统(操作系统正式诞生)：多道程序设计技术允许多个程序同时进入内存并且允许他们在CPU中交替进行，这些程序共享系统中各种硬件软件资源。当一道程序因为I/O请求暂停运行，CPU便立刻转去运行另一道程序。
1.多道批处理系统特征：
多道：内存中同时存放多道独立的程序
宏观上并行：同时进入系统的多道程序都处于运行过程中，微观上串行：内存中的多道程序轮流占有CPU，交替执行
2.多道批处理系统的优缺点
优点：资源利用率高，多道程序共享计算机资源，从而使得资源得到充分利用，
缺点：用户响应时间长，未能提供人机交互能力，用户无法了解自己的程序运行情况，又不能控制计算机
注意点：多批道处理系统比较复杂，多个程序在内存中，这个时候需要内存管理，准备运行多个作业时，处理器必须决定先运行哪个作业，因此需要调度算法

3.分时操作系统
计算机以时间片为单位轮流为各个作业用户服务，每个用户可以通过终端和计算机进行交互。分时系统也支持多道程序设计的系统，但是它不同于多批道处理系统。
分时系统和多批道处理系统区别：
多批道处理系统实现作业自动控制而无须人工干预的系统，分时系统实现人机交互系统，这使得分时系统和批处理系统有着不同的特征。
1.分时系统的特点
同时性：允许多个终端用户同时使用一台计算机， 终端上这些用户可以同时或基本使用计算机
交互性：用户终端采用人机对话的方式直接控制程序运行，和程序进行交互
独立性：多个用户可以独立的进行操作，互不干扰，用户感觉不到别的用户的存在，好像自己在独占计算机
及时性：用户的请求在很短的时间内得到响应
2.分时操作系统的优缺点
优点：用户请求可以立即被响应，**解决了人机交互的问题，**用户对计算机的操作相互独立，感受不到别人的存在。
缺点：不区分任务的紧急性，不能优先处理一些紧急的任务，操作系统对各个用户都是完全公平的，循环的为每个用户服务一个时间片。

4.实时系统

为了解决分时系统无法优先处理紧急任务而诞生的，为了可以在某个时间限制内完成某些紧急任务而不需要时间片排队而诞生的
1.硬实时系统和软实时系统：硬实时系统：某个动作绝对地在规定的时间刻或规定的时间范围内发生，软 实时系统：能够接受偶尔的违法时间规定而且不会引起任何永久性的损害
2.实时操作系统的特点：
实时操作系统的控制下，计算机系统接受到外部信号后及时处理，并且在严格的时间内处理完成，具有很强的及时性和可靠性。
3.实时系统的优缺点：
优点：能够响应紧急 任务，某些紧急任务不需要时间片排队

5.操作系统的运行环境

1.特权指令和非特权指令
特权指令：这类指令具有特殊权限，这类指令权限大，使用不当导致系统奔溃，所以为了保护系统的安全，这类指令只能用于操作系统或者其他软件，不能直接提供给用户使用-----特权指令只能在核心态执行
非特权指令：用户态下只能使用非特权指令，和核心态下可以使用全部指令，当用户态下使用特权指令，将产生中断以阻止用户使用特权指令。
2.用户态和核心态
注意：程序状态寄存器(PSW)中的某些标志位可以标识当前处理器处于什么状态。
用户态：CPU处于用户态只能执行非特权指令
核心态：CPU处于核心态可以执行所有指令
3.内核程序和应用程序
内核程序：操作系统的内核程序是系统的管理者，可以执行全部指令，运行在核心态
应用程序：为了保证系统的安全运行，普通程序只能执行非特权指令，运行在用户态
4.操作系统的内核
1.内核的概念：操作系统中和硬件紧密关联的模块，这部分构成了操作系统的内核

2.大内核和微内核
大内核：把操作系统的主要功能模块都作为系统内核，运行在核心态
优点：性能高 缺点：内核代码庞大，结构混乱 ，难以维护
微内核：只把基本的功能保留在内核
优点：内核功能少，结构清晰，方便维护 缺点：需要频繁在用户态和内核态之间转化，性能低
3.库函数和系统调用
库函数是语言或者应用程序的一部分，可以运行在用户空间，系统调用是操作系统的一部分，是内核为用户提供的程序接口，运行在内核空间。
许多库函数会使用系统调用来实现自己的功能，没有使用系统调用的库函数执行效率要高于使用的 ，因为使用系统调用需要用户态向核心态的转化。
4.内核态和用户态的相互转化’
内核态到用户态：执行一条特权指令，修改PSW标志位标识当前状态为用户态，此时标志操作系统让出CPU的使用权
用户态到内核态：由中断触发，硬件自动完成改变状态过程，此时操作系统强行夺回CPU使用权

总结：操作系统中有内核----》内核态----》执行全部指令

6.中断和异常

1.中断的作用
中断是让操作系统内核夺回CPU使用权的唯一途径，发生中断时，用户会立刻进入核心态，通过硬件实现
2.中断的类型
一：内中断(也称为异常)
陷阱，陷入(trap) 故障(fault) 终止(abort)
内中断：中断信号来自于CPU内部，与当前执行的指令有关，对异常的处理一般依赖于当前的程序运行现场，而且异常无法被屏蔽，一旦出现异常，一定要立即处理。
1.试图在用户态执行特权指令
2.软件故障：执行除法时发现除数为0
3.硬件故障：缺页
4.系统调用：应用程序想要操作系统 内核为其提供服务，此时会执行一条特殊的指令—陷入指令(trap)，该指令会引发一个内中断信号

二：外中断(中断)
时钟中断 I/O请求中断
中断：信号来自于CPU外部，也就是和当前执行的指令无关
1.时钟中断：时钟部件会每隔一个时间片给CPU发送一个时钟中断信号，防止某些程序长时间抢占CPU
2.I/O请求中断：输入输出处理完成后，相关设备发送一个中断信号，希望处理机可以向设备发出下一个输入输出请求，同时也让输入输出后的程序继续运行

3.中断的处理过程

1.关中断：为了保护中断现场期间不被新的中断请求大端的，必须关中断，从而保证被中断的程序在中断执行完成后能够接着正确的执行
2.保存断点：保证中断完成后可以正确返回原程序，就是保存原程序的断点(PC的内容)保存起来
3.中断服务程序寻址：取出中断服务程序的入口地址传给PC
4.保护现场：保存通用寄存器和状态寄存器的内容(即保存ACC寄存器的值)，以便返回原程序可以恢复CPU的环境，可以使用堆栈，可以使用特定的存储单元
5.中断服务：主体部分，如通过程序控制需要打印的字符代码送入打印机的缓冲寄存器(中断服务过程中有可能会修改ACC寄存器的值)
6.恢复现场：通过出栈指令或取数指令把之前保存的信息送回寄存器(把原程序算到一般的ACC值恢复原样)
7.中断返回：通过中断返回指令回到原程序断点处

7.系统调用

1.系统调用：操作系统向上提供的一些接口，其中供应程序使用的叫做程序接口，也叫系统调用，系统调用可以理解为可以供程序调用的特殊函数

2.系统调用的过程
发出系统调用的请求是在用户态下，对系统调用的处理在核心态下
1.传递系统调用参数
2.执行陷入，进入中断
3.执行系统调用
4.返回应用程序

3.系统调用的种类
按照功能：
设备管理 文件管理 进程控制 进程通信 内存管理

8.操作系统体系结构

1.操作系统的内核：时钟管理，中断管理，原语，对系统资源进行管理
时钟管理：实现计时功能
中断管理：负责实现中断机制
原语：具有原子性，运行只能一气呵成，不可中断的最接近硬件部分，操作系统最底端的特殊程序，运行时间短，调用频繁
对系统资源的管理：存储器管理，设备管理，进程管理
2.操作系统的体系结构
1.大内核和微内核

2.分层结构
分层结构：将操作系统分为若干层，最底层是硬件，最高层是用户接口，每一层只能调用紧邻它的低层的功能和服务

优点：便于系统的调试和验证，（从最底层开始一层一层调试，不需要考虑其他部分），易于扩充和维护(需要在操作系统中增加，修改一层中的模块或者整层时，只要不改变相应层间的接口，就不会影响其他层)
缺点：仅仅可以调用相邻低层，难以合理定义各层的边界，效率低，不能跨层调用，系统调用执行时间长

3.模块化
模块化：将系统功能按功能分为若干具有独立性的模块。每个模块具有某一方面的管理功能，规定好各个模块之间的接口，模块之间可以通过接口进行通信，衡量模块之间的独立性主要是内聚性和耦合性两个标准

内聚性：模块内部各个部分间联系的紧密程度，内聚性越高，模块独立性越好
耦合性：模块之间相互联系和相互影响的程度，耦合度越低，模块独立性越好

操作系统模块化后：内核=主模块+可加载内核模块
优点：
模块之间的逻辑清晰，确定好模块之间的接口后，可以实现多模块同时开发，支持动态加载新的模块
缺点：模块之间接口定义未必合理实用，模块之间相互依赖，难以调试和验证

4.外核
内核负责进程调度，进程通信等功能，外核负责为用户进程分配未经抽象的硬件资源，且保证资源实用安全
未经抽象的硬件资源：没有经过操作系统映射的资源
优点：用户进程可以更加灵活地使用硬件资源，减少了硬件资源的映射层，提升了效率
缺点：降低了系统的一致性，使得系统变得更加复杂

9.操作系统的引导

1.

安装了操作系统的磁盘的组成：主引导记录和实际存储内容区域
主引导记录：
1.磁盘引导程序：根据分区表读入C盘，找到引导记录PBR
2.分区表：是一个数据结构，说明每一个盘占用的空间大小和地址范围
实际存储内容区域会划分为多个盘符，c盘，d盘这些。
C盘有三部分组成：C盘用于安装，启动操作系统
1.引导记录PBR：负责找到启动管理器
2.根目录
3.其他
操作系统最终会被加载进入主存，主存由RAM和ROM构成，其中RAM断电后数据不复存在，而ROM则反之，所以会在ROM设置一个特殊的程序—自举程序，从此完成操作系统的引导
引导过程：

2.虚拟机
虚拟机：虚拟化技术，将一台物理机器虚拟化为多台虚拟机，每个虚拟机可以独立运行一个操作系统。
第一类虚拟管理程序：直接运行在硬件上
第二类虚拟管理程序：直接运行在宿主操作系统

二：进程管理

考点：
1.引起进程创建的事件有：用户登陆，作业调度，提供服务，应用请求；设备分配是通过系统中设置相应的数据结构实现的，不需要创建进程
2.进程从就绪态转化为运行态不应该立马降低优先级，应该等进程时间片用完再降低，降低优先级别不一定发生，但是状态一定要改变
3.进程控制块PCB，线程控制块TCB，进程是资源分配的基本单位，线程是调度的基本单位，同一个进程的线程共享进程的地址空间；父进程和子进程共享一部分资源，但不能共享虚拟地址空间，可以并发执行，
4.执行态到阻塞态：请求某种资源(不包括处理机资源)或等待输入输出 ，阻塞被唤醒：进程等待的资源可用时 执行态到就绪态：被剥夺了处理机资源
5.多线程模型中，用户级线程和内核级线程的连接方式分为多对一，一对一，多对多，操作系统为每个用户级线程建立一个线程控制块
6.进程调度算法;
1.综合考虑进程等待时间和执行时间的是：高响应比优先调度算法R=(等待时间+要求服务时间)/要求服务时间
2.满足短作业优先且不会发生饥饿现象的是：高响应比优先，长作业没有得到响应，随着等待时间变长，响应比也会变大，最终得到响应，而非抢占式短作业优先，会导致饥饿现象，
7.处理机调度：不能进行处理机调度的几种情况：
1.处理中断的过程
2.进程在操作系统内核临界区(普通临界区还是可以调度)。
3.其他需要完全屏蔽中断的原子操作过程中。如加锁，解锁，中断现场保护，恢复等原子操作
8.合理的设置进程优先级：应该将进程的CPU时间和I/O时间做综合考虑，对于CPU占用时间较少而I/O占用时间较多的进程，优先调度可以让I/O更早的得到使用，提高了系统的资源利用率，显然应该具有更高的优先级
9.临界互斥方法：单标志法，双标志先检查，双标志后检查，皮特森算法
总结：只有使用记录型信号量才可以实现让权等待
满足循环条件，就一直循环，无法访问临界区，不满足循环条件，就可以访问临界区
经常考皮特森算法：能保证互斥进入临界区，不会出现饥饿现象

1.进程和线程

1.进程的引入：为了更好的管理，描述程序，进程是一个抽象概念，如果把程序比作一个学生，那么进程就是学生的综合测评表，操作系统(学校)通过综合测评表(进程)来管理学生(程序)
2.进程和程序
程序：是一个静态的概念，本质是放在磁盘中的可执行文件，进程：是一个动态概念，是程序的一次执行过程
QQ是一个程序，打开三次就是三次进程

3.进程控制块PCB(本质是一个数据结构)
每个进程对应一个PCB，PCB是进程存在的唯一标识，操作系统把对进程这种抽象概念的管理转化为了对PCB这种数据结构的管理

4.进程的组成
1.进程的组成：PCB，程序段，数据段这三个部分组成，PCB是操作系统用的，数据段和程序段是进程自己使用的
PCB：操作系统对进程管理所需要的信息
程序段：包含程序指令
数据段：包含程序运行时产生的各种数据

2.进程的定义
进程是进程实体的运行过程，是系统进行资源分配和调度的独立单位

5.进程的特征
动态性 并发性 独立性 异步性 结构性

6.进程的状态
进程的状态：进程在其生命周期内，由于系统中各个进程之间的制约关系及系统运行环境的变化，所以进程的状态也在不断发生变化，进程通常有五种状态，前三种是基本状态
1.运行态：进程正在处理机上运行，占有CPU
2.就绪态：已经具备运行的条件，但是由于没有空闲的CPU，从而不能运行，系统中处于就绪状态的进程可能有多个，通常将他们排成一个队列，称为就绪队列
3.阻塞态/等待态：进程正在等待某一事件而暂停运行，该状态下，即使处理机空闲，该进程也不能投入运行。
4.创建态：进程正在被创建，尚未被转到就绪态
5.结束态：进程正在从系统中消失，可能是进程正常结束或其他原因中断退出运行

7.进程的状态转换

运行态到就绪态：时间片到了，让出处理机
运行态到阻塞态：发生请求资源的分配或者事情的发生(中断和异常)
阻塞态到就绪态：请求的资源或者事件发生(I/O操作的结束或中断结束)
注意：
1.运行到阻塞是进程自身的主动行为，阻塞到就绪不是进程自身可以控制的，是一种被动行为
2.阻塞态不能直接转为运行态，就绪不能直接转为阻塞态
阻塞–>就绪----->运行 就绪—>运行----->阻塞

8.进程的组织方式
1.链接方式：按照进程的状态将PCB分为多个队列，操作系统持有各个队列的指针

2.索引的方式
根据进程状态的不同，建立几张索引表，操作系统持有指向各个索引表的指针

9.进程的控制

1.进程的控制：就是如何实现进程的状态转换-----原语
**2.为什么使用原语来控制进程的转换：**进程的控制是一个复杂的过程，整个过程需要一气呵成，不能中断，所以依靠原语实现。
3.完成进程状态转换需要两步：
1.修改PCB中用于标识目前状态的变量state
2.将进程投递到相应的队列
4.原语的原子性如何实现的：依靠开中断，关中断两条特权指令实现的，CPU每执行完一条指令后，会例行检查中断指令，如果有中断指令，则会暂停运行当前的程序，转而执行相应的中断处理程序，当CPU执行了关中断指令后，就不再检查中断信号了，直到执行开中断指令后才会恢复检查，这样一来，关中断开中断之间的指令序列是不可被中断的，实现了原子性。
5.进程的控制原语：
1.进程的创建： 申请空白PCB—>为新进程分配所需要的资源—>初始化PCB----->将PCB插入就绪队列
2.进程的终止:终止改进程和其子进程将所有资源归还给操作系统和其父进程，将其PCB从队列中删除
3.进程阻塞:保护现场，将其状态转换为阻塞态，将PCB插入相应事件的等待队列，将处理机资源调度给其他就绪进程
4.进程唤醒：在等待队列中找到相应的进程的PCB，将其从等待队列中移除，将其状态设置为就绪态，PCB插入就绪队列，等待调度程序调度
5.进程切换：引起的事件有：当前时间片已到；更高优先级的进程到达；当前进程主动阻塞；当前进程终止
过程：1.保存处理机上下文，包括程序计数器和其他寄存器 2.更新PCB信息 3. 把进程的PCB移入相应的队列，如就绪，在某事件阻塞等队 4.选择另一个程序进程执行，并且更新其 PCB 5.更新内存管理的数据结构 6.恢复处理机上下文

10.进程的通信
1.独立性和交互：进程具有独立性，每个进程拥有各自的独立的地址空间，进程间数据互不干扰，所谓进程的通信就是让数据产生交互。
2.进程通信的目的
数据传输 资源共享 通知事件 进程控制
3.实现进程通信的三种方式
共享存储 消息传递 管道通信
1.共享存储：让它们的页表映射到同一片存储空间，这样就可以进程通信了，被映射的区域称为共享存储区，各个进程对共享空间的访问是互斥的
2.消息传递：
进程之间的数据交换以格式化的消息为单位，进程通过操作系统提供的发送消息/接收消息两个原语进行数据交换
消息由两个部分组成：消息头：包括发送进程ID，接受进程ID，消息长度等格式化信息
消息体：消息的主题内容
消息的传递方式：
1.直接通信方式：消息的发送进程直接指明进程的ID

2.间接通信方式：内存中划分出若干个区域，称为信箱，作用是暂存某个进程发送来的消息，多个进程可以向同一个信箱发送信息，也可以从同一个信箱接受信息。

3.管道通信
管道的本质是一个文件，管道有写端：进程通过写端写入数据，有读端，进程要通过读端读入数据
管道需要两个文件描述符控制读端和写端，只有文件描述符打开，读写才能进行。

11.线程的概念
1.什么是线程：线程是一个执行流，处在进程的地址空间内，进程和线程的关系是1：n，引入线程后，进程是资源分配的基本单位，线程是调度的基本单位。
2.引入线程后带来的变化
资源分配和调度方面：引入之前：进程是资源分配和调度的基本单位，引入之后：进程是资源分配的基本单位，线程是调度的基本单位
并发性：引入前进程可以并发，引入后线程之间可以并发，提高了并发度
切换的系统开销：进程切换的系统开销大于线程的切换
3.线程的属性
多CPU计算机中线程可以占用不同的CPU，
每个线程有一个线程ID，线程控制块TCB，
线程也有就绪，阻塞，运行三种基本状态
线程几乎不拥有资源，同一进程的不同线程之间共享进程的资源
同一进程中不同线程的切换不会引起进程的切换，不同进程之间线程的切换会引起进程的切换，切换同进程的线程，系统开销很小
4.线程的优点缺点
优点：创建线程代价小于进程，线程切换操作系统做的工作少，线程占用的资源比进程少
缺点：健壮性降低(线程是进程的执行分支，一个线程出现异常，其实进程也出现了异常从而触发了信号机制，终止进程，进程一旦终止，资源都没有了，所有线程都会全部退出)，性能损失，编程难度提高，缺乏控制访问

5.进程和线程的对比
引入进程：为了可以让多道程序并发执行，提高资源的利用率和系统的吞吐量
引入线程：为了减小程序在并发执行付出的时空开销，提高操作系统的并发性能
线程共享进程的数据，但是也有自己的一部分数据：一组寄存器，栈

三个进程指向一份地址空间，三个进程组成一个进程，每个进程都是这个组成的进程的执行流

12.线程的实现方式和多线程模型

1.线程的实现方式：
一：用户级线程
应用程序通过线程库实现，所有的线程管理工作由应用程序负责。
线程切换在用户态就可以完成，不需要改变状态

用户级线程优点：用户级线程切换在用户空间就可以，不需要切换到核心态，线程管理开销小，效率高。
用户级线程的缺点：当一个用户级线程被阻塞后，整个进程都会被阻塞，并发度不高，多个线程不可在多核处理机并行运行。
2.内核级线程
线程管理工作在操作系统内核完成，线程调度，切换工作均由内核完成，各项工作需要在核心态下才能完成。

内核级线程优缺点：
优点：当一个线程被阻塞，别的线程还可以继续执行，并发能力强，多线程可以在多核处理机上并行执行
缺点：一个用户进程会占用多个内核级线程，线程管理成本高
2.多线程模型
在同时支持用户级和内核级线程的系统中，由几个用户级线程映射到几个内核级线程的问题引出了多线程模型的问题
1.一对一模型
一个用户级线程映射到一个内核级线程，

2.多对一模型
多个用户级线程映射到一个内核级线程

3.多对多模型
优点：克服了多对一 模型中并发度不高的问题，克服了一对一模型中用户进程占用太多内核级线程

3，线程的状态和转换

和进程的状态转换基本一致

4.线程的组织和控制
线程的 组织和控制和进程的组织和控制基本一致，也有与之对应的数据结构，即线程控制块TCB

2.进程的调度，分类及其调度算法

1.调度的基本概念
多道程序体系中，进程数量大于处理机的个数，所以会出现进程争用处理机，调度就是以满足系统目标的方式通过一定的算法，把进程分配到一个或多个处理机上执行，实现进程的并发执行。
2.调度的层次

高级：创建 中级：就绪 低级：运行
从本质上说：调度属于队列管理问题
3.调度的时机
一：需要进程调度与切换的情况
(1)当前进程主动放弃处理机
进程正常终止；运行中发生异常终止，进程主动请求阻塞
(2)当前进程被动放弃处理机
分配给进程的时间片用完；有更紧急的事情需要处理；有更高优先级的进程进入就绪队列
二：不能进行进程的调度和切换的情况
进程在操作系统内核程序临界区；原子操作中，原则操作不可中断，需要一气呵成；进程在操作系统内核程序临界区中
4.调度的方式
1.非抢占式调度：允许进程主动放弃处理机，即使有更紧迫的任务到达，当前进程仍然会使用处理机，直到该进程终止或主动要求进入阻塞态，适合早期的批处理系统
2.抢占式调度：如果有一个优先级更高的进程需要使用处理机，立刻暂停正在执行的进程，将处理机分配给优先级更高的进程，适合实时操作系统。
5.进程的切换和过程
(1)进程的切换：
进程的切换主要完成：对原来进程 的各种数据进行保存；对进程的各种数据进行恢复
(2)进程的调度的广义和狭义
狭义的调度：从就绪队列选择一个要运行的进程
广义的调度：包含选择一个进程和进程切换两个步骤
6.调度器(调度程序)
调度器：进程的就绪和运行状态之间的转换是由调度程序引起的，主要决定以下两件事情：调度算法和时间片大小
触发调度程序：
1.创建新进程
2.进程退出
3.运行进程阻塞
4.I/O中断发生
注意：
对于非抢占式调度策略：只有进程的阻塞或者退出时才会触发调度程序工作
对于抢占式调度策略：每个时钟中断或者k个时钟中断会触发调度程序工作
7.闲逛进程
他是调度进程永远的备胎，没有其他进程就绪时，会进行闲逛进程
特性：优先级最低，能耗低，可以是零地址，占一个完整的指令周期
8.调度算法的评价指标
1.CPU占用率：CPU处于忙碌状态的时间占比
2.系统吞吐量：单位时间CPU完成作业的数量
3.周转时间：作业提交到作业完成所经历时间
4.等待时间：进程处于等待处理机状态的时间和
5.响应时间：用户提交请求到系统首次产生响应所用的时间

9.调度算法详细解析
饥饿现象：进程长时间得不到服务，如果一直得不到服务，称之为饿死
**周转时间：**完成时间-到达时间
带权周转时间：周转时间/运行时间
**等待时间：**周转时间-运行时间
**平均周转时间：**所有时间周转时间之和/进程数
一：先来先服务(FCFS)
先来后到：对长作业有利，对短作业不利，适合CPU繁忙型，不适合I/O繁忙型。
饥饿现象：不会
非抢占式


周转时间：P1=7 P2=9 P3=8 P4=11
等待时间：P1=0 P2=5 P3=7 P4=7
带权周转时间：P1=1 P2=2.25 P3=8 P4=2.75

二：最短作业优先调度
要求服务时间最短的作业/进程得到服务，可以用于作业调度**，每次选择当前已经到达且时间最短**

对短作业有利，对长作业不利
会导致饥饿现象
非抢占式(抢占式是最短剩余时间)
三：最短剩余时间优先
新达到的进程的剩余时间比当前运行的进程的剩余时间更短，那么由新进程抢占处理机，被抢占的就会回到就绪队列。

抢占式，会饥饿
四：高响应比优先调度算法

非抢占式
P1到达先上处理机，7后P1主动放弃处理机，此时就绪队列中P2响应比=2.25，P3的响应比：4
P4响应比：1.5 (这里的等待时间是默认自己是下一个响应的)

五：时间片轮转调度法
轮流，公平的为各个进程服务，进程未在一个时间片完成，则剥夺处理机，然后放入就绪队列重新排队
抢占式算法
不会导致饥饿的现象
时间片大小的影响：
时间片太大：就和先来先服务算法一样，
时间片太小：会导致频繁切换，系统会花大量时间来处理进程的切换
六：优先级调度算法
分为抢占式和非抢占式，优先级的数字越大，优先级越高
进程优先级的设置原则：
系统进程大于用户进程；交互进程大于非交互进程；I/O密集进程大于计算密集进程
优缺点：
优点：可以用于实时操作系统，灵活调整各种作业/进程的偏好程度
缺点：有可能导致低优先级进程得不到运行
会导致饥饿现象
七：多级反馈队列调度算法
多级：表示有多个队列，每个队列优先级从高到低，优先级越高，时间片越短
反馈：如果有新的进程加入优先级高的队列，立刻停止当前正在运行的进程，转而去运行优先级高的队列

3.进程同步和互斥，信号量及经典进程同步问题

1.进程同步和互斥的基本概念
一：进程同步
进程同步又叫做直接制约关系，它 是指为了完成某种任务而建立的两个或者多个进程，这些进程因为需要在某些位置上协调工作次序而产生一种制约关系
二：进程互斥
临界资源的访问过程分为四个部分
进入区：负责检查是否可以进入临界区，如果可以进入，应该设置正在访问临界资源标识，也就是上锁，以防止其他进程同时进入临界区
临界区：访问临界资源的那段代码
剩余区;做其他处理
进程互斥叫做间接制约关系，就是对临界资源的互斥访问，遵循以下原则：
空闲让进：临界空间空闲时，可以允许一个请求进入临界区的进程立刻进入临界区
忙则等待：对于已经有进程进入临界区，其他试图进入临界区的进程必须等待
有限等待：对于请求访问的进程，应该保证在有限时间内进入临界区，也就是不能饥饿
让权等待：当进程不能进入临界区域时，应该立即释放处理机，防止进程处于忙则等待
2.实现进程互斥的软件方法
一：单标志法
每个进程进入临界区的权限只能被另一个进程所赋予，该算法可以实现同一时刻最多只允许一个进程访问临界区
方法：设置一个公用整形变量turn，用于指示被允许进入临界区的进程编号

turn=0 p1允许进入临界区 turn=1 p2允许进入临界区
缺陷：违反了空闲让进原则，对于临界区的访问是p1->p2->p1->p2…的顺序，如果p1一直不访问临界区，虽然临界区空闲，但是不允许p1访问
二：双标志先检查法
设置一个布尔型数组flag[]，用于标志各个进程是否想要进入临界区，比如flag[0]=true表示p0想进入临界区，每个进程想进入临界区时先检查当前有没有别的进程想进入临界区，如果没有把自己的标志设置为true，之后开始访问临界区。

缺陷：违反了忙则等待，如果两个进程是并发的就会打折两个进程同时访问临界区
三：双标志后检查法
先上锁后检查，和双标志检查法差不多，就是先上锁后检查，
缺陷：违背了空闲让进和有限等待，这种算法可能导致两个进程都没有办法访问临界区，导致饥饿现象。

上锁：标志自身为true,flag[i]=TRUE,检查：检查另一个标志是否为TRUE,while(flag[j])
四，Petersion算法
算法思想：为了防止两个进程为了进入临界区而无限等待，又设置了一个变量，每个进程先设置自己的标志再设置turn标志，在同时检查另一个进程状态标志和不允许进入标志，以保证两个进程同时要求进入临界区时，只允许一个进程进入临界区

第二行检查 的是另一个进程的不允许进入的标志，如果turn=0，这是表示优先P0进入临界区
遵循：空闲让进，忙则等待，有限等待三个原则
缺陷：没有遵循让权等待，上面P1不能进入临界区，还是会卡在while循环，不能释放处理机，使得处理机处在了忙等状态

while();这个语句，如果内部的条件为TRUE,则保持循环状态
3实现进程互斥的硬件方法
一：中断屏蔽方法
思想：当一个进程正在使用处理机执行他的临界区代码时，为了防止其他进程进入临界区进行访问，暴力禁止一切中断发生，称之为屏蔽中断，关中断。因为CPU只在发生中断时引起进程的切换

优缺点：
优点：简单，高效，
缺点：不适合多处理机，限制了处理机交替执行程序的能力，而且只适合内核进程，不适合用户进程，因为开关中断指令属于特权指令
二：TSL
思想：为每个临界资源设置共享布尔变量lock，lock=true表示正在被占用，初值设置为flase。在进程访问临界资源之前，利用teatandset检查和修改标志lock，如果有进程在临界区，则重复检查，直到进程退出。
teatandset：这是一个原子操作，执行过程中不会被中断，使用硬件实现，
优点：实现简单，吧上锁和检查操作使用硬件方式编程了原子操作
缺点：不满足让权等待，无法进入临界区，会占用cpu执行循环tsl
三：swap指令
为临界资源设置一个共享布尔变量lock，lock=true表示正在被占用初始值设为false，然后再每个进程中再设置一个局部变量key，用于和lock交换信息，再进入临界区前，先利用swap指令交换lock和key的内容，然后检查Key的状态，在进入临界区时，重复交换和检查过程，直到进程退出。

优点：实现简单，适合多处理机制，
缺点：不满足让权等待
4.信号量机制
可以从上面知道，无论是硬件还是软件方法都没有办法解决让权等待的问题，而信号量则是一种功能较强的机制，可以有效的互斥与同步的问题
一：信号量定义
信号量：本质是一种变量，表示系统中某种资源的数量，控制信号量有两种原子操作，P操作，V操作
P操作(wait原语)：这个操作会把信号量减去1，相减后如果信号量**<0则表示资源已经被占用，进程需要阻塞**，相减后，如果信号量>=0，表明还有资源可以使用，进程可以正常执行
V操作(signal原语)：这个操作会把信号量加一，想加后如果信号量<=0，则表明当前有阻塞的进程，于是会把该进程唤醒，相加后如果信号量>0，则表明当前没有阻塞中的进程
二：整型信号量
使用一个整型变量作为信号量，用来表示系统中某种资源的数量。比如某种资源S初始为1

int S=1;//初始信号量，表示当前系统中可用资源数

void wait(int S){//wait原语相当于进入区
	while(S<=0);//如果资源数不够，就一直循环等待
	S=S-1;//如果资源数够，就占用一个资源
}

void signal(int S){//signal原语，相当于退出区
	S=S+1;//使用完资源后释放资源，也即归还
}

1
2
3
4
5
6
7
8
9
10
11

缺点;不满足让权等待，会发生忙等待
三：记录型信号量
除了需要使用一个代表资源数目的整形变量value外，还需要增加一个进程链表L，用于链接所有等待该资源的进程，使用一个指针的指向。
该数据结构：

typedef struct
{
	int value;//剩余资源数目
	struct process* L;//等待队列
}semaphore;

1
2
3
4
5
6

对应的P和V操作
1.进程需要用到资源时，进行的P操作

void wait(semaphore S)
{
	S.value--;//进行P操作，资源数量减一
	if(S.value < 0)
	{
		block(S.L);//<0时代表资源已经是使用完了。所以使用block原语将进程从运行态转化为阻塞态，并将其挂到信号量为S的阻塞队列中
	}
}

1
2
3
4
5
6
7
8
9

2.进程使用完进程的资源时，需要进行V操作

void signal(semaphore S)
{
	S.value++;
	if(S.value<=0)
	{
		wakeup(S.L);
	]
	
}

1
2
3
4
5
6
7
8
9
10

总结：只有使用记录型信号量才可以实现让权等待
5.用信号量实现进程互斥，同步和前驱的关系
一：使用信号量实现进程互斥
1.分析并发进程的关键活动，划定临界区
2.设置互斥信号量mutex，初值设置为1
3.在临界区之前执行P操作
4.在临界区之后执行V操作

semaphore mutex=1;//互斥信号量
P1()
{
	//其他代码
	P(mutex);//进入临界区前加锁
	临界区代码
	V(mutex);//退出临界区时要解锁

}

P2()
{
	//其他代码
	P(mutex);//进入临界区前加锁
	临界区代码
	V(mutex);//退出临界区时要解锁

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

进程P1在访问临界资源前，先执行了P操作，由于信号量初值mutex=1，所以P1在执行完P操作后MUTEX=0，P1访问临界资源
此后进程P2也想要访问临界资源，执行P操作后，其mutex变成了-1，表明系统中已经没有可以分配的资源，所以执行block原语，被阻塞
P1访问完临界资源后，执行V操作，信号量恢复，即mutex=0，然后使用wakeup原语唤醒阻塞中的P2，并且把资源分配给它
这里面的P和V都是上面的记录型信号量中的函数
注意：1.对于不同的临界资源需要设置不同的互斥信号量。比如资源A和资源B可以设置为互斥信号量mutex1,mutex2。
2.一定要注意P,V操作必须成对出现
缺少P操作：不能保证临界资源的互斥资源
缺少V操作：导致资源永远不会释放，继而等待进程永远不会被唤醒
二：使用信号量实现进程同步
必须保证一前一后执行两个操作
设置同步信号量s，初值0，
在必须要先执行的操作之后执行V操作；在必须要后执行的操作之前执行P操作

这里期待代码1代码2在代码4之前执行
semphore S=0;//同步信号量

P1()
{
	代码1；
	代码2
	V(S);
	代码3;
}

P2()
{
	P(S);
	代码4；
	代码5
	代码6;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

1.P2的方法先执行：如果先执行P操作，表明P2优于P1执行，这不是期望的顺序，此时，由于s=0，执行P操作后s=-1，此时P2会执行block语句进行阻塞，P1执行完之后，进行V操作，此时S++，所以s=0，所以P1会执行wakeup原语，唤醒p2进程，这样就实现了同步
2.P1的方法先执行：先执行了V操作，P1会优先于P2进行，此时即可正常进行，执行V后执行p不会发生阻塞的情况
三：使用信号量实现前驱关系
前驱关系就是实现多组进程的同步关系
思想：
为每一对前驱关系各设置一个同步变量；在必须要先执行的操作之后对相应的同步变量执行v操作
在必须后执行的操作之前对相应的同步变量执行P操作

P1()
{
	...
	S1;
	V(a);
	V(b);
	...
}
P2()
{
	...
	P(a);
	S2;
	V(c);
	V(d);
	...
}
P3()
{
	...
	P(b);
	S3;
	V(g);
	...
}
P4()
{
	...
	P(c);
	S4;
	V(e);
	...
}
P5()
{
	...
	P(d);
	S5;
	V(f);
	...
}
P6()
{
	...
	P(e);
	P(f);
	P(g);
	S6;
	...
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

总结：互斥P在前，V在后 ；同步V在前P在后
总结：进程互斥和同步都是由于资源有限的问题，进程的调度算法是按照某种策略从就绪队列中选取一个进程，将处理机分配给它

6.经典同步问题之生产者和消费者问题

3种关系，2个角色，1个场所
3个关系：生产者和生产者是互斥的，消费者和消费者是互斥的，生产者和消费者是同步的
2个角色：生产者和消费者
1个场所：他们之间数据的交互是在一个缓冲区中，这个缓冲区可以有多种表现形式

分析：
消费者生产者问题是一类很经典的需要使用信号量(P,V操作)来完成互斥和同步的例子，这里PV操作题目分析步骤如下：
分析同步和互斥的关系：
同步关系：生产者想要放数据必须等待缓冲区没有满，消费者想要取数据必须等待缓冲区没有空
互斥关系：缓冲区作为临界资源，各进程必须互斥访问(每一个进程，不管消费者还是生产者)；缓冲区放入/取走产品需要互斥
思路
这里注意生产者放入的是数据，但是数据会占用资源，所以生产者放入数据实则是资源减少过程，同时消费者拿掉数据实则是归还资源的过程
生产者每次消耗§一个缓冲区，并且生产(V)一个产品；消费者每次消耗§一个产品，并且释放(V)一个缓冲区
设置信号量
互斥信号量：初值一般设置为1；
同步信号量：初值要看对应资源的初始值是多少

semaphore mutex=1;互斥信号量，实现对缓冲区的互斥访问
semaphore empty=n;同步信号量，表示空闲缓冲区数量
semaphore full=0;同步信号量，表示非空闲缓冲区数量，也就是产品数量


1
2
3
4
5

信号量设置很重要：互斥mutex=1，进程实现同步s=0,同步信号量，表示空闲缓冲区数量empty=n,上面也表示了互斥信号量初值一般是1，而同步信号量的初值的设置需要根据情况来定
具体代码
实现同步：
生产者：将产品放入缓存区之前需要执行P(empty)以消耗一个空闲缓冲区，放入缓冲区之后需要执行V(full)以增加一个产品数量
消费者：从缓冲区取出产品之前需要执行P(full)以消耗一个产品，从缓冲区取出产品后需要执行V(empty)以增加一个空闲缓冲区
实现互斥：
生产者：将产品放入缓冲区前需要执行P(mutex),放入缓冲区之后需要执行V(mutex)
消费者：从缓冲区取出产品需要执行P(mutex),从缓冲区取出产品后需要执行V(mutex)

semaphore mutex=1;互斥信号量，实现对缓冲区的互斥访问
semaphore empty=n;同步信号量，表示空闲缓冲区数量
semaphore full=0;同步信号量，表示非空闲缓冲区数量，也就是产品数量

Producer()
{
	while(1)
	{
		//生产者生产数据
		p(empty);要用什么，P一下    //获取空缓冲区
		p(mutex)：互斥夹紧
		//将数据放入缓冲区
		V(mutex)：互斥夹紧
		V(full)：提供什么，V一下    //产品数量增加
	}
}

Consumer()
{
	while(1)
	{
		p(full);要用什么，P一下    //获取产品
		p(mutex)：互斥夹紧
		//消费者取出产品
		V(mutex)：互斥夹紧
		V(empty)：提供什么，V一下    //空缓冲区增加
		//消费者使用数据
	}

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

注意：
1.实现互斥的P操作一定要在实现同步的P操作之后，如果顺序相反，会导致两个进程同时阻塞，但是都希望对方唤醒自己
2,V操作顺序可以交换，不会导致阻塞

7.经典同步之多生产者与多消费者问题
一：问题描述

二：问题分析

互斥关系：爸爸妈妈是互斥关系，他们对于缓冲区，也就是盘子的访问需要互斥进行
同步关系：爸爸和女儿， 母亲和儿子是同步关系，这两对进程必须连起来
儿子和女儿没有关系，盘子为空的事件可以由儿子或女儿触发，事件发生后才允许父亲或母亲放水果


代码的实现：

semaphore plate=1;//盘子中还可以放多少个水果
semaphore apple=0;//盘子中有几个苹果
semaphore orange=0;//盘子中有几个句子

dad()
{
	while(1)//就是plate=1时
	{
		准备一个苹果；
		P(plate);//互斥放水果
		向盘子中放苹果；
		V(apple);//可以取苹果	
	}
}
mom()
{
	while(1)
	{
		准备一个橘子；
		P(plate);//互斥放水果
		向盘子中放橘子；
		V(orange);//允许取橘子	
	}
}

son()
{
	while(1)
	{
		P(orange);//互斥从盘子中取橘子
		取橘子
		V(plate);//取完归还盘子
		吃橘子
	}
}

daughter()
{
	while(1)
	{
		P(apple);//互斥从盘子中取苹果
		取苹果
		V(plate);//取完归还盘子
		吃苹果
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

注意

8.经典同步之吸烟者问题
一：问题描述


二：问题分析


三：代码实现

semaphore offer1=0;//组合一的数量
semaphore offer2=0;//组合二的数量
semaphore offer3=0;//组合三的数量
semaphore finish=0;//抽烟是否完成
int i=0;//用于实现轮流抽烟
对于生产者，通过取余的方式轮流放置组合一，组合二和组合三，放置完成之后如果消费者不执行V(finish),他将会在P(finish)被阻塞
provider
{
	while(1)
	{
		if(i==0)
		{
			组合一放桌子上
			V(offer1);
		}
		else if(i==1)
		{
			组合二放桌子上
			V(offer2);
		}
		else if(i==2)
		{
			组合三放桌子上
			V(offer3);
		}
		i=(i+1)%3;
		P(finish);
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

对于三个消费者，首先检查是否有自己的组合，如果没有就会被阻塞，如果有，执行完毕后使用V(finish)通知生产者生产
smoker1()
{
	while(1)
	{
		P(Offer1);
		一系列卷烟、抽烟操作、拿走组合一
		V(finish);
	}
}
smoker2()
{
	while(1)
	{
		P(Offer2);
		一系列卷烟、抽烟操作、拿走组合二
		V(finish);
	}
}

smoker3()
{
	while(1)
	{
		P(Offer3);
		一系列卷烟、抽烟操作、拿走组合三
		V(finish);
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

9.经典同步问题之读者写者问题



代码实现：

int count=0;
semaphore mutex=1;
semaphore rw=1;
semaphore w=1;//用于实现写优先


writer()
{
	while(1)
	{
		P(w);
		P(rw);//写之前加锁
		写文件;
		V(rw);//写之后解锁
		V(w);
	}
}

reader()
{
	while(1)
	{
		p(w);//在无写进程的情况下进入
		P(mutex);//使用P操作保护count，防止多个读进程对临界资源的操作
		if(count==0)
			P(rw);//第一个读进程
		count++;
		V(mutex);
		V(w);
		
		写文件;
		P(mutex);
		count--;
		if(count==0)
			V(rw);//最后一个读进程
		V(mutex);
		
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

10.哲学家进餐问题
一：问题描述


二：问题分析

semaphore chopsticks[5]={1,1,1,1,1};
P i()//i号哲学家进程
{
	while(1)
	{
		P(chopsticks[i]);//拿左
		P(chopsticks[i+1]%5);//拿右
		吃饭
		V(chopsticks[i]);//拿左
		V(chopsticks[i+1]%5);//拿右
		思考
	}

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

三：代码实现

如果哲学家左右筷子都可以拿起来：

11.管程及条件变量
出现的背景：信号量机制中的PV操作在编写程序有一定的困难，有可能造成死锁等严重问题，所以产生了高级同步工具—管程，他保证了进程的互斥，无需程序员自己实现互斥，从而降低了死锁发生的可能性，同时也提供了条件变量，可以让程序员灵活实现进程同步
管程：管理一个或者多个执行程序
一：管程的定义和基本特征
管程是一种特殊的软件模块，

monitor Test//定义了一个名称为"Test"的管程
{
	Data Structure DS;//定义共享数据结构，对应系统中的某种共享资源
	Init_Code()//对共享数据结构初始化语言
	{
		DS=5;//初始资源数目为5
	}
	
	Take_Away()//过程1：申请一个资源
	{
		对共享数据结构的一系列操作
		DS--;//可用资源数目减一
		...
	}
	Give_Back()//过程2：归还一个资源
	{
		对共享数据结构的一系列操作
		DS++;//可用资源数目加一
		...
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

二：条件变量

monitor Test()
{
	Data Structure DS;//定义共享数据结构，对应系统中的某种共享资源
	condition x;//定义了一个条件变量x
	Init_Code(){...}
	
	Take_Away()
	{
		if(DS<=0)
		{
			x.wait();//资源不够，在条件变量x上阻塞的大概
		}
		资源足够，分配资源，做一系列相应处理
	}
	
	Give_Back()
	{
		归还资源，做一系列相应处理
		if(进程在等待)
			x.sginal();//唤醒一个阻塞进程
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

四：死锁和避免死锁

1.死锁基本概念
一：死锁的定义
**死锁：**多个进程竞争资源而造成的一种互相等待的局面，没有外力的作用，这些进程将无法向前推进

死锁和饥饿和死循环：死锁进程等待永远不会被释放的资源，饿死进程等待会被释放但却不会分配给自己的资源，表现为等待时限没有上界(排队等待或忙式等待)，死循环：某进程执行过程中一直跳不出循环；

2.死锁的必要条件
死锁必须满足四个条件(都要满足)：
互斥条件
持有并等待条件
不可剥脱条件
循环等待条件(发生死锁一定有循环等待，发生循环未必死锁)
1.互斥条件
只有对必须互斥使用的资源抢夺时才可能导致死锁。
2.不可剥夺条件
进程在获得资源没有使用完之前，不能由其他进程强行剥夺，只能主动释放
3.持有并等待条件
进程已经至少保持了一个资源，但是又提出了新的资源请求，但是该资源又被其他进程占有，此时请求进程被阻塞，但是对自己持有的资源保持不放
4.循环等待条件
存在一种进程资源的循环等待链，链中的每一个进程已经获得的资源同时被下一个进程所请求
3.死锁产生的原因
对不可剥夺的资源的不合理分配，可能会导致死锁
一：对系统资源的争夺 二：进程推进顺序非法 三：信号量使用不当
4：死锁处理策略
死锁处理策略：
预防死锁：破坏死锁产生的四个必要条件中的一个或者几个
避免死锁：用某种方法防止系统进入不安全状态，从而避免死锁，例如银行家算法
死锁的检测和解除：允许死锁产生，不过操作系统会负责检测出死锁的发送，然后采取某种措施解决死锁

3.死锁处理策略之预防死锁
一：破坏互斥条件
把只能互斥使用的资源改造为允许其共享使用，但是为了系统安全，很多资源都可以改造成为可以共享使用资源的，所以互斥条件一般无法破坏
二：破坏不可剥夺条件
1.即使资源没有用完，但是别的进程请求也要主动释放 2.通过操作系统协助，剥夺资源
三：破坏持有并等待条件
静态分配法：一次申请完所需要的资源
四：破坏循环等待条件
顺序资源分配法：给系统的资源进行编号，规定每个进程必须按照编号递增的顺序请求资源，编号相同的资源一次申请完

4.死锁处理策略之避免死锁(银行家算法)
一：安全状态，安全序列
避免死锁：系统在进行资源分配的时候，应该计算此次分配的安全性，若此次分配不会导致系统进入不安全状态，则允许分配，否则等待。
安全序列：系统按照某种进程推进顺序为每个进程分配其所需的资源，直到满足每个进程资源的最大需求，使得每个进程都可以顺序完成。其中(P1,P2,P3,P4…)称之为安全序列
安全状态：只要能找出一个安全序列，系统就是安全状态。
不安全状态：并非所有不安全状态都是死锁状态，但是系统进入不安全状态，就有可能进入死锁状态，系统处于安全状态，则一定不会进入死锁状态。
二：银行家算法






5.死锁处理策略之检测和解除
一：死锁检测算法：
对系统是否已经发生死锁进行检查，
必须保证某种数据结构来保存资源的请求和分配信息-资源分配图
提供一种算法，利用上述信息来检测系统是否进入死锁状态
(1)资源分配图
两种结点：
进程结点：对应一个进程
资源结点：对应一类资源，数量可能有多个
两种边：
进程结点-》资源结点：进程想要申请多少个资源，每条边代表一个
资源结点->进程结点：表示已经为进程分配了多少个资源，每条边代表一个

(2)死锁定理



二：死锁解除算法

三：内存管理

考点：
1.分区分配内存管理方式的主要保护措施：界地址保护 ；每个进程都有自己独立的进程空间，若进程运行的地址在其地址空间之外，则发生地址越界
2.内存分配：1.单一连续分配(就一道程序占所有，有内部碎片，无外部碎片) 2.固定分区分配(多道程序固定分配，有内部碎片，无外部碎片) 3.动态分区分配 (无内部碎片，有外部碎片)
内部碎片：内存分配给进程的空间没有完全利用完 外部碎片：内存中有剩余空间太小无法利用；紧凑技术：让动态分区没有内部碎片；拼接技术：让动态分区没有外部碎片
3.4种动态分区算法

4.允许进程分配到内存的不同 的地方：非连续分配：基本分页式，基本分段式，段页式
1.分页式：
区别页框，页和页表之间的关系：
操作系统以页框为单位为各个进程分配内存空间，每个页面分别放入一个页框。
页框和页是一 一对应的关系
操作系统为一个进程创建一个页表，一个进程对应一个页表，一个页对应一个页表项，页表中存放着很多页的的页表项(页号+块号)，也即是虚拟页号和物理页号
逻辑地址到物理地址的转换：动态重定位：内存起始地址+逻辑偏移地址
页表项物理地址：页表存储的物理地址+页号*页表项大小

快表TLB：程序局部性原理：访问速度快于主存的高速缓存器，和cache很像

二级页表：页表的页表=页目录表(一级页号)

页目录表中含有的表项的个数：总的页表项数(总的页数)/一个页面可以存储的页表项的个数
多级页表的优点：减少页表所占的连续内存空间
分页回收地址后，如果回收的地址和其他空闲地址相连，那么会重新合并成为一个新的空闲块，并且回收内存后，算法会对空闲分区链按照分区的大小从小到大进行排序
2.非连续之分段式(一个进程对应一个段表)

页号，段号都是连续的，不会占存储空间；分页：空间利用率高，会产生少量内部碎片，不会产生外部碎片 分段：会产生外部碎片、
分页，每一页大小都一样的 分段：段的大小不一样
共享段对于不同的进程P1,P2来说，使用的位置可能不同，所以在不同进程中的逻辑段号可能不同
CPU页表基址寄存器中存放的是当前进程的顶级页表的起始物理地址
3.段页式存储
先分段，再在段中分页

5.程序经过预处理-》编译-》汇编-》链接-》产生可执行文件，经过链接才能装载，链接后形成的目标程序中的地址就是逻辑地址

一：内存基本知识，分配管理方式等

1.内存基础知识，程序编译运行原理





2.内存管理的基本概念








3.覆盖和交换
覆盖和交换是在多道程序的环境下用来扩充内存的两种方法






4.连续分配的管理方式













总结：从上到下为低地址到高地址，分区号也是从低地址的空闲块开始计数



5.动态分区分配算法
这里空闲块都是以循环链表连接的数据结构

6.1非连续分配管理方式----基本分页存储管理














区别页框，页和页表之间的关系：
操作系统以页框为单位为各个进程分配内存空间，每个页面分别放入一个页框。
页框和页是一 一对应的关系
操作系统为一个进程创建一个页表，一个进程对应一个页表，页表中存放着很多页的的页表项(页号+块号)，也即是虚拟页号和物理页号

6.2：非连续分配中基本分页管理----基本地址变换机构


计算页号：进行越界检测，计算偏移量==得到块内地址



6.3：非连续分配管理方式—基本分页存储管理—具有快表的地址变换机构
一;程序访问局部性原理




6.4非连续分配管理—基本分页存储管理–两级页表



页表的页表：页目录表

因为第12位表示偏移地址，所以一个内存块大小有2^12位

7.非连续分配管理方式----基本分段管理方式


这里记录详细因为页的大小是一定的，段的大小不一定






8.非连续分配管理方式-----段页式管理

4.2：虚拟内存，请求分页和页面置换算法

考点：
1.虚拟内存：基于非连续式内存分配的基础上，分段，分页，段页式；非一次性装入内存，之前进程都是一次性装入内存
2.页表机制，缺页中断机制，地址变换机构

3.五种页面置换算法

OPT：最佳置换算法：不可能实现，操作系统事先不会知道要访问的序列，实现：从访问序列最后找最后一个被访问到的页面进行替换
FIFO：先进先出：优先淘汰最先进入内存的页面；从队首开始替换，可能出现Belady异常：最先调入的页面往往是最经常访问的页面，所以使用先进先出算法会导致分配页面数增多但是缺页率反而提高的现象
LRU：设置t，每一次访问没有访问到t+1;选择t最大的进行 替换；也可以使用快捷法：对页号从后往前计数，数到页框数个不同的数字为止
CLOCK：时钟置换算法：t=0;表示最近没有访问过，置换 t=1表示最近访问过，置0，跳过，选择别的页面
改进型CLOCK：淘汰的优先级别：(0,0) (0,1) (1,0) (1,1)
缺页数=置换数+分配的页框数目
4.驻留集：给一个进程分配的物理页框数，小于进程的大小
工作集：工作阶段，进程实际访问的页面集合,某一时刻的工作集，从该时刻开始往前数工作集的窗口大小

5.缺页中断：操作系统可能执行的操作有：缺页中断调入新页面，要修改页表项和分配页框，同时内存没有页面，需要外存读入，会发生磁盘I/O；影响请求分页系统有效(平均)访存时间的是：缺页率，内存访问时间，磁盘读写时间，执行缺页处理程序的CPU时间
6.系统发生抖动：抖动是值刚刚被换出的页面很快就要被访问，频繁的置换页面以至于大部分时间都花在页面的置换上，导致系统性能的下降，撤销部分进程可以减少所要使用 的页面数，防止抖动
7.虚拟内存的容量受到外存和内存容量之和的限制
8.磁盘交换区：当内存不足时，操作系统会把一部分数据移动到磁盘交换区中，从而释放出物理内存空间，增大交换区的容量可以提高系统的性能和稳定
9.系统调用是人为请求的，系统调用完成的是：创建新进程；页面置换和进程调度是操作系统自发完成的

1.虚拟内存管理的基本概念






2.请求调页功能


有这些多的状态位是因为，之前的基本分页系统是一次性装入内存的



3.页面置换算法1



**缺页：**想要找的页面不在内存中





4.页面置换算法二


4.页面分配策略

第四章：文件管理

考点：
1.顺序索引文件：定长顺序索引文件可以定长存储，
2.索引文件：一个文件对应一个索引表，一条索引项对应一条文件记录,FCB:文件控制块，一个FCB就是一个文件记录项，文件记录项组成文件目录表
3.文件分配 磁盘块的三种方法

连续分配：物理地址=逻辑地址+起始地址

链式结构不能实现随机访问，连续结构的文件不易于扩展，因此随机访问且易于扩展是索引结构的特性；保证最短查询时间，实现快速播放，连续结构最优
4.删除文时不需要删除文件所在的目录，因为目录下可能存在其他文件，而和此文件相关的目录项和文件控制块(FCB)需要随着文件一起删除，同时释放文件关联的内存；删除文件并不会导致文件的快捷方式被删除，快捷方式属于文件共享中的软连接，本质上创建的是一个链接文件，其中存放的是访问该文件的路径，正如windows删除一个程序后，其快捷方式可能仍然留在桌面上，但是已经无法打开
5.文件首次被打开，会把文件的FCB调入内存，而不会把文件的内容读到内存中，只有进程希望获取文件内容时才会读入文件内容
6.文件索引地址表示的单个文件最大 的长度：
(直接地址索引个数+一级间接地址索引个数乘以一个磁盘快可以存储的地址个数+二级间接地址索引个数乘以两次一个磁盘快可以存储的地址个数)*一个磁盘快可以存储的地址个数
7.一个索引指针对应一个磁盘块，一个索引结点对应一个文件，创建文件数量上限=索引结点数量上限，一个文件分配表对应一个磁盘数
8.用户访问权限抽象为一个矩阵，行代表用户，列代表访问权限，如果你是4行5列，那么需要的位数为20.
9.提高文件的访问速度：提前读；延迟写；为文件分配连续的簇；采用磁盘高速缓存
10.将所有的FCB集中存储，文件数据集中存储，这样随机查找文件名时，只需要访问FCB对应的块，可以减少磁头移动和磁盘I/O访问次数
11.文件数据一次性写入磁盘且不可修改：使用连续文件的数据块的组织方式，磁盘寻道时间更短，文件随机访问效率更高
12.文件的共享
硬连接：基于索引结点， 软连接：基于符号链
count记录共享此文件的用户数目

只有文件拥有者删除文件，其他共享者才不能打开，其他用户删除软链接并不会对其他用户造成影响；快捷方式属于文件共享中的软链接

对于软链接，引用计数值直接复制；建立硬链接时，引用计数值加一；删除文件时，删除操作对于符号链接是不可见的，这并不影响文件系统，当以后再通过符号链接访问时，发现文件并不存在，直接删除符号链接；但是对于硬链接则不可以直接删除，引用计数值减一，若值不为0，则不能删除此文件，因为还有其他硬链接指向此文件
13.设置当前工作目录的主要目的是：加快文件的检索速度
14.若文件f1的 硬链接为f2；那么f1和f2共享同一个内存索引结点，他们的文件描述符fd1和fd2分别指向各自的用户打开文件表中的一项，f1和f2读写指针位置不同
15.文件系统管理空闲磁盘块的数据结构：

16.磁盘调度算法
电梯算法，最短寻道算法
17.绝大多数操作系统为改善 磁盘访问时间，以簇为单位进行空间分配，所以某文件系统的簇和磁盘扇区大小分别为1KB和512B，若一个文件的大小为1026B，则分配给该文件的磁盘空间大小是2048B
18.磁盘格式化程序做的工作是：建立文件系统的根目录。对保存空闲磁盘块信息的数据结构进行初始化
19.系统总是访问磁盘某个磁道而不响应对其他磁道的访问请求，这种现象成为磁臂黏着，先来先服务，按照请求次序进行调度，比较公平，不会出现磁臂黏着

一：文件基本概念，目录，物理结构，逻辑结构，共享和安全

1.文件管理初识(外存：硬盘)

二：文件的组织方式
1.无结构文件：流式文件，由一些二进制或者字符流组成：比如文本文件
2.有结构文件：记录式文件，由一些相似的记录组成，比如数据库表


2.文件的逻辑结构




顺序存储而且定长记录：可以实现随机存储




3.文件目录

4.文件物理结构(文件分配方式)












5.文件存储空间管理


6.文件基本操作

7.文件的共享
一：基于索引结点的共享方式(硬链接)

二：基于符号链的共享方式(软链接)

8.文件保护



9.文件系统的层次管理系统

二：磁盘结构，磁盘调度算法

1.磁盘的结构




2.磁盘调度算法
目标扇区平均转半圈
一：一次读写磁盘消耗的时间



缺点：大量进程分散导致性能很差，寻道时间变长

缺点：可能会导致饥饿现象

3.减少延迟的时间








4.磁盘的管理
一：磁盘的初始化

五：输入输出管理

考点：
1.本地用户通过键盘登陆系统时，首先获得键盘输入信息的程序是：中断处理程序；键盘是典型的通过I/O中断方式工作的外设
2.用户程序发出磁盘I/O请求时，系统的正确处理流程是：
用户程序->系统调用处理程序->设备驱动程序->中断处理程序
3.设备管理软件的四个层次：
用户层->与设备无关的系统调用处理层->设备驱动程序->中断处理程序
用户程序对I/O设备请求采用逻辑设备名，而程序实际执行时使用物理设备名，它们之间的转换是由设备无关软件层完成的。
4.计算柱面号，磁盘号和扇区号的工作是由设备驱动程序完成的
5.系统将数据从磁盘读到内存的过程的操作：
初始化DMA控制器->从磁盘传输一块数据到内存缓冲区->DMA控制器发出中断请求->执行DMA结束，中断服务程序
6.脱机技术：脱离主机进行输入输出操作
7.假脱机技术：共享打印机
8.缓冲区：利用硬件寄存器或者内存作为缓冲区，缓解CPU和I/O的速度不匹配问题
9.单缓冲区

平均处理时间：MAX(C,T)+M
上面是平均处理时间，就是处理的文件块趋于无穷大的时候，实际上的情况，比如n块磁盘块，则总的时间是：n-1乘以平均处理时间+一个磁盘块处理的时间C+T+M
双缓冲区：

实际情况和上面单缓冲区一样：比如n块磁盘块，则总的时间是：n-1乘以平均处理时间+一个磁盘块处理的时间C+T+M

10.可以改善磁盘设备I/O性能：重排I/O请求次序，预读和滞后写，优化文件物理块的分布
不能改善磁盘设备I/O性能：在一个磁盘上设置多个分区
在系统内存中设置磁盘缓冲区的主要目的：减少磁盘I/O次数，将内存经常访问的文件调入磁盘缓冲区，从高速缓存中复制的访问比磁盘I/O的机械操作要快很多
11.假脱机技术：SPOOLing:利用专门的外围控制机，将低速I/O设备上的数据传送到高速磁盘上，是操作系统中采用一项将独占设备改造成为共享设备的技术，SPOOLing技术需要进行输入/输出操作，单道批处理系统无法满足，实现了将独占设备改造成为共享设备的技术(可以让多个进程共享一台独占式设备)，设备的输入井/输出井之间数据的传送是由系统实现的
12设备可以看作是特殊的文件：对于具有设备独立性的系统：可以使用文件名访问物理设备，用户程序使用逻辑设备名访问物理设备；再经过驱动程序的处理来控制物理设备；需要建立逻辑设备与物理设备之间的映射关系；更换物理设备后，需要更换驱动程序，而无需修改应用程序

一：输入输出设备的概念和分类




二：I/O控制器










三：I/O控制方式

四：I/O软件层次结构











5.脱机技术(SPOOLing)




6.设备的分配和回收
一：设备分配时应该考虑的因素









七：缓冲区管理