16.1Silberschatz, Galvin and Gagne ©2005Operating System ConceptsCSMC 412CSMC 412Operating SystemsProf. Ashok K Agrawala© 2005 Ashok AgrawalaSet 66.2Silberschatz, Galvin and Gagne ©2005Operating System ConceptsProcess SynchronizationProcess Synchronization Background The Critical-Section Problem Synchronization Hardware Semaphores Classical Problems of Synchronization Monitors Java Synchronization Solaris Synchronization Windows XP Synchronization Linux Synchronization Pthreads Synchronization Atomic Transactions Log-based Recovery Checkpoints Concurrent Transactions Serializability Locking Protocols26.3Silberschatz, Galvin and Gagne ©2005Operating System ConceptsConcurrency and SynchronizationConcurrency and Synchronization Concurrency The Critical-Section Problem Synchronization Hardware Semaphores Classical Problems of Synchronization Critical Regions Monitors Synchronization in Solaris 2 & Windows 20006.4Silberschatz, Galvin and Gagne ©2005Operating System ConceptsSystems = Objects + ActivitiesSystems = Objects + Activities Safety is a property of objects, and groups of objects, that participate across multiple activities.z Can be a concern at many different levels: objects, composites, components, subsystems, hosts, … Liveness is a property of activities, and groups of activities, that span across multiple objects.z Levels: Messages, call chains, threads, sessions, scenarios, scripts workflows, use cases, transactions, data flows, mobile computations, …36.5Silberschatz, Galvin and Gagne ©2005Operating System ConceptsViolating SafetyViolating Safety Data can be shared by threadsz Scheduler can interleave or overlap threads arbitrarilyz Can lead to interferenceStorage corruption (e.g. a data race/race condition)Violation of representation invariantViolation of a protocol (e.g. A occurs before B)6.6Silberschatz, Galvin and Gagne ©2005Operating System ConceptsHow does this apply to How does this apply to OSsOSs?? Any resource that is shared could be accessed inappropriatelyz Shared memory Kernel threads Processes (shared memory set up by kernel)z Shared resources Printer, Video screen, Network card, … OS must protect shared resourcesz And provide processes a means to protect their own abstractions46.7Silberschatz, Galvin and Gagne ©2005Operating System ConceptsData Race ExampleData Race Examplestatic int cnt = 0;t1.run() {int y = cnt;cnt = y + 1;}t2.run() {int y = cnt;cnt = y + 1;}cnt = 0Start: both threads ready torun. Each will increment theglobal count. Shared state6.8Silberschatz, Galvin and Gagne ©2005Operating System ConceptsData Race ExampleData Race Examplestatic int cnt = 0;t1.run() {int y = cnt;cnt = y + 1;}t2.run() {int y = cnt;cnt = y + 1;}cnt = 0T1 executes, grabbingthe global counter value into y.Shared statey = 056.9Silberschatz, Galvin and Gagne ©2005Operating System ConceptsData Race ExampleData Race Examplestatic int cnt = 0;t1.run() {int y = cnt;cnt = y + 1;}t2.run() {int y = cnt;cnt = y + 1;}cnt = 0T1 is pre-empted. T2executes, grabbing the globalcounter value into y.Shared statey = 0y = 06.10Silberschatz, Galvin and Gagne ©2005Operating System ConceptsData Race ExampleData Race Examplestatic int cnt = 0;t1.run() {int y = cnt;cnt = y + 1;}t2.run() {int y = cnt;cnt = y + 1;}cnt = 1T2 executes, storing theincremented cnt value.Shared statey = 0y = 066.11Silberschatz, Galvin and Gagne ©2005Operating System ConceptsData Race ExampleData Race Examplestatic int cnt = 0;t1.run() {int y = cnt;cnt = y + 1;}t2.run() {int y = cnt;cnt = y + 1;}cnt = 1T2 completes. T1executes again, storing theold counter value (1) ratherthan the new one (2)!Shared statey = 0y = 06.12Silberschatz, Galvin and Gagne ©2005Operating System ConceptsBut When I Run it Again?But When I Run it Again?76.13Silberschatz, Galvin and Gagne ©2005Operating System ConceptsData Race ExampleData Race Examplestatic int cnt = 0;t1.run() {int y = cnt;cnt = y + 1;}t2.run() {int y = cnt;cnt = y + 1;}cnt = 0Start: both threads ready torun. Each will increment theglobal count. Shared state6.14Silberschatz, Galvin and Gagne ©2005Operating System ConceptsData Race ExampleData Race Examplestatic int cnt = 0;t1.run() {int y = cnt;cnt = y + 1;}t2.run() {int y = cnt;cnt = y + 1;}cnt = 0T1 executes, grabbingthe global counter value into y.Shared statey = 086.15Silberschatz, Galvin and Gagne ©2005Operating System ConceptsData Race ExampleData Race Examplestatic int cnt = 0;t1.run() {int y = cnt;cnt = y + 1;}t2.run() {int y = cnt;cnt = y + 1;}cnt = 1T1 executes again, storing thecounter valueShared statey = 06.16Silberschatz, Galvin and Gagne ©2005Operating System ConceptsData Race ExampleData Race Examplestatic int cnt = 0;t1.run() {int y = cnt;cnt = y + 1;}t2.run() {int y = cnt;cnt = y + 1;}cnt = 1T1 finishes. T2 executes, grabbing the globalcounter value into y.Shared statey = 0y = 196.17Silberschatz, Galvin and Gagne ©2005Operating System ConceptsData Race ExampleData Race Examplestatic int cnt = 0;t1.run() {int y = cnt;cnt = y + 1;}t2.run() {int y = cnt;cnt = y + 1;}cnt = 2T2 executes, storing theincremented cnt value.Shared statey = 0y = 16.18Silberschatz, Galvin and Gagne ©2005Operating System ConceptsWhat happened?What happened? In the first example, t1 was preempted after it read the counter but before it stored the new value.z Depends on the idea of an atomic actionz Violated an object invariant A particular way in which the execution of two threads is interleaved is called a schedule. We want to prevent this undesirable schedule. Undesirable schedules can be hard to reproduce, and so hard to debug.106.19Silberschatz, Galvin and Gagne ©2005Operating System ConceptsQuestionQuestion If you run a program with a race condition, will you always get an unexpected result?z No! It depends on the schedulerz ...and on the other threads/processes/etc that are running on the same CPU Race conditions are hard to find6.20Silberschatz, Galvin and Gagne ©2005Operating System ConceptsSynchronizationSynchronizationstatic int cnt = 0;struct Mutex lock;Mutex_Init(&lock);void run() {Mutex_Lock (&lock);int y = cnt;cnt = y + 1;Mutex_Unlock (&lock);}Lock, for protecting The shared stateAcquires the lock;Only succeeds if notheld by anotherthreadReleases the lock116.21Silberschatz, Galvin and Gagne ©2005Operating System ConceptsJavaJava--style style
View Full Document
Unlocking...