•        多道程序设计
%A •        进程
%A •        进程间的相互作用
%A •        进程间的通信
%A •        进程控制
%A •        进程调度（CPU调度）
%A •        死锁
%A 2.1 多道程序设计
%A •        顺序程序                并发程序                        多道程序设计
%A 2.1.1．顺序程序
%A 程序:指令或语句序列,体现了某种算法,所有程序是顺序的
%A 顺序环境: 在计算机系统中只有一个程序在运行,这个程序独占系统中所有资源,其执行不受外界影响。
%A 2.1.1．顺序程序
%A 特征：程序执行的顺序性：
%A 程序执行的封闭性：  独占资源，执行过程中不受外界影响。
%A    程序结果的可再现性：程序运行结果与程序执行速度无关，只要初始状态相同，结果应相同。
%A 2.1.2 并发程序
%A 并发环境：  在一定时间内物理机器上有两个或两个以上的程序同处于开始运行但尚未结束的状态，并且次序不是事先确定的。
%A 特征：(1)不可再现性:并发程序执行的结果与其执行的相对速度有关，是不确定的。
%A (2) 在并发环境下程序的执行是间断性的。
%A (3) 资源共享：系统中资源被多个进程使用。
%A (4) 制约性：        进程之间可相互作用（相互制约）,可分为直接作用和间接作用。
%A (5) 程序和计算不再一一对应。
%A （计算：一个程序的执行。）
%A 引入并发的目的：引入并发是为了提高资源利用率，从而提高系统效率。
%A 并发与并行概念的区别：concurrency,parallel
%A 2.1.3 多道程序设计
%A 定义：Multiprogramming
%A 多道程序设计是指允许多个程序同时进入内存并运行。
%A （引入目的是为了提高系统效率）   与并发不完全是一个概念,但效果相似。
%A 考虑因素：在多道程序环境下如何向用户提供服务;在并发程序之间如何正确传递消息（通讯）
%A 如何对CPU进行调度，保证每个用户相对公平地得到CPU（CPU是一个只可调度，不可分配的资源。）
%A 如何管理其它资源： 当各用户对资源使用上发生冲突时，如何处理竞争。
%A         对CPU只能通过调度来解决竞争问题，而对于其它资源通过申请―分配―使用―回收的办法进行管理，当且仅当占有CPU的时候才可以申请，否则要排队等候。
%A 2.1.4  与时间有关的错误
%A 一个飞机订票系统，两个终端，运行T1、T2进程
%A T1 :                T2:
%A ...                 ...
%A Read(x);            read(x);
%A if x>=1 then        if x>=1 then
%A    x:=x-1;             x:=x-1;
%A write(x);           write(x);
%A ...                 ...
%A Cobegin
%A     get;
%A     copy;
%A     put;
%A Coend
%A             f       s   t    g
%A 初始状态    3,4,...,m  2   2    (1,2)
%A g,c,p       4,5,...,m  3   3    (1,2,3) 
%A g,p,c       4,5,...,m  3   3    (1,2,2) 
%A c,g,p       4,5,...,m  3   2    (1,2,2) 
%A c,p,g       4,5,...,m  3   2    (1,2,2) 
%A p,c,g       4,5,...,m  3   2    (1,2,2) 
%A p,g,c       4,5,...,m  3   3    (1,2,2) 
%A 设信息长度为m，有多少种可能性？
%A 2.2.1 进程的概念
%A 定义：Process
%A   进程是具有独立功能的程序关于某个数据集合上的一次运行活动，是系统进行资源分配和调度的独立单位。
%A 程序与进程之间的区别：
%A 进程更能真实地描述并发，而程序不能。
%A 进程是由程序和数据两部分组成的。
%A 程序是动态的，进程是动态的。
%A 进程有生命周期，有诞生有消亡，短暂的。而程序是相对长久的。
%A 一个程序可对应多个进程，反之亦然。
%A 进程具有创建其它进程的功能，而程序没有。
%A 进程的分类：
%A                 系统进程：
%A                 用户进程：
%A （系统进程优先于用户进程）
%A 2.2.2 进程的基本状态及其转换
%A 进程的三种基本状态：
%A         进程在生命消亡前处于且仅处于三种基本状态之一。
%A         不同系统设置的进程状态数目不同。
%A 运行态（Running）：        进程占有CPU，并在CPU上运行。
%A 就绪态（Ready）：
%A                 一个进程已经具备运行条件，但由于无CPU暂时不能运行的状态。（当调度给其CPU时，立即可以运行）
%A 等待态（Blocked）：阻塞态、挂起态、封锁态.冻结态、睡眠态
%A                 指进程因等待某种事件的发生而暂时不能运行的状态。（即使CPU空闲，该进程也不可运行）
%A 状态转换：在进程运行过程中，由于自身进展情况及外界环境的变化，这三种基本状态可以依据一定的条件相互转换。
%A  就绪―运行: 被调度程序选中;
%A  运行―就绪: 时间片到时,或有更高优先级的进程出现；
%A  运行―等待: 等待某事件发生;    
%A  等待―就绪: 等待的事件发生了。
%A 2.2.3 进程控制块
%A （Process Control Block）
%A 概念： 系统为了管理进程设置的一个专门的数据结构，用它来记录进程的外部特征，描述进程的运动变化过程。
%A 系统利用PCB来控制和管理进程，所以PCB是系统感知进程存在的唯一标志。
%A 进程与PCB是一一对应的。
%A PCB的内容：
%A 调度信息：
%A         进程名；进程的内部标识；用户名；进程状态；进程优先级；进程的存储信息（起始地址，长度）；进程资源清单；进程家族关系；进程的队列指针；进程的消息队列指针；进程当前打开的文件。
%A 现场信息：        记录了重要的寄存器；(虚)时钟等内容。
%A PCB表：系统把所有PCB组织在一起，并把它们放在内存的固定区域，就构成了PCB表。
%A   PCB表的大小决定了系统中最多可同时存在的进程个数，称为系统的并发度。
%A （注：多道程序中的多道与系统并发度不同）
%A 进程控制块（Process Control Block）
%A PCB表组织方式：
%A   常用索引方式，对具有相同状态进程，分别设置各自的PCB索引表，表明PCB在PCB表中的地址。
%A （其他方式：线性表或链表）
%A
%A         进程队列：不同状态进程分别组成队列
%A                 运行队列、就绪队列、等待队列
%A 2.2.4 进程的特征  
%A 并发性：任何进程都可以同其它进程一起向前推进。
%A 动态性：
%A         进程对应程序的执行：
%A                 进程是动态产生，动态消亡的。
%A                 进程在生命周期内，在三种基本状态之间转换。
%A 独立性：        进程是CPU调度的一个独立单位。
%A 交互性：        指进程在执行过程中可能与其它进程产生直接或间接的关系。
%A 异步性：        每个进程都与其相对独立的不可预知的速度向前推进。
%A 结构性：        进程的组成：程序+数据+PCB
%A 可再入程序：
%A                 可被多个进程同时调用的程序，具有下列性质：
%A                 它是纯代码的，即在执行过程中自身不改变，调用它的进程应该提供数据区。
%A 【思考题】：
%A 1．如果系统中有几个进程，运行的进程最多几个，最少几个；就绪进程最多几个最少几个；等待进程最多几个，最少几个。
%A 2. 有没有这样的状态转换，为什么：      
%A                 等待―运行   ；   就绪―等待
%A 3. 一个转换发生，是否另一个转换一定发生，找出所有的可能。
%A 4. 举几个日常生活中类似进程的例子。
%A 2.3 进程间的相互作用
%A 进程间的联系
%A 进程的同步机制──信号量及P.V操作（解决进程同步互斥问题）
%A 2.3.1 进程间的联系
%A 相交进程与无关进程
%A 相交进程：指多个并发进程在逻辑上有某种联系。
%A 无关进程（不相交进程）：在逻辑上无任何联系的进程。
%A 直接作用和间接作用
%A 直接作用：进程间的相互联系是有意识的安排的，直接作用只发生在相交进程间。
%A 间接作用：进程间要通过某种中介发生联系，是无意识安排的，可发生在相交进程之间，也可发生在无关进程之间。
%A 进程的同步（直接作用）
%A 进程的同步：synchronism
%A         指系统中一些进程需要相互合作，共同完成一项任务。具体说，一个进程运行到某一点时要求另一伙伴进程为它提供消息，在未获得消息之前，该进程处于等待状态，获得消息后被唤醒进入就绪态。
%A 例:  
%A        司机   P1       售票员  P2
%A        REPEAT          REPEAT
%A        启动            关门
%A        正常运行        售票
%A        到站停          开门
%A        UNTIL FALSE     UNTIL FALSE
%A 进程的互斥（间接作用）mutual exclusion  
%A         由于各进程要求共享资源，而有些资源需要互斥使用，因此各进程间竞争使用这些资源，进程的这种关系为进程的互斥。
%A 临界资源：critical resource
%A 系统中某些资源一次只允许一个进程使用，称这样的资源为临界资源或互斥资源或共享变量。
%A 临界区（互斥区）：critical section
%A         一个程序片段的集合，这些程序片段分散在不同的进程中，对某个共享的数据结构（共享资源）进行操作。
%A 在进程中涉及到临界资源的程序段叫临界区。
%A 进程的互斥（间接作用）
%A 使用互斥区的原则：
%A 有空让进：当无进程在互斥区时，任何有权使用互斥区的进程可进入。
%A 无空等待：不允许两个以上的进程同时进入互斥区。
%A 有限等待：任何进入互斥区的要求应在有限的时间内得到满足。
%A 前提：任何进程无权停止其它进程的运行, 进程之间相对运行速度无硬性规定
%A 解决方法：
%A 硬件（当一个进程进入临界区,就屏蔽所有中断，但成本高。）
%A 软件（用编程解决，但常常忙等待。 ）
%A 软件解法 (1)
%A       free: 表示临界状态
%A         true: 无进程在临界区(初值)
%A         false:有进程在临界区
%A            ....
%A   L: if free then
%A             begin
%A             free:=false;
%A            ‘进入临界区’
%A             end
%A              else goto L;
%A      free:=true
%A 软件解法 (2)
%A turn: true    P进入临界区
%A       false   Q进入临界区
%A       ....
%A P: repeat until turn;
%A         ‘进入临界区’
%A       turn:=flase;
%A Q: repeat until not turn;
%A         ‘进入临界区’
%A      turn:=true;
%A 软件解法：(3)
%A pturn,qturn: 初值为false
%A P进入临界区的条件: pturn∧ not qturn
%A Q进入临界区的条件: not pturn∧ qturn
%A P   ....                  Q   .....
%A pturn:=true;               pturn:=ture;
%A repeat until not qturn;   repeat until not pturn
%A ‘进入临界区’                ‘进入临界区’
%A pturn:=false;              qturn:=false
%A     ...                       ...
%A
%A 软件解法(4) Dekker算法:
%A 在解法(3)基础上引入turn枚举类型  初值任意
%A     P : Repeat
%A       pturn:=true;
%A       while qturn do
%A       if turn=2 then begin
%A                      pturn:=false;
%A                      while turn=2 do
%A                         pturn:=true
%A                      end;
%A       ‘进入临界区‘
%A       turn:=2;
%A       ptum:=false;
%A        .....
%A         Until false
%A     Q : Repeat
%A       qturn:=true;
%A       while pturn do
%A       if turn=1 then begin
%A                      qturn:=false;
%A                      while turn=1 do
%A                         qturn:=true
%A                      end;
%A       ‘进入临界区‘
%A       turn:=1;
%A       qtum:=false;
%A        .....
%A         Until false
%A 软件解法的缺点:
%A    1. 忙等待
%A    2. 实现过于复杂,需要高的编程技巧
%A 硬件解法 (1)
%A    “测试并建立”指令
%A Function Test_and_Set
%A    (var target:boolean):boolean
%A begin
%A     Test_and_Set:=target;
%A     target:=true
%A end
%A Var lock:boolean;
%A 进入临界区前执行：
%A While Test_and_Set(lock) do
%A     skip;
%A 离开临界区后执行：
%A lock:=false;
%A 硬件解法 (2)
%A    “交换”指令
%A Function Swap(var a,b:boolean)
%A Var temp:boolean;
%A begin
%A     temp:=a;
%A     a:=b;
%A     b:=temp
%A end
%A 每一组共享变量定义一个全局变量
%A Var lock:boolean;
%A 每个进程定义一个局部变量
%A Var key:boolean;
%A 进入临界区前执行：
%A     key:=true;
%A     repeat
%A         swap(lock,key);
%A     until key=false;
%A 离开临界区后执行：lock:=false;
%A 硬件解法 (3)
%A    “开关中断”指令
%A 进入临界区前执行：
%A     执行“关中断”指令
%A 离开临界区后执行：
%A     执行“开中断”指令
%A 2.3.2 进程的同步机制──
%A 信号量及P.V操作（解决进程同步）
%A 同步机制：
%A     信号量及P、V操作；管程；条件临界域；路径表达式等（用于集中式系统中）
%A     会合；通信顺序进程；分布进程；远程过程调用等（适用于分布式系统中）
%A 同步机制应满足的基本要求：
%A * 描述能力                * 可以实现
%A * 效率高                        * 使用方便
%A 信号量：semaphore
%A                 是一个数据结构。定义如下：
%A TYPE  semaphore= RECORD
%A         Value：integer
%A         Queue：Pointer_PCB
%A END
%A 信号量说明：
%A     VAR：S：semaphore
%A P.V操作
%A P操作
%A P(s) :
%A s . Value : = s . Value - 1;
%A IF  s . Value < 0 then
%A         将该进程状态置为等待状态,然后将该进程的PCB插入相应的等待队列末尾。
%A V操作
%A V(s) :
%A s . Value : = s . Value + 1;
%A IF  s . Value < = 0 then
%A 唤醒相应等待队列中等待的一个进程,改变其状态为就绪态，并将其插入就绪队列。
%A P、V操作为原语操作
%A 原语：primitive or atomic action
%A 是由若干多机器指令构成的完成某种特定功能的一段程序，具有不可分割性。
%A         即原语的执行必须是连续的，在执行过程中不允许被中断。
%A 实现：开关中断
%A 信号量的使用：
%A   必须置一次且只能置一次初值，初值不能为负数  
%A   只能执行P、V操作
%A 用P.V操作解决进程间互斥问题
%A 经典的生产者─消费者问题
%A 同步问题：
%A                 P进程不能往“满”的缓冲区中放产品，设置信号量为S1
%A       Q进程不能从“空”的缓冲区中取产品，设置信号量S2
%A P：                             Q：
%A Repeat                        Repeat
%A      生产一个产品；        P(s2);
%A      送产品到缓冲区；    从缓冲区取产品；
%A      V(s2);                          V(s1);
%A      P(s1)                            消费产品
%A Until false;                  Until false;
%A P：                            
%A Repeat                      
%A       P(s1);
%A      生产一个产品；        
%A      送产品到缓冲区；  
%A      V(s2)
%A Until false;
%A 【思考题】要不要对缓冲区（临界资源）进行互斥操作？
%A P：I:= 0
%A REPEAT
%A 生产产品；
%A P(S1)
%A 往Buffer [I]中放产品；
%A V(S2)
%A I:=(I+1) mod n
%A UNTIL false
%A Q： J:= 0
%A     REPEAT
%A     P(S2)
%A     从Buffer[J]取产品；
%A     V(S1)
%A     消费产品
%A     J:=(J+1) mod n
%A     UNTIL false
%A P.V操作讨论
%A 1) 信号量的物理含义：
%A S>0表示有S个资源可用；
%A S=0表示无资源可用；
%A S<0则| S |表示S等待队列中的进程个数。
%A P(S):表示申请一个资源;
%A V(S)表示释放一个资源。信号量的初值应该大于等于0
%A 2) P.V操作必须成对出现，有一个P操作就一定有一个V操作。
%A 当为互斥操作时，它们同处于同一进程。
%A 当为同步操作时，则不在同一进程中出现。
%A 如果P(S1)和P(S2)两个操作在一起，那么P操作的顺序至关重要,一个同步P操作与一个互斥P操作在一起时同步P操作在互斥P操作前。
%A 而两个V操作无关紧要。
%A 3）P.V操作的优缺点
%A 优点：简单，而且表达能力强（用P.V操作可解决任何同步互斥问题。）
%A 缺点：不够安全；P.V操作使用不当会出现死锁；遇到复杂同步互斥问题时实现复杂。
%A 读者与写者问题
%A 第一类：读者优先
%A 如果读者来：1） 无读者写者，新读者可以读。
%A 有写者等，但有其它读者正在读，则新读者可以读。
%A 有其它读者，且有写者等候，新读者也可以读。
%A 如果写者来：2） 无读者，新写者可以写。
%A 有读者，新写者等待。
%A 有其它写者，新写者等待。
%A 2.哲学家就餐问题
%A Repeat
%A     思考；
%A     取fork[i];取fork[(i+1) mod 5]；
%A     进食；
%A     放fork[i];放fork[(i+1) mod 5]；
%A Until false;
%A state:array[0..4] of
%A               (思考，饥饿，进食）；
%A ph: array[0..4] of semaphore;
%A mutex:semaphore;
%A i:0..4;
%A 2.4 进程通信
%A 概念
%A 消息缓冲通信方式
%A 2.4.1 概念
%A         P.V操作实现的是进程之间的低级通讯，所以P.V为低级通讯原语。它只能传递简单的信号，不能传递交换大量信息。
%A         如果要在进程间传递大量信息则要用Send / Receive原语（高级通讯原语）。
%A 进程通信的方式
%A 共享内存：
%A 相互通讯进程间设有公共内存，一组进程向该公共内存中写，另一组进程从公共内存中读，通过这种方式实现两组进程间的信息交换。
%A 这种通信模式需要解决两个问题？
%A 进程通信的方式
%A 消息传递：
%A 系统为进程提供了两个高级通讯原语send和receive。
%A send：        当要进行消息传递时执行send
%A receive：当接收者要接收消息时执行receive
%A 消息传递模式
%A 消息缓冲：  在内存中开设缓冲区，接收进程接收传递。
%A 信箱通信：
%A 管道通信：
%A 直接方式：
%A 发送进程发消息时要指定接收进程的名字，
%A 反过来，接收时要指明发送进程的名字。
%A * 对称形式：一对一
%A * 非对称形式：多对一 （顾客/服务员）
%A 有缓冲（有界，****），无缓冲
%A 间接方式：
%A 发送进程发消息时不指定接收进程的名字，而是指定一个中间媒介，即信箱。进程间通过信箱实现通信。
%A   发送原语：send(MB,Message)
%A   接受原语：receive(MB,Message)
%A
%A 2.4.2 消息缓冲
%A （有界缓冲区原理）：
%A 在操作系统空间设置一组缓冲区，当发送进程需要发送消息时，执行send系统调用，产生自愿性中断，进入操作系统，操作系统为发送进程分配一个空缓冲区，并将所发送的消息从发送进程copy到缓冲区中，然后将该载有消息的缓冲区连接到接收进程的消息链链尾，如此就完成了发送过程。发送进程返回到用户态继续执行；
%A 在以后某个时刻，当接收进程执行到receive接收原语时，也产生自愿性中断进入操作系统，由操作系统将载有消息的缓冲区从消息链中取出，并把消息内容copy到接收进程空间，之后收回缓冲区，如此就完成了消息的接收，接收进程返回到用户态继续进行。
%A 消息缓冲区结构：
%A     消息长度                    消息正文
%A     发送者                    消息队列指针
%A 用P.V操作来实现Send原语:
%A Send（R，M）                P(m-mutex);
%A Begin                       把缓冲区挂到接收进程
%A     根据R找接收进程，       的消息链链尾;
%A     如果没找到出错返回;      V(m-mutex);
%A     申请空缓冲区P（s-b）；  V(s-m);
%A     P(b-mutex);              END
%A       摘空缓冲区;
%A     V(b-mutex);
%A     把消息从M处copy到空缓冲区;
%A 其中s-b初值:n ;s-m初值:0
%A
%A 管道通信方式 Pipe
%A         也称共享文件方式，基于文件系统，利用一个打开的共享文件连接两个相互通信的进程，文件作为缓冲传输介质。
%A 2.5 进程控制
%A   创建、撤消进程以及完成进程各状态之间的转换。由具有特定功能的原语完成。
%A    进程创建原语                                   进程撤消原语
%A    阻塞原语                                           唤醒原语
%A    挂起原语                                           激活（解挂）原语
%A 2.5.1 进程创建原语
%A 进程创建主要完成以下工作：
%A   创建一个PCB（找一个空PCB）；
%A   为进程分配内存等必要资源；
%A   填写PCB中各项目；
%A   把其挂到进程就绪队列。
%A 2.5.2 进程撤消原语
%A 收回进程所占有的资源；
%A 撤消该进程的PCB。
%A 2.5.3 进程阻塞原语
%A   处于运行状态的进程，在其运行过程中期待某一事件发生，如等待键盘输入；等待磁盘数据传输完成；等待其它进程发送消息，当被等待的事件未发生时，由进程自己执行阻塞原语，使自己由运行态变为阻塞态。
%A 2.5.4 进程唤醒原语
%A 2.6 进程调度（CPU调用）
%A 要解决的问题
%A WHAT：按什么原则分配CPU―进程调度算法
%A WHEN：何时分配CPU―进程调度的时机
%A HOW： 如何分配CPU―CPU调度过程
%A       （进程的上下文切换）
%A 2.6.1 进程调度算法
%A   1．进程调度
%A 进程调度的任务是控制协调进程对CPU的竞争即按一定的调度算法从就绪队列中选中一个进程，把CPU的使用权交给被选中的进程。
%A 2．算法确定的原则
%A 具有公平性
%A 资源利用率，特别是CPU利用率
%A 在交互式系统情况下要追求响应时间，其越短越好。
%A 在批处理系统情况下要追求系统吞吐量
%A   3．各种算法
%A 先进先出进程调度算法（FIFO）
%A    按照进程就绪的先后次序来调度进程。
%A    优点:实现简单
%A    缺点:是没考虑进程的优先级
%A 基于优先数的调度
%A （HPF―Highest Priority First）
%A 优先选择就绪队列中优先级最高的进程投入运行
%A 优先级根据优先数来决定
%A 确定优先数的方法
%A 静态优先数法：
%A   在进程创建时指定优先数，在进程运行时优先数不变。
%A 动态优先数法：
%A   在进程创建时创立一个优先数，但在其生命周期内优先数可以动态变化。如等待时间长优先数可改变。
%A 两种占用CPU的方式
%A 可剥夺式（可抢占式Preemptive）：
%A 当有比正在运行的进程优先级更高的进程就绪时，系统可强行剥夺正在运行进程的CPU，以供具有更高优先级的进程使用。
%A 不可剥夺式（不可抢占式Nonpreemptive ）：
%A 某一进程被调度运行后除非由于它自身原因不能运行，否则一直运行下去。
%A 时间片轮转程序调度算法
%A (RR―Round Robin)
%A 把CPU划分成若干时间片,并且按顺序赋给旧序列队中每一个进程，进程轮流占有CPU，当时间片用完时，进程未执行完毕，则系统剥夺该进程的CPU，该进程排列旧序列队末尾。同时选择另一个进程运行。
%A 分时系统中常用时间片轮转法
%A 时间片选择问题：
%A     固定时间片
%A     可变时间片
%A 与时间片大小有关的因素：
%A     系统响应时间
%A     就绪进程个数
%A     CPU能力
%A 多队列反馈调度算法：
%A 将就绪队列分为N级，每个就绪队列分配给不同的时间片，队列级别越高，时间越长，级别越小，时间片越小，最后级采用时间片轮转，其它队列用先进先出； 系统从第一级调用，当第一级为空时， 系统转向第二个了队列，.....当运行进程用完一个时间片，放弃CPU，进入下一级队列，等待进程被唤醒时，进入原来的就绪队列，当进程第一次就绪时，进入第一级队列          
%A
%A * 首先系统中设置多个就绪队列
%A * 每个就绪队列分配给不同时间片，优先级高的为第一级队列给他时间片小，随着队列级别的降低，时间片加大
%A * 各个队列按照先进先出调度算法
%A * 一个新进程就绪后进入第一级队列
%A
%A * 进程由于等待而放弃CPU后，进入等待队列，一旦等待的事件发生，则回到原来的就绪队列
%A * 当有一个优先级更高的进程就绪时，可以抢占CPU，被抢占进程回到就绪队列末尾
%A * 当第一级队列空时，就去调度第二级队列，如此类推
%A * 当时间片到后，进程放弃CPU，回到下一级队列
%A 2.6.2 进程调度的时机
%A 当一个进程运行完毕，或由于某种错误而终止运行
%A 当一个进程在运行中处于等待状态（等待I/O）
%A 分时系统中时间片到
%A 当有一个优先级更高的进程就绪（可抢占式），例如：新创建一个进程，一个等待进程变成就绪。
%A 在进程通讯中，执行中的进程执行了某种原语操作（P操作，阻塞原语，唤醒原语）
%A 2.6.3 CPU调度过程
%A * 保存现场：顺序保存，最后一步保存PSW
%A * 选择要运行的程序
%A   （如果没有就绪进程,系统会安排一个闲逛进程(idle),没有其它进程时该进程一直运行,在执行过程中可接收中断）
%A * 恢复现场：最后一步恢复选中进程的PSW
%A 2.7 系统核心
%A 系统核心：向上提供多个无中断的虚拟机器，在核心内不允许中断。
%A 特点：* 为进程运行提供一个舞台
%A       * 核心常驻内存
%A       * 设计短小精焊
%A 2.7.1 核心的组成
%A    中断处理
%A    进程管理:  调度 控制 通讯 互斥 同步等
%A    原语管理:  在核心中提供一系列原语，同步,通信，创建，撤消等
%A    队列管理:
%A 队列数据结构:指向队首的表指针
%A 三个队列: 运行，就绪，等待队列
%A 排队方式: 排队首
%A            排队尾
%A            插  队
%A 出队方式: 队首出队/队中出队
%A 队列管理: 中断之后，进程调度之前
%A 现场管理:
%A 保存现场;注意顺序,中断之后第一步
%A 恢复现场:恢复时机，进程调度最后一步
%A 时钟管理: 以固定频率 +1 -1
%A    用途:进入绝对时钟
%A         间隔时钟
%A         进行分析比较
%A    虚时钟:
%A 每个进程分配给一个虚时钟来记录CPU时间,这个时钟是虚时钟。
%A 虚时钟存放于PCB中，属于现场一部分，进程运行时，将虚时钟放入内存开避的专门单元，离开CPU放入 PCB中。
%A 2.7.2 核心处理流程
%A 进入核心的唯一入口:中断
%A 中断后进入核心，由硬件完成            
%A 2.7.3 内核的执行的特点
%A 由中断驱动的: 中断→内核→退出
%A 内核执行是连续的
%A 内核执行过程中在屏蔽状态下
%A 内核使用特权指令
%A
%A 2.8 死锁
%A 死锁的基本概念
%A 死锁的解决方案
%A    （预防，避免，检测及解除）
%A 资源分配图
%A 死锁的现象
%A 2.8.1 死锁的基本概念
%A 死锁的定义：
%A   一组进程中，每个进程都无限等待被该组进程中另一进程所占有的资源，因而永远无法得到的资源，这种现象称为进程死锁，这一组进程就称为死锁进程。
%A 2.8.1 死锁的基本概念
%A 死锁（Deadlock）
%A 饥饿（Starvation）
%A 关于死锁的一些结论：
%A    参与死锁的进程至少有两个
%A     （两个以上进程才会出现死锁）
%A 参与死锁的进程至少有两个已经占有资源
%A   参与死锁的所有进程都在等待资源
%A   参与死锁的进程是当前系统中所有进程的子集
%A 注：如果死锁发生，会浪费大量系统资源，甚至导致系统崩溃。
%A 资源
%A 永久性资源：可以被多个进程多次使用（可再用资源）
%A * 可抢占资源
%A * 不可抢占资源
%A 临时性资源：只可使用一次的资源；如信号量,中断信号，同步信号等（可消耗性资源）
%A “申请--分配--使用--释放”模式
%A 产生死锁的四个必要条件：
%A 互斥使用（资源独占）
%A 不可强占（不可剥夺）
%A 请求和保持（部分分配，占有申请）
%A 循环等待
%A 1) 互斥使用（资源独占）：
%A 一个资源每次只能给一个进程使用
%A 2) 不可强占（不可剥夺）：
%A   资源申请者不能强行的从资源占有者手中夺取资源，资源只能由占有者自愿释放
%A 3) 请求和保持：
%A （部分分配，占有申请）
%A 一个进程在申请新的资源的同时保持对原有资源的占有。
%A （只有这样才是动态申请，动态分配）
%A 4) 循环等待：
%A 存在一个进程等待队列
%A {P1 , P2 , … , Pn},
%A 其中P1等待P2占有的资源，P2等待P3占有的资源，…，Pn等待P1占有的资源，形成一个进程等待环路。
%A 2.8.2 死锁的解决方案
%A 1. 产生死锁的例子
%A     申请不同类型资源产生死锁  
%A 申请同类资源产生死锁（如内存）
%A 设有资源R，R有m个分配单位，由n个进程P1,P2,…,Pn（n > m）共享。假设每个进程对R的申请和释放符合下列原则：
%A   * 一次只能申请一个单位
%A   * 满足总申请后才能使用
%A   * 使用完后一次性释放
%A 资源分配不当导致死锁产生。
%A 2. 解决死锁的方法
%A 不让死锁发生：
%A 静态策略：设计合适的资源分配算法，不让死锁发生
%A 动态策略：
%A 让死锁发生：
%A 2.7.3 死锁预防
%A 定义： 在系统设计时确定资源分配算法，保证不发生死锁。具体的做法是破坏产生死锁的四个必要条件之一。
%A 破坏“不可剥夺”条件
%A 在允许进程动态申请资源前提下规定，一个进程在申请新的资源不能立即得到满足而变为等待状态之前，必须释放已占有的全部资源，若需要再重新申请。
%A 破坏“请求和保持”条件
%A 要求每个进程在运行前必须一次性申请它所要求的所有资源，且仅当该进程所要资源均可满足时才给予一次性分配。
%A 破坏“循环等待”条件
%A     采用资源有序分配法：
%A 把系统中所有资源编号，进程在申请资源时必须严格按资源编号的递增次序进行，否则操作系统不予分配。
%A 2.7.4 死锁避免
%A 定义： 在系统运行过程中，对进程发出的每一个系统能够满足的资源申请进行动态检查，并根据检查结果决定是否分配资源，若分配后系统可能发生死锁，则不予分配，否则予以分配。
%A 安全状态与不安全状态
%A 安全状态： 如果存在一个由系统中所有进程构成的安全队列P1，…Pn，则系统处于安全状态。
%A 安全队列：  一个进程序列{P1，…，Pn}是安全的，如果对于每一个进程Pi(1≤i≤n），它以后尚需要的资源量不超过系统当前剩余资源量与所有进程Pj (j < i )当前占有资源量之和，系统处于安全状态。
%A (安全状态一定是没有死锁发生的)
%A 不安全状态:不存在一个安全序列，不安全序列一定导致死锁。
%A 死锁避免：   允许死锁发生，操作系统不断监视系统进展情况，判断死锁是否发生。
%A     一旦死锁发生则采取专门的措施，解除死锁并以最小的代价恢复操作系统运行。
%A 银行家算法
%A n：系统中进程的总数
%A m：资源类总数
%A Available:
%A     ARRAY[1..m] of integer;
%A Max:
%A     ARRAY[1..n,1..m] of integer;
%A 银行家算法
%A Allocation: ARRAY[1..n,1..m] of integer;
%A Need: ARRAY[1..n,1..m] of integer;
%A Request: ARRAY[1..n,1..m] of integer;
%A 简记符号：
%A Available[i]
%A Max[i]
%A Allocation[i]
%A Need[i]
%A Request[i]
%A 当进程pi提出资源申请时，系统执行下列步骤：
%A （1）若Request[i]≤Need[i],转（2）；
%A      否则错误返回
%A （2）若Request[i]≤Available,
%A      转（3）；否则进程等待
%A (3）假设系统分配了资源，则有：
%A Available:=Available-Request[i];
%A Allocation[i]:=Allocation[i]+Request[i];
%A Need[i]:=Need[i]-Request[i]
%A 若系统新状态是安全的，则分配完成
%A 若系统新状态是不安全的，则恢复原状态，进程等待
%A 为进行安全性检查，定义数据结构：
%A Work:ARRAY[1..m] of integer;
%A Finish:ARRAY[1..n] of Boolean;
%A 安全性检查的步骤：
%A (1) Work:=Available;
%A     Finish:=false;
%A (2) 寻找满足条件的i：
%A     a.Finish[i]=false;
%A     b.Need[i]≤Work;
%A 如果不存在，则转(4)
%A (3) Work:=Work+Allocation[i];
%A     Finish[i]:=true;
%A     转(1)
%A (4) 若对所有i,Finish[i]=true,则系统处于安全状态，否则处于不安全状态
%A 2.7.5  死锁的检测与解除
%A 检测时机： 当进程等待时检测死锁
%A    （其缺点是系统的开销大）
%A 定时检测:  系统资源利用率下降时检测死锁
%A 死锁检测算法
%A * 每个进程和资源指定唯一编号
%A * 设置一张资源分配表
%A 记录各进程与其占用资源之间的关系
%A * 设置一张进程等待表
%A 记录各进程与要申请资源之间的关系
%A 资源分配表       进程等待表
%A r1   p2          p1   r1
%A r2   p5          p2   r3
%A r3   p4          p4   r4
%A r4   p1
%A …   …          …   …
%A 死锁的解除：
%A 重要的是以最小的代价恢复系统的运行。方法如下：
%A 1）重新启动
%A 2）撤消进程
%A 3）剥夺资源
%A 4）进程回退
%A 2.7.6 资源分配图
%A 用有向图描述进程的死锁
%A      准确、形象
%A 系统由若干类资源构成，一类资源称为一个资源类；每个资源类中包含若干个同种资源，称为资源实例。
%A 二元组G=（V，E）
%A V：结点集，分为P，R两部分
%A P={p1,p2,…,pn}
%A R={r1,r2,…,rm}
%A E：边的集合，其元素为有序二元组
%A     (pi,rj)或(rj,pi)
%A 表示法
%A 资源类（资源的不同类型）用方框表示
%A 资源实例（存在于每个资源中）用黑圆点表示
%A 进程   用圆圈中加进程名表示
%A 分配边： 资源实例进程的一条有向边
%A 申请边： 进程资源类的一条有向边
%A 有环无死锁
%A 有环有死锁
%A 死锁定理
%A   如果资源分配图中没有环路，则系统中没有死锁，如果图中存在环路则系统中可能存在死锁。
%A   如果每个资源类中只包含一个资源实例，则环路是死锁存在的充分必要条件。
%A 资源分配图化简：方法如下
%A 1）找一个非孤立点进程结点且只有分配边，去掉分配边，将其变为孤立结点。
%A 2）再把相应的资源分配给一个等待该资源的进程，即将某进程的申请边变为分配边
%A