【文章內(nèi)容簡(jiǎn)介】 hile (key == true) Swap(lock,key)。 critical section lock = false。 remainder section } Semaphore ? Synchronization tool that does not require busy waiting（一種不需要忙等待的同步工具） . ? Semaphore S – integer variable（信號(hào)量 S – 整型變量） ? can only be accessed via two indivisible (atomic) operations（僅能通過(guò)兩個(gè)不可分割的 [原子 ]操作訪(fǎng)問(wèn)） P (S): while S? 0 do noop。 S。 V(S): S++。 Critical Section of n Processes ? Shared data: semaphore mutex。 //initially mutex = 1 ? Process Pi: do { wait(mutex)。 critical section signal(mutex)。 remainder section } while (1)。 Semaphore Implementation ? Define a semaphore as a record typedef struct { int value。 struct process *L。 } semaphore。 value是信號(hào)量的值，它是整型變量； *L是等待使用該信號(hào)量的進(jìn)程排成的隊(duì)列的隊(duì)首指針 。 ? Assume two simple operations: ? block suspends the process that invokes it. ? wakeup(P) resumes the execution of a blocked process P. Implementation ? Semaphore operations now defined as wait(S): 。 if ( 0) { add this process to 。 block。 } 如果 =0,則該進(jìn)程繼續(xù)運(yùn)行；如果 0,則將該進(jìn)程置為封鎖狀態(tài)，并 將其送入由 L指示的隊(duì)列。系統(tǒng)將調(diào)度另一進(jìn)程占用處理機(jī)。所以當(dāng)0時(shí)， 其絕對(duì)值表示在信號(hào)量進(jìn)程隊(duì)列中的進(jìn)程數(shù)。 signal(S): ++。 if ( = 0) { remove a process P from 。 wakeup(P)。 } ) 如果 0,該進(jìn)程繼續(xù)運(yùn)行；如果 =0，則釋放該信號(hào)量隊(duì)列中的一個(gè)進(jìn)程，使其轉(zhuǎn)入就緒狀態(tài)，調(diào)用本操作的進(jìn)程繼續(xù)運(yùn)行。 Semaphore as a General Synchronization Tool ? Execute B in Pj only after A executed in Pi ? Use semaphore flag initialized to 0 ? Code: Pi Pj ? ? A wait(flag) signal(flag) B Deadlock and Starvation ? Deadlock – two or more processes are waiting indefinitely for an event that can be caused by only one of the waiting processes（死鎖 – 兩個(gè)或多個(gè)進(jìn)程無(wú)限期地等待一個(gè)事件的發(fā)生，而該事件正是由其中的一個(gè)等待進(jìn)程引起的） . ? Let S and Q be two semaphores initialized to 1（ S和 Q是兩個(gè)初值為 1的信號(hào)量） P0 P1 P(S)。 P(Q)。 P(Q)。 P(S)。 ? ? V(S)。 V(Q)。 V(Q) V(S)。 ? Starvation – indefinite blocking. A process may never be removed from the semaphore queue in which it is suspended（饑餓 – 無(wú)限期地阻塞。進(jìn)程可能永遠(yuǎn)無(wú)法從它等待的信號(hào)量隊(duì)列中移去） . Two Types of Semaphores ? Counting semaphore – integer value can range over an unrestricted domain（計(jì)數(shù)信號(hào)量 – 變化范圍沒(méi)有限制的整型值） . ? Binary semaphore – integer value can range only between 0 and 1。 can be simpler to implement（二值信號(hào)量 – 變化范圍僅限于 0和 1的信號(hào)量；容易實(shí)現(xiàn)） . ? Can implement a counting semaphore S as a binary semaphore（可以將計(jì)數(shù)信號(hào)量 S用作二值信號(hào)量） . Implementing S as a Binary Semaphore ? Data structures: binarysemaphore S1, S2。 int C: ? Initialization: S1 = 1 S2 = 0 C = initial value of semaphore S Implementing S ? wait operation wait(S1)。 C。 if (C 0) { signal(S1)。 wait(S2)。 } signal(S1)。 ? signal operation wait(S1)。 C ++。 if (C = 0) signal(S2)。 else signal(S1)。 Classical Problems of Synchronization ? BoundedBuffer Problem （有限緩沖區(qū)問(wèn)題） ? Readers and Writers Problem （讀者寫(xiě)者問(wèn)題） ? DiningPhilosophers Problem （哲學(xué)家就餐問(wèn)題） BoundedBuffer Problem ? Shared data semaphore full ,empty 當(dāng)它們的值大于或等于 0時(shí)，則分別表示緩存中尚可存放的產(chǎn)品數(shù)以及可用產(chǎn)品數(shù)。當(dāng)它們的值為負(fù)數(shù)時(shí)，則它們的絕對(duì)值分別表示正在等待存放產(chǎn)品的生產(chǎn)者進(jìn)程數(shù)和正在等待取用產(chǎn)品的消費(fèi)者進(jìn)程數(shù)。 semaphore mutex。 用于臨界區(qū)互斥，以免有一個(gè)以上進(jìn)程同時(shí)對(duì)緩存進(jìn)行存、取操作 . Initially: full = 0, empty = n, mutex = 1 BoundedBuffer Problem Producer Process do { … produce an item in nextp … wait(empty)。 wait(mutex)。 … add nextp to buffer … signal(mutex)。 signal(full)。 } while (1)。 BoundedBuffer Problem Consumer Process do { wait(full) wait(mutex)。 … remove an item from buffer to nextc … signal(mutex)。 signal(empty)。 … consume the item in nextc … } w