wilson404的个人博客

前述各种互斥手段的缺点

临界段操作的代码以及进入和退出临界段时的“上锁”和“开锁”操作代码，均要由用户来编写，加重了用户的负担；
所有同步原语操作都分散在用户编写的各程序代码中，由进程来执行，这样系统无法有效地控制和管理这些同步原语操作；
用户编程时难免会发生不正确地使用同步原语操作的错误，这种错误会给系统带来不堪设想的后果（如死锁），更麻烦的是，无论是编译程序或操作系统都无法发现和纠正此类错误。

管程的引入

使用PV操作实现同步时，对共享资源的管理分散在各个进程之中，进程能直接对共享变量进行处理，因此，难以防止有意或无意的违法同步操作，而且容易造成程序设计错误。如果能把有关共享变量的操作集中在一起，就可使并发进程之间的相互作用更为清晰,更容易编写出正确的并发程序。

进程间通信

并发进程之间的交往本质上是互相交换信息。有些情况下进程之间交换的信息量很少，例如仅仅交换某个状态信息。有些情况下进程之间交换大批数据，例如传送一批信息或整个文件。
进程之间互相交换信息的工作称之为进程通信IPC(InterProcess Communication)。

在进程间交换一定数量的信息，称为进程间通信；
进程间通信不但存在于一个作业的诸进程间，而且也存在于共享有关资源的进程之间，以及客户和服务器进程之间。

进程间通信的方式

通过软中断提供的信号（signal）通信机制；
使用信号量及其原语操作（PV、读写锁、管程或其他操作）控制的共享存储区(shared memory)通信机制；
通过管道(pipeline)提供的共享文件(shared file)通信机制；
使用信箱和发信/收信原语的消息传递(message passing)通信机制。
其中前两种通信方式属于低级通信机制，仅适用于集中式操作系统。
消息传递机制属于高级通信机制，共享文件通信机制是消息传递机制的变种，这两种通信机制，既适用于集中式操作系统，又适用于分布式操作系统。

间接通信方式

发送者进程不是把消息直接发送给接收者进程，而是把消息发送到一个共享的数据结构—信箱中去。接收者进程也到信箱中去取消息。
直接通信常用于进程间相互关系比较紧密的情况下；
间接通信用于联系不十分紧密的进程间；
间接通信方式的灵活性：
 发送者进程和接收者进程之间的关系可以有一对一、一对多、多对一、多对多等多种关系；
 信箱可以是静态的、固定不变的，也可以是动态的、可变的。

一对一：主要用于两个进程间建立私用的通信连接，可以不受其他进程的干扰和影响；
一对多：指一个发送者和多个接收者的通信关系，用于一个发送者进程向一组中的多个进程以广播的方式发送一个或多个消息的应用场合；
多对一：客户/服务器模式下客户进程和服务器进程之间的关系。

消息传递的方式

直接通信方式—消息缓冲区
 在直接通信方式下，企图发送或接收消息的每个进程必须指出信件发给谁或从谁那里接收消息。
间接通信方式—信箱
 采用间接通信方式时，进程间发送或接收消息通过一个信箱来进行，消息可以被理解成信件，每个信箱有一个唯一的标识符。当两个以上的进程有一个共享的信箱时，它们就能进行通信。一个进程也可以分别与多个进程共享多个不同的信箱，这样，一个进程可以同时和多个进程进行通信。

生产者—消费者问题

在操作系统中，生产者进程可以是计算进程、发送进程；而消费者进程可以是打印进程、接收进程等等。
生产者--消费者问题表述如下：有n个生产者和m个消费者，连接在一个有k个单位缓冲区的有界缓冲上，故又叫有界缓冲问题。其中，pi和cj都是并发进程，只要缓冲区未满，生产者pi生产的产品就可投入缓冲区；类似地，只要缓冲区不空，消费者进程cj就可从缓冲区取走并消耗产品。
缓冲区可以解决处理器处理速度和输出设备输出不匹配的问题

引入信号量

出现不正确结果不是因为并发进程共享了缓冲区，而是因为它们访问缓冲区的速率不匹配，或者说pi，cj的相对速度不协调，需要调整并发进程的进行速度。
并发进程间的这种制约关系称进程同步，交往的并发进程之间通过交换信号或消息来达到调整相互速率，保证进程协调运行的目的。
操作系统实现进程同步的机制称同步机制，它通常由同步原语组成。不同的同步机制采用不同的同步方法，迄今己设计出许多种同步机制，其中最常用的同步机制：信号量，管程和消息传递。

信号量（semaphore）

在多个相互合作的进程之间使用简单的信号来同步，一个进程被强制停止在某一特定状态，直到收到专门的信号为止。
一个信号量被定义为一个整型变量，在其上定义了以下三个操作：
 可以被“初始化”为一个非负数；
（P操作） Wait操作将信号量值减1后，若该值为负，则执行wait操作的进程等待；
（V操作） Signal操作将信号量值增1后，若该值非正，则执行signal操作的进程唤醒等待进程。
（信号量表示可使用资源个数）

用信号量实现进程间互斥

对于两个并发进程，互斥信号量的值仅取1、0和-1三个值：
 若mutex = 1，表示没有进程进入临界区；
 若mutex = 0，表示有一个进程进入临界区；
 若mutex = -1，表示一个进程进入临界区，另一个进程等待进入。

生产者—消费者问题举例

桌上有一只盘子，每次只能放入一只水果。爸爸专向盘子中放苹果(apple)，妈妈专向盘子中放桔于(orange)，一个儿子专等吃盘子中的桔子，一个女儿专等吃盘子里的苹果。

这个问题实际上是两个生产者和两个消费者被连结到仅能放一个产品的缓冲器上。生产者各自生产不同的产品，但就其本质而言，他们是同一类生产者。而消费者则各自取需要的产品消费，他们的消费方式不同。

读者—写者问题

有两组并发进程：读者和写者，共享一个文件F，要求：
 允许多个读者同时执行读操作；
 任一写者在完成写操作之前不允许其它读者或写者工作；
 写者执行写操作前，应让已有的写者和读者全部退出。
单纯使用信号量不能完成读者与写者问题，必须引入计数器rc对读进程计数，s是用于对计数器rc互斥的信号量，W表示允许写的信号量。
（s控制对rc的访问）

互斥的软件方法

问题：有两个并行进程P0和P1 ，互斥地共享单个资源（磁带机或某共享数据）。P0和P1是一个循环进程（即进程执行一个无限循环程序），每次只使用资源为一个有限的时间间隔。

解法1：用标志位flag[i]来标示进程i是否在临界段中执行，当flag[i]为真，则表示它正在执行临界段，反之不在临界段中执行；

存在的问题：当两个进程的标志位最初都为false，这时刚好两个进程同时都想进入临界段，并且同时发现对方标志位为false，于是两个进程同时进入了各自的临界段，违背了临界段设计原则，每次至多只允许一个进程进入临界段。（并发问题）

解法2：用一个指针turn来指示应该哪个进程进入临界段，若turn = i，则该进程Pi进入临界段；

存在的问题：强制两个进程以交替次序进入临界段，如果Pi进程的处理器速度要快得多，或者进程Pi的其他代码部分很长，那么进程Pi在进程Pj尚未进入临界段前要求再次进入临界段时，尽管此时临界段为空（无进程处于其中），进程Pi也无法进入临界段，从而使临界资源的使用率不高。

解法3：用flag[i]来表示进程i想要进入临界段，这是基于对解法1存在的问题：未表明自己想进入临界段的意向，而只检测对方是否已在临界段中，从而导致同时进入的情况的改进；

存在的问题：两个进程同时想进入临界段，于是把各自的标志位都置为true，并且同时检测对方的状态，发现对方也想进入（或已在临界段中），于是互相“谦让”而阻塞了自己，谁也进不了临界段，从而违反了临界段设计原则（2）。

解法4：为每个进程设置一个标志位flag[i]，同样，当该位为真时，则表示该进程Pi要求进入临界段（或已在临界段中执行），反之为假，另外还设置了一个指针turn以指出应该由哪一个进程进入临界段，若turn=i则应该由进程Pi进入临界段。

引入硬件方法

分析临界区管理的尝试中的几种算法，问题出在管理临界区的标志时要用到两条指令，而这两条指令在执行过程中有可能被中断，从而导致了执行的不正确。
能否把标志看作为一个锁，开始时锁是打开的，在一个进程进入临界区时便把锁锁上以封锁其它进程进入临界区，直至它离开其临界区，再把锁打开以允许其它进程进入临界区。如果希望进入其临界区的一个进程发现锁未开，它将等待，直到锁被打开。
要进入临界区的每个进程必须首先测试锁是否打开，如果是打开的则应立即把它锁上，以排斥其它进程进入临界区。
测试和上锁这两个动作不能分开，以防两个或多个进程同时测试到允许进入临界区的状态。

互斥的硬件方法

中断屏蔽方法
 在单处理器系统中，引起进程开关，使得当前运行进程交出处理器的唯一原因是中断；
 屏蔽中断就能保证当前运行进程把临界段代码顺利地执行完，保证互斥实现，然后再开中断；
 缺点：首先系统要付出较高代价；其次这种方法在多处理器系统中是不能保证进程间互斥的。
当进入锁测试之前关闭中断，直到完成锁测试并上锁之后再开中断。在这一短暂的期间，计算机系统不响应中断，因此不会转向调度，也就不会引起进程或线程切换，从而保证了锁测试和上锁操作的连续性和完整性，有效的实现了临界区管理。
但关中断时间过长会影响系统效率，关中断方法也不适用于多CPU系统。

硬件指令方法
TS（test-and-set）指令，又称检测和设置指令；
Swap指令，又称交换指令；
实现互斥的方法：为每个临界段或其他互斥的资源设置一个布尔变量，当其值为false则临界段未被使用，反之则说明正有进程在临界段中执行；
缺点：当进程正在临界段中执行时，其他想进入临界段的进程必须不断地检测布尔变量的值，即所谓“忙等待”，从而造成了处理器机时的浪费。

硬件指令实现互斥的优缺点

硬件指令方法实现互斥不但适用于单处理器情况，而且适用于共享主存的对称多处理器情况；
方法简单、行而有效；
可以被使用于多重临界段情况，每个临界段可以定义它自己的共享变量。
但，硬件指令方法一般采取“忙等待”的简单方法，进程不断地检测临界段状态，会造成处理器时间的浪费。

临界区（critical sections）
 进程中访问共享变量的代码段
 不同进程关于同一变量的临界段代码可能是完全不同的
 临界资源—共享变量（一次只允许一个使用）

临界区的互斥要求

进程对共享变量的读写操作必须互斥的进行；
对进程互斥地使用临界区有以下原则：
 在共享同一个临界资源的所有进程中，每次只允许有一个进程处于它的临界区；
 若有多个进程同时要求进入它们的临界区时，应在有限的时间内让其中之一进入临  界区，而不应相互阻塞；
 进程只应在临界区内逗留有限时间；
 不应使要进入临界区的进程无限期地等待在临界区之外；
 在临界区之外运行的进程不可以阻止其他的进程进入临界区；
 不要预期和假定进程进展的相对速度以及可用的处理器数目，因为这是不可预期的。

在多道程序设计系统中，同一时刻可能有许多进程，这些进程之间存在两种基本关系：竞争关系和协作关系。
竞争关系：（系统中的多个进程之间彼此无关，它们并不知道其他进程的存在，但由于共享系统资源，就会出现竞争。当多个进程竞争共享硬设备、变量、表格、链表、文件等资源时，可能导致处理出错。）
 死锁、饥饿（资源的竞争出现了这两个控制问题）
 进程的互斥（临界区管理）(特殊的同步)
协作关系：（某些进程为完成同一任务需要分工协作。例如：input, compute, output ，协作进程之间各自知道对方的存在）
 进程的同步（解决进程间协作关系的手段 ）
进程互斥关系是一种特殊的进程同步关系，即逐次使用共享资源。

所谓状态是指线程当前正在干什么和它能干什么
几个基本状态：
 就绪状态
 运行状态
 等待状态（或阻塞状态）

几点说明

线程没有挂起操作和挂起状态；
 线程不是资源的拥有者，资源属于进程，所以线程不应有决定整个进程或自己从主存撤出的权力。
进程中可能有多个线程，当其中一个线程在执行中成为阻塞状态时，不阻塞其他
线程，该进程中其他线程仍然可以参与调度运行；
对于多线程进程中的进程状态，可以只划分为活动（可运行）状态和非活动（不
可运行）状态。

线程的生命周期

线程的描述

线程状态（就绪、运行、阻塞等）；
当线程不运行时，被保存的现场信息；
  程序计数器、程序状态字、通用寄存器、堆栈指针
一个执行堆栈；
存放每个线程的局部变量的主存区；
访问被同一进程中所有线程共享的该进程的主存和其他资源。
线程控制块TCB——描述和记录其属性和调度所需的数据，是线程存在的标志；
进程对象和线程对象

进程对象属性

进程ID——系统中进程的唯一标识
存取令牌——包含该进程所对应的已登录用户的安全信息的对象
基本优先级——该进程的线程的基线执行优先级
默认处理器族——进程的线程所能运行的默认处理器族
配额限制——一个用户进程所能使用的分页和非分页的系统主存，页面调度文件空间和处理器时间的最大数量
执行时间——进程的所有线程的执行时间总量
I/O计数器——记录其所有线程所执行的I/O操作数和种类的变量
VM操作计数器——记录其所有线程所进行的虚拟存储操作数量和种类的变量
异常情况/调试端口——进程间通信的信道
退出状态——进程终止原因

线程对象属性

线程ID——当线程调用一个服务时，对该线程的唯一标识
线程描述表（context）——定义线程执行状态数据，如程序计数器、程序状态字的内容和通用寄存器、堆栈指针等
动态优先级——在给出时刻的线程的执行优先级
基本优先级——线程动态优先级的最低限
线程处理器族——线程可以运行的处理器集合
线程执行时间——线程在用户态和内核态已执行时间的累计量
报警信号状态——指示线程是否执行在异步过程调用的标志
挂起计数——线程的执行没有被恢复的次数
模仿令牌——允许线程在其他进程中执行操作的临时性的访问令牌
终止端口——当线程终止时，发送给进程管理程序一个消息的进程间的通信通道
线程出口状态——线程终止的原因

线程的管理（与进程类似）

也用链指针将TCB或线程对象按它们所处的状态链接成相应的线程队列来加以管理；
操作系统的进程管理程序为某用户应用程序创建进程时，同时为该进程创建第一个线程；
以后在线程的运行过程中，线程可以在需要的时候创建所需的线程；
线程间不提供父子关系的支持。

线程控制原语

创建线程原语：为线程得到一个TCB或线程对象，并初始化线程ID，线程描述表（程序计数器PC、程序状态字PSW、通用寄存器、堆栈指针等）和其他有关项，然后进入相应就绪队列。
撤消线程原语：撤消线程TCB或线程对象、线程堆栈和描述表。
阻塞或等待原语
挂起一个线程
恢复（解挂）一个线程
改变优先数

基于线程观点的操作系统分类

单进程和单线程系统——只有一个进程，每个进程中只有一个线程，如MS-DOS；
多进程和单线程系统——有多个进程，但每个进程中只有一个线程，如传统意义上的UNIX系统；
单进程和多线程系统——只有一个进程，但每个进程有多个线程；
多进程和多线程系统——有多个进程，每个进程中又有多个线程，是当前应用最广泛的系统类型。

线程的引入

提高系统的并行性
 硬件方面：流水线计算机、数据流计算机、并行处理器、流水存储器、多体交叉及多端口存储器等
 操作系统方面：中断、通道、多道程序设计技术、并发程序技术
仅使用进程来解决并行性问题的缺点
 经常性进程开关，系统开销很大（切换时资源浪费）
  与进程运行有关的表格要改写
  进程的地址空间要进行转换为新被调度的进程地址空间
  两次模式开关的开销（用户模式-内核模式-用户模式）

进程再操作系统中担任的角色

进程是拥有自己资源的单元体
 虚拟地址空间
 控制其他为进程运行所需要的I/0资源
进程是被调度分派再处理器上运行的基本单位

第一个要点是关于拥有资源的主权（由进程来完成）
第二个要点是关于应用程序的执行（由线程来完成）

线程的引入

传统的进程概念由两个严重的局限性
 许多应用想并发执行彼此间独立的任务，但又必须要共享一个公告的地址空间和其他资源，将这类应用中独立的任务串行化，效率很低
 传统的进程不能很好的利用多处理器系统
（传统的单线程进程即使分配了多个处理器单元，也只能穿行的执行）
（多线程可以并行的执行）

线程的模型

多线程机制的优点

在进程内创建多线程，可以提高系统的并行处理能力。
线程机制可显著提高程序执行的有效性，也可方便用户编程；
不但适用于多机系统（尤其是对称式多机系统），而且对大多数单CPU系统也同样有好处。

线程（thread）的概念

进程内的一个执行单元
进程内的一个可调度实体
线程是程序（或进程）中相对独立的一个控制流序列
线程是执行的上下文，即执行的现场数据和其他调度所需要的信息

线程是进程内一个相对的、可调度的执行单元
有些系统把线程称为轻质进程（lightweight process）

线程的性质

线程是进程内一个相对独立的可执行单元；
线程是操作系统中的基本调度单元，因此线程中应包含有调度所需要的必要信息；
每个进程在创建时，至少需要同时为该进程创建一个线程，即进程中至少要有一个或一个以上线程，否则该进程无法被调度执行；
需要时，线程可以创建其他线程；
进程是被分给并拥有资源的基本单元，同一进程内的多个线程共享该进程的资源，但线程并不拥有资源，只是使用它们；
由于共享资源（数据和文件），所以线程间需要通信和同步机制；
线程有生命期，有诞生和死亡，在生命期中有状态的变化。

多线程机制

一个进程可以有多个线程，这些线程共享该进程资源；
这些线程驻留在相同的地址空间，共享数据和文件；
如果其中的一个线程修改了一个数据项，其他线程可以了解和使用此结果数据；
一个线程打开并读一个文件时，同一进程中的其他线程也可同时读此文件。

多线程机制的优点

首先用于创建和撤消线程的开销比创建和撤消进程的系统开销（CPU时间）要少得多（比如不需要建立它的地址空间和所需资源等）；
CPU在线程之间开关时的开销也远比在进程之间开关的开销小；
线程机制也增加了通讯的有效性（无须内核参与）；
方便和简化了用户的程序结构工作。

时间片轮转调度
优先级调度
多级队列
最短作业优先
保证调度算法
策略与机制
两级调度法

调度算法应考虑的问题

公平——确保每个进程获得合理的CPU份额
效率——使CPU百分之百地忙碌
响应时间——使交互用户的响应时间尽可能短
周转时间——使批处理用户等待输出的时间尽可能短
吞吐量——使每小时处理的作业数量多

时间片轮转调度

每个进程被分配一个时间段，称作它的时间片，即该进程允许运行的时间；
如果在时间片结束时进程还在运行，则CPU将被剥夺并分配给另一个进程；
如果进程在时间片结束前阻塞或结束，则CPU当即进行切换。

该方法中唯一有趣的问题是时间片的长度；
结论可以归结为：时间片设得太短会导致过多的进程切换，降低了CPU效率；而设得太长又可能引起对短的交互请求的响应时间变长；
通常将时间片设为100ms，是一个比较合理的折衷。

优先级调度

基本思想：每个进程被赋予一个优先级，优先级最高的就绪进程被率先执行；
优先级可以为静态或动态；
将一组进程按优先级分成若干类，在各类之间采用优先级调度，而各类进程内部采用时间片轮转调度。

多级队列

为CPU密集的进程设置较长的时间片，比频繁地分给它们很短的时间片要高效（因为减少了交换的次数）；
进程的长时间片又会影响响应时间，因此设立优先级类，属于最高级类的进程运行一个时间片，属于次高优先级类的进程运行2个时间片，再次一级运行4个时间片，依此类推，当一个进程用完分配的时间片后，它被移到下一类。

最短作业优先

进程控制原语

原语：由若干条指令组成，用于完成一定功能的一个过程，与一般过程区别：是“原子操作”，不可分割、不允许中断、常驻内存

建立一个进程原语
撤消一个进程原语
挂起一个进程原语
解除挂起进程原语
改变优先数原语
阻塞一个进程原语
唤醒一个进程原语
调度进程运行原语

建立进程原语

所有进程只能由父进程建立，不是自生自灭的
建立进程原语是供进程调用，以建立子进程使用的
主要功能是创建一个指定标识符的进程
主要任务是形成该进程的进程控制块PCB

挂起进程原语

执行挂起命令的功能模块
调用挂起原语的进程只能挂起他自己或它的子孙，而不能挂起其他族系的进程，否则认为该命令非法

撤销进程原语

当一个进程完成其任务后，应将其撤销，以便及时释放出它所占用的资源
撤销原语采取的策略
 只撤销某一个具有指定标识符的进程
 撤销它的一个子进程及该子进程的所有子孙
命令的形式为kill或exit

改变进程优先级原语

进程的优先数数是表示进程的重要性及运行的优先性，供进程调度程序调度进程运行时使用的
防止一些进程因优先数较低，而长期得不到运行的情况

进程的优先数与以下因素有关
 与作业开始时的静态优先数有关
 与进程的类型有关
 与进程所使用的资源量有关
 与进程在系统中等待时间有关

进程间通信（补充）（Inter Process Communication,IPC）

竞争条件
临界区
忙等待的互斥
睡眠与唤醒
信号量

进程的描述

进程的描述应包含哪些信息和内容
 一个或多个程序
 数据
 充分的主存
 用于保存过程调用现场信息和过程间传递的参数等信息的一个堆栈
 有关情况的属性信息

进程控制块（PCB）

系统在建立进程的同时就建立该进程的PCB，在撤销一个进程的同时也就撤销其PCB。所以说进程的PCB对进程说是它存在的具体物理标志和体现

进程标识信息
 本进程的标识Id
 父进程的标识Id
 用户标识
处理器状态信息
 用户使用的寄存器
 控制和状态寄存器
 堆栈指针
进程控制信息
 调度和状态信息
 进程在有关队列中的链接指针
 进程间的通信信息
 主存使用信息
 进程使用的其他资源信息
 进程得到有关服务的优先级

PCB的作用

PCB是操作系统中最重要的数据结构
 PCB记录进程的属性信息，以便操作系统对其进行控制和管理
 PCB是进程存在的具体物理标志和体现
 PCB对是调度进程的主要的数据基

进程管理

各进程的PCB的组织方法
 把所有不同状态的进程的PCB组织在一个表格中
 分别把有着相同状态的进程的PCB组织在同一个表格中
 分别把具有相同状态的所有进程的PCB按优先数排成一个或多个队列