计算机操作系统 （第四版 汤小丹）（持续学习中）

第一章-操作系统概述

操作系统基本概念

操作系统（Operation System），简称OS，是管理计算机『硬件』与『软件』资源的计算机程序。它负责计算机的全部软、硬资源的分配、调度工作，控制和协调并发活动，实现信息的存取和保护。

操作系统的目标和作用

在计算机系统上配置操作系统，其主要目标是：方便性（管理系统资源），有效性（方便用户使用），可扩充性和开放性（作为扩充机器）。
操作系统的作用：
①作为用户与计算机硬件系统之间的接口
②作为计算机资源的管理者（资源可分为四类处理机，存储器，I/O设备以及文件（数据和程序））
处理机管理
1．进程控制
2．进程同步
3．进程通信
4．调度
储存器管理
1． 内存分配
2． 内存保护
3． 地址映射
4． 内存扩充
IO设备管理
1． 缓冲管理
2． 设备分配
3． 设备处理
文件管理
1．文件存储空间的管理
2．目录管理
3．文件的读/写管理和保护
③实现了对计算机资源的抽象
开放了简单的访问方式（接口），隐藏了实现细节（封装）

计算机系统的组成

计算机系统主要由硬件和软件两部分组成：
硬件部分：指其物理装置本身，包括各种处理器（如中央处理器、输入输出处理和该系统中的其他处理器）、存储器、输入输出设备和通信装置；
软件部分：指由计算机硬件执行以完成一定任务的所有程序及其数据。

操作系统的发展过程

1，操作系统内的发展过程
（1），手工操作阶段
①人工操作方式
②脱机输入/输出方式
（2），批处理阶段
①单道批处理系统
②多道批处理系统
（3），分时操作系统
（4），实时操作系统
（5），微机操作系统的发展
2，单道批处理系统（OS前身）
将一批作业输入磁带，并配置监督程序（OS），在此程序调度下保持作业能被连续处理
优点：自动性（不需人工干预），顺序性，单道性
缺点：内存中只有一道程序，CPU需要等待I/O完成
3，多道批处理系统
将批量作业存在外存，由作业调度程序按照一定的算法从外存中选择若干作业调入内存，使其共享资源
优点：提高CPU的利用率（I/O时可同时处理），可提高内存和I/O设备利用率，增加系统吞吐量
缺点：平均周转时间长（全部完成后输出结果队列），无人机交互（等结果）
4，单道批处理和多道批处理系统对比
单道批处理系统：主要解决CPU、内存和I/O设备利用率不足的问题
多道批处理系统：主要解决I/O操作时CPU闲置问题
5，分时操作系统(Time Sharing System)
一台主机连接多个带有显示器和键盘的终端，同时允许多个用户通过自己的终端，以交互方式使用计算机，共享主机中的资源。
优点：人机交互，共享主机，便于用户上机
缺点：作业/用户优先级相同，不能优先处理紧急任务
6，实时操作系统(Real Time System)
系统能即时响应外部事件的请求，在规定的时间（毫秒级）内完成对该事件的处理，并控制所有实时任务协调一致地运行。
实时任务
周期/非周期性实时任务（根据周期性）
硬/软实时任务（根据截止时间）
7，实时系统与分时系统比较
多路性：按照分时原则为多个终端用户服务
独立性：系统中的每个终端用户在与系统交互时，彼此相互独立互不干扰
及时性：以用户能接受的等待时间为准
交互性：人与系统的交互性仅限于访问系统中的某些特定的服务程序
可靠性：多级容错，保障系统和数据的安全（出现不同级别的错误如何处理）
8，其它操作系统
网络操作系统
资源共享
远程通信
分布式操作系统（服务器端）
分布性
并行性

操作系统的基本特征

os的四个基本特征，并发，共享，虚拟，异步
1，并行与并发(concurrence)
并行性是指两个或多个事件在同一时刻发生
并发性是指两个或多个事件在同一时间间隔发生
2，共享性(Sharing)
在os环境下的资源共享或称为资源复用，是指系统中的资源可供内存中多个并发执行的进程共同使用
（宏观上限定了事件是进程在内存期间，限定了地点内存）
同时访问方式：同一时段允许多个程序同时访问共享资源
互斥共享方式：也叫独占式，允许多个程序在同一个共享资源上独立而互不干扰的工作
3，并发和共享互为存在条件
共享性要求OS中同时运行着多道程序
若只有单道程序正在运行，则不存在共享的可能
并发性难以避免的导致多道程序同时访问同一个资源
若多道程序无法共享部分资源（比如磁盘），则无法并发
4，虚拟（Virtual）
（1）时分复用技术：提高资源利用率的根本原因在于，它利用某设备为一用户服务器的空闲时间，又转去为其他用户服务，使设备得到最充分的利用
（2）虚拟处理机技术：利用多道程序设计技术，为没到程序建立至少一个进程，让多道进程并发执行
（3）虚拟设备技术：通过分时复用的方法，将一台物理I/O设备虚拟为多台逻辑上的I/O设备，并允许多个用户占用一台逻辑上的I/O设备
5，异步(Asynchronism)
多道程序环境下，允许多个程序并发执行；单处理机环境下，多个程序分时交替执行；
程序执行的不可预知性,获得运行的时机
因何暂停
每道程序需要多少时间
不同程序的性能，比如计算多少，I/O多少
宏观上“一气呵成”，微观上“走走停停”

操作系统的主要功能

处理机管理， 存储器管理， 设备管理，文件管理， 用户接口， 现代操作系统的新功能
1，处理机管理
处理机管理以进程为单位
主要功能
（1）进程控制：创建、撤销进程（线程）
（2）进程同步：协调多个进程（线程）的运行
（3）进程通信：实现进程（线程）间信息交换
（4）进程调度：按一定算法为进程（线程）分配处理机使用权
2，存储器管理
目的： 提高利用率，方便用户使用，从逻辑上扩充内存，提供足够的存储空间 ，方便进程并发运行。
（1）内存分配
（2）内存保护
（3）地址映射
（4）内存扩充
3，设备管理
目的 完成用户进程提出的I/O请求，为用户进程分配所需的I/O设备，完成指定的I/O操作，提高CPU和I/O设备的利用率
（1）缓冲管理
（2）设备分配
（3）设备处理
4，文件管理
目的： 对用户文件和系统文件进行管理，方便用户使用，并保证文件安全性
（1）文件存储空间管理
（2）目录管理
（3）文件读写管理与保护
5，用户接口
目的： 为用户提供使用系统的渠道
（1）命令接口
（2）程序接口
（3）图形接口

第二章-进程的描述与控制

前趋图和程序执行

1.程序的顺序执行
一个程序由若干个程序段组成，而这些程序段的执行必须是顺序的，这种程序执行的方式就称为程序的顺序执行。
2. 程序顺序执行时的特征
(1) 顺序性
处理机的操作严格按照程序所规定的顺序执行。
(2) 封闭性
程序一旦开始执行，独占全机资源，其计算结果不受外界因素的影响。
(3) 可再现性
程序执行的结果与它的执行速度无关(即与时间无关)，而只与初始条件有关
3，前趋图
前趋图是一个有向无循环图(DAG)，用于描述进程之间执行的前后关系
4，程序并发执行时的特征
(1)间断性
在多道程序设计的环境下，程序的并发执行，以及为完成一项任务而相互合作，这些程序之间要共享系统的资源，形成了相互制约的关系。
相互制约导致并发程序具有“执行—暂停—执行”这种间断性的活动规律。
(2)失去封闭性
程序在并发执行时，系统的资源状态由多道程序来改变，程序运行失去封闭性。程序的运行受到其他程序的影响。
(3)不可再现性
程序在并发执行时，多次运行初始条件相同的同一程序会得出不同的运行结果。
例：共享公共变量的两个程序，它们执行时可能产生不同结果。

进程的描述

在多道程序设计的环境下，为了保证程序执行时依然保持顺序性、封闭性和可再现性，必须引入新的概念——进程。
1，进程的定义
（1）进程是程序的一次执行
（2）进程是一个程序及其数据在处理及上顺序执行是所发生的活动
（3）进程是具有独立功能的程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位
行为的一个规则叫做程序，程序在处理机上执行时所发生的活动称为进程（Dijkstra） 。
进程（有时称为任务）是一个程序与其数据一道通过处理机的执行所发生的活动。（Alan.C. Shaw）
进程是执行中的程序。（Ken Thompson and Dennis Ritchie）
2、进程的特征（与程序比较）
(1) 结构特征
进程控制块(PCB) + 程序段 + 数据段 = 进程实体（进程）
PCB（Process Control Block）：用来描述进程的基本情况和活动过程，便于系统控制和管理进程，是进程的唯一标识。
(1) 动态性–最基本特征
进程：进程实体的一次执行过程，有生命周期。
程序：程序是一组有序指令的集合，是静态的概念
(2) 并发性
指多个进程实体同存于内存中，且能在一段时间内同时运行。
程序不可并发，静态
(3) 独立性
进程实体是一个能够独立运行，独立获得资源和独立接受调度的基本单位
(4) 异步性
进程按各自独立的、不可预知的速度向前推进
3、进程的三种基本状态
(1)就绪状态(Ready)
创建进程后，进程已分配到除CPU之外的所有必需的资源，只要再获得cpu，立即可以运行。
(2)执行状态(Running)
进程已获得运行所必需的全部资源，它正在处理机上执行。
(3)阻塞状态(Blocked)
正在执行的进程由于发生某事件（例：I/O得不到满足）而暂时无法执行时，便放弃处理机而处于暂停状态，称该进程处于阻塞状态或等待状态
4，三种基本状态的转换
处于就绪状态的进程，在调度程序为之分配了处理机之后便可执行，相应的，其状态就由就绪状态转为了执行态；正在执行的进程（当前程序）如果因分配给它的事件片已完而被剥夺处理机暂停执行，其状态就由执行转为就绪
5、挂起状态
原来内存中的就绪队列与阻塞队列，占用了内存资源，可引入挂起状态将其移入外存，便可暂时搁置。
（1) 引起挂起状态的原因：
终端用户的请求
父进程请求
负荷调节的需要
操作系统的需要
（2）活动就绪和静止就绪
活动就绪：当进程处于未被挂起的就绪状态就是，称此活动为就绪状态
静止状态：当进程被Suspend挂起后，该进程便转为静止就绪状态。
活动阻塞：进程处于未被挂起的阻塞状态
静止阻塞：进程被挂起后的阻塞
（3） 三个进程状态的转换
①活动就绪–>静止就绪
②活动阻塞–>静止阻塞
③静止就绪–>活动就绪
④静止阻塞–>活动阻塞

进程控制块

存放进程管理和控制信息的数据结构称为进程控制块。它是进程管理和控制的最重要的数据结构，在创建进程时，建立PCB，并伴随进程运行的全过程，直到进程撤消而撤消。
PCB就像我们的户口。
PCB是进程存在的唯一标志。
系统的所有PCB组织成链表或队列，常驻内存的PCB区
1,，进程控制块的作用
作为进程独立运行基本单位的标志
能实现间断性的运行方式
提供进程管理所需要的信息
提供进程调度所需要的信息
实现与其它进程的同步与通信
2,，进程控制块中包含的信息
(1) 进程标示符
每个进程都必须有一个唯一的标识符
内部标示符（系统）
外部标示符（用户）
(2) 处理机状态
主要有处理机的各种寄存器中的内容组成。处理机运行时的信息若被中断（时间片用完），则将其放置在PCB中。
(3) 进程调度信息
进程状态（进程所处于什么状态，为进程调度提供依据）
进程优先级
进程调度所需的其他信息
事件（引起进程状态转变的事件）
(4) 进程控制信息
程序和数据的地址（访问数据位置）
进程通信和同步机制
资源清单（进程所需资源，不同进程的不同资源）
链接指针（上一进程执行完后下一个进程的地址）
3，进程控制块的组织方式
(1) 链接方式
把具有同一状态进程的PCB分别通过PCB中的连接字连接成一个队列，用链接成一个队列。
（2）索引方式
即系统根据所有进程的状态的不同，建立几张索引表，并把各索引表在内存的首地址记录在内存的专用单元中。（索引表的表目中记录了相应状态的某个PCB在PCB表中的地址）

进程控制

学习目标：
理解进程树
掌握进程的创建与终止
掌握进程的阻塞与唤醒
掌握进程的挂起与激活
1，定义：进程控制是对系统中的全部进程实施有效的管理，包括进程创建、终止、进程阻塞和唤醒。
2，OS 内核：在现代OS中，常把一些功能模块（与硬件紧密相关的、常用设备的驱动程序及运行频率较高的）放在紧靠硬件的软件层次中，加以特殊保护，同时把它们常驻内存，以提高OS的运行效率，这部分功能模块就称OS的内核
内核是基于硬件的第一层软件扩充，它为系统控制和管理进程提供了良好的环境。
3，OS内核包含两大功能：
(1),支撑功能
中断处理
程序运行时发生的中断操作，系统调用、I/O操作，进程调度等都依赖中断处理
时钟管理
时间片轮转调度、截止时间控制等都依赖时钟管理
原语操作
原语，指有若干条指令组成，用于完成一定功能的一个过程。
原子操作，一个操作中的所有动作要么全做，要么全不做。
（原语在执行过程中不允许被中断）
(2),资源管理功能
进程管理
存储器管理
设备管理
4,进程树
进程图是用来描述进程关系的有向树，用来描述一个进程的家族关系
结点代表进程，结点间的有向边代表父子关系
父子进程：进程A创建进程B，则A称为B的父进程，B称为A的子进程
祖先进程：父进程的创建者
子进程可以从父进程继承资源，子进程结束后要将资源归还其父，父进程终止时要同时终止其子
5，引起进程创建的事件
① 用户登录：合法用户登录时，在终端为其建立一个初始化进程，并插入就绪队列，该进程通常会用来配置用户工作环境。（分时操作系统）
②作业调度：每个被调度到的作业会被分配相应PCB（创建进程）并分配资源，最后放入就绪队列
③ 提供服务：为了响应用户的请求，创建一个新的进程完成所需服务
④ 应用请求：由应用进程自身创建一个或多个完成特定功能的子进程
6，进程的创建
发生上述创建进程的典型事件后，Create原语将按照下述步骤创建新进程
① 申请空白PCB：为新进程申请新的进程号（数字标识符），同时从PCB集合中索取一个空白PCB
② 分配资源：为进程分配运行时所需各种资源并放入PCB，如内存、文件、I/O设备和CPU时间等
③ 初始化PCB：包括对标识信息、处理机状态信息和控制信息的初始化（记录）
④ 将新进程插入就绪队列：上述工作顺利完成后，如果就绪队列未满，即可插入就绪队列等待CPU
7，引起进程终止的事件
(1)正常结束
当进程运行到结束指令，则该进程生命期结束，撤销PCB并释放资源
(2)异常结束
①进程运行期间出现异常而被迫终止进程，通常有越界错、非法指令、特权指令错、运行超时、等待超时等
②外界干预：进程自身运行正常时，应外界请求而终止，通常有操作人员干预请求、父进程请求、父进程终止等
8，进程终止过程
① 根据进程标识符寻找其PCB并读取进程状态；
② 对正在执行的进程，应立即终止，并置CPU调度状态为真；
③对具有子孙的进程，应同时终止其子孙，避免不可控进程的出现
④被终止进程的资源要归还系统或其父
⑤被终止进程的PCB从所在队列或链表中清除
9，引起进程阻塞和唤醒的典型事件
请求系统服务：正在执行的进程申请的资源无法响应时，暂时阻塞
等待某种操作完成（某进程必须等待I/O操作才可继续执行）
新数据尚未到达（两个合作进程其中一个需要数据）
无新工作可作（进程：发送数据包）
10，进程阻塞过程
① 进程阻塞时首先调用阻塞原语block阻塞自身
②进入block过程时，先要停止进程执行
③ 修改PCB状态为阻塞，并按照阻塞原因将其放入阻塞队列
④保存当前处理机状态（PCB），以便日后再次执行可以从断点正确继续
⑤将处理机分配给另一就绪进程，并进行切换
⑥进程阻塞是进程本身的主动行为
11，进程唤醒过程
当进程所期待的事件发生后，相关的其他进程（比如用完临界资源并释放的进程）将调用唤醒原语wakeup
被阻塞的进程将从阻塞队列中移出
修改被阻塞进程的PCB状态为就绪，并放入就绪队列等待CPU
12，进程挂起
需要挂起进程时，首先调用挂起原语suspend，将指定进程或处于阻塞的进程挂起
正在执行的进程被挂起时，转向调度程序重新调度
处于活动就绪或活动阻塞的进程，将要被转为相应的静止状态
被挂起进程的PCB需要复制到指定的内存区域，以备查询
13，进程激活
激活原语active执行时，将进程从外存调入内存
若为静止就绪，将状态改为活动就绪；若为静止阻塞，将状态改为活动阻塞
比较被激活的进程的优先级，若比当前运行进程的高，立即抢断；反之，等待运行

进程同步

学习目标
掌握临界资源与临界区的概念
掌握信号量机制
熟练使用信号量机制解决进程同步问题
理解管程机制
1、同步主要任务
对多个进程在执行次序上进行协调，使并发执行的各进程间能有效的共享资源和相互协作，从而使程序的执行具有可再现性
2，进程的两种制约关系
间接相互制约关系：源于资源共享，由于共享同一资源而形成的制约关系，例如打印机、图书馆的书 互斥
直接相互制约关系：源于进程合作，进程A的执行结果导致进程B的执行，进程B的执行影响进程A是否等待，例如缓冲区资源、流水线资源 同步
3、临界资源
临界资源（Critical Resource）:把一段时间内只允许一个进程访问的资源称为临界资源或独占资源（打印机、教室）
临界区（Critical Section）:每个进程中访问临界资源的那段代码称为临界区（执行打印操作的代码、在教室上课的行为/时间）
各进程必须使用互斥方式共享的临界资源
典型问题：生产者－消费者问题
4，生产者消费者问题
生产者与消费者进程都是异步方式运行，但两者之间必须保持同步
生产者和消费者本身互不干扰，互不关心
不允许消费者进程到空缓冲区取产品
不允许生产者进程向已装满产品且尚未被取走的缓冲区中放产品
线性缓冲区使用完后需要重置指针，使用不便
为了保证生产者进程与消费者进程的并发同步执行，使用环状缓冲池控制两者的工作
环状缓存池由多个缓冲区组成，每个缓冲区存放一个产品，生产者一次放一个产品，消费者一次使用一个产品
5，临界区
临界区：进程中访问临界软硬件资源的代码称为临界区（互斥区）
临界区的使用方法
进程在进入临界区前，先检查临界资源，若该资源未被访问，进程可以即刻进入临界区运行并激活临界资源正被访问的标识；反之，则不进入临界区
6，同步机制应该遵循的准则
空闲让进（无进程在临界区时允许其它进程访问）
忙则等待（互斥）
有限等待（保证有限时间内进入临界区访问，不能长时间等待）
让权等待（当进程不能进入自己的临界区时，应立即释放处理机，以免进程陷入“忙等”状态
7,进程同步的基本概念
互斥：指多个进程不能同时使用同一个资源。
死锁：指多个进程互不相让，都得不到足够的资源。
饥饿：指某一个进程一直得不到资源（其他进程可能轮流占用资源）。
8，信号量机制
1965年荷兰Dijkstra提出的信号量（Semaphores）是一种卓有成效的进程同步工具，在长期的应用中，得到了很大的发展，从“整型信号量” 经过“记录型信号量”发展到“AND型信号量”，进而发展为“信号量集”机制。
信号量就是OS提供的管理公有资源的有效手段。
信号量代表可用资源实体的数量。
互斥信号量：为了管理临界资源，使多个进程互斥地访问临界资源，而设置的信号量。
9，整型信号量
定义：把整型信号量定义为一个用于表示资源数目的整型量S，除初始化外，仅能通过两个原子操作wait(S),signal(S)来访问（又经常被称为P，V操作）
P操作（进入区） wait(S):
While S<=0 do no-op;
S:=S-1;
V操作（退出区） signal(S):
S:=S+1;
10，记录型信号量
因为整形信号量并未遵循让全等待的准则，所以记录型信号量采取了让权等待的策略，但是又出现了多个进程等待访问同一临界资源的情况。
引入整型变量value(代表资源数目)、进程链表L (链接/放置所有等待进程/阻塞)
记录型数据结构：
type semaphore=record
value: integer;
L: list of process;（进程）
end;
11，Wait（P） 操作：
申请资源，减量操作，S.value:=S.value-1
当S.value<0时，表示资源分配完，进行自我阻塞，放置链表。
Signal（V）操作：
释放资源，增量操作，S.value:=S.value+1
当S.value≤0，唤醒S.L链表中的等待进程。
注：| S.value |为链表中因申请不上进程导致阻塞的进程数量
12，执行完wait操作后，若S.value<0，表示该类资源已分配完毕，进程调用block原语阻塞自己，放弃处理机，并插入到信号量链表L中。
执行完signal操作后，若S.value≤0，表示在链表中仍有等待该资源的进程被阻塞，因此要调用wakeup原语唤醒链表中的第一个进程。
若S.value初值为1，表示只允许一个进程访问临界资源，此时的信号量称为互斥信号量。
13， 利用信号量实现进程互斥（记录型信号量）
为使多个进程互斥的访问某临界资源，须为该资源设置一互斥信号量mutex，并设其初始值为1，然后将各进程访问资源的临界区置于wait(mutex)/进入区 和signal(mutex)/退出区 之间即可。

Var  mutex: semaphore  :=1; //定义互斥信号量
        begin
        parbegin（并发进程）
            process 1: begin
                                 repeat
                                   wait(mutex);（申请互斥信号量/权利）
                                   critical section
                                   signal(mutex);
                                   remainder section
                                 until false;
                               end
        parend 
       end 
1
2
3
4
5
6
7
8
9
10
11
12
13

wait和signal必须成对出现
14，利用信号量实现前趋关系
设有两个并发执行的进程P1和P2，P1中有语句S1，P2中有语句S2，希望在S1执行后再执行S2。
方法：使进程P1和P2共享一个公用信号量S，并赋予其初值为0。（依然按照记录型信号量的操作）
一条语句后面有n条直接后继，则后面会跟n个signal（V）操作；若一条语句前面有n条直接前驱，则前面会有n个wait（P）操作
实现前驱关系：
先数箭头，箭头数量表示信号量数量
定义（箭头数量的）公用信号量，初始值为0
从第一个节点开始往后数后继关系，依据上面的原则进行各项操作

管城机制

P、V操作的优缺点
优点：简单，而且表达能力强（用P、V操作可解决任何同步互斥问题）
缺点：不够安全；P、V操作使用不当会出现死锁；遇到复杂同步互斥问题时实现复杂
1，为降低管理分散在各个进程中大量信号量的困难，以及避免同步操作不当所导致的死锁，引入管程作为新的同步工具
管程是管理进程间同步的机制，它保证进程互斥地访问共享变量，并方便地阻塞和唤醒进程。管程可以用函数库的形式实现，比信号量好控制。
2，基本思想：把信号量及其操作原语封装在一个对象内部。
一个管程定义了一个数据结构和能为并发进程所执行（在该数据结构上）的一组操作，这组操作能同步进程和改变管程中的数据。
管程的组成：
① 作用于本管程的共享变量说明
② 对该数据结构进行操作的一组过程
③ 对作用于本管程的数据设置初值的语句
3，管程的主要特性：
模块化：一个管程是一个基本程序单位，可以单独编译。
抽象数据类型：管程是一种特殊的数据类型，其中不仅有数据，而且有对数据进行操作的代码。
信息封装：管程是半透明的，管程中的外部过程（函数）实现了某功能，至于这些功能是怎样实现的，在其外部则是不可见的。
4，管程实现要素
管程将共享变量和对它进行操作的若干过程封装起来，所有进程要访问临界资源时，都必须经过管程才能进入，且每次只能有一个进程进入管程，从而实现进程互斥
5，管程语法

Monito monitor-name{//管程名
share variable declarations;//共享变量说明
cond declarations；//条件变量说明
public：  //能被进程调用的过程
void P1(…) //对数据结构操作的过程
{  }
void P2(…)
{  }
             …
void Pn(…)
{  }
{  //管程主体
      initialization code;//初始化代码
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

6，条件变量
当进程在管程内执行时，会发现它必须等待其他进程对管程所保护的信息进行某些特定操作后才能继续工作，因此引入了条件变量（等待的原因）
7，条件变量是一种可能在管程中出现的结构，它对管程的所有过程是全局性的，并通过下面的两个操作来操控它的值
wait：阻塞活动进程，直到另一个进程向条件变量发送了唤醒信号
signal：若有另外某个进程由于对条件变量的wait操作而被挂起，则解挂它；否则，不产生任何操作
8，管程在实现进程同步时会对请求资源但暂时无法获得响应的进程执行P操作，并将其放入等待队列；仅当另一进程访问完并释放资源后，才用V操作将队首进程调入

为了区别不同原因的等待队列，管程中通常会在P/V操作之前设置条件变量condition，其形式为: condition x,y。

进程的同步问题

生产者-消费者问题

1，对于生产者-消费者问题的分析
可利用互斥信号量mutex实现诸进程对缓冲池的互斥使用；利用资源信号量empty和full分别表示缓冲池中空缓冲区和满缓冲区的数量。
①互斥 定义互斥信号量mutex，初值mutex=1
同步 先生产才能消费，消费完才可以再生产，定义资源信号量empty与full
②申请mutex，就可以直接使用缓冲区了吗？
不，想让进程执行，申请上mutex互斥信号量的同时还要申请empty与full资源信号量
2，1利用记录型信号量解决生产者–消费者问题
设环状缓冲池中有n个缓冲区
互斥信号量mutex保证各进程对缓冲池的互斥使用
资源信号量empty和full分别表示缓冲池中空、满缓冲区数量
in、out分别指示下一个可以放入产品的空缓冲区和下一个可以取产品的满缓冲区
3，代码

Var  mutex, empty, full: semaphore :=1, n, 0; //定义信号量
        buffer: array [ 0, …, n-1] of item;//定义缓冲区
        in, out: integer := 0, 0; //定义指针
begin
    parbegin
        producer : 
            begin
                repeat
                   …
                   生产一个产品放入nextp;
                   …
                   wait(empty); //申请缓冲区中空的位置
                    wait(mutex); //申请使用缓冲区的权利
                    buffer(in):=nextp; //放入缓冲区
                    in:=(in+1) mod n; //指向下一位置
                    signal(mutex); //释放信号量
                    signal(full); //占用位置
                until  false;   
           end
consumer : 
    begin
        repeat
           wait(full); //申请缓冲区中的位置
           wait(mutex); //申请使用缓冲区权利
           nextc:=buffer(out); //取出商品
           out:=(out+1) mod n; //指向下一个
           signal(mutex); //释放信号量
           signal(empty); //释放位置
           消费 nextc中的产品;                        
        until  false;   
    end
parend
end
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

4，注意:
每个程序中用于实现互斥的信号量mutex的wait(mutex)和signal(mutex)必须成对地出现。对资源信号量empty和full的wait和signal操作，同样需要成对地出现，但处于不同的程序中。
在每个程序中的多个wait操作顺序不能颠倒。应先执行对资源信号量的wait操作，再执行对互斥信号量的wait操作，否则可能引起进程死锁。（假如两个程序中wait位置互换，则会造成生产者等消费者消费，消费者等生产者生产这样的死循环）
释放资源时顺序无要求。

哲学家进餐问题

1，五个哲学家（0-4）共用一张圆桌，分别坐在周围的五张椅子上，在桌子上有五只碗和五支筷子（c0-c4），他们的生活方式是交替地进行思考和进餐。
平时，一个哲学家进行思考，饥饿时便试图取用其左右最靠近他的筷子，只有在他拿到两只筷子时才能进餐。进餐毕，放下筷子继续思考。
分析：最多只能有两人同时进餐；
相邻两位不能同时进餐；
若5人同时饥饿将导致死等。
2，利用记录型信号量解决哲学家进餐问题
该问题是典型的同步问题，代表着需要在多个进程间分配多个资源且不会出现死锁和饥饿的简单表示。
解决办法：放在桌子上的筷子是临界资源，在一段时间内只允许一个哲学家使用。为实现对筷子的互斥使用，用一个信号量表示一只筷子，五个信号量构成信号量数组：
3， 解决办法
①最多只允许四位哲学家同时去拿左边筷子，使得最少有一位哲学家可以进餐，并且在用毕后释放出他用过的两只筷子，从而使更多哲学家能够进餐。
②仅当哲学家的左右两只筷子均空闲时才可以拿起筷子进餐。（AND型信号量）
③规定奇数号哲学家先拿他左边的筷子，然后再去拿右边的筷子；偶数号哲学家则相反。最后总有一位哲学家可以获得两只筷子进餐（例如3号先拿）。
4，解决办法1：最多允许4个人同时去拿左边筷子

Var chopstick: array [0, …, 4] of semaphore:=1; //互斥信号量组
Var  count: semaphore :=4; //多定义一个资源信号量count，值为4
 repeat
          wait(count); //先申请资源信号量count，保证只能4个人同时申请筷子
          wait(chopstick[ i ]); //申请左边筷子（先申请资源信号量再申请互斥信号量）                  	wait(chopstick[ ( i +1) mod 5] ); //申请右边筷子
          …
          eat;
          …
          signal(chopstick[ i ]); //释放左边筷子
          signal(chopstick[(i +1)mod 5]); //申请右边筷子
          signal(count);  //释放资源信号量count
       …
      think;
 until  false;
1
2
3
4
5
6
7
8
9
10
11
12
13
14

5，解决方法三：奇数先拿左，偶数先拿右

Var chopstick: array [0, …, 4] of semaphore:=1;
repeat
     if  i mod 2=1（//判断哲学家的奇偶号） then
        begin
          wait(chopstick[ i ]); //申请左边筷子
          wait(chopstick[ ( i +1) mod 5] ) //申请右边筷子
        end
     else
        begin
          wait(chopstick[ ( i +1) mod 5] ); //申请右边筷子
          wait(chopstick[ i ]) //申请左边筷子
        end
          eat;
          signal(chopstick[ i ]); //释放左边筷子
          signal(chopstick[(i +1)mod 5]); //释放右边筷子
        …
      think;
until  false;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

读者-写着问题

1，一个数据文件或记录可被多个进程共享（使用）。
只要求读文件的进程称为“Reader进程”，其它进程则称为“Writer进程”。
允许多个进程同时读一个共享对象（某时间段可以有许多读进程），但不允许一个Writer进程和其他Reader进程或Writer进程同时访问共享对象。
读者–写者问题”是保证一个Writer进程必须与其他进程互斥地访问共享对象的同步问题。
2，利用记录型信号量解决读者写者问题
定义：
①互斥信号量wmutex : 决定读、写权利，实现Reader与Writer进程间在读或写时的互斥；
②整型变量Readcount : 临界资源，统计正在读的进程数目，记录当前多少进程在读数据。决定读之前是否要申请wmutex信号量，也决定读完之后是否需要释放wmutex信号量。
③ 互斥信号量rmutex：保证Reader进程间互斥访问临界资源Readcount
当Readcount=0，无Reader进程在读时，Reader才需要执行Wait(wmutex)操作(Readcount>0，就不需要继续申请wmutex便可直接读）；若Wait(wmutex)操作成功，Reader进程便可去读，相应地做Readcount+1操作。只要有一个Reader进程在读，便不允许Writer进程写。
同理，仅当最后一个Reader进程在执行了Readcount减1操作后其值为0时，才需执行signal(wmutex)操作，释放互斥信号量，以便让Write进程写。
3，总结
当第一个读进程来时，需申请wmutex互斥信号量，得到访问（读）资源的权利；若再有下一个要读的进程来，则不需要申请wmutex信号量，直接读并改变readcount的值使其加1。
当最后一个读进程读完时，令readcount的值为0，需释放信号量wmutex，释放资源；若不是最后一个读进程，不需要释放，等待最后一个读进程读完去释放即可。
读进程对readcount的值的访问应互斥访问，故定义互斥信号量rmutex实现读进程互斥访readcount。

Var  wmutex, rmutex :semaphore :=1, 1;  //定义两互斥信号量
        Readcount :integer :=0; //定义整型变量，初始读进程数0
begin
    parbegin
        Reader : begin
             repeat
                wait(rmutex); //申请读取并申请改变readcount值
                if Readcount=0 then //判断当前进程是否为第一个读进程，是否需要申请wmutex
     	wait(wmutex); //申请互斥信号量，申请读资源
                Readcount :=Readcount +1; //表示有进程读，加一
                signal(rmutex); //释放readcount值，以便下一个读进程访问改变readcount
                   …读;…
                wait(rmutex); //申请读取并申请改变readcount值
                Readcount :=Readcount -1; //读进程结束，减一
                if Readcount=0 then //判断是否当前进程为最后一个读进程，决定是否释放wmutex
	signal(wmutex); //释放互斥信号量，释放资源
                signal(rmutex); //释放readcount的值
            until  false;
       end
     parend	
end 
wmutex: 读、写互斥；写、写互斥
rmutex: 读间访问Readcount互斥
Readcount: 记录读者进程数
评价：能实现读者—写者问题，保证读读共享，读写互斥，写写互斥；但读优先，读完才可以写，对写者不公平
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

进程通信

进程通信的类型

1，进程通信的定义：进程间的信息交换称为进程通信（经典进程同步问题）
进程通信的分类
①低级通信：进程间交换少量信息的通信方式，例如进程间的互斥和同步
缺点：（1）效率低：每次存取的单位数据量小（一次一个数据）；（2）通信对用户不透明：通信过程是用户手工实现，用户必须通过自身掌握操作完成通信，OS只提供共享存储器
② 高级通信：进程之间可以交换大量数据。用户可以直接利用OS所提供的一组通信命令，高效的传送大量数据
优点：（1）效率高；（2）隐藏了进程通信的细节（OS来做），对用户透明，减少用户编程序的复杂性
2，共享存储器系统：相互通信的进程共享某些数据结构或存储区，进程通过这些共享空间进行通
①基于共享数据结构的通信方式（生-消的缓冲区、全局变量等）：进程公用某些数据结构，借以实现诸进程间的信息交换。
实现：公用数据结构的设置及对进程间同步的处理，都是程序员的职责。
操作系统–提供共享存储器
特点：低效。只适合传递相对少量的数据，属于低级通信。
②基于共享存储区的通信方式：诸进程通过对系统中的一块共享存储区中读写操作实现通信，数据的控制等操作由进程负责，属于高级通信方式
使用此方式进行通信时，需要通信的进程在通信前，需要申请获得共享存储区中的分区，并将该分区附加到自己的地址空间中，便可对其中数据进行读写。完成后可归还存储区。
3，消息传递系统：应用最广泛的进程通信机制。
进程间数据交换以格式化的信息（封装后规定好格式）为单位，在网络OS中，这种信息称为报文。
程序员利用系统提供的通信原语完成通信，其实现细节被隐藏在这些系统提供的原语中，简化了通信程序的复杂性。
分为直接通信方式和间接通信方式
4，管道通信
管道：指用于连接一个读进程和一个写进程以实现他们之间通信的一个打开的共享文件，又名pipe文件。
通信方式：写进程以字符流形式向共享文件提供大量数据的输入，读进程则从该共享文件中读取
② 管道机制具有三方面协调能力
互斥：共享文件同一时刻只可有一个使用者，不可同时读与写，互斥访问
同步：读写进程完成当前工作后唤醒对方，自身休眠
互相确认对方存在：在对方存在的情况下才有通信的必要

消息传递通信的实现方式

消息进程间通信时，源进程可以直接或间接地将消息传送给目标进程，由此可将进程通信分为直接通信和间接通信。
1，直接通信方式
发送进程利用OS提供的发送命令，直接把消息发送给目标进程。发送进程和接收进程都以显式方式提供对方的标识符。
直接通信原语
消息的格式
进程的同步方式
通信链路
2，直接通信原语
对称寻址方式： 发送进程和接收进程都以显式方式提供对方的标识符
Send(receiver,message) //发送消息给接收进程，放置在massage中
Receiver(sender, message) //接收发送进程传来的消息，放置在massage中
非对称寻址方式：一个接收进程与多个发送进程通信时，接收原语中的源进程参数是完成通信后的返回值
Send(P, message)
Receive(id, message)

线程

1， 引入原因
减少程序在并发执行时所付出的时空开销，使OS具有更好的并发性。特别有利于共享存储器的多处理机系统
由于进程是资源的拥有者，在创建、撤销、和切换时系统必须为之付出较大的时空开销，因此系统中的进程数量不宜过多、切换频率不宜过高，限制了并发性
2， 设计思想
将进程的两个属性分开处理：作为调度和分派的基本单位的实体不同时作为拥有资源的单位；作为拥有资源的基本单位，不进行频繁的切换
为了适应对称多处理机OS的需要，当代的主流OS厂家都引入了线程技术
3，进程中包含多个线程，每个线程是利用CPU的最小单位
线程属性
轻型实体：仅拥有用于保证独立运行的少量资源，如TCB（线程控制块）、指令计数器、寄存器、堆栈等
独立调度和分派的基本单位
可并发执行：同一进程或不同进程中的各相关线程间可同时并发执行
共享进程资源：同一进程中的各线程可以共享该进程拥有的资源
4, 线程运行的三个基本状态
执行状态：线程已经获得处理机而正在运行
就绪状态：具备了运行的基本条件，只需获得CPU即可运行
阻塞状态：因某事件受阻而暂停执行
5,可拥有资源的基本单位
除了通常会得到的资源外，还需要为进程分配用于实现进程间和线程间同步与通信的机制
多个线程可并发执行
一个进程中至少有多个线程，进程为线程提供资源及环境令其可以并发执行
进程已不是可执行的实体
进程的执行态表示该进程中的某线程正在执行；挂起或激活某进程时，该进程的所有线程都被挂起或激活
6, 为支持不同频率的交互操作和不同程度的并行，在多线程OS中提供多种同步机制
互斥锁
用于线程之间高频度访问的关键互斥共享资源和数据段的访问控制
条件变量
每个条件变量通常都与一个互斥锁一起使用，互斥锁用于短期锁定，条件变量用于长期等待
信号量机制
私用信号量用来实现同一进程内部线程同步，属于特定进程内部所有，OS不可直接管理；公用信号量用来实现进程间或不同进程间各线程的同步，由OS为它分配空间和管理，比较安全
7, 用户级线程在用户空间实现，具有相同的结构并运行于一个中间系统之上
运行时系统：本质是管理和控制线程的函数集合，线程运行时系统中的所有函数都驻留在用户空间并成为用户级线程与内核间的接口
内核控制线程（轻型进程LWP）：LWP共享进程资源，通过系统调用获得内核服务，用户级进程运行时将其自身连接在一个LWP上以获得内核支持，多个用户级线程可以多路复用一个LWP，但只有当前连接到LWP的线程可与内核通信，其余进程阻塞或等待LWP（P83）
8,本章要求
掌握进程及进程同步的概念
掌握进程状态之间的转换
掌握临界资源与临界区的基本概念
掌握四种信号量机制
掌握使用信号量机制实现互斥、前驱与同步
掌握经典的进程同步问题
掌握进程通信与进程和线程之间的区别
掌握进程及进程同步的概念
掌握进程状态之间的转换
掌握临界资源与临界区的基本概念
掌握四种信号量机制
掌握使用信号量机制实现互斥、前驱与同步
掌握经典的进程同步问题
掌握进程通信与进程和线程之间的区别

第三章-处理机调度与死锁

处理机调度的层次和算法调度的目标

1，处理机调度的基本概念
在多道程序环境下，内存中存在着多个进程，其数目往往多于处理机数目。这就要求系统能按照某种算法，动态的将处理机分配给处于就绪状态的一个进程使之执行。
分配处理机的任务是由处理机调度程序完成的。对于大型系统运行时的性能，如系统吞吐量、资源利用率和作业周转时间等，在很大程度上取决于处理机调度性能的好坏。因此处理机调度便成为操作系统中至关重要的部分。
2，多道程序系统中，调度的实质是一种资源分配，处理机调度是对处理机资源进行分配。
不同OS中的各类型作业都必然会经历进程调度（低级调度）过程，而某些系统中还有中级调度和作业调度（高级调度）过程，每个级别的调度过程都可以根据具体需求选择不同的调度算法。
3，作业
（1）作业与作业步
作业：即用户给操作系统提交的任务。作业不仅包含了通常的程序和数据，而且还应配有一份作业说明书，系统根据该说明书来对程序的运行进行控制。
作业步：在作业运行期间，每个作业都必须经过若干个相对独立，又相互关联的顺序加工步骤才能得到结果，其中的每一个加工步骤称为一个作业步。
（2）作业控制块（Job Control Block, JCB）
为了管理和调度作业，在系统中为每个作业设置了一个作业控制块JCB，它是作业在系统中存在的标志，保存了系统对作业进行管理和调度所需的全部信息。
通常包含：作业标识、用户名称、用户账号、作业类型、作业状态、调度信息、资源需求、资源使用情况等。
②进程控制块（PCB）中包含的信息

1. 进程标示符
2. 处理机状态
3. 进程调度信息
4. 进程控制信息

作业和进程

①作业是用户向计算机提交任务的任务实体。
进程是完成用户任务的执行实体，是资源分配的基本单位。没有作业任务，进程无事可干；没有进程，作业任务没法完成。
②作业建立完毕后，是放在外存等待运行。
进程一经创建，总由相应的部分存于内存，并为其分配内存资源（但是不一定连续）。
③一个作业可由多个进程组成（难度不同），且必须至少由一个进程组成，反之则不然。
④作业的概念更多地用在批处理系统中。
进程的概念几乎可以用在所有的多道程序系统中。
5,作业调度和进程调度
作业调度：使作业进入主存储器。
处于后备状态的作业在系统资源满足的前提下可以被作业调度选中进入内存计算。
进程调度：使作业进程占用处理器。
只有处于执行状态的作业才真正构成进程获得计算的机会。
6，三级调度
一个批处理型作业，从进入系统并驻留在外存的后备队列上开始，直至作业运行完毕，可能要经历下述三级调度。

1. 高级调度（High Scheduling）
2. 中级调度（Intermediate-Level Scheduling）
3. 低级调度（Low Level Scheduling）

高级调度（High Scheduling）

又称作业调度，其主要功能为：根据某种算法，决定将外存上处于后备队列中的哪几个作业调入内存，为它们创建进程，分配必要的资源（除了不分配），并将它们放入就绪队列。
对于用户来说，总希望自己作业的周转时间尽可能的少；而对于系统来说，则希望作业的平均周转时间尽可能少，这样有利于提高CPU的利用率和系统的吞吐量。
所以，在每次执行作业（高级）调度时，都须作出两个决定：
接纳多少作业——每次接纳多少作业进入内存。取决于多道程序度（并发执行的进程的数量），也就是允许多少个作业同时在内存中运行。
接纳哪些作业——应接纳哪些作业从外存调入内存，取决于所采用的调度算法。如先来先服务，短作业优先等。
②回顾
批处理系统 （Batch Processing System)：指用户将一批作业提交给操作系统后就不再干预，由操作系统控制它们自动运行。
分时系统 (Time-Sharing System)：一台计算机连接多个终端，用户通过各自的终端把作业送入计算机；计算机可以轮流为终端用户服务。
实时系统 (Real-Time System)：系统对随机发生的外部事件作出及时响应并在规定的时间内对其进行处理，否则将带来灾难性的后果。
③在不同系统中作业调度所占的比重不同
在批处理系统中，因作业进入系统后先驻留在外存，故需要有作业调度。
在分时系统中为做到及时响应，命令或数据被直接送入内存，故不需作业调度。
在实时系统中，一般不需作业调度。
7，作业运行的三个阶段和三种状态：
收容阶段：操作员把用户提交的作业通过某种方式输入到硬盘上，再为该作业建立JCB，并把它放入作业后备队列中。相应的作业状态为“后备状态”
运行阶段：当作业被作业调度选中后，便为它分配必要的资源和建立进程，并将它放入就绪队列。一个作业从他第一次进入就绪状态开始，直到它运行结束前，在此期间都处于“运行状态”
完成阶段：当作业运行完成、或因异常提前结束时，便进入完成阶段，作业为“完成状态”。此时系统中的“终止作业”程序将回收已分配给该作业的资源，并将运行结果进行输出

低级调度

1，低级调度（Low Level Scheduling）
通常也称为进程调度或短程调度（Short-Term Scheduling），用来决定就绪队列中的哪个进程应获得处理机，然后再由分派程序把处理机分配给该进程。
为最基本的一种调度，三种类型OS中都必须有进程调度。
2，进程(低级)调度的功能（任务）
假设当某一进程时间片用完时：
① 保存处理机的现场信息（进程运行的信息）
② 按某种算法选取新进程
③ 把处理机分配给新进程
3，进程调度中的三个基本机制
为了实现进程调度，应具有如下三个基本机制：
①排队器：将作业从外存调入内存，形成就绪队列，排队器决定就绪队列中进程如何安排，与算法有关。
②分派器(分派程序)：根据进程调度所选的进程，将其从就绪队列中取出，进行从分派器到新选出进程间的上下文切换，将处理机分配给新选出的进程。
③上下文切换机制
例如，有A,B两个进程，A的时间片用完后回到就绪态，再由分派器将CPU分配给进程B。
A暂停执行时，通过上下文切换机制保存当时进程的信息。
4，进程调度可采用下述两种调度方式：
非抢占方式（Non-preemptive Mode）
抢占方式（Preemptive Mode）
①非抢占方式（Non-preemptive Mode）
一旦把处理机分配给某进程后，便让该进程一直执行，直至该进程完成或发生某突发事件而被阻塞时，才把处理机分配给其他新进程，决不允许进程抢占已分配出去的处理机。（例如班级搞活动）
评价
优点：实现简单、系统开销小；适用于大多数的批处理OS
缺点：在要求比较严格的实时系统中，不宜采用这种调度方式
(2)在采用非抢占调度方式时，可能引起进程调度（调度其他新进程）的因素有：
1、进程执行完毕，或因发生某突发事件而不能继续执行
2、执行中的进程因提出I/O请求而暂停执行
3、执行了某种原语操作：如P操作、Block（阻塞原语）
②抢占方式（Preemptive Mode）
允许调度程序根据某种原则，去暂停某个正在执行的进程，将处理机重新分配给另一进程。
抢占依据的原则：
时间片原则：各进程按时间片运行，一个时间片用完时，停止该进程执行重新进行调度。
短作业（进程）优先原则：短作业（进程）可以抢占长作业（进程）的处理机。
优先级原则：优先级高的可以抢占优先级低的进程的处理机。

中级调度（Intermediate-Level Scheduling）

通常又称内存调度或中程调度（Medium-Term Scheduling）。引入目的是为了提高内存利用率和系统吞吐量。
进程运行过程中，OS会使暂时不能运行的进程不再占用宝贵的内存资源，而将它们调到外存去等待，把此时的进程状态称为就绪驻外存状态或挂起状态。
当这些进程又具备运行条件、且内存又稍有空闲时，由中级调度来决定把外存上的那些具备运行条件的就绪进程，重新调入内存等待进程调度。
1,中级调度实际上就是存储器管理中的对换功能（外存移入内存)

三种调度的比较

进程调度的运行频率最高，在分时系统中通常是10~100ms进行一次进程调度，因而进程调度算法不能太复杂，以免占用太多的CPU时间。
作业调度是发生在一个作业运行完毕，退出系统，而需要重新调度一个作业进入内存时，故作业调度的周期较长，大约几分钟一次。因而允许作业调度算法花费较多的时间。
中级调度的运行频率，介于进程调度和作业调度之间。

调度队列模型

高级、中级或者低级调度之间并不是孤立的，因为他们之间存在联系，由此形成了三种类型的调度队列模型：

1. 仅有进程调度的调度队列模型
2. 具有高级和低级调度的调度队列模型
3. 同时具有三级调度的调度队列模型
   1，仅有进程调度的队列模型
   分时系统中为做到及时响应，命令或数据被直接送入内存，其中的就绪进程组织成FIFO（先进先出）队列形式，当创建一个新进程时，将它放入队列末尾，后按某进程调度算法去调度进程。
   2，具有高级和低级调度的队列模型
   在批处理系统中，因作业进入系统后先驻留在外存，故需要作业调度，又需要进程调度。
   调度过程为：由作业调度按一定的调度算法，从外存的后备队列中选择一批作业调入内存，并为它们建立进程，送入就绪队列（排序方式为按照优先级），然后才由进程调度按照一定的进程调度算法，选择一个进程把处理机分配给该进程。
   3，2和1比较区别在于
   (1)就绪队列的形式。（1多采用FIFO的队列形式）（优先级队列形式）
   (2) 设置多个阻塞队列。（使阻塞队列不至于过长，从而提高对阻塞队列的操作效率
   ）（每一队列对应一个阻塞事件）
   4，同时具备三级调度的队列模型
   当在OS中引入中级调度后，可以把进程的就绪状态分为内存就绪和外存就绪，把阻塞状态分为内存阻塞和外存阻塞两种状态。
   在调出操作的作用下，可使进程状态由内存就绪转变为外存就绪，由内存阻塞转变为外存阻塞；在中级调度的作用下，又可使外存就绪转变为内存就绪。
   ①作业调度：从后备队列中依据某些算法将作业调入内存中的就绪队列。
   ②进程调度：从就绪队列中依据某些算法为进程分配CPU，进程执行后又可能会出现三种情况。
   ③中级调度：引入挂起操作后进程移到外存，当内存足够时使用该中级调度依据某些算法选择进程放入内存中的就绪队列。

选择调度方式和调度算法的若干准则（处理机调度算法的目标）

在一个OS的设计中，调度方式和算法的选择取决于OS的类型和目标
不同的OS具有不同的调度目标。如在批处理系统、分时系统和实时系统中，通常都采用不同的调度方式和算法。选择的准则，有的是面向用户的，有的是面向系统的。
1,面向用户的准则
周转时间短（评价批处理系统的指标，因为批处理往往源源不断来作业）
1. 周转时间； 2. 平均周转时间
3. 带权周转时间； 4. 平均带权周转时间
响应时间快：响应时间（评价分时系统的指标）
截止时间的保证： 截止时间（评价实时系统的指标）
优先级准则：保证用户提交任务的优先级
2，面向系统的准则
系统吞吐量高：希望单位时间内处理任务多，评价批处理系统的重要准则
处理机利用率好：让每个作业有条不紊地完成，多用于分时系统
各类资源（存储器外部设备等）平衡利用：多用于大中型系统
3，周转时间
周转时间=等待的时间+CPU服务的时间=完成时间点-到达时间点
是指从作业被提交给系统开始，到作业完成为止的这段时间间隔；对于进程来说，周转时间表示为从进程被创建开始，到进程完成的这段时间间隔。用户总是希望周转时间越短越好。
包括四部分时间：
作业在外存后备队列上等待调度的时间
进程在内存就绪队列上等待调度的时间
进程在CPU 上执行的时间
以及进程等待I/O 操作完成的时间/进程阻塞等待的时间
(2) 平均周转时间
每个作业的周转时间之和除以作业个数n，即系统的平均周转时间。
(上中下)T=1/n[Σ（n）（i=1）（Ti）]
(3) 带权周转时间
作业的周转时间Ti与系统为它提供服务的时间Ts（即CPU执行该作业的时间）之比，反应作业在系统中等待时间的长短。
W = Ti /Ts
(4)平均带权周转时间
每个作业的带权周转时间之和除以作业个数n，反应系统中作业的平均等待时间。
W=1/n[Σ（n）（i=1）（Ti/Ts）]
（5）带权周转时间=周转时间/CPU服务时间
2. 响应时间（衡量分时系统性能的指标）
是从用户通过键盘提交一个请求开始，直至系统首次产生结果响应为止的时间间隔。
包括三部分时间：
从键盘输入的请求信息传送到处理机的时间
处理机对请求信息进行处理的时间
将所形成的响应信息回送到终端显示器的时间
3. 截止时间（衡量实时系统性能的指标）
是指某任务必须开始执行的最迟时间，或必须完成的最迟时间。
对于严格的实时系统，其调度方式和调度算法必须能保证这一点，否则将可能造成难以预料的后果。

调度算法

在OS中调度的实质是一种资源分配，因而调度算法是指：根据系统的资源分配策略所规定的资源分配算法。
对于不同的系统和系统目标，通常采用不同的调度算法。有些算法既适用于进程调度，也适用于作业调度。
在批处理系统中为照顾为数众多的短作业，应采用短作业优先的调度算法；
在分时系统中，为了保证系统具有合理的响应时间，应采用时间片轮转法进行调度。

先来先服务调度算法（first-come first-served，FCFS）

是一种最简单的调度算法，既可用于作业调度，也可用于进程调度。
进程调度采用FCFS算法时，每次调度都从就绪队列中选择一个最先进入内存中就绪队列的进程，为之分配处理机，使之运行。
作业调度采用FCFS算法时，按照进入外存中后备队列的时间先后顺序选择一个或多个作业，使之进入内存并为之分配资源、创建进程、插入就绪队列。
算法简单，易于实现
有利于长作业（进程），而不利于短作业（进程）
有利于CPU繁忙型，不利于I/O繁忙型

短作业（进程）优先调度算法 （short job first，SJ§F）

对短作业或短进程优先调度的算法，可以分别用于作业调度和进程调度。
短作业优先（SJF）的调度算法：从外存中的后备队列中选择一个或若干个估计运行时间最短的作业，将它们调入内存并为之分配资源、创建进程、插入就绪队列。
短进程优先（SPF）调度算法，是从内存就绪队列中选出一估计运行时间最短的进程，将处理机分配给它，使它立即执行。

3,SJF调度算法的优缺点：
优点：
有效降低作业的平均等待时间，提高系统吞吐量。
缺点：
总是优先调度短作业，对长作业不利。
①该算法完全未考虑作业的紧迫程度，因而不能保证紧迫性进程（作业）会被及时处理。
②由于进程（作业）的长短只是根据估计执行时间定的，主观因素较大，不一定能真正做到短作业优先。

高优先级优先(HPF)调度算法

为照顾紧迫性作业，使之在进入系统后便获得优先处理，引入了最高优先级优先调度算法。
作业调度：从外存的后备队列中选取若干个优先级最高的作业装入内存
进程调度：把处理机分配给就绪队列中优先级最高的进程
此算法常用于批处理系统中作为作业调度算法，也作为多种操作系统中的进程调度算法，还可用于实时系统中。
5，优先级的类型
对于最高优先级优先调度算法，关键在于：使用静态优先级、动态优先级；如何确定进程的优先级。
静态优先级：在创建进程时确定的，在进程的整个运行期间保持不变。利用某一范围的整数来表示（0～7），又称为优先数。
动态优先级：在创建进程时所赋予的优先级可以随进程的推进或随其等待时间的增加而改变。
6，确定进程优先级的依据有如下三个方面：
进程类型：一般来说系统进程高于用户进程。
进程对资源的需求：如进程的估计运行时间及内存需要量的多少，对要求少的进程赋予较高优先级。
用户要求：由用户进程的紧迫程度及用户所付费用的多少来确定优先级。
7，具体应用
在批处理系统中，短作业优先算法是一种比较好的算法，其主要不足是长作业的运行得不到保证。我们为每个作业引入动态优先级，并使作业的优先级随着等待时间的增加而以速率 a 提高，则可解决问题。见下式：
优先权=(等待时间+要求服务时间)/要求服务时间
由于等待时间与服务时间之和就是系统的响应时间，故上式又表示为：Rp=响应时间/要求服务时间。
8，优先权=(等待时间+要求服务时间)/要求服务时间
或 Rp=响应时间/要求服务时间
由上式可以看出：
如作业等待时间相同，则要求服务的时间愈短优先级愈高，所以该算法利于短作业。
当要求服务的时间相同，作业优先级的高低决定于其等待时间的长短，所以是先来先服务。
对于长作业，作业的优先级可以随等待时间的增加而提高，当其等待时间足够长也可获得处理机。

轮转调度算法

在分时系统中，为保证能及时响应用户的请求，必须采用基于时间片轮转式进程调度算法。在早期，分时系统中采用的是简单的时间片轮转法，进入90年代后，广泛采用多级反馈队列调度算法。下面分别介绍这两种方法。
1，时间片轮转调度算法（RR）
系统将所有的就绪进程按先来先服务（FCFS）的原则排成一个队列，每次调度时，把CPU分配给首进程，并令其执行一个时间片。
时间片的大小从几ms到几百ms。当执行的时间片用完时，停止该进程的执行并将其送往就绪队列的末尾。这样就可以保证就绪队列中所有进程在一定时间内均能获得一时间片的处理机执行时间，系统能在给定的时间内响应所有用户的请求。
2，该算法需要注意的地方
（1）时间片大小的确定
在时间片轮转算法中，时间片的大小对系统性能有很大的影响，不能太短也不能太长。一个比较可取的大小是，时间片略大于一次典型的交互所需要的时间。
（2）进程切换的时机
若时间片尚未用完，正在运行的进程便已经完成，就立即激活调度程序，将它从就绪队列中删除，再调度就绪队列中队首的进程运行，并启动新的时间片。
在一个时间片用完时，计时器中断处理程序被激活，如果进程尚未运行完毕，调度程序将把他送往就绪队列的末尾。

（3）多级反馈调度队列
多级反馈队列调度算法是目前公认的较好的进程调度算法
3，轮转调度算法
（1）设置多个就绪队列并为各个队列赋予不同的优先级，第一个最高，依次降低。各个队列中进程执行时间片的大小设置为：优先级越高，时间片越短。如第一个队列时间片为1ms,第二个队列的时间片为2ms, ……
（2）当一个新进程进入内存后，首先将它放入第一个队列的末尾，按FCFS原则排队等待调度。当轮到该进程执行时，如它能在该时间片内完成，便可撤离系统；如果它在一个时间片结束时尚未完成，调度程序便将该进程转入第二队列的末尾，在同样地按FCFS原则等待调度执行；如果它在第二队列中运行一个时间片后仍未完成，再依次将它放入第三队列，……如此下去，当一个长作业（进程）从第一队列依次降到第n队列后，在第n队列中便采取按时间片轮转的方式运行。
（3）仅当第一队列空闲时，调度程序才调度第二队列中的进程运行，仅当第1～(i-1)队列均空时，才会调度第i队列中的进程运行。
4，优势
多级反馈队列调度算法具有较好的性能，能较好的满足各种类用户的需要。
终端型作业用户：大多属于较小的交互性作业，只要能使作业在第一队列的时间片内完成，便可令用户满意。
短批处理作业用户：周转时间仍然较短，至多在第二到三队列即可完成。
长批处理作业用户：将依次在1～n级队列中轮转执行，不必担心作业长期得不到处理。
5，基于公平原则的调度算法
保证调度算法
①向用户所做出的保证并不是优先运行，而是明确的性能保证，该算法可以做到调度的公平性。
一种比较容易实现的性能保证是处理机分配的公平性。
如果在系统中有 n 个相同类型的进程同时运行，为公平起见，须保证每个进程都获得相同的处理机时间 1/n。
②分配给每个进程相同的处理机时间，显然，这对诸进程而言，是体现了一定程度的公平，但如果各个用户所拥有的进程数不同，就会发生对用户的不公平问题。

死锁概述

资源问题

1,可重复性资源和消耗性资源
(1)可重用性资源
①定义：是一种可供用户重复多次使用的资源
②进程再使用可重复性资源是，按照请求资源，使用资源，释放资源的顺序执行
(2)可消耗性资源
又被称为临时资源，他是在进程动态地创建和消耗的
一般都有如下性质：
①每一类可消耗性资源的单元数目在进程运行期间是可以不断变化的，又有时它可以有许多，有时可能为0
②进程在运行中，可以不断地创造可消耗性资源的单元，将他们放入该资源类的缓冲区中，以增加该类资源的单元数目
③进程在运行过程中，可以强求若干个可消耗性资源单元，用于进程自己的消耗，不再将他们返回给该资源类中。
可消耗性资源通常是由生产者进程创建，由消费者进程消耗，最典型的可消耗性资源就是用于进程通信的消息等
2，可抢占性资源和不可抢占性资源
(1)可抢占性资源，是指某进程在获得这类资源后，该资源可以再被其他进程或系统抢占。
（2）不可抢占性资源
一旦系统把资源分配给该进程后，就不能将它强行收回，只能再进程用完后自行释放。

计算机系统中的死锁

①，竞争不可抢占性资源因引起死锁
通常系统中所拥有的不可抢占资源其数量不足以满足多个进程运行的需要，是的进程在运行过程中，会因争夺资源而陷入僵局。】
②，竞争可消耗性资源引起死锁
③，进程推进顺序不当引起死锁
1，死锁的定义，必要条件，和处理方法
如果一组进程中的每一个进程都在等待仅由该组进程中其它进程才能引发的事件，那么改组进程是死锁（Deadlock）
2，产生死锁的必要条件
（1）互斥条件:进程对所分配到的资源进行排他性使用，即以断时间内，某资源只能被一个进程占用。
（2）请求和保持条件：进程已经保持了一个资源，但又对新的资源提出请求，而该资源已经被其它进程占有，此时请求进程被阻塞，但对自己以获得的资源保持不放
（3）不可抢占条件:进程以获得的资源在未使用完之前不能被抢占，只能在进程使用完由自己释放
（4）循环等待条件：在发生死锁时，必然存在一个进程–资源的循环连，即进出港呢集合中的某一个正在等待被另一个进程占用的资源
3，处理死锁的方法
（1）预防死锁
通过设置某些限制条件，区破坏死锁四个必要条件中的一个或几个来预防产生死锁
(2)避免死锁
在资源动态分配过程中，用某种方法防止系统进入不安全状态，从而避免死锁的发生
（3）检测死锁
允许产生死锁，但可以通过检测机构即使检测出死锁的发生，然后采取适当的措施，把进程从死锁中解脱出来
（4）解除死锁
当检测到系统中已经发生了死锁时，就采取相应的措施，将进程从死锁状态中解脱出来，常用方法就是撤销一些进程，回收它的资源将他们分配给已处于阻塞状态的进程，使其能够继续运行

预防死锁

1，预防死锁和避免死锁这两种方法，实质上都是通过施加某些限制条件，来预防发生死锁。
两者的主要区别在于：
预防死锁：施加的限制条件较严格，往往会影响进程的并发执行。
避免死锁：施加的限制条件则较宽松，这给进程的运行提供了较为宽松的环境，有利于进程的并发执行。
2，预防死锁的方法是使四个必要条件中的第2、3、4条件之一不能成立，来避免发生死锁。
必要条件1，因为它是由设备的固有条件所决定的，不仅不能改变，还应加以保证。
3，破坏请求与保持条件
系统规定所有进程在开始运行之前，都必须一次性的申请其在整个运行过程所需的全部资源。此时若系统有足够资源就一次性分配给该进程，该进程在运行期间不会提出资源要求，从而破坏了“请求”条件；若系统没有足够资源分配给它，就让该进程等待，因而也破坏了“保持”条件，从而避免发生死锁。
优点：算法简单、易于实现且很安全。
缺点：资源浪费严重和进程延迟运行。假设某进程需打印机与扫描仪，且时间不同，会导致一直占用最后才使用的资源，导致浪费严重，其他进程不能使用。
4，破坏不可抢占条件
系统规定，进程是逐个地提出对资源的要求的。当一个已经保持了某些资源的进程，提出新的要求不被满足时必须释放它已经保持的所有资源，待以后需要时再重新申请。从而破坏了“不可抢占”条件。
某一进程已经占有的资源，在运行过程中会被暂时释放掉，认为是被剥夺了。
实现起来比较复杂且付出很大代价。可能会前功尽弃，反复申请和释放等情况，延长了周转时间，增加系统开销。
5，破坏循环等待条件
系统将所有资源按类型进行线性排队，并赋予不同的序号。所有进程对资源的请求必须严格按照资源序号递增的次序提出，这样在所形成的资源分配图中，不可能会出现环路，因而破坏了“循环等待”条件。
例如，对资源R1和R2进行编号1和2，进程申请资源时按照编号的顺序进行申请，即P1与P2都是先申请R1再申请R2，便会让两进程同时申请第一个资源，哪个进程先申请上就可以使用且不会造成死锁。
②与前两种策略比较，该方法资源利用率和系统吞吐量都有较明显的改善。但也存在严重问题：
1、为资源编号限制新设备的增加（中途加入新设备会导致麻烦）；
2、进程使用设备顺序与申请顺序不同，浪费资源（例：申请顺序1→2→3，使用顺序3→2→1，将会导致1资源的严重浪费）；
3、限制用户编程自由。

系统的安全状态

在预防死锁的几种方法中，都施加了较强的限制条件；在避免死锁的方法中，所施加的限制条件较弱，又能获得令人满意的系统性能。
在该方法中把系统的状态分为安全状态和不安全状态，只要能使系统始终都处于安全状态，便可避免发生死锁。
思路：允许进程动态地申请资源，但在资源分配前，应先计算资源分配的安全性，若此次分配不会导致系统进入不安全状态，则将资源分配给进程，否则，令进程等待
2，安全状态是指系统能按某种进程顺序（ P0, P1, P2, …, Pn ）来为每个进程Pi分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可顺利地完成。如果系统无法找到这样一个安全序列，则称系统处于不安全状态。
虽然并不是所有的不安全状态都是死锁状态，但当系统进入不安全状态后，便可能进入死锁状态；反之只要处于安全状态就不会死锁。
故避免死锁的实质是：系统在进行资源分配时，设法使系统不进入不安全状态。

利用银行家算法避免死锁

银行家算法是最有代表性的避免死锁的算法。
由于该算法能用于银行系统现金贷款的发放而得名的。
1,算法思想
每一个进程进入系统时，它必须申明在运行过程中，可能需要每种资源类型的最大单元数目，其数目不应超过系统所拥有的资源总量。
当进程请求一组资源时，系统必须首先确定是否有足够的资源分配给该进程。若有，再进一步计算在将这些资源分配给进程后，是否会使系统处于不安全状态。如果不会，才将资源分配给它，否则让进程等待。
2,银行家算法中的数据结构
设系统中有m类资源，n个进程，n个进程会使用m类资源。
（1）系统可利用资源向量Available。含有m个元素的一维数组，每个元素代表一类可利用的资源数目，其值随着资源的分配和回收不断发生变化。
如果Available[j]=k,表示系统中现有Rj类资源k个。
（2）最大需求矩阵Max。是一个nm的矩阵，定义了系统中n个进程中的每一个进程对m类资源的最大需求。
如果Max[i,j]=k,则表示进程i需要Rj类资源的最大数目为k。
（3）分配矩阵Allocation。为nm的矩阵，它定义了系统中每类资源当前已分配给每个进程的资源数。Allocation[i,j]=K,表示进程i当前已分得Rj类资源的数目为K。
（4）需求矩阵Need。为n*m的矩阵，表示每个进程尚需的各类资源数。Need[i,j]=K, 表示进程i还需要Rj类资源K个，方能完成其任务。
三个矩阵间的关系：Need[i,j] = Max[i,j] - Allocation[i,j]
3，银行家算法处理的步骤
设Requesti[j]=k,表示某一时刻进程Pi需要k个Rj类型的资源
（1）如果Requesti[j] <= Need[i,j],便转向步骤2；否则认为出错，因为它所请求的资源数已超过它所需要的最大值。
（2）如果Requesti[j] <= Available[j],便转向步骤3；
否则，表示尚无足够资源，Pi需等待，进行阻塞。
（3）系统试探着把资源分配给进程Pi ，并修改下面数据结构中数值：
Available[j]:= Available[j] - Requesti[j];
Allocation[i,j]:=Allocation[i,j] + Requesti[j];
Need[i,j]:=Need[i,j] - Requesti[j];
（4）系统执行安全性算法，是为了检查此次资源分配后系统是否处于安全状态，以决定是否完成本次分配。若安全，则正式分配资源给进程Pi；否则，不分配资源，让进程Pi等待。
4，安全性算法
步骤：
（1）设置两个向量：
工作向量work：表示系统可提供给进程继续运行所需的各类资源数目，含有m个元素的一维数组，初始进程未执行时，work:=Available，执行后work=avaliable+allocation
Finish: 表示系统是否有足够的资源分配给n个进程，使之运行完成。开始时先令Finish[i]:=false (i=1…n); 当有足够资源分配给进程i时，再令Finish[i]:=true。只有所有进程的Finish值为true时，系统才为安全状态。
5,例题


6，银行家算法总结
(1)首先判断当前时刻的安全性(安全性算法)
(2)若安全，当某进程提出资源申请Request[i]时，尝试进行预分配(两个比较，并修改相关值)；
(3)判断预分配后的安全性(安全性算法)；
(4)若仍安全（存在安全序列），则实施分配；否则，该进程等待
7，死锁的检测
当系统为进程分配资源时，若未采取任何限制性措施，则系统必须提供检测和解除死锁的手段，为此系统必须：
①保存有关资源的请求和分配信息；
②提供一种算法，以利用这些信息来检测系统是否已进入死锁状态。
8，我们可以利用资源分配图加以简化的方法，来检测系统处于某
状态时是否为死锁状态。简化方法如下：

1. 在资源分配图中找出一个既不阻塞又非独立的进程结点Pi，在顺利的情况下运行完毕，释放其占有的全部资源。
2. 由于释放了资源，这样能使其它被阻塞的进程获得资源继续运行。
3. 在经过一系列简化后若能消去图中的所有的边，使所有进程结点都孤立，则称该图是可完全简化的，反之是不可完全简化的。
   9，若资源分配图中没有环出现，则不会产生进程死锁；如果有环，可能存在死锁
   若每个资源类型均只有一个实例，有环一定有死锁
   若每个资源类型有多个实例，有环并不意味着已经出现了死锁
   10， 思考：不同的简化顺序，是否会得到不同的简化图？
   死锁定理可表述为“当且仅当某状态的资源分配图是不可完全简化时，就会产生死锁”。（死锁状态的充分条件）
   死锁检测算法的数据结构与银行家算法类似，在此不再阐述。
   11，死锁检测算法的应用取决于两个因素：
   死锁发生的频率：经常发生死锁的系统需要经常调用检测算法。
   死锁影响的进程数量：参与死锁循环的进程数量可能会不断增加。
   经常性的调用死锁检测算法会增加系统计算开销，另一个不太昂贵的方法是在一个不频繁的时间间隔中调用或由人工方式确定激活策略
   12，检测到死锁后可以采用多种措施解除
   资源抢占
   逐步从进程中抢占资源给其他进程使用，直到死锁环被打破为止，此方法需要考虑选择最小代价牺牲品、如何回滚至安全状态、如何避免饥饿。
   进程终止
   终止所有死锁进程：代价大，被终止进程的前期工作必须放弃。
   一次终止一个进程，逐个撤销，直到取消死锁循环为止：系统开销大，每次终止进程时都要调用死锁检测算法确定进程是否仍处于死锁。
   13，学习要求
   掌握处理机调度的基本概念
   掌握各种调度算法
   掌握实时调度算法
   掌握死锁产生的原因、预防办法及检测与解决方法
   深入理解银行家算法，掌握其用法，会使用银行家算法解决实际问题

这篇文章仅供个人日常复习使用，如有错误请留言，在此感谢