操作系統(tǒng)英文課件：ch2b Process and Thread

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)H

2、ow 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進(jìn)程同步：對(duì)多個(gè)相關(guān)進(jìn)程在執(zhí)行次序上的協(xié)調(diào)，用于保證這種關(guān)系的相應(yīng)機(jī)制稱為進(jìn)程同步。（或相互合作的一組并發(fā)進(jìn)程在一些關(guān)鍵點(diǎn)上可能需要互相等待與互通消息，這種相互制約的等待與互通消息稱為進(jìn)程同步。）

3、v例：醫(yī)生為病員診病，認(rèn)為需要化驗(yàn)，開(kāi)出化驗(yàn)單。病員取樣送到化驗(yàn)室，等化驗(yàn)完畢交給醫(yī)生化驗(yàn)結(jié)果，繼續(xù)診病。醫(yī)生診病是一個(gè)進(jìn)程，化驗(yàn)室的化驗(yàn)工作是另一個(gè)進(jìn)程，它們各自獨(dú)立的活動(dòng)，但又共同完成醫(yī)療任務(wù)。化驗(yàn)進(jìn)程只有在接收到診病進(jìn)程的化驗(yàn)單后才開(kāi)始工作；而診病進(jìn)程只有獲得化驗(yàn)結(jié)果后才能繼續(xù)為該病員診病，并根據(jù)化驗(yàn)結(jié)果確定醫(yī)療方案。v例：計(jì)算進(jìn)程與打印進(jìn)程共享一個(gè)單緩沖區(qū)的問(wèn)題。4Spooling Example: CorrectSpooler DirectoryabcProg.cProg.n4567F2outinProcess 1Process 2next_free = in;next_free =

4、 inint next_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

5、 F2 into next_free;int 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 proces

6、ses access shared data 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(臨界資源)一次僅允許一個(gè)進(jìn)程訪問(wèn)的資源稱為臨界資源臨界資源包括：硬件資源：輸入機(jī)、打印機(jī)等軟件資源：變量、表格、隊(duì)列、文件等vCritical R

7、egion (Critical Section)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.8程 序 段1程 序 段2程 序 段n共 享 變 量9a := a -1

8、 print (a)a := a +1 print (a)P1P2If a 0then a := a +1else a:= a-1P3Mutual exclusionentry sectionexit section critical section remainder section10Critical Region RequirementvFour conditions to provide mutual exclusion1.No two processes simultaneously in critical region2.No assumptions made about spee

9、ds or numbers of CPUs3.No process running outside its critical region may block another process4.No process must wait forever to enter its critical region11Mutual exclusion using critical regions12Mutual ExclusionvPossible Solutions Disabling Interrupts Lock Variables Strict Alternation Petersons so

10、lution TSL Sleep and Wakeup13Solution 1 - Disabling Interrupts How does it work? Disable all interrupts just after entering 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 proc

11、ess to another as a result of clock or other interrupts, and with interrupts disabled, no switching can occur.) Problems: What if the process forgets to enable the interrupts? Multiprocessor? (disabling interrupts only affects one CPU) Only used inside OS14Solution 2 - Lock Variable shared int lock

12、= 0;/* entry_code: execute before entering critical section */while (lock != 0) /* do nothing */ ;lock = 1; - critical section -/* exit_code: execute after leaving critical section */lock = 0;This solution may violate property 1. If a context switch occurs after one process executes the while statem

13、ent, 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 solution may violate property 3. Since the processes must strictly alternate entering their critical sections, a process wanting to enter

14、 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 );Critical regionleave_region ( i );Noncritical regionprocess i17Solution 4 - PetersonsPetersons solution for achieving mutual exclu

15、sion18Hardware 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 in memory (flag) to a CPU register (b) set flag to 1.19Test-and-Set Locks (TSL)Entering and leaving a critical re

16、gion 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, require BUSY-WAITING; that is, a process executing the entry code will sit in a tight loop using up CPU cy

17、cles, 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 Exclusion with Busy WaitingvExample: Test-and-set Locks: P0 (low) - in cs -x | context switch | P1 (hig

18、h) -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 blocking a high-priority process, and this is called PRIORITY-INVERSION.23Sleep an

19、d 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 region24Producer-Consumer Problem (Bounded-buffer problem )vConsider two processes share

20、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 WakeupProducer-consumer problem with fatal race conditionSwitch to produc

21、er26Semaphores (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;27Semaphores vA semaphore count represents count number of abstra

22、ct 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. vAny semaphore operation is indivisible, must be executed

23、 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) enqueue the pid of P in S.Q,(b) block proces

24、s P (remove the pid from the ready queue), and(c) pass control to the scheduler. 執(zhí)行一次P操作后，若S.count0，則|S.count|等于Q隊(duì)列中等待S資源的進(jìn)程數(shù)。29SemaphoresV操作操作 UP(S): S.count = S.count + 1; /release a resource if ( S.count0表示有S.count個(gè)資源可用 S.count=0表示無(wú)資源可用 S.count0則|S.count|表示S等待隊(duì)列中的進(jìn)程個(gè)數(shù) P(S)：表示申請(qǐng)一個(gè)資源 V(S)：表示釋放一個(gè)資源。

25、信號(hào)量的初值應(yīng)該大于等于02) P,V操作必須成對(duì)出現(xiàn)，有一個(gè)P操作就一定有一個(gè)V操作當(dāng)為互斥操作時(shí)，它們同處于同一進(jìn)程；當(dāng)為同步操作時(shí)，則不在同一進(jìn)程中出現(xiàn)。如果P(S1)和P(S2)兩個(gè)操作在一起，那么P操作的順序至關(guān)重要，一個(gè)同步P操作與一個(gè)互斥P操作在一起時(shí)同步P操作在互斥P操作前；而兩個(gè)V操作的順序無(wú)關(guān)緊要。討論：討論：453) 信號(hào)量同步的缺點(diǎn)用信號(hào)量可實(shí)現(xiàn)進(jìn)程間的同步，但由于信號(hào)量的控制分布在整個(gè)程序中，其正確性分析很困難。4) 引入管程 1973年，Hoare和Hanson提出一種高級(jí)同步原語(yǔ)管程； 其基本思想是把信號(hào)量及其操作原語(yǔ)封裝在一個(gè)對(duì)象內(nèi)部。 管程是管理進(jìn)程間同步的機(jī)

26、制，它保證進(jìn)程互斥地訪問(wèn)共享變量，并方便地阻塞和喚醒進(jìn)程。 管程可以函數(shù)庫(kù)的形式實(shí)現(xiàn)。相比之下，管程比信號(hào)量好控制。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 condition variable

27、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 resumes ex

28、actly 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 IPC:1) Sha

29、red 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

30、(mailbox, 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 Pr

31、oblemsvThese 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 tabl

32、e. There is one 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 p

33、revent deadlock Dining 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, dead

34、lock will occur and no philosophers 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 statements following think() by mutexPick-up the forks only if both are available. See F