02-Processes and Interactions

1 .2. Processes and Interactions 2.1 The Process Notion 2.2 Defining and Instantiating Processes Precedence Relations Implicit Process Creation Dynamic Creation With fork And join 2.3 Basic Process Interactions Competition: The Critical Section Problem Cooperation 2.4 Semaphores Semaphore Operations and Data Mutual Exclusion Producer/Consumer Situations 1 Operating Systems

2 .Processes A process is the activity of executing a program on a CPU. Conceptually… Each process has its own CPU Processes are running concurrently Physical concurrency = parallelism This requires multiple CPUs Logical concurrency = time-shared CPU Processes cooperate (shared memory, messages, synchronization) Processes compete for resources 2 Operating Systems

3 .Why Processes? Hardware-independent solutions Processes cooperate and compete correctly, regardless of the number of CPUs Structuring mechanism Tasks are isolated with well-defined interfaces 3 Operating Systems

4 .How to define/create Processes? Need to: Define what each process does (the program) Create the processes (data structure/PCB ) Subject of another chapter Specify precedence relations: when processes start and stop executing, relative to each other 4 Operating Systems

5 .Specifying precedence relations A general approach: Process flow graphs Directed acyclic graphs (DAGs) Edges = processes Vertices = starting and ending points of processes 5 Operating Systems

6 .Process flow graphs Example : parallel evaluation of arithmetic expression: (a + b) * (c + d) - (e / f) 6 Operating Systems

7 .Other examples of Precedence Relationships 7 Operating Systems Process flow graphs

8 .Process flow graphs (PFG) Challenge: devise programming language constructs to capture PFG Special case: Properly Nested Graphs A graph is properly nested if it corresponds to a properly nested expression , where S(p1 , p2, …) describes serial execution of p1, p2 , … P(p1, p2, …) describes parallel execution of p1 , p2 , … 8 Operating Systems

9 .Process flow graphs 9 Operating Systems (a) S(p1 , p2, p3, p4) (b) P(p1 , p2, p3, p4 ) Strictly sequential or strictly parallel execution

10 .Process flow graphs (c) corresponds to the properly nested expression: S(p1, P(p2, S(p3, P(p4, p5)), p6), P(p7, p8)) (d) is not properly nested (proof: text, page 44) 10 Operating Systems

11 .Language Constructs for Process Creation to capture properly nested graphs cobegin // coend forall statement to capture unrestricted graphs fork/join/quit 11 Operating Systems

12 .c obegin / coend statements syntax : cobegin C 1 // C 2 // … // C n coend meaning : a ll C i may proceed concurrently w hen all C i ’s terminate, next statement can proceed cobegin / coend are analogous to S/P notation S( a,b )  a; b (sequential execution by default) P( a,b )  cobegin a // b coend 12 Operating Systems

13 .cobegin / coend example 13 Operating Systems cobegin Time_Date // Mail // { Edit; cobegin { Compile; Load; Execute} // { Edit; cobegin Print // Web coend } coend } coend

14 .Data parallelism Same code is applied to different data The forall statement syntax : forall (parameters) statements m eaning : Parameters specify set of data items Statements are executed for each item concurrently 14 Operating Systems

15 .Example of forall statement Example: Matrix Multiply A=B*C forall ( i:1..n, j:1..m ) { A[i][j] = 0; for ( k=1; k<=r; ++k ) A[i][j] = A[i][j] + B[i][k]*C[k][j]; } Each inner product is computed sequentially All inner products are computed in parallel 15 Operating Systems

16 .fork/join/quit cobegin / coend limited to properly nested graphs forall limited to data parallelism fork/join/quit can express arbitrary functional parallelism (any process flow graph) 16 Operating Systems

17 .fork/join/quit Syntax : fork x Meaning : create new process that begins executing at label x Syntax : join t,y Meaning : t = t–1; if (t==0) goto y; Syntax : quit Meaning : terminate current process 17 Operating Systems

18 .fork/join/quit example A simple Example : execute x and y concurrently w hen both finish, execute z t = 2; fork L1; fork L2; quit; L1: x; join t,L3; quit L2: y; join t,L3; quit; L3: z; Better: t = 2; fork L2; x ; join t,L3 ; quit ; L2: y; join t,L3 ; quit L3: z; 18 Operating Systems

19 .fork/join/quit example Example: Graph in Figure 2-1(d) t1 = 2; t2 = 3; p1; fork L2; fork L5; fork L7; quit; L2: p2; fork L3; fork L4; quit; L5: p5; join t1,L6; quit; L7: p7; join t2,L8; quit; L4: p4; join t1,L6; quit; L3: p3; join t2,L8; quit; L6: p6; join t2,L8; quit; L8: p8; quit; 19 Operating Systems

20 .Example: the Unix fork statement procid = fork() Replicates calling process Parent and child are identical except for the value of procid Use procid to diverge parent and child: if ( procid ==0) do_child_processing else do_parent_processing 20 Operating Systems

21 .Explicit Process Declarations Designate piece of code as a unit of execution Facilitates program structuring Instantiate: Statically (like cobegin ) or Dynamically (like fork ) 21 Operating Systems

22 .Explicit Process Declarations process p process p1 declarations_for_p1 begin ... end process type p2 declarations_for_p2 begin ... end begin ... q = new p2; ... end 22 Operating Systems

23 .Process Interactions Competition Two processes both want to access the same resource Example: write the same file, use the same printer Requires mutual e xclusion Cooperation Two processes work on a common problem Example: Producer  Buffer  Consumer Requires coordination 23 Operating Systems

24 .Process Interactions Competition: The Critical Section Problem x = 0; cobegin p1: … x = x + 1; … // p2: … x = x + 1; … c oend After both processes execute, we should have x=2, but … 24 Operating Systems

25 .The Critical Section Problem Interleaved execution (due to parallel processing or context switching) p1: R1 = x; p2: … R2 = x; R1 = R1 + 1; R2 = R2 + 1; x = R1 ; … x = R2; x has only been incremented once. The first update ( x = R1 ) is lost. 25 Operating Systems

26 .The Critical Section Problem General problem statement: cobegin p1: while(1) {CS1; program1;} // p2: while(1) {CS2; program2;} // ... // pn : while(1) { CSn ; programn ;} coend Guarantee mutual exclusion : At any time, at most one process should be executing within its critical section ( CSi ). 26 Operating Systems

27 .The Critical Section Problem In addition to mutual exclusion , must also prevent mutual blocking : 1. Process outside of its CS must not prevent other processes from entering its CS (no “dog in manger”) 2. Process must not be able to repeatedly reenter its CS and starve other processes (fairness) 3. Processes must not block each other forever (no deadlock) 4. Processes must not repeatedly yield to each other (“after you—after you”) (no livelock ) 27 Operating Systems

28 .The Critical Section Problem Solving the problem is subtle We will examine a few incorrect solutions before describing a correct one: Peterson’s algorithm 28 Operating Systems

29 .Attempt 1 (incorrect) Use a single turn variable: int turn = 1; cobegin p1: while (1) { while (turn != 1); /*wait*/ CS1; turn = 2; program1; } // p2: while (1) { while (turn != 2); /*wait*/ CS2; turn = 1; program2; } coend Violates blocking requirement (1), “dog in manger” 29 Operating Systems