操作系统2016

1、计算机操作系统计算机操作系统第三章第三章 进程与线程进程与线程目目 录录3.1 进程概念进程概念3.2 进程控制进程控制3.3 线程线程3.4 互斥和同步互斥和同步23.1 进程概念进程概念3.1.1 程序的顺序执行及其特征1. 程序的顺序执行 通常可以把一个应用程序分成若干个程序段，各程序段之间必须按照某种先后次序顺序执行，仅当前一程序段（操作）执行完后，才能执行后继程序段（操作）。 33.1.1 程序的顺序执行及其特征程序的顺序执行及其特征 1. 程序的顺序执行 63.1.1 程序的顺序执行及其特征程序的顺序执行及其特征2. 程序顺序执行的特征 （1）顺序性：处理机的操作严格按照程序所规定

2、的顺序执行，即每一操作必须在上一操作结束之后开始。 （2）封闭性：程序是在封闭的环境下执行的，即程序运行时独占整个系统资源，资源的状态（除初始状态外）只有本程序可以改变。 （3）可再现性：只要程序执行时的环境和初始条件相同，当程序重复执行时，不论它的执行方式如何，是连续执行或“走走停停”的执行，其结果都是相同的。73.1.2 程序的并发执行及其特征程序的并发执行及其特征1. 程序的并发执行 为了提高计算机的利用率、处理速度和系统的吞吐量，并行处理技术和并发程序设计技术在计算机中已经得到了广泛应用，成为了现代操作系统的基本特征之一。 93.1.2 程序的并发执行及其特征程序的并发执行及其特征 具

3、有以下四条语句的一个程序段： S1: a:=x+2; S2: b:=y+4; S3: c:=a+b; S4: d:=c+b;11图 3.3 四条语句的前趋图 程序两两并发必须满足（P37）3.1.2 程序的并发执行及其特征程序的并发执行及其特征2. 程序并发执行的特征 （1）间断（异步）性：程序在并发执行时, 由于它们共享系统资源，以及为了完成同一任务而相互合作，致使这些并发程序之间形成了相互制约的关系。 （2）失去封闭性：程序在并发执行时，多程序共享系统中的各种资源，因此系统资源的状态将由多个程序来改变，致使程序失去了封闭性。 （3）不可再现性：程序在并发执行时，由于失去了封闭性，也将导致其

4、失去执行的可再现性。 13已有的一些定义充分反映了进程的实质：l进程是程序的一次执行；l进程是可以和别的计算并发执行的计算；l进程是定义在一个数据结构上，并能够在其上进行操作的一个程序；l进程是程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位。3.1.3 进程的概念及其特征进程的概念及其特征15 综上，将进程定义为： 进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位。3.1.3 进程的概念及其特征进程的概念及其特征16 程序和进程之间的区别与联系：程序是完成特定任务的一组指令的集合，可以永久保存，具有静态性；进程有生命周期，是程序在某一数据结构上的一次执

5、行过程，是系统进行资源分配和调度的基本单位，具有动态性；一个进程可以包含多个程序，一个程序也可以被多个进程执行。3.1.3 进程的概念及其特征进程的概念及其特征181. 两状态模型包含运行态（Running）和非运行态（Not running）两种进程状态l创建了一个新进程之后，它会以非运行态加入到系统中，等待操作系统为其分派处理器l当前处于运行态的进程会不时地中断，由系统中的分派器选择处于非运行状中的某一个进程运行3.1.4 进程状态进程状态19（a） 状态变迁图3.1.4 进程状态进程状态20（b） 排队图3.1.4 进程状态进程状态212.五状态模型包括就绪态（Ready）、运行态（Ru

6、nning）、阻塞态（Blocked）、新建态（New）和终止态（Terminate） 进程状态描述： （1）新建态：刚刚创建的新进程，通常是指进程控制块已经创建，但还没有加载到系统内存中的进程 （2）就绪态：进程等待系统为其分派处理器，而此时处理器被其它进程占据，所以该状态进程不能执行但已经具备了除处理器之外的进程执行所需要的所有条件。3.1.4 进程状态进程状态22 （3）运行态：进程已获得所需资源并占据处理器，处理器正在执行该进程 （4）阻塞态：也称为等待态、挂起态或睡眠态，进程在等待某个事情的发生而暂时不能运行，例如等待某个I/O操作的完成 （5）终止态：进程或者因为执行结束或者因为被

7、撤销而从可执行进程组中退出3.1.4 进程状态进程状态23图图3.5 五状态模型（五状态模型（P40）3.1.4 进程状态进程状态24 对于内存中的多个进程，处理器依次选中运行，当一个进程正在等待 I/O 事件发生时，处理器转移到另一个进程。但是处理器的速度比 I/O 要快很多，有可能内存中所有进程都在等待 I/O 事件的完成，导致处理器处于空闲状态。 一种可行的解决问题的办法是引入挂起的概念。3.1.4 进程状态进程状态25图图3.6 引入挂起的进程状态转换模型引入挂起的进程状态转换模型3.1.4 进程状态进程状态27l进程控制块（Process control block, PCB）是操作

8、系统用来记录进程状态和相关信息，控制进程运行的数据结构，是进程的唯一标识符。l在PCB中，主要包含如下的信息：3.1.5 进程控制块进程控制块28进程标识符进程状态调度信息程序计数器上下文数据内存指针I/O 状态信息l进程控制是进程管理中最基本的功能进程控制是进程管理中最基本的功能l在操作系统中，不同功能都是通过执行各种原语（Primitive）操作实现l原语是由若干条指令构成、可完成特定功能的程序段；它是不可分割的操作单元，在执行过是不可分割的操作单元，在执行过程中不会被中断程中不会被中断！3.2 进程控制进程控制30l引起进程创建的事件： （1）批处理作业 （2）用户登录 （3）提供服务

9、（4）进程派生3.2.1 进程创建进程创建31l创建一个新进程的具体步骤： （1）系统为新建进程申请一个空白的进程控制块，获得一个唯一的进程标识符。 （2）系统为新建进程分配运行所需的资源，包括：内存、处理器时间、I/O设备等。 （3）进程控制块（PCB）初始化。 （4）设置链接，如果就绪队列允许新进程插入，则将新进程插入就绪队列。3.2.1 进程创建进程创建32l引起进程终止的事件： （1） 正常完成 （2） 运行超时 （3） 等待超时 （4） 内存不足 （5） 越界错误 （6） 保护错误 （7） 算术错误3.2.2 进程终止进程终止33（8） I/O错误（9） 无效指令（10）特权指令（1

10、1）操作员或操作系统干涉（12）父进程请求（13）父进程终止l终止原语的具体步骤： （1）根据需要终止进程的进程标识符，从PCB集合中查找对应进程，从中读出该进程的状态。 （2）若被终止进程正处在执行状态，则应立即终止该进程的执行，并设置相应的调度信息，用于指示该进程被终止后应重新进行调度。 （3）将被终止进程所拥有的所有资源归还给其父进程，或者归还给系统。 （4）若被终止进程还拥有子孙进程，则将其所有子孙进程一并终止。 （5）归还PCB所占据的空间。3.2.2 进程终止进程终止341. 进程阻塞l进程阻塞是指进程在执行过程中因等待某个事件的发生或等待某个操作的完成而不得不让出处理机，是进程主

11、动、自愿的行为进程主动、自愿的行为。l引起进程阻塞的主要事件有： （1）请求系统服务 （2）启动某种操作 （3）新数据尚未到达 （4）无新工作可做3.2.3 进程阻塞和唤醒进程阻塞和唤醒35l阻塞原语（Block primitive）的具体步骤： （1）正在执行的进程立即终止执行，把PCB中的进程状态由执行改为阻塞，并将处理机状态写入PCB中。 （2）将PCB插入阻塞队列中，等到事件的发生或操作的完成。 （3）系统将处理机重新分派给另一就绪进程，按照新进程的处理机状态更新处理机环境，就绪进程开始执行。 （4）当被阻塞进程等待的事件发生或者等待的操作完成时，则操作系统会通过唤醒原语将等待该事件的

12、进程唤醒。3.2.3 进程阻塞和唤醒进程阻塞和唤醒362. 进程唤醒l当被阻塞进程等待的事件发生（如等待的 I/O 操作已完成、或等待的操作完成时），则操作系统会通过唤醒原语将等待该事件的进程唤醒。l唤醒原语（Wakeup primitive）的具体步骤： （1）根据进程标识符从等待该事件的阻塞队列中找到需要唤醒的进程PCB。 （2）将PCB中的进程状态阻塞改成就绪，并将该进程插入到就绪队列中。3.2.3 进程阻塞和唤醒进程阻塞和唤醒371. 进程挂起l当系统中出现了引起挂起的事件，如内存资源不足时，操作系统将利用挂起原语将处于阻塞状态的进程挂起。l挂起原语（Suspend primitive

13、）的具体步骤： （1）根据进程标示符，在PCB集合中找到需要挂起的进程。 （2）检查挂起进程的状态。3.2.4 进程挂起和激活进程挂起和激活382. 进程激活l激活，对应于挂起，是让被挂起的进程重新活跃起来，也就是把进程从外存调入到内存中。当系统中出现了引起激活的事件时，操作系统会利用激活原语将挂起进程激活。l激活原语（Active primitive）的具体步骤： （1）根据进程标示符，在PCB集合中找到需要激活的进程。 （2）检查激活进程的状态。3.2.4 进程挂起和激活进程挂起和激活39l早期的计算机操作系统中，进程既是资源分配的基本单位，又是调度的基本单位l操作系统发展至今，进程在调度

14、中会存在许多问题，增加了调度的难度和开销l现代操作系统很重要的一方面是进程的并发执行，然而进程的并发执行使得进程调度的开销日益增大，系统效率明显降低3.3 线线 程程40l进程包含两方面特点： （1）资源所有权：进程是一个可拥有资源的独立单位。 （2）调度：进程同时又是一个可独立调度和分派的基本单位。一个进程通过一个或多个程序的一条执行路径执行。执行中可能与其它进程的执行过程交替进行，所以，一个进程具有一个执行状态和一个分派的优先级，同时又是一个能被操作系统调度和分派的实体。3.3.1 线程简介线程简介41l在操作系统中引入进程，是为了使多个程序能并发执行，以提高资源利用率和系统吞吐量。l在操

15、作系统中再引入线程，则是为了减少程序在并发执行时所付出的时空开销，使操作系统具有更好的并发性。l通常把调度和分派的基本单位称做线程线程或轻量级轻量级进程进程（Light weight process, LWP），而把资源分配的基本单位称做进程进程或者任务任务。3.3.1 线程简介线程简介42l进程在任一时刻只有一个执行控制流，通常将这种结构的进程称为单线程进程（Single threaded process）l多线程进程（Multiple threaded process）同一进程中设计出多条控制流，并且满足： （1）多控制流之间可以并行执行； （2）多控制流切换不需通过进程调度； （3）多控

16、制流之间可以通过内存直接通信联系，从而降低通信开销。3.3.2 多线程多线程43图3.7 进程和线程3.3.2 多线程多线程442.多线程环境下的进程和线程 （1）多线程环境下的进程 在多线程环境中，进程被定义为资源分配的基本单位，与进程相关的有：存放进程映象的虚拟地址空间受保护地对处理器、其他进程、文件和I/O资源的访问3.3.2 多线程多线程45（2）多线程环境下的线程 一个进程内包含一个或者多个线程，每个线程都包含：线程执行状态当线程处于非运行状态时，有一个受保护的线程上下文，用于存储现场信息一个执行堆栈容纳每个线程的局部变量的存储空间与进程内其它线程共享访问进程的内存空间和资源3.3.

17、2 多线程多线程46图3.8 单线程和多线程环境下的进程模型3.3.2 多线程多线程47l线程的主要特性： （1）并发性 （2）共享性 （3）动态性 （4）结构性3.线程状态l线程的关键状态有：运行态、就绪态、阻塞态l与线程状态转换相关的操作：派生、阻塞、解除阻塞、结束3.3.2 多线程多线程481.线程实现（1）用户级线程（User level thread, ULT） 线程管理的所有工作都由应用程序完成，内核意识不到线程的存在。3.3.3 线程实现与线程模型线程实现与线程模型49 用户级线程方式优点：因为所有线程的管理数据结构都在该进程的用户空间中，因此线程切换不需要转换到内核空间，从而节

18、省了模式切换的开销。调度算法可以是基于不同进程量身定做。不同进程可以根据自身需要，为自己量身定做适合自身的调度算法完成对线程进行管理和调度。用户级线程的实现与操作系统平台无关，即可以在任何操作系统中运行。3.3.3 线程实现与线程模型线程实现与线程模型50 用户级线程方式缺点：许多系统调用会引起阻塞，当用户级线程执行一个系统调用时，不仅该线程会被阻塞，而且该线程所在进程内的所有线程都会被阻塞。在纯粹的用户级线程实现方式中，多线程应用不能利用多处理机技术。内核一次只为每个进程分配一个处理器，即进程每次只有一个线程处于运行状态，其它线程此时只能等待。3.3.3 线程实现与线程模型线程实现与线程模型

19、51（2）内核级线程（Kernel level thread, KLT） 线程管理的所有工作都是由内核完成，应用程序并没有参与其中。即：无论是用户进程中的线程，还是系统进程中的线程，他们的创建、终止和切换等也是依靠内核，在内核空间实现的。3.3.3 线程实现与线程模型线程实现与线程模型52内核级线程方式优点：内核能够同时为同一进程中的多个线程分配多个处理器，即能让多个线程并行执行。如果进程中的一个线程被阻塞了，内核可以为该进程中的其它线程分派处理器资源使其运行，当然也可以调度其它进程中的线程运行。内核本身也可以采用多线程技术，从而提高系统的执行速度和效率。3.3.3 线程实现与线程模型线程实现

20、与线程模型53 内核级线程方式缺点： 因为线程调度和管理是在内核实现，而用户进程的线程却是在用户态下运行。因此在进行线程与同一进程内其它线程切换时，需要从用户态转到内核态进行，从而导致较大的系统开销。3.3.3 线程实现与线程模型线程实现与线程模型54（3）组合方式 同一个进程内的多个线程可以同时在多处理器上并行执行，而且一个线程被阻塞时，同一进程内的其它线程可以调度运行，并不需要阻塞整个进程。组合方式多线程机制能够结合 KLT 和 ULT 两者的优点，并克服了各自的不足。3.3.3 线程实现与线程模型线程实现与线程模型55图3.9 线程实现方式3.3.3 线程实现与线程模型线程实现与线程模型

21、562.线程模型（1）多对一模型3.3.3 线程实现与线程模型线程实现与线程模型57图3.10 多对一模型（2）一对一模型3.3.3 线程实现与线程模型线程实现与线程模型58图3.11 一对一模型（3）多对多模型3.3.3 线程实现与线程模型线程实现与线程模型59图3.12 多对多模型l操作系统设计中的核心问题是关于进程和线程的管理，例如：采用多道程序设计技术管理单处理器系统中的多个进程采用多处理技术管理多处理器系统中的多个进程采用分布式处理技术管理多台分布式计算机系统中的多个进程l并发是上述管理问题实现的基础，也是操作系统设计的核心3.4 互斥和同步互斥和同步60l并发涉及的术语：（1）临界

22、区临界区（Critical section）（2）竞争（Competition）（3）同步同步（Synchronization）（4）互斥（Mutual exclusion）（5）死锁死锁（Deadlock）（6）饥饿（Starvation）3.4.1 并发原理并发原理613.4.1 并发原理并发原理62l2.临界区和临界资源l临界资源临界资源（Critical resource），多个进程间采取互斥的方式实现对临界资源的共享访问l使用临界资源的程序代码称为临界区临界区l进程间竞争资源产生如下的几个控制问题 （1）互斥 （2）死锁 （3）饥饿3.4.1 并发原理并发原理63多个进程共享临界区，

23、需遵循如下的调度原则：3.4.1 并发原理并发原理651.关中断关中断：使进程在临界区时不响应中断2.TestAndSet指令：指令：指令描述如下：boolean TestAndSet(boolean *lock) boolean temp = *lock; *lock = TRUE; return temp;3.4.2 硬件同步硬件同步66lTestAndSet指令实现互斥的示例如下：do while(TestAndSet(&lock) ;/ do nothing / critical section lock = FALSE; / remainder sectionwhile(TR

24、UE);3.4.2 硬件同步硬件同步673.Swap指令：指令：为对换指令，定义如下：void Swap(boolean *a, boolean *b) Boolean temp = *a; *a = *b; *b = temp;3.4.2 硬件同步硬件同步68l使用Swap指令实现互斥的示例如下：do data = TRUE; while(data = TRUE) Swap(&lock, &data); / critical section lock = FALSE; / reminder section while(TRUE);3.4.2 硬件同步硬件同步693.4.3 信

25、号量机制信号量机制1.整型信号量 Dijkstra把整型信号量 s 定义成一个用于表示资源数目的整型变量。进程通过信号量传送信号，利用两个特殊的操作发送和接收信号。 signal(s)：通过信号量：通过信号量 s 传送信号传送信号 wait(s)：通过信号量：通过信号量 s 接收信号接收信号 如果相应的信号仍然没有发送则进程被挂起，直到发送完为止。3.4.3 信号量机制信号量机制71void wait(s)void wait(s) while(s=0) while(s=0)； /do nothing /do nothing s-; s-; 3.4.3 信号量机制信号量机制72void sign

26、al(s)void signal(s) s+; s+; 2.记录型信号量l整型信号量机制没有满足让权等待的原则，可能使进程处于饥饿的忙等状态。l假设 s 为一个记录型数据结构，其中一个分量为整形数整形数value，另一个为信号量队列信号量队列queue。lvalue通常是一个具有非负初值的整型变量，queue 表示一个初始时为空的进程队列，当某进程必须等待信号量时，就加入到该队列中。3.4.3 信号量机制信号量机制73lwait 和 signal 操作定义相应为： wait(s)：信号量 s 减 l，若结果小于0，则调用wait(s)的进程被设置成等待信号量 s 的状态。 signal(s)：

27、将信号量 s 加 1，若结果不大于0，则释放一个等待信号量s的进程。3.4.3 信号量机制信号量机制74（1）若 s.value 值为正，则该值表示在对进程进行阻塞之前对信号量 s 可以实施的wait( )操作个数，即：系统中某类资源实际可用数目系统中某类资源实际可用数目；（2）若 s.value 值为负，则它的绝对值表示阻塞队列阻塞队列s.queue 中等待的进程个数中等待的进程个数；（3）每次wait()操作，表示进程请求一个单位的该类请求一个单位的该类资源资源，使系统中可供分配的该类资源数减少一；每次signal()操作，表示执行进程释放一个单位该资源释放一个单位该资源，使系统中可供分配

28、的该类资源数增加一。3.4.3 信号量机制信号量机制753.二元信号量（P56）l假设 s 为一个记录型数据结构，其中一个分量为 value，它仅能取值 0 和 1，另一个分量为信号量队列 queue。l一个二元信号量的值只能是 0 或者 13.4.3 信号量机制信号量机制761.1.生产者生产者- -消费者问题消费者问题（1）问题描述 假设有n个生产者和m个消费者，连接在一个有 k 个公用缓冲区的有界缓冲上，pi 表示生产者进程，cj 表示消费者进程。应满足应满足：只要缓冲区未满，生产者pi 即可将生产的产品放 入空闲缓冲区中；否则pi 阻塞只要缓冲区不空，消费者cj 就可从缓冲区从取走并消

29、耗产品；否则cj 阻塞3.4.5 经典同步问题经典同步问题80u注意：单一过程中控制对资源的互斥访问的wait(mutex)和signal(mutex)的操作必须成对出现。对记录资源的信号量empty和full的wait和signal操作也必须成对出现，但允许它们根据逻辑需要出现在不同的过程中。为避免死锁，控制互斥访问和记录资源的信号量的wait操作顺序不能乱，必须先执行wait(empty)，再执行wait(mutex)。3.4.5 经典同步问题经典同步问题872.2.读者读者- -写者问题写者问题（1）问题描述 有一个多进程共享的数据区，把只要读该数据区的记为Reader进程（读者），把只

30、要往数据区内写数据的记为Writer进程（写者）。满足满足：允许多个读者同时执行读操作一次只能有一个写者执行写操作如果一个写者在执行写操作，则其它任何读者都如果一个写者在执行写操作，则其它任何读者都不能执行读操作不能执行读操作883.3.哲学家就餐问题哲学家就餐问题3.4.5 经典同步问题经典同步问题93（1）问题描述 有五位哲学家，用一生来思考和吃饭。他们围坐在一张圆桌旁，桌子中央有一大碗米饭，桌上还有五个碗和五只筷子，他们的生活方式是交替地进行思考和进餐。当某位哲学家进行思考时，他不与其它哲学家交互。当他感觉到饥饿时，便试图拿起与其左右最靠近的筷子。一个哲学家每次只能拿起一只筷子，且他不能

31、从其他哲学家手里拿筷子只有在他拿到两只筷子时才能进餐3.4.5 经典同步问题经典同步问题94 （2）用信号量解决哲学家就餐问题u每一只筷子的使用都必须是互斥的，在某一时刻只允许一个哲学家使用，它是临界资源u利用一个信号量表示一只筷子，五只筷子的信号量数组定义为：u利用变量 i 区分不同的哲学家及筷子：3.4.5 经典同步问题经典同步问题951. 管程的定义 管程是由一个或多个过程、一个初始化序管程是由一个或多个过程、一个初始化序列和数据组成的软件模块列和数据组成的软件模块，是一种程序设计语言结构成分，具有和信号量同等的表达能力。 进程可以通过调用管程实现对资源的请求和释放。3.4.4 管程管程

32、100 管程对分散在各进程中的临界区集中进临界区集中进行管理行管理，并将系统中的共享资源用数据结构抽象地表示出来。 管程中的共享变量每次只能被一个进程访问，从而可以提供互斥机制。l管程的主要特点：共享性共享性：一个进程通过调用管程的一个过程进入管程，管程中的过程可被所有要调用它的进程所共享。安全性安全性：管程的局部数据变量只能被管程的过程访问，任何其它外部过程都不能访问；一个管程的过程也不能访问任何非局部于它的变量。互斥性互斥性：在任一时刻，只能有一个进程进入管程执行，调用管程的其它任何进程都将被阻塞，只能等待直到当前访问进程退出管程。3.4.4 管程管程1022.管程的条件变量l在管程的调用

33、过程中可能存在如下现象：一个进程调用了管程，之后在管程中处于阻塞或挂起状态，只有当进程解除阻塞或挂起的条件满足后才能恢复执行。l引入条件变量条件变量（Condition variables）的同步机制，及其对应的原语操作cwait 和 csignal。3.4.4 管程管程103 条件变量也是一种信号量，但它不同于信号量机制中的计数信号量。 由于一个进程被阻塞或挂起的条件或原因一般存在多个，因此也在管程中设置多个条件变量以便完成对进程的描述控制。 条件变量的访问只在管程中进行，因此条件变量的访问只在管程中进行，因此对其的同步原语操作可以用来控制进入管程对其的同步原语操作可以用来控制进入管程的进程的进程。lcwait 和和 csignal 操作的意义：操作的意义： （1）cwait(c) 操作操作：正在调用管程的进程因条件 c