操作系统设计与实现(第二章).ppt

《操作系统设计与实现(第二章).ppt》由会员分享，可在线阅读，更多相关《操作系统设计与实现(第二章).ppt（113页珍藏版）》请在三一办公上搜索。

1、操作系统设计与实现,Chapter 2 Processes,*The importance of process in an operating system2.1 Introduction to processes*common Parallelism=Pseudoparallelism*It is the cpu rapid switching back and forth*multiprocessor is the real parallelism*people design a model,sequential processes 顺序进程,2.1.1 The process mode

2、l,Characters:*All the runnable software are organized into a number of sequential processes;(in this chapter we called it processes)*The process is an executing program;The process include the values of the all the program counter,registers，and variables;(进程包括程序计数器、寄存器和变量的当前值。）To these characters,it

3、 is easy to analysis the collection of the processes than keep track the rapid switch of CPU,Process-Program,Process is an executing program,it has program,input,output,and state.An example:scientist prepare the cake for his daughter.Recipe:/resipi/食谱*A Process is an activity of some kind,It has a p

4、rogram,input,output,and a state,A single processor may be shared among several processes,with some scheduling algorithm being used to determine when to stop work on one process and service a different one.,理解进程和程序的区别：CPU：计算机科学家程序1：烘制生日蛋糕的食谱数据：面粉、鸡蛋、糖和香草汁等对应的进程1：阅读食谱、取来各种原料以及烘制蛋糕的一系列动作的总和。事件：女儿被蜜蜂螫伤保

5、存进程1的当前状态：计算机科学家就记录下自己照着食谱做到哪儿了。程序2：急救手册数据：药物等对应的进程2：实施医疗救治（高优先级进程）当蜜蜂螫伤处理完之后，计算机科学家又回来做蛋糕，从他离开时的那一步继续做下去。,进程的创建,系统初始化(1)前台进程：同用户交互并替它们完成工作的哪些进程。(2)后台进程：守护进程，处理网页、打印之类活动的进程。2.正在运行的一个进程执行了创建进程的系统调用。3.用户请求创建一个新进程。在交互式系统中，用户可以通过键入命令启动程序。4.批处理作业的初始化 在操作系统认为有资源运行另一个作业时，它创建一个新的进程，并运行其输入队列中的一个作业。,进程的终止,正常退

6、出：多数进程由于完成了它们的工作而终止。出错退出（自愿）:进程发现了严重错误。严重错误（非自愿）：通常是由于程序中的错误所致。例如，执行了一条非法指令，引用了不存在的内存，或除数是零。被其它进程杀死：当一个进程终止时，由该进程所创建的所有进程也都立即被杀死。,Process hierarchies,Any OS,to support process,it must provide some way to create all the processes needed.Use fork()to create a new process,the father process can create

7、his child processes,0more,and later,the process tree may appeared.In Minix,the root is init,and it works in this way:read info,create terminal,start program,NFS,SMTP,WWW,FTP,Process States,进程之间经常需要交互、通信以及和其他进程同步。For Communication between processesexchange info among them,but,once more than one proce

8、sses lead to block*logically,it have to stop,it will.(wait our input)*logically,it should continue,but it stopped,now,the CPU may be occupied by another process.运行态（Running，在该时刻实际占用处理机）。就绪态（Ready，可运行，因为其它进程正在运行而暂时被挂起）。阻塞态（Blocked，除非某种外部事件发生，否则不能运行）。,2.1.2 Implementation of Processes,*Process Table(a

9、n array of structures)（进程表）each process is a record of this table,and each record include the state of the process,program counter,stack pointer,and allocation of memory.;thus,when the process is in ready state,all the info wont lose.In MINIX,the process management,memory management,and file managem

10、ent are each handled by separate modules within the system,so the process table is partitioned.Look at the pic:,Interrupt Vector（中断向量）,An interruption,it relate to each kinds of I/O device(hardware),it contain the address of the interrupt service procedure.The interrupt procedure store the current v

11、ariables and info to stacks,and did some works related to its recover.Now,the pre process is stored,and the new one could continue.When it is finished,the old one could be recalled,and runs smoothly,just nothing had happened.Of course the interrupt must related to their priority.The real procedure i

12、s:,2.1.3 Threads（线程）,1.Conceptto the traditional process,one process just has one control clue（控制流）and one program counter.In modern OS,more and more OS support the multi-control clue in a process,and we call these control clue threads.The real application of threads model from the application to sh

13、ow its importance to OS,多线程的应用（1）,explorer netscape（网络浏览器）许多Web页面都包含有多幅很小的图像。site:the images folder lies D:siteimagesprocess:build up one connectionthreads:build up more connection 在浏览器内设立多个进程，同时请求传输多幅图像，可节省建立和释放链接的时间。To small size files,the connection-building needs more time than transporting.tran

14、smitting use.rar.zip than folder.,多线程的应用（2）,网络蚂蚁(NetAnts)是从因特网下载文件的工具软件，设计特点如下：(A)支持HTTP和FTP协议，可同时下载1-5个文件；(B)可随时中止正在下载的任务，任务将自动保存当前状态；(C)支持拖放，可从浏览器中将链接拖入任务列表；(D)裁剪板自动监视，并可指定将捕获的文件类型；(E)捕获浏览器的动作，当用户在浏览器中单击链接时，网络蚂蚁将自动激活。,A,B,To A:when sever is busy,it will stopped,the writing will stopped.save the de

15、stination to.To B:when server is busy,other threads will still try.the writing wont stopped.use flashget netant,进程和线程的区别,允许在同一个进程环境中有多个执行流（线程），这些流在很大程度上相对独立，但共享相同的地址空间。进程用来集合资源，而线程是CPU中调度的实体。,To B:these threads share the same address spaceAnd these threads can write the information to the same place

16、,the same file.So the table will can be used to threads,then the threads can be restore、block、ready.Meaning:all the program can use the resources more efficiently,improved the OSs performance.,2.ProblemsTo different OS,the problems are different.1）OS dont know the existence of threadsThe control of

17、threads will by in user space.Then many threads packages are there.eg P-threads2)OS know the existence of threadsthe kernel will create the table to maintain the threads,threads table.,The difference of the two kind of OS,Conclusion:Get them together,adopt them two.,3)The new problems!Parent-process

18、&child-processparents process has many child threads,then how about the child-process!Multi processes share the data-structureone thread is closing a file,while the file is be reading by another thread.one thread is apply the memory,but now,switch happened,another threads will reapply.!Error reports

19、in Unix,the returned error value is stored in a variable,when one is stored a value there,then another cleared the value,and write a new value to there,then?,2.2 Inter Processes Communication(IPC),CONTENTS:How a process to send messages to another one;We must make sure the processes cant effect each

20、 other when they are visiting the critical area;When the reliable relations are there,how to design their proper order.,2.2.1 Race condition（竞争条件）,To Process A:read In,write 7 to Next-free-slot(local);Interruption:A blocked,and B came in;B read In,got 7,then save name to slot7;In+1=8,B will think hi

21、s job is finished;A came back,and read local next-free-slot,save name to slot 7,and next-free-slot+1=8,save 8 to In.B will never be print.,打印机假脱机系统,2.2.2 Critical region-Critical section,Mutual exclusion（互斥）:any share resource(memory、file)may happen the similar errors(spooler),we have to take this m

22、easure to prevent the race.,When the race will happen?If the race happens between two processes,they wont race from the beginning to the end.Only when they visit the same memory area or the same file,the race will happen.Here,if a program segment could visit the shared memory,we called the program s

23、egment critical region or critical section.(临界区或临界段）,临界区的定义：,假如两个或更多的进程需要访问一个不可共享的资源（打印机），在执行过程中，每个进程都给该I/O设备发送命令，接受状态信息，发送数据，接收数据。我们把这类资源称作临界资源，使用临界资源的那一部分程序称作成程序的临界区。一次只允许有一个程序在临界区中。,互斥的定义：用某种手段，避免多个进程访问同一个临界区的操作叫做互斥。,进程的交互关系：可以按照相互感知的程度来分类,互斥，指多个进程不能同时使用同一个共享资源；死锁，指多个进程互不相让，都得不到足够的资源；饥饿，指一个进程一直得不

24、到资源（其他进程可能轮流占用资源）,相互感知的程度,交互关系,一个进程对其他进程,的影响,潜在的控制问题,相互不感知,(,完全不,了解其它进程的存,在,),竞争,(competition),一个进程的操作对其,他进程的结果无影响,互斥，死锁（可释放的,资源），饥饿,间接感知,(,双方都与,第三方交互，如共享,资源,),通过共享进行协作,一个进程的结果依赖,于从其他进程获得的,信息,互斥，死锁（可释放的,资源），饥饿，数据一,致性,直接感知,(,双方直接,交互，如通信,),通过通信进行协作,一个进程的结果依赖,于从其他进程获得的,信息,死锁，饥饿,How to solve it?if we co

25、uld settle the processes very well,to avoid the processes visit the shared memory at the same time,then the race will be solved.To any good plans,we should make sure that:!Any two processes cant stayed in the critical area at the same time;!We shouldnt do any supposition to CPUs speed and number;!Th

26、e process out of critical area cant block other process;!We shouldnt let the process keep on waiting out of the critical area.,2.2.3 Exclusion of busy waiting,忙等待形式的互斥*Close interrupt（关中段）the simplest way,when the process entered the critical area.It will close the interrupt,when it is finished,it w

27、ill open the interrupt again;Shortage:it is fool to let the user has right to start or close interrupt.and to multi-processor PC,close interrupt is effected to one processor,and to other processors,the visit of the shared memory will continue.,*锁变量,对于某一个临界区，在它之外设置一个锁，每个进程要进入临界区的时候，首先要测试这把锁，如果锁打开着的（锁

28、的值为0），则该进程可以进入（并将锁置1），如果关闭着的（锁的值为1），则该进程不能够进入；同样，一个进程进入了临界区后就把这把锁给锁上，当它出来后再打开这把锁，这样会对这个临界区有很好的保护作用，实现了互斥。,但是矛盾依然有，跟Spooler目录一样。,严格轮换法（交替法）,严格轮换法是指几个进程轮换进入某一临界区，且顺序不能紊乱。,While(TRUE)while(turn!=0);/*wait*/critical_region();turn=1;noncritical_region();,While(TRUE)while(turn!=1);/*wait*/critical_region(

29、);turn=0;noncritical_region();,初始值：turn=0;,忙等待：进程不断地读turn的值，只是他没有做任何有意义的事（等待），而且浪费了cpu的时间（忙）。故称作忙等待 busy waiting,turn=1,正常情况,假如两个进程：首先A进程进入，使用临界区后，修改turn的值，然后进入非临界区，然后B进程进入，根据判断，发觉可以进入，就进入临界区，执行完后，修改临界区的值，在然后进入自己的非临界区。依次A、B轮换执行。异常:(此时虽然不会竞争，但浪费了资源)如果进程A的非临界区很快能执行完，而进程B的非临界区却非常慢，则会：,t,t,t,此时，两个进程的完成时

30、间的衡量就应该按照慢的那个来衡量，而且，如果任何一个进程死掉了，则进程则会永远堵塞下去，不管是在临界区内还是在临界区外。荷兰数学家T.Dekker通过设置加警告变量的方法来回避这种情况的发生，但警告的同时也必须能够监测其他进程此时对临界区的使用情况，即出现了Dekker算法。参考别的书籍。（操作系统内核与设计原理P154）,Dekkers Algorithm,Process 0Process 1.flag0=true;flag1=true;while(flag1=true)while(flag0=true)if(turn=1)if(turn=0)flag0=false;flag1=false;

31、while(turn=1);while(turn=0);flag0=true;flag1=true;turn=1;turn=0;flag0=false;flag1=false;.,Peterson算法-(两个进程的Peterson算法),Boolean flag2:数组元素int turn;Void P0()while(TRUE)flag0=TRUE;turn=0;while(flag1/*noncritical area*/,Void P1()while(TRUE)flag1=TRUE;turn=1;while(flag0/*noncritical area*/,初始值为false,Pete

32、rson算法是正确的算法turn=j;描述可进入的进程（同时修改标志值）检查对方flag，如果不在临界区则自己进入空闲则入；否则再检查turn：保存的是较晚的一次赋值，则较晚的进程等待，较早的进程进入先到先入，后到等待。,硬件手段(TSL-test and set lock),原子操作：这种操作在运行的过程中，是不能也不允许被打断的，它是操作的最底层的部分，是不可分割的，称其为原子操作。TSL工作原理：将一个存储器字读到寄存器当中，然后在这个内存中存一个非零的值。这个读写的过程是个原子操作，是不可分割的。,Enter_region:tsl register,lockcmp register,#

33、0jne enter_regionretLeave_region:move lock,#0ret,硬件方法的优点适用于任意数目的进程，在单处理器或多处理器上简单，容易验证其正确性可以支持进程内存在多个临界区，只需为每个临界区设立一个布尔变量硬件方法的缺点等待要耗费CPU时间，不能实现让权等待可能饥饿：从等待进程中随机选择一个进入临界区，有的进程可能一直选不上可能死锁（见下页）,2.2.4 睡眠和唤醒的引入,对于Peterson和TSL问题，都能够很好地实现互斥，但也都同时存在问题：*忙等待，浪费CPU的资源。*进程的优先级有差别：当有两个进程，A、B，A的优先级高，处于就绪状态，而此时，B在临

34、界区内，由于优先级低，故无法被调度，也就无法离开临界区，那A就只能够在临界区外等待。解决的途径就是引入新的概念：睡眠 唤醒睡眠：对应着在临界区外的不停判断和等待；唤醒：对应着触发另一个满足条件的进程进入临界区。,生产者和消费者问题：,问题描述：若干进程通过有限的共享缓冲区交换数据。其中，生产者进程不断写入，而消费者进程不断读出；共享缓冲区共有N个；任何时刻只能有一个进程可对共享缓冲区进行操作。,#define N 100int count=0;void producer(void)while(TRUE)produce_item();if(count=N)sleep();enter_item()

35、;count=count+1;if(count=1)wakeup(consumer),void consumer(void)while(TRUE)remove_item();if(count=0)sleep();enter_item();count=count-1;if(count=N-1)wakeup(producer),对于生产者：只有当缓冲区里为零的时候，这时候消费者才有可能睡觉；对于消费者：只有当缓冲区里装满的时候，这时候生产者才有可能睡觉。导致的问题：类Spooler目录问题 缓冲区为空，消费者检查，得到count=0,但未睡觉的时候，被调度程序挂起，此时它将保留一个局部变量来存储c

36、ount的值，此时生产者开始工作并向缓冲区内放入资源，当资源等于1后，向消费者发送唤醒信号，而此时消费者没有睡眠，等消费者被恢复以后，检查自己存储过的count，发觉它等于零，则开始睡眠，而生产者则不停生产，当缓冲区满了以后自己也开始睡眠，这时候他们就都处于睡眠状态。,2.2.5 信号量,1965年，由荷兰学者Dijkstra提出（所以P、V分别是荷兰语的test(proberen)和increment(verhogen)），是一种卓有成效的进程同步机制。原理：两个或多个进程可以通过简单的信号进行合作，一个进程可以被迫在某一个位置停止，直到他接受到一个特定的信号。为了发信号，需要一个特殊的变量

37、-信号量s为了通过信号量s传送信号，进程可执行原语signal(s);为了通过信号量s接收信号，进程可执行原语wait(s);,对信号量的操作,1.一个信号量可以初始化为非负数2.Wait操作是信号量减一，如果值变为了负数，则执行wait的进程被阻塞；Signal操作是信号量加一，如果值不是正数，则被wait操作阻塞的进程被解除阻塞。除了以上三种操作以外，没有任何其他地方可以检查或操作信号量。Wait=PSignal=V,多元信号量的P V 操作,Struct semaphore int count;queueType queue;Void wait(semaphore s)s.count-;

38、if(s.count 0)place this process in s.queue;block this process;,Void signal(semaphore s)s.count+;if(s.count=0)remove a process P from s.queue;place process P on ready list;,此处的wait 和signal 都是原子操作，不会被中断影响。,二元信号量的P V操作,Void waitB(binary_semaphore s)if(s.value=1)s.value=0;else place this process in s.qu

39、eue;block this process;,Void signalB(binary_semaphore s)if(s.queue.is_empty()s.value=1;else remove a process P from s.queue;place process P on ready list;,Struct binary_semaphore enmu(zero,one)value;queueType queuw;,P原语wait(s),s.count-;/表示申请一个资源;if(s.count 0)/表示没有空闲资源;调用进程进入等待队列s.queue;阻塞调用进程;,V原语si

40、gnal(s),s.count+;/表示释放一个资源；if(s.count=0)/表示有进程处于阻塞状态；从等待队列s.queue中取出一个进程P;进程P进入就绪队列;,V原语通常唤醒进程等待队列中的头一个进程,利用信号量实现互斥,为临界资源设置一个互斥信号量mutex(MUTual Exclusion)，其初值为1；在每个进程中将临界区代码置于P(mutex)和V(mutex)原语之间必须成对使用P和V原语：遗漏P原语则不能保证互斥访问，遗漏V原语则不能在使用临界资源之后将其释放（给其他等待的进程）；P、V原语不能次序错误、重复或遗漏,#define N 100/缓冲区内槽数Typedef

41、int semaphore;semaphore mutex=1;semaphore full=0;semaphore empty=N;,Void producer(void)int item;while(TRUE)produce_item(,Void consumer(void)int item;while(TRUE)down(,上面程序是利用信号量互斥来解决生产者-消费者问题的。其中：信号量mutex用于互斥，保证任意时刻只能有一个进程读写缓冲区和相关的变量，保证了临界区、临界资源的合理安全使用。信号量full和empty用来保证一定的时间顺序发生或不发生，它用来通知生产者和消费者，保证了当

42、缓冲区满的时候生产者停止运行，以及当缓冲区空的时候消费者停止运行。,2.2.6 管程,信号量同步的缺点同步操作分散：信号量机制中，同步操作分散在各个进程中，使用不当就可能导致各进程死锁（如P、V操作的次序错误、重复或遗漏）易读性差：要了解对于一组共享变量及信号量的操作是否正确，必须通读整个系统或者并发程序；不利于修改和维护：各模块的独立性差，任一组变量或一段代码的修改都可能影响全局；正确性难以保证：操作系统或并发程序通常很大，很难保证这样一个复杂的系统没有逻辑错误；,2.管程的引入1973年，Hoare和Hanson所提出；其基本思想是把信号量及其操作原语封装在一个对象内部。即：将共享变量以及

43、对共享变量能够进行的所有操作集中在一个模块中。管程的定义：管程是关于共享资源的数据结构及一组针对该资源的操作过程所构成的软件模块。管程可增强模块的独立性：系统按资源管理的观点分解成若干模块，用数据表示抽象系统资源，同时分析了共享资源和专用资源在管理上的差别，按不同的管理方式定义模块的类型和结构，使同步操作相对集中，从而增加了模块的相对独立性引入管程可提高代码的可读性，便于修改和维护，正确性易于保证：采用集中式同步机制。一个操作系统或并发程序由若干个这样的模块所构成，一个模块通常较短，模块之间关系清晰。,3.管程的主要特性模块化：一个管程是一个基本程序单位，可以单独编译；抽象数据类型：管程是一种

44、特殊的数据类型，其中不仅有数据，而且有对数据进行操作的代码信息封装：管程是半透明的，管程中的外部过程（函数）实现了某些功能，至于这些功能是怎样实现的，在其外部则是不可见的.,4.管程的实现要素管程中的共享变量在管程外部是不可见的，外部只能通过调用管程中所说明的外部过程（函数）来间接地访问管程中的共享变量；为了保证管程共享变量的数据完整性，规定管程互斥进入；管程通常是用来管理资源的，因而在管程中应当设有进程等待队列以及相应的等待及唤醒操作；,5.条件变量(condition)由于管程通常是用于管理资源的，因而在管程内部，应当存在某种等待机制。当进入管程的进程因资源被占用等原因不能继续运行时使其等

45、待。为此在管程内部可以说明和使用一种特殊类型的变量-条件变量。每个表示一种等待原因，并不取具体数值相当于每个原因对应一个队列。,6.管程的格式（类Pascal）TYPE monitor_name=MONITOR;共享变量说明define 本管程内所定义、本管程外可调用的过程（函数）名字表use 本管程外所定义、本管程内将调用的过程（函数）名字表PROCEDURE 过程名（形参表）；过程局部变量说明；BEGIN语句序列；END;.,7.管程的的组成名称：为每个共享资源设立一个管程数据结构说明：一组局部于管程的控制变量操作原语：对控制变量和临界资源进行操作的一组原语过程（程序代码），是访问该管程的

46、唯一途径。这些原语本身是互斥的，任一时刻只允许一个进程去调用，其余需要访问的进程就等待。初始化代码：对控制变量进行初始化的代码,生产者消费者的管程实现,Monitor ProducerConsumer condition full,empty;integer count;procedure enter;begin if count=N then wait(full);enter_item;count:=count+1;if count=1 then signal(empty)end,procedure remove;begin if count=0 then wait(empty);remov

47、e_item;count:=count-1;if count=N-1 then signal(full)end count:=0;End monitor;,Procedure producer;begin while true do begin produce_item;ProducerConsumer.enter end end;,Procedure consumer;begin while true do begin ProducerConsumer.remove;consume_item;end end;,管程与信号量的比较 由于管程的机制，在某个时刻，只能有一个管程过程是活跃的，就类似

48、于原语操作一样，也能够很好地解决Spooler目录的问题，而且更为简洁，在使用的过程中，能够直接分析代码，更容易理解使用。而且它的互斥操作是由编译器所支持的，更为安全，不宜出错。用信号量可实现进程间的同步，但由于信号量的控制分布在整个程序中，其正确性分析很困难。管程是管理进程间同步的机制，它保证进程互斥地访问共享变量，并方便地阻塞和唤醒进程。管程可以函数库的形式实现。相比之下，管程比信号量好控制。,弊端，支持管程的编程语言太少，因为它要求编译器的支持，而信号量对于一个操作系统来说是很容易添加的；他们都是用来解决访问同一个公共存储器的一个或多个CPU的互斥问题。通过将信号量放入共享内存中并用TS

49、L指令来保护他们，可以避免竞争。但对于一个具有多个CPU，且每个CPU有自己的内存，有一个局域网相连的分布式系统来说，这些原语将完全失败。而管程由于编程语言的限制很难被实际应用。所以这两种都不是很实际的解决方法。需要新的解决方法。,2.2.7 消息传递,1.消息的原语形式Send(destination,&message)Receive(source,&message),都属于系统调用,2.消息传递中的要点-针对与通信进程位于网络中不同机器上的情况1）由于进程发送了消息以后，接受者才能接收，故*对于一个执行send的进程*对于一个执行receive的进程,发送被阻塞，等回复发送没有阻塞，做别的

50、,接受消息，继续执行等待消息a)等，直到接收到 b)放弃接收,2）消息接收的处理发送者发送消息，接收者收到后发送一个应答，这时：*应答信息被发送者收到，则继续发送新的消息；*应答信息丢失，则重发刚才的信息，此时，接收者需要区分消息的新旧，利用给消息加上连续序号来解决；3）消息系统设计的其他注意事项*系统需要解决进程命名的问题，保证消息的正确发送和接收；*效率的提升：严格控制系统中所用信息的长度，保证能够送入寄存器。,3.阻塞的处理及实用性阻塞可以对于send方发生，也可以对receive 方发生，一般有三种组合：1）阻塞send，阻塞receive：发送和接收者都被阻塞，一直到完成信息的交付，