《计算机操作系统-ch2b全解优秀PPT.ppt》由会员分享，可在线阅读，更多相关《计算机操作系统-ch2b全解优秀PPT.ppt（62页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、1Chapter 2Processes and Threads2.1 Processes2.2 Threads2.3 Inter-process communication2.4 Classical IPC problems2.5 Scheduling2Inter-process CommunicationvThree issues are involved in inter-process communication(IPC)1.How one process can pass information to another.2.Resource shared(e.g.printer)How
2、to make sure two or more processes do not get into each others way when engaging in critical activities.3.Process cooperationProper sequencing when dependencies are present.3Process Synchronizationv进程同步：对多个相关进程在执行次序上的协调，用于保证这种关系的相应机制称为进程同步。（或相互合作的一组并发进程在一些关键点上可能须要相互等待与互通消息，这种相互制约的等待与互通消息称为进程同步。）v例：医
3、生为病员诊病，认为须要化验，开出化验单。病员取样送到化验室，等化验完毕交给医生化验结果，接着诊病。医生诊病是一个进程，化验室的化验工作是另一个进程，它们各自独立的活动，但又共同完成医疗任务。化验进程只有在接收到诊病进程的化验单后才起先工作；而诊病进程只有获得化验结果后才能接着为该病员诊病，并依据化验结果确定医疗方案。v例：计算进程与打印进程共享一个单缓冲区的问题。4Spooling Example:CorrectSpooler DirectoryabcProg.cProg.n4567F2outinProcess 1Process 2next_free=in;next_free=inint ne
4、xt_free;Stores F1 into next_free;Stores F2 into next_free;int next_free;124in=next_free+1F1in=next_free+1356895Spooling Example:RacesShared memoryabcProg.cProg.n4567outinProcess 1Process 2next_free=in;/*value:7*/next_free=in/*value:7*/int next_free;Stores F1 into next_free;Stores F2 into next_free;i
5、nt next_free;152in=next_free+1F1in=next_free+1634F26Mutual exclusionSome way of making sure that if one process is using a shared variable or file,the other processes will be excluded from doing the same thing.Race conditionsRace conditions are situations in which several processes access shared dat
6、a and the final result depends on the order of operations.The key to avoid race conditions is to prohibit more than one process from reading and writing the shared data at the same time.7vCritical Resource(临界资源)一次仅允许一个进程访问的资源称为临界资源临界资源包括：硬件资源：输入机、打印机等软件资源：变量、表格、队列、文件等vCritical Region(Critical Sectio
7、n)The part of the program where the critical resource is accessed is called critical region or critical section.If we could arrange matters such that no two processes were ever in their critical regions at the same time,we could avoid races.89a:=a-1 print(a)a:=a+1 print(a)P1P2If a 0then a:=a+1else a
8、:=a-1P3Mutual exclusion10Critical Region RequirementvFour conditions to provide mutual exclusion1.No two processes simultaneously in critical region2.No assumptions made about speeds or numbers of CPUs3.No process running outside its critical region may block another process4.No process must wait fo
9、rever to enter its critical region11Mutual exclusion using critical regions12Mutual ExclusionvPossible Solutions Disabling Interrupts Lock Variables Strict Alternation Petersons solution TSL Sleep and Wakeup13Solution 1-Disabling InterruptsHow does it work?Disable all interrupts just after entering
10、a critical section and re-enable them just before leaving it.Why does it work?With interrupts disabled,no clock interrupts can occur.(The CPU is only switched from one process to another as a result of clock or other interrupts,and with interrupts disabled,no switching can occur.)Problems:What if th
11、e process forgets to enable the interrupts?Multiprocessor?(disabling interrupts only affects one CPU)Only used inside OS14Solution 2-Lock Variable shared int lock=0;/*entry_code:execute before entering critical section*/while(lock!=0)/*do nothing*/;lock=1;-critical section-/*exit_code:execute after
12、leaving critical section*/lock=0;This solution may violate property 1.If a context switch occurs after one process executes the while statement,but before setting lock=1,then two(or more)processes may be able to enter their critical sections at the same time.15Solution 3-Strict AlternationThis solut
13、ion may violate property 3.Since the processes must strictly alternate entering their critical sections,a process wanting to enter its critical section twice in a row will be blocked until the other process decides to enter(and leave)its critical section.16Solution 4-Petersonsenter_region (i);Critic
14、al regionleave_region (i);Noncritical regionprocess i17Solution 4-PetersonsPetersons solution for achieving mutual exclusion18Hardware solution 5:Test-and-Set Locks(TSL)The hardware must support a special instruction,tsl,which does 2 things in a single atomic action:tsl register,flag(a)copy a value
15、in memory(flag)to a CPU register(b)set flag to 1.19Test-and-Set Locks(TSL)Entering and leaving a critical region using the TSL instruction返回20Test-and-Set Locks(TSL)Entering and leaving a critical region using the XCHG instruction.21Mutual Exclusion with Busy WaitingvThe last two solutions,4 and 5,r
16、equire BUSY-WAITING;that is,a process executing the entry code will sit in a tight loop using up CPU cycles,testing some condition over and over,until it becomes true.vBusy-waiting may lead to the PRIORITY-INVERSION PROBLEM if simple priority scheduling is used to schedule the processes.22Mutual Exc
17、lusion with Busy WaitingvExample:Test-and-set Locks:P0(low)-in cs-x|context switch|P1(high)-tsl-cmp-jnz-tsl.x-tsl-cmp.x-.forever.vNote,since priority scheduling is used,P1 will keep getting scheduled and waste time doing busy-waiting.:-(vThus,we have a situation in which a low-priority process is bl
18、ocking a high-priority process,and this is called PRIORITY-INVERSION.23Sleep and WakeupvSolution of previous problems:sleep and wakeup(busy waiting)Block instead of busy waiting when it is not allowed to enter the Critical Region(sleep)Wakeup when it is OK to retry entering the critical region24Prod
19、ucer-Consumer Problem(Bounded-buffer problem)vConsider two processes share a circular buffer that can hold N items.vProducers add items to the buffer and Consumers remove items from the buffer.vThe Producer-Consumer Problem is to restrict access to the buffer so correct executions result.25Sleep and
20、 WakeupProducer-consumer problem with fatal race conditionSwitch to producer26Semaphores(E.W.Dijkstra,1965)vA SEMAPHORE,S,is a structure consisting of two parts:(a)an integer counter,COUNT (b)a queue of pids of blocked processes,QvThat is,struct sem_struct int count;queue Q;semaphore;semaphore S;27S
21、emaphores vA semaphore count represents count number of abstract resourcesCounting semaphores:0.NBinary semaphores:0,1vThere are 2 operations on semaphoresThe Down(P)operation is used to acquire a resource and decrements count.The Up(V)operation is used to release a resource and increments count.vAn
22、y semaphore operation is indivisible,must be executed atomically.(what is primitive?)28SemaphoresvSuppose that P is the process making the down and up system calls.The operations are defined as follows:P操作操作 DOWN(S):S.count=S.count-1;/apply for a resource if(S.count 0)/if no resourceblock(P);(a)enqu
23、eue the pid of P in S.Q,(b)block process P(remove the pid from the ready queue),and(c)pass control to the scheduler.执行一次P操作后，若S.count0，则|S.count|等于Q队列中等待S资源的进程数。29SemaphoresV操作操作 UP(S):S.count=S.count+1;/release a resource if(S.count0表示有S.count个资源可用 S.count=0表示无资源可用 S.count0则|S.count|表示S等待队列中的进程个数 P
24、(S)：表示申请一个资源 V(S)：表示释放一个资源。信号量的初值应当大于等于02)P,V操作必需成对出现，有一个P操作就确定有一个V操作当为互斥操作时，它们同处于同一进程；当为同步操作时，则不在同一进程中出现。假如P(S1)和P(S2)两个操作在一起，那么P操作的依次至关重要，一个同步P操作与一个互斥P操作在一起时同步P操作在互斥P操作前；而两个V操作的依次无关紧要。探讨：探讨：453)信号量同步的缺点用信号量可实现进程间的同步，但由于信号量的限制分布在整个程序中，其正确性分析很困难。4)引入管程1973年，Hoare和Hanson提出一种高级同步原语管程；其基本思想是把信号量及其操作原语封
25、装在一个对象内部。管程是管理进程间同步的机制，它保证进程互斥地访问共享变量，并便利地堵塞和唤醒进程。管程可以函数库的形式实现。相比之下，管程比信号量好限制。46MonitorsvA monitor is a collection of procedures,variables,and data structures that can only be accessed by one process at a time(for the purpose of mutual exclusion).vTo allow a process to wait within the monitor,a cond
26、ition variable must be declared,as condition x,y;vCondition variable can only be used with the operations wait and signal(for the purpose of synchronization).The operationwait(x);means that the process invoking this operation is suspended until another process invokessignal(x);The signal(x)operation
27、 resumes exactly one suspended process.If no process is suspended,then the signal operation has no effect.47MonitorsExample of a monitor48MonitorsOutline of producer-consumer problem with monitorsonly one monitor procedure active at one timebuffer has N slots49Message passingPossible Approaches of I
28、PC:1)Shared memory2)Shared file mode;pipe:is a shared filevOne end is for reading and one end is for writing.3)Message passing:primitive:send and receivevAssign each process a unique address such as addr.Then,send messages directly to the process:send(addr,msg);recv(addr,msg);vUse mailboxes:send(mai
29、lbox,msg);recv(mailbox,msg);50Message PassingThe producer-consumer problem with N messages51BarriersvUse of a barriera)processes approaching a barrierb)all processes but one blocked at barrierc)last process arrives,all are let throughvExample:Parallel matrix multiplication52Classical IPC ProblemsvTh
30、ese problems are used for testing every newly proposed synchronization scheme:Bounded-Buffer(Producer-Consumer)ProblemDining-Philosophers ProblemReaders and Writers Problem53Dining PhilosophersvDining Philosophers Problem Dijkstra,1965:Problem:Five philosophers are seated around a table.There is one
31、 fork between each pair of philosophers.Each philosopher needs to grab the two adjacent forks in order to eat.Philosophers alternate between eating and thinking.They only eat for finite periods of time.54vPhilosophers eat/thinkvEating needs 2 forksvPick one fork at a time vHow to prevent deadlock Di
32、ning Philosophers55Dining PhilosophersA nonsolution to the dining philosophers problem56Dining PhilosophersvProblem:Suppose all philosophers execute the first DOWN operation,before any have a chance to execute the second DOWN operation;that is,they all grab one fork.Then,deadlock will occur and no p
33、hilosophers will be able to proceed.This is called a CIRCULAR WAIT.vOther Solutions:Only allow up to four philosophers to try grabbing their forks.Asymmetric solution:Odd numbered philosophers grab their left fork first,whereas even numbered philosophers grab their right fork first.Protect the five
34、statements following think()by mutexPick-up the forks only if both are available.See Fig.2-46.57Dining PhilosophersSolution to dining philosophers problem(part 1)58Dining PhilosophersSolution to dining philosophers problem(part 2)59Readers and Writers ProblemvThe readers and writers problem models a
35、ccess to a shared database.vRules:Multiple readers can read the data simultaneously Only one writer can write the data at any time A reader and a writer cannot in critical section together.Reader WriterReader OKNoWriterNoNo60Readers and Writers ProblemvOne solution(reader preference):Suppose new rea
36、der come:if writer is waiting and some reader is reading,then read ok.Suppose new writer come:if no reader or writer,it can write,else wait.vOne variation of the problem,called weak readers preference,is to suspend the incoming readers as long as a writer is waiting.61Readers and Writers ProblemA so
37、lution to the readers and writers problementryexit62SummaryvRace condition,Critical region and mutual exclusionvMutual exclusion using busy waitingPetersons SolutionTSLvSleep and WakeupvSemaphoresvMonitorvBarriervPassing Message vClassic synchronization problemsDining-Philosophers ProblemReaders and Writers Problem