《计算机操作系统》学习笔记（二）---处理机管理

在传统的多道程序系统中，处理机的分配和运行，都是以进程为基本单位，因而对处理机的管理，可归结为对进程管理，对进程的管理主要有包括：进程控制、进程同步、进程通信、进程调度。
一、进程的基本概念
  1、程序有两种执行方式，其中包括顺序执行和并发执行。
     顺序执行的特征为：顺序性、封闭性（程序运行时独占全机资源，其执行结果不受外界影响）、可再现性（只要运行环境和初始条件相同，程序重复执行都获得相同结果）；
     并发执行的特征为：间断性（程序之间的相互制约导致“执行-暂停-执行”）、失去封闭性、不可再现性（即使运行环境和初始条件相同，程序重复执行都获得结果也不一定相同）；
  2、进程的特征：
     （1）结构性
         由程序段、数据段和PCB三部分便构成了进程实体；
     （2）动态性
         进程由创建而产生，由调度而执行，由撤销而消亡，进程是有一定的生命周期，是动态的；
         程序只是一组有序的指令集合，并存放于某些介质上，其本身不具有运动的含义，是静态的；
     （3）并发性
         这是指多个进程实体同存于内存中，且能在一段时间内同时运行；
     （4）独立性
         进程是一个能独立运行、独立分配资源和独立接受调度的基本单位；
     （5）异步性
         这是指进程按各自独立的、不可预知的速度向前推进。
   3、进程的基本状态：
      一共4种：就绪状态、执行状态、阻塞状态、挂起状态
      就绪状态：当前进程已分配到除CPU以外的所有必要资源；
      执行状态：当前进程已分配到包括CPU在内的所有必要资源；

      阻塞状态：正在执行的进程请求I/O，申请缓冲空间等；

      挂起状态：即将该进程从内存中暂时调出到外存，原因如：终端用户的请求、父进程的请求、负荷调节的需要、操作系统的需要。

   4、进程控制块
      系统将所有的PCB组织成若干个链表（或队列），存放在操作系统中专门开辟的PCB区内。PCB是进程存在的唯一标志，常驻于内存中。
      PCB主要包括四方面的信息：进程标识符、处理机状态、进程调度信息、进程控制信息
      （1）进程标识符
           内部标识符，进程的序号，方便系统调用；
           外部标识符，由创建者提供，方便用户使用；
      （2）处理机状态
           处理机在运行时，许多信息都放在寄存器中。当处理机被中断时，所有这些信息都必须保存在PCB中，以便中断后重新执行。这些信息包括（通用寄存器、指令计数器、程序状态字PSW、用户栈指针）这些寄存器的数据；
      （3）进程调度信息
           与进程调度和进程对换的相关信息，包括：进程状态、进程优先级、进程调度的其他信息和事件（即阻塞原因）；
      （4）进程控制信息
           包括程序和数据的地址、进程同步和通信机制（如消息队列指针、信号量等）、资源清单（即进程所需的全部资源）、链接指针（指向下一个PCB）。
      PCB在内存中的组织方式有链接方式和索引方式两种。

二、进程控制

   进程控制包括：进程的创建、进程的终止、进程的状态转换
   1、进程的创建
      引起创建进程的事件包括：用户登录、作业调度、提供服务、应用请求。
      创建进程的过程：申请空白PCB—>为新进程分配资源—>初始化PCB—>将PCB插入就绪队列。
   2、进程的终止
      引起终止进程的事件包括：正常结束、异常结束、外界干预（如父进程终止）。
      终止进程的过程：根据进程标识符读取PCB（若执行状态，置调度标志真）—>终止子孙进程—>释放全部资源—>将PCB从队列移除。
   3、进程的状态转换
      （1）进程的阻塞和唤醒
           引起事件：请求系统服务（阻塞）、启动某种操作（唤醒）、新数据尚未到达（阻塞）、无新工作可做（阻塞）。
           进程阻塞的过程：停止本进程—>改变PCB—>调度新进程；
           进程唤醒的过程：PCB从阻塞队列移除—>改变PCB—>PCB插入到就绪队列；
      （2）进程的挂起和激活
           进程挂起的进程：改变PCB—>复制PCB（方便用户或父进程考查该进程）—>调度新进程；
           进程激活的进程：将该进程从外存调入内存—>改变PCB—>调度该进程；
三、进程同步

   进程同步的主要任务，是是并发执行的诸进程之间能有效地共享资源和相互合作，从而使程序的执行具有可再现性。
   1、同步机制
      间接相互制约关系：如：A进程使用一资源，B进程只能等待，即A进程通过共享资源简介制约B进程；
      直接相互制约关系：如：B进程执行所需的数据由A进程得到，即A进程直接制约B进程；
      同步机制应遵循的规则包括：空闲让进、忙则等待、有限等待、让权等待。
   2、信号量机制
      其中包括整形信号量、记录型信号量、AND信号量。
      三种信号量的区别：
      整形信号量N只是一个整型值，代表着某类资源的数目，当N<=0，即后申请使用该资源的进程会不断地查询是否N>0，一旦N>0，即取之来用，这是一种忙等现象；
      记录型信号量S是一个结构体，S.value相当于整形信号量N，当S.value<=0，即后申请使用该资源的进程会进入阻塞状态，并将其挂在S.L中，等待唤醒，遵循“让权等待”策略；
      AND信号量代表着多类资源的数目，其中有一类资源的数目小于零，即分配资源失败。
四、进程通信

   高级进程通信机制有五种：共享存储器系统、消息传递系统、管道通信系统、信号机制、信号量机制。
   
   1、共享存储器系统（传送大量数据，锁机制）：
   共享内存区域是被多个进程共享的一部分物理内存。如果多个进程都把该内存区域映射到自己的虚拟地址空间，则这些进程就都可以直接访问该共享内存区域，从而可以通过该区域进行通信。共享内存是进程间共享数据的一种最快的方法，一个进程向共享内存区域写入了数据，共享这个内存区域的所有进程就可以立刻看到其中的内容。
   共享内存实现分为两个步骤:（1）创建共享内存（2）映射共享内存，将这段创建的共享内存映射到具体的进程空间去
   
   2、消息传递系统（消息缓冲队列通信机制，传送小量数据）：
      （1）进程间的数据交换是以格式化的消息（报文）为单位的，程序员直接利用系统提供的通信原语进行通信，操作系统隐藏了通信的实现细节。其中的直接通信方式即直接向某进程发送报文或直接向某进程接收报文，而间接通信方式即为向某信箱发送报文或向某信箱接收报文，其中的信箱为“中转站”，包括私有信箱、公用信箱、共享信箱。
      （2）由于消息缓冲机制中所使用的缓冲区为公用缓冲区，因此使用消息缓冲机制传送数据时，两通信进程必须满足如下条件。
第一，在发送进程把写入消息的缓冲区挂入消息队列时，应禁止其他进程对该消息队列的访问，否则，将引起消息队列的混乱。同理，当接收进程正从消息队列中取消息时，也应禁止其他进程对该队列的访问。
第二，当缓冲区中无消息存在时，接收进程不能接收到任何消息；而发送进程是否可以发送消息，则只由发送进程是否能够申请到缓冲区决定。

   3、管道通信系统（读者-写者）：
   管道是单向的、先进先出的、无结构的、固定大小的字节流，它把一个进程的标准输出和另一个进程的标准输入连接在一起。写进程在管道的尾端写入数据，读进程在管道的首端读出数据。数据读出后将从管道中移走，其它读进程都不能再读到这些数据。管道提供了简单的流控制机制。进程试图读空管道时，在有数据写入管道前，进程将一直阻塞。同样，管道已经满时，进程再试图写管道，在其它进程从管道中移走数据之前，写进程将一直阻塞；
   
   4、信号机制：发送信号
   
   5、信号量机制：P、V操作，进程间同步互斥，生产者-消费者，哲学家进餐等。
五、进程调度

   1、进程调度的种类
      高级调度：又叫作业调度，即每次要接纳多少个作业进入内存；
      中级调度：把那些暂时不能运行的进程调至外存上等待；
      低级调度：又叫进程调度，即将处理机分配给哪个进程使用。
      进程调度的准则：
      面向用户的准则包括：周转时间短、响应时间快、截止时间保证；
      面向系统的准则包括：系统吞吐量高、处理机利用率好、各类资源的平衡利用。
   2、调度算法
      （1）先来先服务调度算法（FCFS）：有利于长作业，而不利于短作业；
      （2）短作业优先调度（SJF）：对长作业不利；未考虑作业的紧迫程度；作业长短的时间估计不一定精确；
      （3）高优先权先调度读算法（FPF）：其中的高响应比优先调度算法比较理想；
      （4）基于时间片的轮转调度算法：其中的多级反馈队列调度算法比较理想；
   3、实时系统中的调度
      为了实现实时调度，系统应向调度进程提供相关信息，包括：就绪时间、开始截止时间和完成截止时间、处理时间、资源要求和优先级。常使用最早截止时间优先算法（EDF）（利用到开始截止时间）和最低松弛度优先算法（LLF）（利用到完成截止时间和处理时间）；
   4、多处理机系统中的调度
      多处理机系统的分类：从多处理机之间耦合的紧密程度分为紧密耦合和松弛耦合，根据系统中所用处理机的相同与否可分为对称多处理机系统和非对称多处理机系统。
      进程分配方式：静态分配，即一个进程从开始执行直至其完成，都被固定地分配到一个处理机上去执行；而动态分配，即系统中设有一个公共就绪队列，分配时，可将进程分配到任何一个处理机上；
      进程调度方式：自调度方式，即系统中设有一个公共就绪队列，哪一个处理机有空闲，就自己去该队列中取一就绪进程来运行；成组调度方式，即将一个进程中的一组线程分配到一组处理机上去执行，可面向所有应用程序平均分配处理机时间，也可以面向所有线程平均分配处理机时间；专用处理机分配，即专门为该应用程序分配一组处理器，每个线程一个处理机，直至该应用程序完成。
   5、死锁
      产生原因：竞争资源、进程间推进顺序非法；
      必要条件：互斥条件、请求和保持条件、不剥削条件、环路等待条件；
      处理方法：预防死锁（执行前预防）、避免死锁（执行时避免）、检测和解除死锁（执行后检测和解除）