Operating system chapter 5

Operating system chapter 5

اسلاید 1: 1Concurrency: Mutual Exclusion and SynchronizationChapter 5

اسلاید 2: 2ConcurrencyMultiple applicationsStructured applicationsOperating system structure

اسلاید 3: 3Concurrency

اسلاید 4: 4Difficulties of ConcurrencySharing of global resourcesOperating system managing the allocation of resources optimallyDifficult to locate programming errors

اسلاید 5: 5CurrencyCommunication among processesSharing resourcesSynchronization of multiple processesAllocation of processor time

اسلاید 6: 6ConcurrencyMultiple applicationsMultiprogrammingStructured applicationApplication can be a set of concurrent processesOperating-system structureOperating system is a set of processes or threads

اسلاید 7: 7A Simple Examplevoid echo(){chin = getchar();chout = chin;putchar(chout); }

اسلاید 8: 8A Simple ExampleProcess P1Process P2. .chin = getchar(); .. chin = getchar();chout = chin;chout = chin;putchar(chout);..putchar(chout);. .

اسلاید 9: 9Operating System ConcernsKeep track of various processesAllocate and deallocate resourcesProcessor timeMemoryFilesI/O devicesProtect data and resourcesOutput of process must be independent of the speed of execution of other concurrent processes

اسلاید 10: 10Process InteractionProcesses unaware of each otherProcesses indirectly aware of each otherProcess directly aware of each other

اسلاید 11: 11

اسلاید 12: 12Competition Among Processes for ResourcesMutual ExclusionCritical sectionsOnly one program at a time is allowed in its critical sectionExample only one process at a time is allowed to send command to the printerDeadlockStarvation

اسلاید 13: 13Requirements for Mutual ExclusionOnly one process at a time is allowed in the critical section for a resourceA process that halts in its noncritical section must do so without interfering with other processesNo deadlock or starvation

اسلاید 14: 14Requirements for Mutual ExclusionA process must not be delayed access to a critical section when there is no other process using itNo assumptions are made about relative process speeds or number of processesA process remains inside its critical section for a finite time only

اسلاید 15: 15Mutual Exclusion: Hardware SupportInterrupt DisablingA process runs until it invokes an operating system service or until it is interruptedDisabling interrupts guarantees mutual exclusionProcessor is limited in its ability to interleave programsMultiprocessingdisabling interrupts on one processor will not guarantee mutual exclusion

اسلاید 16: 16Mutual Exclusion: Hardware SupportSpecial Machine InstructionsPerformed in a single instruction cycleAccess to the memory location is blocked for any other instructions

اسلاید 17: 17Mutual Exclusion: Hardware SupportTest and Set Instructionboolean testset (int i) {if (i == 0) {i = 1;return true;}else {return false;}}

اسلاید 18: 18Mutual Exclusion: Hardware SupportExchange Instructionvoid exchange(int register, int memory) {int temp;temp = memory;memory = register;register = temp;}

اسلاید 19: 19Mutual Exclusion

اسلاید 20: 20Mutual Exclusion Machine InstructionsAdvantagesApplicable to any number of processes on either a single processor or multiple processors sharing main memoryIt is simple and therefore easy to verifyIt can be used to support multiple critical sections

اسلاید 21: 21Mutual Exclusion Machine InstructionsDisadvantagesBusy-waiting consumes processor timeStarvation is possible when a process leaves a critical section and more than one process is waiting. DeadlockIf a low priority process has the critical region and a higher priority process needs, the higher priority process will obtain the processor to wait for the critical region

اسلاید 22: 22SemaphoresSpecial variable called a semaphore is used for signalingIf a process is waiting for a signal, it is suspended until that signal is sent

اسلاید 23: 23SemaphoresSemaphore is a variable that has an integer valueMay be initialized to a nonnegative numberWait operation decrements the semaphore valueSignal operation increments semaphore value

اسلاید 24: 24Semaphore Primitives

اسلاید 25: 25Binary Semaphore Primitives

اسلاید 26: 26Mutual Exclusion Using Semaphores

اسلاید 27: 27

اسلاید 28: 28

اسلاید 29: 29Producer/Consumer ProblemOne or more producers are generating data and placing these in a bufferA single consumer is taking items out of the buffer one at timeOnly one producer or consumer may access the buffer at any one time

اسلاید 30: 30Producerproducer:while (true) {/* produce item v */b[in] = v;in++; }

اسلاید 31: 31Consumerconsumer:while (true) { while (in <= out) /*do nothing */;w = b[out];out++; /* consume item w */}

اسلاید 32: 32Producer/Consumer Problem

اسلاید 33: 33Producer with Circular Bufferproducer:while (true) {/* produce item v */while ((in + 1) % n == out) /* do nothing */;b[in] = v;in = (in + 1) % n}

اسلاید 34: 34Consumer with Circular Bufferconsumer:while (true) {while (in == out)/* do nothing */;w = b[out];out = (out + 1) % n;/* consume item w */}

اسلاید 35: 35

اسلاید 36: 36

اسلاید 37: 37

اسلاید 38: 38

اسلاید 39: 39

اسلاید 40: 40MonitorsMonitor is a software moduleChief characteristicsLocal data variables are accessible only by the monitorProcess enters monitor by invoking one of its proceduresOnly one process may be executing in the monitor at a time

اسلاید 41: 41

اسلاید 42: 42

اسلاید 43: 43

اسلاید 44: 44

اسلاید 45: 45Message PassingEnforce mutual exclusionExchange informationsend (destination, message)receive (source, message)

اسلاید 46: 46SynchronizationSender and receiver may or may not be blocking (waiting for message)Blocking send, blocking receiveBoth sender and receiver are blocked until message is deliveredCalled a rendezvous

اسلاید 47: 47SynchronizationNonblocking send, blocking receiveSender continues onReceiver is blocked until the requested message arrivesNonblocking send, nonblocking receiveNeither party is required to wait

اسلاید 48: 48AddressingDirect addressingSend primitive includes a specific identifier of the destination processReceive primitive could know ahead of time which process a message is expectedReceive primitive could use source parameter to return a value when the receive operation has been performed

اسلاید 49: 49AddressingIndirect addressingMessages are sent to a shared data structure consisting of queuesQueues are called mailboxesOne process sends a message to the mailbox and the other process picks up the message from the mailbox

اسلاید 50: 50

اسلاید 51: 51Message Format

اسلاید 52: 52

اسلاید 53: 53

اسلاید 54: 54Readers/Writers ProblemAny number of readers may simultaneously read the fileOnly one writer at a time may write to the fileIf a writer is writing to the file, no reader may read it

اسلاید 55: 55

اسلاید 56: 56