操作系統(tǒng)課件：Chapter-02 Processes and Threads

1、1Processes and ThreadsChapter 22.1 Processes2.2 Threads2.3 Interprocess communication2.4 Classical IPC problems2.5 Scheduling2ProcessesThe Process Model Multiprogramming of four programs Conceptual model of 4 independent, sequential processes Only one program active at any instant為了描述程序在并發(fā)執(zhí)行時對系統(tǒng)資源的共

2、享，需要一個描述程序執(zhí)行時動態(tài)特征的概念，這就是進程。3多道程序設計與進程管理 計算機中程序運行模式的發(fā)展歷程 順序執(zhí)行模式：單道程序獨占CPU和其他資源 并發(fā)執(zhí)行模式：兩個/多個程序共享CPU和其他資源 多道程序設計：并發(fā)模式下的OS設計與實現(xiàn) 程序運行模式的特征 順序執(zhí)行模式 順序性、封閉性、獨占性、確定性（結果可再現(xiàn)性） 并發(fā)執(zhí)行模式 并發(fā)性、間斷性、共享性、不確定性、獨立性和制約性 問題1：并發(fā)與并行的區(qū)別是什么？ 問題2：如何計算并發(fā)環(huán)境下的計算機工作效率？4并行與并發(fā)的概念差別 并行（Parallel） 同一時刻，兩個事物均處于活動狀態(tài) 示例：CPU中的超流水線設計和超標量設計 并

3、發(fā)（Concurrency） 宏觀上存在并行特征，微觀上存在順序性 同一時刻，只有一個事物處于活動狀態(tài) 示例：分時操作系統(tǒng)中多個程序的同時運行5并發(fā)所帶來的效率提升6并發(fā)所帶來的效率提升 順序執(zhí)行模式下的系統(tǒng)工作效率 系統(tǒng)總運行時間：80 CPU使用效率：CPU占用時間 / 總時間 40/80 = 50% DEV1使用效率：15 / 80 18.75% DEV2使用效率：25 / 80 = 31.25% 并發(fā)執(zhí)行模式下的系統(tǒng)工作效率 系統(tǒng)總運行時間：45 CPU使用效率：40 / 45 = 89% DEV1使用效率：15 / 45 = 33% DEV2使用效率：25 / 45 55.6%7并發(fā)

4、所帶來的設計難題 共享性帶來的問題：如何調度或分配資源？ 最大限度的保證系統(tǒng)運行效率：誰首先獲得資源？ 最大限度的保證系統(tǒng)運行安全：死鎖情況的預防 間斷性和不確定性帶來的問題：如何保證互斥？ 互斥問題示例：見下頁圖 經典IPC問題：進程管理的重點 間斷性和獨立性帶來的問題：如何調度和保護？ 每個程序運行時都感覺不到間斷：上下文切換 復雜應用帶來的問題：如何進行通信？ 多個程序間可動態(tài)交換信息：進程通信機制8互斥問題 Get、Copy、Put為三個并發(fā)的程序 F、G為保存多條數(shù)據(jù)的緩沖區(qū)，S、T為臨時緩沖區(qū) 三個程序順序執(zhí)行，可將F的值經過S、T保存到G中 正常情況下，不存在任何問題 但是程序運

5、行順序發(fā)生變化時，結果可能出錯9互斥問題con.初始狀態(tài)FSTG分析程序運行順序3，4，5221，2G、C、P4，5331，2，3正確G、P、C4，5331，2，2錯誤C、P、G4，5321，2，2錯誤C、G、P4，5321，2，2錯誤P、C、GP、G、C10進程概念 進程的核心思想 進程是某個程序在某個數(shù)據(jù)集合上的運行過程，它進程是某個程序在某個數(shù)據(jù)集合上的運行過程，它有程序、輸入、輸出和狀態(tài)。有程序、輸入、輸出和狀態(tài)。 在分時操作系統(tǒng)中，單個在分時操作系統(tǒng)中，單個CPU被若干進程共享，它被若干進程共享，它使用某種調度算法決定何時停止一個進程的運行，使用某種調度算法決定何時停止一個進程的運行

6、，轉而為其他進程提供服務。轉而為其他進程提供服務。進程概念進程概念11進程的特征 動態(tài)性：進程具有動態(tài)的地址空間（數(shù)量和內容），地址空間上包括： 代碼（指令執(zhí)行和CPU狀態(tài)的改變） 數(shù)據(jù)（變量的生成和賦值） 系統(tǒng)控制信息（進程控制塊的生成和刪除） 獨立性：各進程的地址空間相互獨立，除非采用進程間通信手段； 并發(fā)性、異步性：虛擬 結構化：代碼段、數(shù)據(jù)段和核心段（在地址空間中）；程序文件中通常也劃分了代碼段和數(shù)據(jù)段，而核心段通常就是OS核心（由各個進程共享，包括各進程的PCB）進程概念進程概念12進程與程序的區(qū)別 進程是動態(tài)的，程序是靜態(tài)的：程序是有序代碼的集合；進程是程序的執(zhí)行。通常進程不可在計

7、算機之間遷移；而程序通常對應著文件、靜態(tài)和可以復制。 進程是暫時的，程序的永久的：進程是一個狀態(tài)變化的過程，程序可長久保存。 進程與程序的組成不同：進程的組成包括程序、數(shù)據(jù)和進程控制塊（即進程狀態(tài)信息）。 進程與程序的對應關系：通過多次執(zhí)行，一個程序可對應多個進程；通過調用關系，一個進程可包括多個程序。進程概念進程概念13進程控制塊(PCB, process control block)進程概念進程概念進程控制塊是由OS維護的用來記錄進程相關信息的一塊內存。 每個進程在OS中的登記表項（可能有總數(shù)目限制），OS據(jù)此對進程進行控制和管理（PCB中的內容會動態(tài)改變），不同OS則不同 處于核心段，通

8、常不能由應用程序自身的代碼來直接訪問，而要通過系統(tǒng)調用，或通過UNIX中的進程文件系統(tǒng)(/proc)直接訪問進程映象(image)。文件名為進程標識（如：00316），權限為創(chuàng)建者可讀寫。14進程控制塊的內容進程概念進程概念 進程描述信息： 進程標識符(process ID)，唯一，通常是一個整數(shù)； 進程名，通常基于可執(zhí)行文件名（不唯一）； 用戶標識符(user ID)；進程組關系(process group) 進程控制信息： 當前狀態(tài)； 優(yōu)先級(priority)； 代碼執(zhí)行入口地址； 程序的外存地址； 運行統(tǒng)計信息（執(zhí)行時間、頁面調度）； 進程間同步和通信；阻塞原因 資源占用信息：虛擬地址

9、空間的現(xiàn)狀、打開文件列表 CPU現(xiàn)場保護結構：寄存器值（通用、程序計數(shù)器PC、狀態(tài)PSW，地址包括棧指針）15PCB的組織方式進程概念進程概念 鏈表：同一狀態(tài)的進程其PCB成一鏈表，多個狀態(tài)對應多個不同的鏈表 各狀態(tài)的進程形成不同的鏈表：就緒鏈表、阻塞鏈表 索引表：同一狀態(tài)的進程歸入一個index表（由index指向PCB），多個狀態(tài)對應多個不同的index表 各狀態(tài)的進行形成不同的索引表：就緒索引表、阻塞索引表PCB TableReadyBlockedPCB TableIndex TableReadyBlocked16進程上下文進程上下文是對進程執(zhí)行活動全過程的靜態(tài)描述。進程上下文由進程的用

10、戶地址空間內容、硬件寄存器內容及與該進程相關的核心數(shù)據(jù)結構組成。 用戶級上下文：進程的用戶地址空間（包括用戶棧各層次），包括用戶正文段、用戶數(shù)據(jù)段和用戶棧； 寄存器級上下文：程序寄存器、處理機狀態(tài)寄存器、棧指針、通用寄存器的值； 系統(tǒng)級上下文： 靜態(tài)部分（PCB和資源表格） 動態(tài)部分：核心棧（核心過程的棧結構，不同進程在調用相同核心過程時有不同核心棧） 17Process CreationPrincipal events that cause process creation1. System initialization2. Execution of a process creation s

11、ystem call by a running process3. User request to create a new process4. Initiation of a batch job18Process Creation System Call Unix: fork() -only one system call two process (the parent and the child) have: the same memory image, the same environment strings, and the same open files. use execve()

12、to change its memory image. Windows: CreateProcess() handles both process creation and loading the program into the new process.19Process TerminationConditions which terminate processes1. Normal exit (voluntary) ( Unix: exit(), Windows: ExitProcess() )2. Error exit (voluntary)3. Fatal error (involun

13、tary)4. Killed by another process (involuntary) ( Unix: kill(), Windows: TerminateProcess() )20Process Hierarchies Parent creates a child process, child processes can create its own process Forms a hierarchy UNIX calls this a process group Windows has no concept of process hierarchy all processes ar

14、e created equal21Process States (1) Possible process states running:運行態(tài)，正在占用CPU運行程序 blocked:阻塞態(tài)，等待外部事件發(fā)生，無法占用CPU ready:就緒態(tài)，可運行，但其他進程正在占用CPU，所有被暫時掛起 Transitions between states shown22Problem 問題1：為什么不能從阻塞態(tài)變?yōu)檫\行態(tài)呢？ 問題2：為什么不能從就緒態(tài)變?yōu)樽枞麘B(tài)呢？ 提示： 三種狀態(tài)的變換體現(xiàn)了OS的資源管理作用 進程的核心思想在于運行CPU資源的分配23進程的復雜狀態(tài) 其他復雜的進程狀態(tài) 創(chuàng)建、中止

15、、掛起三種狀態(tài) 五種狀態(tài)模型增加了“創(chuàng)建”、“退出”兩種狀態(tài) 七種狀態(tài)模型針對進程的存在位置（內存或者外存），進一步增加“阻塞掛起”和“就緒掛起”兩種狀態(tài) 進程狀態(tài)模型的重要性 OS管理CPU資源的核心運行機制 直接關系到進程數(shù)據(jù)結構與相關算法的設計24進程的復雜狀態(tài)con.25進程的復雜狀態(tài)con.活動活動掛起掛起事件事件發(fā)生發(fā)生事件事件發(fā)生發(fā)生等待等待事件事件掛起掛起調度調度超時超時釋放釋放活動活動掛起掛起26Process States (2) Lowest layer of process-structured OS handles interrupts, scheduling Abo

16、ve that layer are sequential processes27進程管理 單個進程的管理 進程的創(chuàng)建、刪除：靜態(tài)與動態(tài)概念的差別。 多個進程的管理 樹狀進程集合：父進程和子進程 進程的調度：保持CPU效率的關鍵 進程之間的通信 最簡單：兩個進程之間如何傳遞信息？ 中級：如何保持進程之間的互斥？ 高級：如何維系進程之間的依賴關系？28Implementation of Processes (1)Fields of a process table entry29Implementation of Processes (2)Skeleton of what lowest level

17、of OS does when an interrupt occurs30進程小結 概念 CPU資源的管理載體OS通過進程實現(xiàn)對CPU的管理 核心思想動態(tài)概念進程與程序的區(qū)別 進程實現(xiàn)生存周期狀態(tài)的變遷 進程管理 單個進程進程調度進程通信 進程序列進程樹線程 數(shù)據(jù)傳遞共享與互斥依賴關系維護 術語 Cocurrency & Parallel & MultiProgramming Program & Process & Thread Program & Process: 靜態(tài)和動態(tài)的思想 MultiProgramming: 并發(fā)與互斥的思想31線程 進程：資

18、源分配單位（存儲器、文件）和CPU調度（分派）單位。又稱為任務(task) 線程：作為CPU調度單位，而進程只作為其他資源分配單位。 只擁有必不可少的資源，如：線程狀態(tài)、寄存器上下文和棧 同樣具有就緒、阻塞和執(zhí)行三種基本狀態(tài)32線程 引入線程的目的是簡化線程間的通信，以小的開銷來提高進程內的并發(fā)程度。 線程的優(yōu)點：減小并發(fā)執(zhí)行的時間和空間開銷（線程的創(chuàng)建、退出和調度），因此容許在系統(tǒng)中建立更多的線程來提高并發(fā)程度。 線程的創(chuàng)建時間比進程短； 線程的終止時間比進程短； 同進程內的線程切換時間比進程短； 由于同進程內線程間共享內存和文件資源，可直接進行不通過內核的通信33ThreadsThe Th

19、read Model (1)(a) Three processes each with one thread(b) One process with three threads34The Thread Model (2) Items shared by all threads in a process Items private to each thread35The Thread Model (3)Each thread has its own stack Every thread can access every memory address within the process addr

20、ess space. There is no protection between threads because 1) it is impossible, and 2) it should not be necessary.36Thread Call create new threads: thread_create() exit thread: thread_exit() one thread wait for a specific thread to exit: thread_wait() allow a thread to voluntarily give up the CPU to

21、let another thread run: thread_yield()37進程和線程的比較 地址空間和其他資源（如打開文件）：進程間相互獨立，同一進程的各線程間共享某進程內的線程在其他進程不可見 通信：進程間通信IPC，線程間可以直接讀寫進程數(shù)據(jù)段（如全局變量）來進行通信需要進程同步和互斥手段的輔助，以保證數(shù)據(jù)的一致性 調度：線程上下文切換比進程上下文切換要快得多；38ThreadControlBlockUserStackUserStackKernelStackKernelStackUserAddressSpaceUserAddressSpaceProcessControlBlockPr

22、ocessControlBlockThreadSingle-ThreadedProcess ModelMultithreadedProcess ModelThreadControlBlockUserStackKernelStackThreadThreadControlBlockUserStackKernelStackThread線程切換和進程切換39Reason for thread In many applications, multiple activities are going on at once. By decomposing it into multiple sequential

23、 threads, the programming model becomes simpler. Threads do not have any resources attached to them, they are easier to create and destroy than processes. When there is substantial computing and also substantial I/O, having threads allows these activities to overlap, thus speeding up the application

24、. Threads are useful on systems with multiple CPUs, where real parallelism is possible.40Thread Usage (1)A word processor with three threads threads: one interacts with user, another handles reformatting in the background, a third thread automatically save the entire file to disk during a specific t

25、ime (handle the disk backups without interfering with the other two).41Thread Usage (2)A multithreaded Web server42Thread Usage (3) Rough outline of code for previous slide(a) Dispatcher thread(b) Worker thread43Thread Usage (4)Three ways to construct a server44用戶線程(user-level thread)不依賴于OS核心，應用進程利用

26、線程庫提供創(chuàng)建、同步、調度和管理線程的函數(shù)來控制用戶線程。如：數(shù)據(jù)庫系統(tǒng)informix，圖形處理Aldus PageMaker。調度由應用軟件內部進行，通常采用非搶先式和更簡單的規(guī)則，也無需用戶態(tài)/核心態(tài)切換，所以速度特別快。一個線程發(fā)起系統(tǒng)調用而阻塞，則整個進程在等待。時間片分配給進程，多線程則每個線程就慢。 用戶線程的維護由應用進程完成； 內核不了解用戶線程的存在； 用戶線程切換不需要內核特權； 用戶線程調度算法可針對應用優(yōu)化；45Implementing Threads in User SpaceA user-level threads package46Implementing Th

27、reads in User Space: Advantage A user-level threads package can be implemented on an operating system that does not support threads. Doing thread switching is faster than trapping to the kernel, no trap is needed, no context switch is needed, the memory cache need not be flushed, and so on. This mak

28、es thread scheduling very fast. Allow each process to have its own customized scheduling algorithm. Scale better, since kernel threads invariably require some table space and stack space in the kernel, which can be a problem if there are a very large number of threads.47Implementing Threads in User

29、Space: Problems the problem of how blocking system calls are implemented: 1) one blocking call may stop all the threads, 2) nonblocking system call changing require changes to the OS, 3) to tell in advance if a call will block: do the call if it is safe, if the call will block, the call is not made.

30、 Instead, another thread is run. the problem of page faults: block even though other runnable threads. Within a single process, there are no clock interrupts, Unless a thread enters the run-time system of its own free will, the scheduler will never get a chance. Programmers generally want threads in

31、 applications where the threads block often. Block vs computing. 48內核線程(kernel-level thread)依賴于OS核心，由內核的內部需求進行創(chuàng)建和撤銷，用來執(zhí)行一個指定的函數(shù)。Windows NT和OS/2支持內核線程； 內核維護進程和線程的上下文信息； 線程切換由內核完成； 一個線程發(fā)起系統(tǒng)調用而阻塞，不會影響其他線程的運行。 時間片分配給線程，所以多線程的進程獲得更多CPU時間。49Implementing Threads in the KernelA threads package managed by th

32、e kernel50Implementing Threads in the KernelAdvantage No run-time system is needed Kernel threads do not require any new, nonblocking system calls. The kernel can easily check which thread (in the same process) when page fault.Disadvantage The cost of a system call is substantial, so if thread opera

33、tions (creation, termination, etc.) are common, much more overhead will be incurred.51Hybrid Implementations Multiplexing user-level threads onto kernel- level threads52Scheduler Activations Goal mimic functionality of kernel threads gain performance of user space threads Avoids unnecessary user/ker

34、nel transitions eg. block by synchronizing thread in user space Kernel assigns virtual processors to each process lets runtime system allocate threads to processors Problem: Fundamental reliance on kernel (lower layer) calling procedures in user space (higher layer)53Pop-Up Threads Creation of a new

35、 thread when message arrives(a) before message arrives(b) after message arrives54Making Single-Threaded Code Multithreaded (1)Conflicts between threads over the use of a global variable55Making Single-Threaded Code Multithreaded (2)Threads can have private global variables56SUN Solaris 線程舉例 Solaris支

36、持內核線程(Kernel threads)、輕權進程(Lightweight Processes)和用戶線程(User Level Threads)。一個進程可有大量用戶線程；大量用戶線程復用少量的輕權進程，不同的輕權進程分別對應不同的內核線程。Timesliceor PreemptWakeupStopBlockingSystemCallWakeupDispatchRunnableRunningActiveStoppedContinueStopStopStopSleepDispatchStopWakeupContinuePreemptStoppedRunnableActiveSleeping用

37、戶級線程輕權進程57SUN Solaris 線程(con.) 用戶級線程在使用系統(tǒng)調用時（如文件讀寫），需要“捆綁(bound)”在一個LWP上。 永久捆綁：一個LWP固定被一個用戶級線程占用，該LWP移到LWP池之外 臨時捆綁：從LWP池中臨時分配一個未被占用的LWP 在使用系統(tǒng)調用時，如果所有LWP已被其他用戶級線程所占用（捆綁），則該線程阻塞直到有可用的LWP例如6個用戶級線程，而LWP池中有4個LWP 如果LWP執(zhí)行系統(tǒng)調用時阻塞（如read()調用），則當前捆綁在LWP上的用戶級線程也阻塞。58SUN Solaris 線程(con.) 用戶線程、輕權進程和核心線程的關系Process

38、 1PermanentlyBoundThreadsProcess 1KTKTKTKTKTKTCPU 1CPU 1LWPUTUTUTUTLWPLWPUnboundThreadsPool of LWPs forUnbound ThreadsKernalUTLWP59Windows NT線程 就緒狀態(tài)(Ready)：進程已獲得除處理機外的所需資源，等待執(zhí)行。 備用狀態(tài)(Standby)：特定處理器的執(zhí)行對象，系統(tǒng)中每個處理器上只能有一個處于備用狀態(tài)的線程。 運行狀態(tài)(Running)：完成描述表切換，線程進入運行狀態(tài)，直到內核搶先、時間片用完、線程終止或進行等待狀態(tài)。 等待狀態(tài)(Waiting)：線

39、程等待對象句柄，以同步它的執(zhí)行。等待結束時，根據(jù)優(yōu)先級進入運行、就緒狀態(tài)。 轉換狀態(tài)(Transition)：線程在準備執(zhí)行而其內核堆棧處于外存時，線程進入轉換狀態(tài)；當其內核堆棧調回內存，線程進入就緒狀態(tài)。 終止狀態(tài)(Terminated)：線程執(zhí)行完就進入終止狀態(tài)；如執(zhí)行體有一指向線程對象的指針，可將線程對象重新初始化，并再次使用。 初始化狀態(tài)(Initialized)：線程創(chuàng)建過程中的線程狀態(tài)；60Windows NT線程(con.)運行終止就緒等待描述表切換搶先或時間片結束等待對象句柄執(zhí)行完成初始化轉換備用選擇執(zhí)行搶先放入就緒隊列等待完成等待完成換出的內核堆棧換入的內核堆棧重新初始化創(chuàng)建

40、和初始化線程對象61Windows NT線程(con.) CreateThread()函數(shù)在調用進程的地址空間上創(chuàng)建一個線程，以執(zhí)行指定的函數(shù)；返回值為所創(chuàng)建線程的句柄。 ExitThread()函數(shù)用于結束本線程。 SuspendThread()函數(shù)用于掛起指定的線程。 ResumeThread()函數(shù)遞減指定線程的掛起計數(shù)，掛起計數(shù)為0時，線程恢復執(zhí)行。62進程通信（IPC） 進程間的關系 完全無關（異步）：不同進程間無任何關聯(lián) 使用共享數(shù)據(jù)（互斥）：有效保護各個進程的正確運行 存在先后順序（同步）：保證進程運行順序的正確 進程通信需要考慮的問題 如何實現(xiàn)兩個進程間的信息傳遞 如何協(xié)調兩個

41、或者多個進程之間的互斥和同步情況 問題難點分析 金字塔法則：20的簡單問題80的困難問題 難點：臨界區(qū)的保護63Interprocess Communication How one process can pass information to another Making sure two or more process do not get into each others way when engaging in critical activities. Proper sequencing when dependencies are present.Note: passing infor

42、mation is easy for threads since they share a common address space. However, keeping out of each others hair and proper sequencing apply equally well to threads64Interprocess CommunicationRace ConditionsTwo processes want to access shared memory at same time65Spooler目錄問題（互斥）6667Interprocess Communic

43、ation 進程調度機制的深入理解 何時發(fā)生進程調度時鐘中斷 進程切換時的操作壓棧，進入就緒隊列 邊界情況的進程通信困難 互斥情況調度順序影響運行結果 同步情況運行過程影響應用效果 多進程分時運行的臨界情況 正常情況下不存在任何問題 臨界情況下將產生不可預知的后果（墨菲法則） 解決的關鍵 保持進程之間正確的運行順序 OS與普通應用程序設計都需要考慮 解決機制：提升系統(tǒng)運行的穩(wěn)定性68一些IPC概念 競爭條件 兩個或者多個進程讀寫共享數(shù)據(jù)，而運行結果取決于進程運行時的精確時序，則這種情況稱之為競爭條件 當競爭條件存在時，進程處理結果可能失效甚至發(fā)生錯誤 臨界區(qū) 對共享內存（數(shù)據(jù)）進行訪問的程序片

44、斷稱為臨界區(qū) 互斥 防止多個進程同時操作相同共享數(shù)據(jù)的手段(多個進程不能同時使用同一個資源)死鎖多個進程互不相讓，都得不到足夠的資源饑餓一個進程一直得不到資源（其他進程可能輪流占用資源）69Interprocess Communication 同步關系分析 兩個或者多個進程在運行順序上存在固定的規(guī)則 由于分時操作系統(tǒng)的不確定性，導致同步關系無法保持 必須進行顯式的程序控制，保證同步關系的正確 同步與互斥的差別 互斥：體現(xiàn)為排他性，可表現(xiàn)為“01”關系(保護臨界區(qū)，防止多個進程同時進入) 同步：體現(xiàn)為時序性，比互斥更加復雜和多變(保證進程運行的順序合理) 解決思路 保證解決辦法對互斥和同步的適用

45、性70Critical Regions (1)Four 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 forever to enter its critical re

46、gion互斥原則：任何兩個進程不能同時處于臨界區(qū)通用性原則：不應對CPU的速度和數(shù)目進行任何假設有效性原則：臨界區(qū)外的進程不應阻塞其他進程合理性原則：不得使進程在臨界區(qū)外無限制的等待；當進程無法進入臨界區(qū)時，應放棄CPU資源71Critical Regions (2)Mutual exclusion using critical regions72IPC機制 忙等待模型（只解決互斥問題） 進程進入臨界區(qū)時進行嚴格的檢查 睡眠和喚醒模型（互斥與同步） 通過改變進程的狀態(tài)來實現(xiàn)互斥和同步 消息傳遞模型（復雜的IPC機制） 以公共的通信機制來控制進程狀態(tài)變化，實現(xiàn)同步和互斥73忙等待模型 模型思想

47、設定一個變量，標識臨界區(qū)的狀態(tài) 互斥進程均檢查這個變量，只有當其滿足條件時方可進入臨界區(qū) 模型方法 關中斷 鎖變量 嚴格輪轉 Peterson解決方案74關中斷 解決思想 在臨界區(qū)中防止發(fā)生進程調度 保證臨界區(qū)操作的完整性 方法分析 用戶控制系統(tǒng)中斷是非常危險的 本方法對多個CPU系統(tǒng)將失去作用75鎖變量 解決思想 設定監(jiān)控變量（lock），通過其值變化控制進程操作 方法分析 依然存在競爭條件，不能根本解決互斥問題 致命缺陷：不具有操作的原子性76鎖變量的缺陷示例發(fā)生進程調度，互發(fā)生進程調度，互斥的進程開始運行斥的進程開始運行發(fā)生進程調度，發(fā)生進程調度，A并不并不知道知道B也進入臨界區(qū)也進入臨

48、界區(qū)發(fā)生進程調度，發(fā)生進程調度，B并不并不知道知道A也進入臨界區(qū)也進入臨界區(qū)77Mutual Exclusion with Busy WaitingProposed solution to critical region problem(a) Process 0. (b) Process 1.嚴格輪轉法：忙等待浪費CPU時間；存在邊界情況，違反解決原則第三條78嚴格輪轉法的缺陷示例第一次運行時，可第一次運行時，可嚴格保證互斥關系嚴格保證互斥關系進程進程B需要第二次進入臨需要第二次進入臨界區(qū)時，必須等待進程界區(qū)時，必須等待進程A將將turn值改為值改為1。但是進。但是進程程A的非臨界區(qū)操作很慢的

49、非臨界區(qū)操作很慢79Mutual Exclusion with Busy Waiting (2)Petersons solution for achieving mutual exclusion80Use Petersons solution81Mutual Exclusion with Busy Waiting (3)Entering and leaving a critical region using the TSL instruction測試并加鎖：硬件TSL指令硬件實現(xiàn)提高速度，適用于多處理機; 依然存在忙等待的問題TSL RX LOCK: 硬件實現(xiàn)鎖變量機制, 保證LOCK讀寫原子

50、性82忙等待模型分析 優(yōu)點分析 實現(xiàn)機制簡單易懂，可有效保證互斥 缺點分析 只適用于兩個進程間互斥，不具有通用性 忙等待嚴重浪費CPU資源，降低硬件效率 “優(yōu)先級調度”“忙等待” 優(yōu)先級反轉 進程H和L，H優(yōu)先級比L優(yōu)先級高 L先進入臨界區(qū)，H后進入臨界區(qū) H開始忙等待，而L由于無法獲得CPU也不能離開臨界區(qū)83睡眠-喚醒模型 模型思想 OS提供系統(tǒng)調用原語（Atomic Action），改變進程狀態(tài) 無法進入臨界區(qū)的進程轉為阻塞態(tài)，條件滿足則被喚醒 可有效克服忙等待造成的資源浪費 更重要的優(yōu)點：可同時實現(xiàn)同步與互斥 模型方法 簡單的睡眠喚醒方法 信號量機制 管程方法84簡單的睡眠喚醒方法 操

51、作系統(tǒng)原語設計 Sleep()：調用該原語的進程將變?yōu)樽枞麘B(tài) Wakeup(ID)：該原語將喚醒ID標識的進程 原語使用思想 進入臨界區(qū)前檢查競爭條件，如不滿足則睡眠 離開臨界區(qū)后喚醒互斥進程85生產者消費者問題 問題描述 一個有限空間的共享緩沖區(qū)，負責存放貨物 生產者向緩沖區(qū)中放物品，緩沖區(qū)滿則不能放 消費者從緩沖區(qū)中拿物品，緩沖區(qū)空則不能拿86Sleep and WakeupProducer-consumer problem with fatal race condition87潛在的競爭條件發(fā)生進程調度，導致發(fā)生進程調度，導致C進進程并未進行程并未進行SleepP進程認為進程認為C在睡眠

52、，試在睡眠，試圖喚醒圖喚醒C由于錯過了由于錯過了Wakeup信號，信號，C進入了睡眠狀態(tài)進入了睡眠狀態(tài)P進程一直運行下去，填進程一直運行下去，填滿緩沖區(qū)后也睡眠了滿緩沖區(qū)后也睡眠了88 臨界情況 count的訪問未加限制，形成競爭條件 必須增加喚醒等待位，以解決互斥問題 方法分析 較忙等待更進一步，有效節(jié)省CPU資源 存在競爭條件，需要額外處理 當互斥進程數(shù)增加時，方法有效性下降 改進辦法 由OS提供宏觀調控管理機制 徹底消除調度順序引起的錯亂 OS實現(xiàn)更高層次的原語級操作89信號量機制 基本概念 信號量：表示累積的睡眠或者喚醒操作 Down與Up原語（P/V、S/W原語） Dijkstra于

53、1965年提出Probern和Verhogen原語 核心思想 引入新的數(shù)據(jù)結構定義：信號量 利用信號量，提供更為復雜的原語級操作 從根本上解決“潛在競爭條件”問題 可以方便的推廣到一般情況，適用于多進程的互斥與同步90信號量與Down/Up原語 基本概念 對于一種互斥或者同步關系，用一個整型變量來描述 當信號量大于0時，說明“環(huán)境安全”，可繼續(xù)運行 當信號量小于0時，說明“互斥等待”，只能阻塞 推廣到一般情況，信號量可解決復雜的同步互斥問題原語：OS以關中斷形式實現(xiàn)的不可打斷操作91最基本互斥機制的實現(xiàn)92SemaphoresThe producer-consumer problem usin

54、g semaphores93 互斥信號量 mutex：防止多個進程同時進入臨界區(qū) 讀者和寫者不能同時進入共享數(shù)據(jù)區(qū) 多個寫者不能同時進入共享數(shù)據(jù)區(qū) 多個讀者可以同時進入共享數(shù)據(jù)區(qū) 同步信號量 empty和full：保證事件發(fā)生的順序 緩沖區(qū)滿時，Producer停止運行 緩沖區(qū)空時，Consumer停止運行 讀者進入緩沖區(qū)，寫者必須等待 寫者進入緩沖區(qū)，讀者必須等待 讀者優(yōu)先：一旦有讀者進入，則后續(xù)讀者均可進入 合理順序：讀者在先來的寫者之后 寫者優(yōu)先：只要有寫者等待，則后續(xù)讀者必須等待94MutexesImplementation of mutex_lock and mutex_unlock

55、95管程方法 死鎖的危險 一旦信號量的處理代碼發(fā)生錯誤，則會引起進程死鎖 核心思想 實現(xiàn)一種包含過程、變量、數(shù)據(jù)結構的獨立模塊 任何時刻，只能有一個活躍進程在管程內 由編譯器提供支持，實現(xiàn)進程間的互斥 方法分析 優(yōu)點：實現(xiàn)了進程互斥的自動化 缺點：依賴于編譯器，無法通用或普及96管程的引入 1973年，由Hoare和Hansen提出的一種高級同步原語，將共享變量以及對共享變量能夠進行的所有操作集中在一個模塊中。 管程的定義：一個管程是一個由過程、變量及數(shù)據(jù)結構等組成的集合，它們組成一個特殊的模塊或軟件包。進程可在任何需要的時候調用管程中的過程，但它們不能在管程之外聲明的過程中直接訪問管程內的數(shù)

56、據(jù)結構。97管程的主要特性 為了保證管程共享變量的數(shù)據(jù)完整性，規(guī)定管程互斥進入，即：任一時刻管程中只能有一個活躍進程，這一特性使管程能有效地完成互斥。 進入管程時的互斥由編譯器負責，而不是由程序員來安排互斥，出錯的可能性小。98管程的多個進程進入 管程提供了實現(xiàn)互斥的途徑，此時，還需要一種辦法使得進程在無法繼續(xù)運行時被阻塞，其解決的辦法是：引入條件變量和wait、signal兩個操作。 當一個管程過程無法繼續(xù)運行時，將在某個條件變量上執(zhí)行wait 被阻塞 條件變量不能象信號量那樣積累信號，為了防止信號丟失，規(guī)定： wait操作必須在signal操作之前。99管程中的多個進程進入 當一個進入管程

57、的進程執(zhí)行wait操作時，它應當釋放管程的互斥權；當一個進入管程的進程執(zhí)行signal操作時（如喚醒），管程中便存在兩個同時處于活動狀態(tài)的進程。 Brinch Hansen的處理方法：執(zhí)行signal操作的進程必須立即退出管程，即，signal語句只可作為管程過程的最后一條語句。 如果在一個條件變量上有多個進程正在等待，則對該條件變量的signal后，系統(tǒng)調度程序只能在其中選擇一個使其恢復運行。100Monitors (1)Example of a monitor101Monitors (2) Outline of producer-consumer problem with monitors

58、 only one monitor procedure active at one time buffer has N slots102Monitors (3)Solution to producer-consumer problem in Java (part 1)103Monitors (4)Solution to producer-consumer problem in Java (part 2)104信號量模型分析 優(yōu)點分析 徹底解決忙等待弊端，提高OS的管理層次 可實現(xiàn)復雜的同步與互斥情況，特別是多進程間通信 可最大限度的保證并發(fā)效率 缺點分析 實現(xiàn)機制復雜，互斥和同步關系分析困難

59、存在死鎖陷阱，需要謹慎小心嚴密的設計105消息傳遞模型 模型思想 提供Send和Receive原語，用來傳遞消息 進程通過發(fā)送和接收消息來實現(xiàn)互斥與同步 重要的優(yōu)點：不僅實現(xiàn)了同步，還能夠傳送大容量信息 設計要點 如何保證消息傳遞中不丟失？（ACK機制） 如何命名進程，使得其地址唯一并確認身份 如何規(guī)范消息格式，降低處理時間106Message PassingThe producer-consumer problem with N messages107Barriers Use of a barrier processes approaching a barrier all processes

60、 but one blocked at barrier last process arrives, all are let through108Dining Philosophers (1) Philosophers eat/think Eating needs 2 forks Pick one fork at a time How to prevent deadlock 互斥分析 筷子：同一時刻只能有一個哲學家拿起筷子同步分析 就餐：只有獲得兩個筷子后才能進餐特殊情況 死鎖：如果每個哲學家都拿起一只筷子，都餓死 并行程度：五只筷子允許兩人同時進餐109Dining Philosophers (2)A nonsolution t