孙卫真-第2章-考研计算机专业课冲刺班操作系统讲义[共6.pdf

《孙卫真-第2章-考研计算机专业课冲刺班操作系统讲义[共6.pdf》由会员分享，可在线阅读，更多相关《孙卫真-第2章-考研计算机专业课冲刺班操作系统讲义[共6.pdf（9页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1第二章 进程管理2.1 进程的基本概念进程的基本概念2.2 进程控制进程控制2.3 进程同步进程同步2.4 经典进程的同步问题经典进程的同步问题2.5 进程通信进程通信2.6 线程线程2.1 进程的基本概念进程的基本概念2.1.1 程序的顺序执行及其特征2.1.2 前趋图前趋图(Precedence Graph)是一个有向无循环图，记为DAG(Directed Acyclic Graph)，用于描述进程之间执行的前后关系。2.1.3 程序的并发执行及其特征2.1.4 进程的特征与状态前趋图的形式前趋图的表示One program which has an independent functi

2、onworks on certain data set dynamically and allocate resources dynamically进程的定义一个具有一定独立功能的程序对某个数据集合上的一次动态执行过程和资源分配过程进程的元素：代码、数据、进程表（进程控制块）Code、Data、PT（PCB）进程和程序的区别与联系 进程是动态的，程序是静态的 进程是暂时的，程序是永久的 进程和程序的组成不同 程序主要包含代码和数据 进程除了包含代码和数据以外，还有进程表 进程和程序间有非常紧密的联系 程序经过多次创建，可以对应不同的进程 一个进程通过系统调用，可以被多个程序所使用选择填空进程包

3、含（）、（）和（）。数据；记录项；目录；代码；进程表；文件，共享库。2选择填空（）是进程存在的唯一标志。数据；记录项；目录；代码；进程表；文件，共享库。2.进程的三种基本状态1)就绪(Ready)状态2)执行(Running)状态3)阻塞(Blocking)状态后备2.1.5 进程表1.进程表的作用2.进程表中的信息3.进程表的组织方式1)链接方式2)索引方式就绪队列链表（一般为一个）阻塞队列链表（可能依据不同阻塞原因有多个队列链表）进程表就绪队列索引阻塞队列索引32.2 进 程 控 制2.2.1 进程的创建(1)用户登录。(2)作业调度。(3)提供服务。(4)应用请求。(1)申请空白进程表。

4、(2)为新进程分配资源。(3)初始化进程表。(4)如果进程就绪队列能够接纳新进程，便将新进程插入就绪队列。2.2.2 进程的创建过程选择题进程创建后，所有创建完成后的进程PCB被链接成一个序列，这个序列称为什么？阻塞序列；挂起序列；就绪序列；运行序列。2.2.2 进程的终止1)正常结束（自愿的）2)异常结束-普通错误退出（自愿的）-致命错误退出（非自愿的）3)外界干预（非自愿的）2.进程的终止过程(1)根据被终止进程的标识符，从进程表中检索出该进程的进程控制块，从中读出该进程的状态。(2)若被终止进程正处于执行状态，应立即终止该进程的执行，并置调度标志为真，用于指示该进程被终止后应重新进行调度

5、。(3)若该进程还有子孙进程，还应将其所有子孙进程予以终止，以防他们成为不可控的进程。(4)将被终止进程所拥有的全部资源，或者归还给其父进程，或者归还给系统。(5)将被终止进程(它的进程控制块)从所在队列(或链表)中移出，等待其他程序来搜集信息。2.2.3 进程的阻塞与唤醒1.引起进程阻塞和唤醒的事件1)请求系统服务2)启动某种操作3)新数据尚未到达4)无新工作可做2.2.4 进程的挂起与激活2.3 进 程 同 步进 程 同 步2.3.1 进程同步的基本概念1.两种形式的制约关系(1)间接相互制约关系。(2)直接相互制约关系。2.临界资源(Critical Resource)3.临界区(cri

6、tical section)4一个飞机订票系统（软件相同），两个终端，运行T1、T2进程T1：read(x);if x=1 thenx:=x-1;write(x);T2：read(x);if x=1 thenx:=x-1;write(x);互斥关系Coming data blocks初始状态结果正确错误错误错误错误错误同步关系4.同步机制应遵循的规则(1)空闲让进。(2)忙则等待。(3)有限等待。(4)让权等待。(Petersons Algorithm)：先修改、后检查、后修改者等待 正确的算法 turn=j;描述可进入的进程（同时修改标志时）在进入区先修改后检查，并检查并发修改的先后：检查对

7、方flag，如果不在临界区则自己进入空闲则入 否则再检查turn：保存的是较晚的一次赋值，则较晚的进程等待，较早的进程进入先到先入，后到等待硬件TSL指令 Entering and leaving a critical region using the TSL instruction2.3.2 信号量机制1.整型信号量最初由Dijkstra把整型信号量定义为一个整型量，仅能通过初始化和两个标准的原子操作(Atomic Operation)wait(S)和signal(S)来访问。两个操作被分别称为P、V操作(primitive)。525P P 原语原语wait(s);down(s);P(s)w

8、ait(s);down(s);P(s)?-s.count;/表示申请一个资源;if(s.count 0)/表示没有空闲资源;调用进程进入等待队列 s.queue;阻塞调用进程;26V V 原语原语signal(s);up(s);V(s)signal(s);up(s);V(s)?+s.count;/表示释放一个资源；if(s.count=0)/表示有进程处于阻塞状态；从等待队列s.queue中取出一个进程P;进程P进入就绪队列;Semaphores The producer-consumer problem using semaphores2.4 经典进程的同步问题经典进程的同步问题2.4.1

9、生产者消费者问题1.利用信号量解决生产者消费者问题Dining Philosophers Philosophers eat/think Eating needs 2 forks Pick one fork at a time How to prevent deadlock2.4.2 哲学家进餐问题 让奇数号的哲学家先取右手边的筷子，让偶数号的哲学家先取左手边的筷子。send(i)beginif i mod 2=0 then else P(ci);P(ci+1 mod 5);P(ci+1 mod 5);P(ci);eat;eat;V(ci+1 mod 5);V(ci);V(ci);V(ci+1

10、mod 5);end62.4.3 读者-写者问题读者-写者问题描述数据区读者计数互斥互斥The Readers and Writers Problem1.利用信号量解决读者-写者问题睡眠的理发师问题编程题1 李松和他的女朋友汪媛共享一个银行帐号，他们均可以往里存款和提款，他们的行为可以编成程序（见例程）。李松和汪媛可能会同时存、取款，于是可能会发生奇怪的事件，假设李松先前已经往帐户里存了500美元，当他再往里存100美元的同时汪媛恰好提取200美元，按程序，他们谁都执行的同一段代码，那么，考虑不同情形，他们离开后帐户里会变成多少美元呢？（有多种结果）如何采用PV操作来避免上述情况的发生呢？请重

11、新修改程序。int amount=0;while(TRUE)proc_save(money)int m=0;m=amount;m=m+money;amount=m;proc_drawing(money)int m=0;m=amount;m=m-money;amount=m;7编程题2 桌子上有一个盘子，只能装一只水果。爸爸弗兰克能往里放苹果，妈妈杰西卡能往里放桔子。但是它们必须互斥地进行。儿子汤姆只取桔子吃，女儿安妮只取苹果吃，它们也是必须互斥操作。那么，请写出爸爸、妈妈、儿子、女儿四个进程的正确操作。Shared memory(共享内存)Message(消息机制)Pipe(管道)Signal

12、(信号)Socket(套接字)Interprocess Communication2.5 进 程 通 信进 程 通 信2.6 线 程线 程2.6.1 线程的基本概念1.线程的引入For Example2.线程的属性(1)轻型实体（容易创建和撤销）。(2)独立调度和分派的基本单位。(3)可并发执行。(4)共享进程资源。(5)适应硬件的发展线程表 Items shared by all threads in a process Items private to each thread83.线程的状态(1)状态参数。(2)线程运行状态。5.多线程OS中的进程在多线程OS中，进程是作为拥有系统资源的基

13、本单位，通常的进程都包含多个线程并为它们提供资源，但此时的进程就不再作为一个执行的实体。多线程OS中的进程有以下属性：(1)作为系统资源分配的单位。(2)可包括多个线程。(3)进程不是一个可执行的实体。4.线程的创建和终止2.6.2 线程间的同步和通信1.互斥锁(mutex)互斥锁是一种比较简单的、用于实现线程间对资源互斥访问的机制。2.条件变量2.6.3 内核支持线程和用户级线程1.内核支持线程这里所谓的内核支持线程，也都同样是在内核的支持下运行的，即无论是用户进程中的线程，还是系统进程中的线程，他们的创建、撤消和切换等，也是依靠内核实现的。此外，在内核空间还为每一个内核支持线程设置了一个线

14、程控制块，内核是根据该控制块而感知某线程的存在的，并对其加以控制。Implementing Threads in the Kernel A threads package managed by the kernel2.用户级线程用户级线程仅存在于用户空间中。对于这种线程的创建、撤消、线程之间的同步与通信等功能，都无须利用系统调用来实现。对于用户级线程的切换，通常是发生在一个应用进程的诸多线程之间，这时，也同样无须内核的支持。由于切换的规则远比进程调度和切换的规则简单，因而使线程的切换速度特别快。可见，这种线程是与内核无关的。9Implementing Threads in User Space A user-level threads packageHybrid Implementations Multiplexing user-level threads onto kernel-level threadsThe Multithreading Revolution本章重要习题分析