《操作系统20140409lecture13syn》由会员分享，可在线阅读，更多相关《操作系统20140409lecture13syn（72页珍藏版）》请在金锄头文库上搜索。
1、Operating Systems,IIIS Department of Computer Science & Technology Tsinghua University,Lecture 13: Synchronization,Outline,Background Basic Concepts Critical Section Approach 1: Disabling Hardware Interrupt Approach 2: Software-based Solution Approach 3: Higher-level Abstractions,Multi-programming,S
2、o far in this course Multi-programming: an important feature of modern OS Parallelism is good (why?) Hint: multiple concurrent entities: CPU(s), I/O, , users, Process/thread: OS abstractions to support multi-programming CPU schedule: mechanism to realize multi-programming Scheduling algorithms diffe
3、rent policies Next topic Collaborative multi-programming and the concurrency problem,Correctness with concurrent threads,Independent threads: No state shared with other threads Deterministic Input state determines results Reproducible Can recreate Starting Conditions, I/O Scheduling order doesnt mat
4、ter Cooperating threads: Shared state between multiple threads Non-deterministic Non-reproducible Non-deterministic and Non-reproducible means that bugs can be intermittent Sometimes called “Heisenbugs”,Why allow cooperating threads?,People cooperate, so computers/devices must cooperate Advantage 1:
5、 Share resources One computer, many users One bank balance, many ATMs Embedded systems (robot control: coordinate arm & hand) Advantage 2: Speedup Overlap I/O and computation Multiprocessors chop up program into parallel pieces Advantage 3: Modularity Chop large problem up into simpler pieces To com
6、pile, for instance, gcc calls cpp | cc1 | cc2 | as | ld Makes system easier to extend,Cooperation Instance: Creating a New Process ID,A program calls fork() to create a new process OS needs to assign a new and unique process ID So somewhere in the kernel, this system call will do new_pid = next_pid+
7、 ; Translating into machine instructions LOAD next_pid Reg1 STORE Reg1 new_pid INC Reg1 STORE Reg1 next_pid Assume two processes execute concurrently If next_pid is 100, then one process should get 100, the other should get 101, and next_pid should increase to 102,Work correctly under all possible i
8、nterleaving?,Process 1 LOAD next_pid Reg1 STORE Reg1 new_pid INC Reg1 STORE Reg1 next_pid Gets 100 as the new PID next_pid becomes 101,Process 2 LOAD next_pid Reg1 STORE Reg1 new_pid INC Reg1 STORE Reg1 next_pid Gets 100 as the new PID next_pid becomes 101,Concurrency: Correctness Requirements,Threa
9、ded programs must work for all interleavings of thread instruction sequences Cooperating threads inherently non-deterministic and non-reproducible Really hard to debug unless carefully designed! Need to be careful about correctness of concurrent programs, since non-deterministic Always write down be
10、havior first Impulse is to start coding first, then when it doesnt work, pull hair out Instead, think first, then code,Outline,Background Basic Concepts Critical Section Approach 1: Disabling Hardware Interrupt Approach 2: Software-based Solution Approach 3: Higher-level Abstractions,Concept: Race C
11、ondition,A flaw in the system where the outcome depends on the sequence/timing of concurrent executions or events Like the previous example Non-deterministic Non-reproducible How do you avoid such race condition in an OS design?,Concept: Atomic Operation,An atomic operation is one that executes to c
12、ompletion without any interruption or failure Either it executes to completion, or it did not execute at all, and no one else should see a partially-executed state Operations are often not atomic Many that we thought to be are not so by the computer Not even a simple statement like “x+” ! Translated
13、 into a sequence of 3 instructions Sometimes not even so for a machine instruction Remember pipeline, super-scalar, out-of-order, page fault?,Another Concurrent Program Example,Two threads, A and B, compete with each other One tries to increment a shared counter The other tries to decrement the coun
14、ter Thread A Thread B i = 0; i = 0; while (i -10) i = i + 1; i = i 1; printf(“A wins!”); printf(“B wins!”); Assume that memory loads and stores are atomic, but incrementing and decrementing are not atomic Who wins? Is it guaranteed that someone wins? What it both threads have their own CPU running a
15、t same speed?,Concepts,Critical section A section of code within a process that requires access to shared resources and which may not be executed while another process is in a corresponding section of code. Mutual exclusion The requirement that when one process is in a critical section that accesses
16、 shared resources, no other process may be in a critical section that accesses any of those shared resources. Deadlock A situation in which two or more processes are unable to proceed because each is waiting for one of the others to do something. Starvation A situation in which a runnable process is overlooked indefinitely by the scheduler; although it is able to proceed, it is never chosen.,Motivation Example: “Too much milk”,Great thing about OSs-analogy between p
