• 要点：

  1. 基础：进程描述及控制
  2. 策略：进程调度
  3. 实现：互斥与同步
  4. 避免：死锁与饥饿
  5. 解决：几个经典问题

• 进程的引入

  1. 程序的顺序执行
     • 源代码程序，目标程序和可执行程序
     • 程序执行：编辑，编译，链接，执行
     • 程序的结构：顺序，分支，循环结构
     • 程序执行的特征：顺序性，封闭性，可再现性
  2. 程序并发执行
     • 多道程序设计技术：多个程序并发执行
     • 程序并发执行时的特征：间断性，非封闭性，不可再现性
     • 并发执行引发的问题：
       • 协调各程序的执行顺序：输入数据还未全部输入内存时，计算必须等待
       • 多个执行程序共享系统资源，程序之间可能会相互影响，甚至影响输出结果
       • 选择那些，多少个程序进入内存执行
       • 内存中的执行程序谁先执行，谁后执行
       • 内存如何有效分配？

• 引入进程带来的问题

  1. 增加了空间开销：为进程建立数据结构
  2. 额外的时间开销：管理和协调，跟踪，填写和更新有关数据结构，切换进程，保护现场
  3. 更难控制：协调多个进程竞争和共享资源如何预防；解决多个集成因为竞争资源而出现的故障
  4. 处理机的竞争尤为突出

• 进程的结构

  1. 组成（进程映像）：程序、数据集合、进程控制块PCB（Process Control Block）
  2. PCB是进程存在的唯一标志。创建进程时，创建PCB；进程结束时，系统将撤销其PCB
  3. PCB中的信息： 进程名、进程状态、进程优先级、信号量、现场保护区、进程参数、进程程序地址

• PCB

  1. 进程标识信息：进程的内部（系统分配给它的标示）和外部标示符（name of a person）
  2. 处理机状态信息：通用寄存器值，指令计数器值，程序状态字PSW值，用户栈指针值
  3. 进程调度信息：进程状态，进程优先权，进程调度的其他信息
  4. 其他信息：程序及数据指针，进程同步和通讯机制，资源清单，连接指针

•  PCB的组织方式

  1. 单一队列：所有进程的PCB通过链表组织成为一个单一队列。适用于进程数目不多的系统。如windows操作系统

　　　　   2. 表格结构（查找效率较高）

　　　　　　　　PCB按进程状态不同组织成不同的表格：就绪进程表，执行进程表（多机系统中）及阻塞进程表

　　　　　　　　系统分别记载各PCB表的起始地址

　　　　  3. PCB多级队列

 

• 多进程引发的问题

  1. 多个进程竞争内存资源
  2. 内存资源紧张
  3. 无就绪进程，处理机空闲：I/O的速度比处理机的速度慢很多，可能出现全部进程阻塞等待I/O
  4. 解决办法：
     1. 采用交换技术：换出一部分进程到外存，以腾出内存空间
     2. 采用虚拟存储技术：每个进程只能装入一部分程序和数据（存储管理部分）

•  进程的控制

          两种执行模式  

         　　 1. 系统模式（又称为系统态）、控制模式或内核模式  

　　　　　　① 具有较高特权

　　　　　　② 运行系统特定的指令，包括读写控制寄存器的指令，基本IO指令以及与存储管理有关的指令及一些特定的内存区

　　　　　　③ 内核模式下的处理机及其指令、寄存器和内存都受到完全控制和保护

          　　2. 用户模式（或用户态）

　　　　　　① 较低的特权

　　　　　　② 用户一般运行在用户模式

        模式切换

　　　　用户->系统：用户执行到一条系统调用，进入操作系统内核执行

　　　　系统->用户：执行完系统调用的功能，返回到用户程序

　　　　特殊情况：程序执行到结束语句时，切换到系统模式，不再返回到用户程序

　　 进程调度

　　  调度是指，在一个队列中，按照某种方法（算法），选择一个合适的个体的过程。

        调度的关键是需要某种方法或者算法，好的调度算法有利于选择到合适的个体

　　  调度目标：公平性、提高处理机利用率、提高系统吞吐量、尽量减少进程的响应事件

        调度原则：

               1.  满足用户的要求：

　　　　　　   响应时间：考虑尽可能使绝大多数用户的请求能在响应时间内完成，常用于评价分时系统的性能

　　　　　　　周转时间：作业提交给系统开始到作业完成的这段时间间隔，评价批处理系统的性能

　　 　　　　  截止时间：实时系统中，某任务必须开始执行的最迟时间，或必须完成的最迟时间，常用来评价实时系统的性能

               2. 满足系统的需求：

　　　　　　   系统吞吐量

                     处理机利用率

                    各类资源的平衡使用

                    公平性及优先级

　　　调度方式： 

　　　　　1. 非剥夺方式

　　　　　　    执行完毕or申请IO阻塞自己

　　　　　　　 不利于“及时性”要求较高的分时和实时系统，主要用于批处理系统

　　　　   2. 剥夺方式

　　　　　　     操作系统可以在新进程到来时，或某个具有较高优先权的被阻塞进程插入就绪队列时，或在基于时间片调度的的系统中，时间片用完而中断当前进程的执行，调度新的进程执行。这种方式会产生较多的中断，主要用于实时性要求较高的实时系统及性能要求较高的批处理系统

　　　调度类型：

　　　　   1. 批处理调度，分时调度，实时调度和多处理机调度

　　 　　  2. 长程调度（long-term scheduling，外存到内存）：

　　　　　　    又称为高级调度或者作业调度，它为被调度作业或用户程序创建进程，分配必要的系统资源，并将新创建的进程插入就绪队列，等待短程调度

　　　　　　　 某些采用交换技术的系统将新创建的进程插入到就绪/挂起队列，等待中程调度

　　　　　　　 在批处理系统中，作业进入系统后，先驻留在磁盘上，组织成批处理队列，称为后备队列。长程调度从该队列中选择一个或者多个作业，为之创建进程

　　　　　　   需要考虑的问题：

　　　　　　　　    ① 选择多少个进入内存--取决于多道程序的度，即允许同时在内存中运行的进程数

　　　　　　　　　 ② 选择哪些作业：取决于长程调度算法

  　　　　 3. 中程调度（进程间的外存内存之间）

　　　　　　　　又称为中级调度

　　　　　　　　内存空间紧张时，或处理机找不到一个可执行的就绪进程时，需要选择一个进程（阻塞或就绪状态）换出到外存，释放出内存空间给别的进程使用；当内存空间较充裕时，从外存选择一个挂起状态的进程调度到内存（换入）；

　　　　　　　　目的：为了提供内存的利用率和系统的吞吐量

　　　　　　　　只有支持进程挂起的操作系统才具有中程调度功能

　　　　   4. 短程调度（内存里）：

　　　　　　　　也成为近程调度，或低级调度，决定就绪队列中的哪个进程将获得处理机

　　　　　　  　 短程调度运行频率最高

　　　　　　　　现代操作系统几乎都具有短程调度功能

　　　　  5. IO调度（相近的磁道）

 进程调度算法

　　1、FCFS(先来先服务，同时适合于三种调度)：

　　　　非剥夺调度方式，实现简单，看似公平

　　　　注意：对于后进入队列的运行时间较短的进程或者IO型进程而言，可能需要较长时间的等待

　　　　对段进程不公平

　　2、短进程优先（对FCFS的改进）

　　　　非剥夺 

　　　　难以准确预测进程的执行时间

　　　　可能导致长进程饥饿

　　　　采用非剥夺调度方式，未考虑进程的紧迫程度，不适合于分时系统和事务处理系统

　　3、时间片轮转调度法 

        

　　　　用户数多时进程急剧增加

　　　　时间片大小会影响处理性能

　　　　　　① 进程切换会增加系统额外开销

　　　　　　② 太长太短都不好

　　　　　　③ 需要综合考虑系统最大用户数，响应时间，系统效率等因素

 　　　 对于短的，计算型的进程较有利

 　　　 不适合IO型的进程

　　　  改进方法之一：可以将IO阻塞时间完成的进程单独组织成一个就绪队列，该队列进程的时间片可以设置的小一点，且优先调度

 

　　4、基于优先级的调度算法

　　　　设定进程的优先级

　　　　　　① 进程完成功能的重要性

　　　　　　② 进程完成功能的紧迫性

　　　　　　③ 为均衡系统资源的使用，指定进程（作业）优先级

　　　　　　④ 进程对资源的占用程度，例如，可以为短进程（或作业）赋予较高的优先级

　　　　静态与动态优先级

　　　　　　动态优先级：

　　　　　　　　剩余时间最短者优先（剥夺型）

　　　　　　　　响应比高者优先

　　　　　　　　进程的优先级与等待时间成正比

　　　　　　　　难以准确的估计进程的语气执行时间

　　　　　　　　计算响应比增加系统开销

　　5、反馈调度法

　　　　根据执行历史而非未来进行调度，将解决这个问题

　　　　根据进程的执行历史调整调度方式的调度方法，它结合了优先级和时间片轮转调度的方法

 　　　  有利于交互性短进程或批处理作业，他们一般只需要一个或者几个时间片即可完成

　　      可能是长进程的周转时间急剧增加

　　 　  如果不断有新进程进来，还可能造成进程出现长期饥饿现象

　　      可以为各队列设置不同的时间片，优先级愈低时间片愈长

 进程的互斥与同步

　　问题：如何协调多个进程对系统资源(如内存空间，外部设备等)的竞争和共享？如何解决多个进程因为竞争资源而出现的执行结果异常，设置系统不稳定，失效等问题？

　　并发控制：

　　　　1、竞争资源

• 1. 有可能造成死锁
  2. 某些资源必须互斥的使用--临界资源
  3. 访问临界资源的那段代码称为临界区
  4. 任何时刻，只允许一个进程进入临界区，以此实现进程对临界资源的互斥访问

　　　                               　

　　　　2、互斥使用临界区

　　　　　1. 在进程需要使用临界资源时，通过获得临界区的使用权实现的。

　　　　　2. 首先，在进入区判断是否可以进入临界区，如果可以进入，则必须设置临界区使用标志，阻止其他后来的进程进入临界区。后来的进程通过查看临界区使用标志，知道自己不能够进入临界区，就进入阻塞队列，将自己阻塞

　　　　　3. 当临界区内的进程使用完毕，退出临界区时，即在退出区修改临界区使用标志，并负责唤醒阻塞队列中的一个进程，让其进入临界区

　　　　   4. 必须保证“临界区使用标志”是可以被系统中的所有进程共享的全局变量，而且诸进程对该标志的修改操作必须互斥的进行

 　　　 3、临界区使用原则

　　　　　1. 每次只允许一个进程进入临界区（忙则等待）

　　　　　2. 进程只能在临界区内逗留有限时间，不得使其他进程在临界区外无限等待（有限等待）

　　　　　3. 如果临界区空闲，则只要有进程申请就立即让其进入（空闲让进）

　　　　　4. 进入临界区的进程，不能够在临界区内长时间阻塞等待某事件，必须在一定期限内退出临界区（让权等待）

　　　　　5. 不能限制进程的执行进度及处理机的数量

 　　    4、竞争资源可能引起死锁

　　　  5、竞争资源可能引起饥饿

　　　  6、并发控制-共同协作

　　　　　　1. 多个进程常常需要共同修改某些共享变量，表格文件数据库等，协作完成一些功能

　　　　　　2. 必须确保他们对共享变量的修改时正确的，保证数据的完整型

　　　　      3. 共享协作同样涉及到互斥死锁和饥饿问题，当更强调对数据的写操作必须互斥的进行

　　　　      4. 必须保证数据的一致性（银行存款取款余额）

　　　　      5. 一般通过事务处理来保证数据的一致性，进入临界区的进程必须一次性完成对这一些列数据的修改操作

　　　　      6. 只有该进程退出临界区以后，才允许其他进程进入临界区进行数据修改，以保证数据的一致性。

 　　　 7、并发控制-通信协作

　　　　　　当进程进行通信合作时，各个进程之间需要建立连接，通信进程需要同步和协调。进程通信的方式很多，包括消息传递，管道，共享存储区等。

　　　　　　通过消息传递实现进程通信时，由于没有共享资源，故无需互斥，但仍可能出现死锁与饥饿

　　　　　　通信死锁与饥饿

 　　    8、互斥与同步的解决策略

　　　　　　软件方法

　　　　　　　　由进程自己，通过执行相应的程序指令，实现与别的进程的同步于互斥，无需专门的程序设计语言或操作系统的支持

　　　　　　　　很难正确的控制进程间的同步与互斥，而且可能会大大增加系统的额外开销

　　　　　　硬件方法

　　　　　　　　通过屏蔽中断或采用专门的机器指令控制同步与互斥

　　　　　　　　减少了系统额外开销，需要太强的硬件约束条件，以及可能导致进程饥饿与死锁现象，没有成为通用的解决方法

　　　　　　信号量方法（重点）

　　　　　　　　由操作系统，或专门的程序设计语言提供特别支持，包括信号量方法，管程方法和消息传递方法

　　　　　　　　通用方法

　　　　　　管程方法

　　　　　　消息传递方法

 　　　 9、软件方法

 　　　　　 Dekker算法

　　　　　  Peterson算法

　　　　　  初步设想：控制两个互斥进入临界区，可以让两个进程轮流进入临界区

　　　　　　　　保证了互斥

　　　　　　　　出现忙等现象

　　　　　　　　a非要等b用完一次才能使用下一次

 

 

 参考：