Understanding Concurrency in Operating Systems

Slide Note
Embed
Share

Concurrency is a crucial feature in modern operating systems, enabling concurrent execution of processes/threads. It involves issues like communication, synchronization, resource sharing, and contention. This discussion explores design problems, solutions, principles of concurrency, interactions among processes, and mutual exclusion challenges in concurrency.


Uploaded on Oct 05, 2024 | 0 Views


Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

E N D

Presentation Transcript


  1. Xinu Semaphores

  2. Concurrency An important and fundamental feature in modern operating systems is concurrent execution of processes/threads. This feature is essential for the realization of multiprogramming, multiprocessing, distributed systems, and client-server model of computation. Concurrency encompasses many design issues including communication and synchronization among processes, sharing of and contention for resources. In this discussion we will look at the various design issues/problems and the wide variety of solutions available. 10/5/2024 Page 2

  3. Principles of Concurrency Interleaving and overlapping the execution of processes. Consider two processes P1 and P2 executing the function echo: { input (in, keyboard); out = in; output (out, display); } 10/5/2024 Page 3

  4. ...Concurrency (contd.) P1 invokes echo, after it inputs into in , gets interrupted (switched). P2 invokes echo, inputs into in and completes the execution and exits. When P1 returns in is overwritten and gone. Result: first ch is lost and second ch is written twice. This type of situation is even more probable in multiprocessing systems where real concurrency is realizable thru multiple processes executing on multiple processors. Solution: Controlled access to shared resource Protect the shared resource : inbuffer; critical resource one process/shared code. critical region 10/5/2024 Page 4

  5. Interactions among processes In a multi-process application these are the various degrees of interaction: 1. Competing processes: Processes themselves do not share anything. But OS has to share the system resources among these processes competing for system resources such as disk, file or printer. Co-operating processes : Results of one or more processes may be needed for another process. 2. Co-operation by sharing : Example: Sharing of an IO buffer. Concept of critical section. (indirect) 3. Co-operation by communication : Example: typically no data sharing, but co-ordination thru synchronization becomes essential in certain applications. (direct) 10/5/2024 Page 5

  6. Interactions ...(contd.) Among the three kinds of interactions indicated by 1, 2 and 3 above: 1 is at the system level: potential problems : deadlock and starvation. 2 is at the process level : significant problem is in realizing mutual exclusion. 3 is more a synchronization problem. We will study mutual exclusion and synchronization here, and defer deadlock, and starvation for a later time. 10/5/2024 Page 6

  7. Mutual exclusion problem Successful use of concurrency among processes requires the ability to define critical sections and enforce mutual exclusion. Critical section : is that part of the process code that affects the shared resource. Mutual exclusion: in the use of a shared resource is provided by making its access mutually exclusive among the processes that share the resource. This is also known as the Critical Section (CS) problem. 10/5/2024 Page 7

  8. Software Solutions: Algorithm 1 Process 0 ... while turn != 0 do nothing; // busy waiting < Critical Section> turn = 1; ... Problems : Strict alternation, Busy Waiting Process 1 ... while turn != 1 do nothing; // busy waiting < Critical Section> turn = 0; ... 10/5/2024 Page 8

  9. Algorithm 2 PROCESS 0 ... flag[0] = TRUE; while flag[1] do nothing; <CRITICAL SECTION> flag[0] = FALSE; PROCESS 1 ... flag[1] = TRUE; while flag[0] do nothing; <CRITICAL SECTION> flag[1] = FALSE; PROBLEM : Potential for deadlock, if one of the processes fail within CS. 10/5/2024 Page 9

  10. Algorithm 3 Combined shared variables of algorithms 1 and 2. Process Pi do { flag [i]:= true; turn = j; while (flag [j] and turn = j) ; critical section flag [i] = false; remainder section } while (1); Solves the critical-section problem for two processes. 10/5/2024 Page 10

  11. Semaphores Think about a semaphore as a class Attributes: semaphore value, Functions: init, wait, signal Support provided by OS Considered an OS resource, a limited number available: a limited number of instances (objects) of semaphore class is allowed. Can easily implement mutual exclusion among any number of processes. 10/5/2024 Page 11

  12. Critical Section of n Processes Shared data: Semaphore mutex; //initially mutex = 1 Process Pi: do { mutex.wait(); critical section mutex.signal(); remainder section } while (1); 10/5/2024 Page 12

  13. Semaphore Implementation class Semaphore { int value; // semaphore value ProcessQueue L; // process queue //operations wait() signal() } In addition, two simple utility operations: block() suspends the process that invokes it. Wakeup() resumes the execution of a blocked process P. Define a semaphore as a class: 10/5/2024 Page 13

  14. Semantics of wait and signal Semaphore operations now defined as S.wait(): S.value--; if (S.value < 0) { } add this process to S.L; block(); // block a process S.signal(): S.value++; if (S.value <= 0) { remove a process P from S.L; wakeup(); // wake a process } 10/5/2024 Page 14

  15. Semaphores for CS Semaphore is initialized to 1. The first process that executes a wait() will be able to immediately enter the critical section (CS). (S.wait() makes S value zero.) Now other processes wanting to enter the CS will each execute the wait() thus decrementing the value of S, and will get blocked on S. (If at any time value of S is negative, its absolute value gives the number of processes waiting blocked. ) When a process in CS departs, it executes S.signal() which increments the value of S, and will wake up any one of the processes blocked. The queue could be FIFO or priority queue. 10/5/2024 Page 15

  16. Two Types of Semaphores Counting semaphore integer value can range over an unrestricted domain. Binary semaphore integer value can range only between 0 and 1; can be simpler to implement. ex: nachos Can implement a counting semaphore using a binary semaphore. 10/5/2024 Page 16

  17. Semaphore for Synchronization Execute B in Pj only after A executed in Pi Use semaphore flag initialized to 0 Code: Pi A flag.signal() Pj flag.wait() B 10/5/2024 Page 17

  18. Classical Problems of Synchronization Bounded-Buffer Problem Readers and Writers Problem Dining-Philosophers Problem 10/5/2024 Page 18

  19. Producer/Consumer problem Producer repeat produce item v; b[in] = v; in = in + 1; forever; Consumer repeat while (in <= out) nop; w = b[out]; out = out + 1; consume w; forever; 10/5/2024 Page 19

  20. Solution for P/C using Semaphores Producer repeat produce item v; MUTEX.wait(); b[in] = v; in = in + 1; MUTEX.signal(); forever; Consumer repeat while (in <= out) nop; MUTEX.wait(); w = b[out]; out = out + 1; MUTEX.signal(); consume w; forever; Ans: Consumer will busy- wait at the while statement. What if Producer is slow or late? 10/5/2024 Page 20

  21. P/C: improved solution repeat produce item v; MUTEX.wait(); b[in] = v; in = in + 1; MUTEX.signal(); AVAIL.signal(); forever; repeat AVAIL.wait(); MUTEX.wait(); w = b[out]; out = out + 1; MUTEX.signal(); consume w; forever; Producer Consumer What will be the initial values of MUTEX and AVAIL? ANS: Initially MUTEX = 1, AVAIL = 0. 10/5/2024 Page 21

  22. P/C problem: Bounded buffer Producer repeat produce item v; while((in+1)%n == out) NOP; b[in] = v; in = ( in + 1)% n; forever; How to enforce bufsize? Consumer repeat while (in == out) NOP; w = b[out]; out = (out + 1)%n; consume w; forever; ANS: Using another counting semaphore. 10/5/2024 Page 22

  23. P/C: Bounded Buffer solution repeat produce item v; BUFSIZE.wait(); MUTEX.wait(); b[in] = v; in = (in + 1)%n; MUTEX.signal(); AVAIL.signal(); forever; What is the initial value of BUFSIZE? Producer repeat AVAIL.wait(); MUTEX.wait(); w = b[out]; out = (out + 1)%n; MUTEX.signal(); BUFSIZE.signal(); consume w; forever; ANS: size of the bounded buffer. Consumer 10/5/2024 Page 23

  24. Semaphores - comments Intuitively easy to use. wait() and signal() are to be implemented as atomic operations. Difficulties: signal() and wait() may be exchanged inadvertently by the programmer. This may result in deadlock or violation of mutual exclusion. signal() and wait() may be left out. Related wait() and signal() may be scattered all over the code among the processes. 10/5/2024 Page 24

  25. Xinu Resources & Critical Resources Shared resources: need mutual exclusion Tasks cooperating to complete a job Tasks contending to access a resource Tasks synchronizing Critical resources and critical region A important synchronization and mutual exclusion primitive / resource is semaphore 10/5/2024 Page 25

  26. Critical sections and Semaphores When multiples tasks are executing there may be sections where only one task could execute at a given time: critical region or critical section There may be resources which can be accessed only be one of the processes: critical resource Semaphores can be used to ensure mutual exclusion to critical sections and critical resources 10/5/2024 Page 26

  27. Semaphores See semaphore.h of xinu 10/5/2024 Page 27

  28. Semaphores in exinu #include <kernel.h> #include <queue.h> /**< queue.h must define # of sem queues */ /* Semaphore state definitions */ #define SFREE 0x01 /**< this semaphore is free */ #define SUSED 0x02 /**< this semaphore is used */ /* type definition of "semaphore" */ typedef ulong semaphore; /* Semaphore table entry */ struct sentry { char state; /**< the state SFREE or SUSED */ short count; /**< count for this semaphore */ queue queue; /**< requires q.h. */ }; 28

  29. Semaphores in exinu (contd.) extern struct sentry semtab[]; /** * isbadsem - check validity of reqested semaphore id and state * @param s id number to test; NSEM is declared to be 100 in kernel.h A system typically has a predetermined limited number of semaphores */ #define isbadsem(s) (((ushort)(s) >= NSEM) || (SFREE == semtab[s].state)) /* Semaphore function declarations */ syscall wait(semaphore); syscall signal(semaphore); syscall signaln(semaphore, short); semaphore newsem(short); syscall freesem(semaphore); syscall scount(semaphore); 29

  30. Definition of Semaphores functions static semaphore allocsem(void); /** * newsem - allocate and initialize a new semaphore. * @param count - number of resources available without waiting. * example: count = 1 for mutual exclusion lock * @return new semaphore id on success, SYSERR on failure */ semaphore newsem(short count) { irqmask ps; semaphore sem; ps = disable(); /* disable interrupts */ sem = allocsem(); /* request new semaphore */ if ( sem != SYSERR && count >= 0 ) /* safety check */ { semtab[sem].count = count; /* initialize count */ restore(ps); /* restore interrupts */ return sem; /* return semaphore id */ } restore(ps); } 30

  31. Semaphore: newsem contd. /** * allocsem - allocate an unused semaphore and return its index. * Scan the global semaphore table for a free entry, mark the entry * used, and return the new semaphore * @return available semaphore id on success, SYSERR on failure */ static semaphore allocsem(void) { int i = 0; while(i < NSEM) /* loop through semaphore table */ { /* to find SFREE semaphore */ if( semtab[i].state == SFREE ) { semtab[i].state = SUSED; return i; } i++; } return SYSERR; } 31

  32. Semaphore: wait() /** * wait - make current process wait on a semaphore * @param sem semaphore for which to wait * @return OK on success, SYSERR on failure */ syscall wait(semaphore sem) { irqmask ps; struct sentry *psem; pcb *ppcb; ps = disable(); /* disable interrupts */ if ( isbadsem(sem) ) /* safety check */ { restore(ps); return SYSERR; } ppcb = &proctab[currpid]; /* retrieve pcb from process table */ psem = &semtab[sem]; /* retrieve semaphore entry */ if( --(psem->count) < 0 ) /* if requested resource is unavailable */ { ppcb->state = PRWAIT; /* set process state to PRWAIT*/ 32

  33. Semaphore: wait() ppcb->sem = sem; /* record semaphore id in pcb */ enqueue(currpid, psem->queue); resched(); /* place in wait queue and reschedule */ } restore(ps); /* restore interrupts */ return OK; } 33

  34. Semaphore: signal() /*signal - signal a semaphore, releasing one waiting process, and block * @param sem id of semaphore to signal * @return OK on success, SYSERR on failure */ syscall signal(semaphore sem) { irqmask ps; register struct sentry *psem; ps = disable(); /* disable interrupts */ if ( isbadsem(sem) ) /* safety check */ { restore(ps); return SYSERR; } psem = &semtab[sem]; /* retrieve semaphore entry */ if ( (psem->count++) < 0 ) /* release one process from wait queue */ { ready(dequeue(psem->queue), RESCHED_YES); } restore(ps); /* restore interrupts */ return OK; } 34

  35. Semaphore: usage Problem 1: Create 3 tasks that each sleep for a random time and update a counter. Counter is the critical resources shared among the processes. Only one task can update the counter at a time so that counter value is correct. Problem 2: Create 3 tasks; task 1 updates the counter by 1 and then signal task 2 that updates the counter by 2 and then signals task 3 to update the counter by 3. 35

  36. Problem 1 #include <..> //declare semaphore semaphore mutex1 = newsem(1); int counter = 0; //declare functions: proc1,proc1, proc3 ready(create((void *)proc1, INITSTK, INITPRIO, PROC1",, 2, 0, NULL), RESCHED_NO); ready(create((void *)proc2, INITSTK, INITPRIO, PROC2",, 2, 0, NULL), RESCHED_NO); ready(create((void *)proc3, INITSTK, INITPRIO, PROC3",, 2, 0, NULL), RESCHED_NO); 36

  37. Problem 1: multi-tasks void proc1() { while (1) { sleep (rand()%10); wait(mutex1); counter++; signal(mutex1); } } void proc2() { while (1) { sleep (rand()%10); wait(mutex1); counter++; signal(mutex1); } } //similarly proc3 37

  38. Problem 1 Task 1 Counter1 Task 2 Task 3 38

  39. Problem 2 semaphore synch12 = newsem(0); semaphore synch23 = newsem(0); semaphore synch31 = newsem(0); ready(create((void *)proc1, INITSTK, INITPRIO, PROC1",, 2, 0, NULL), RESCHED_NO); ready(create((void *)proc2, INITSTK, INITPRIO, PROC2",, 2, 0, NULL), RESCHED_NO); ready(create((void *)proc3, INITSTK, INITPRIO, PROC3",, 2, 0, NULL), RESCHED_NO); signal(synch31); 39

  40. Task flow void proc1() void proc2() void proc3() { while (1) { sleep (rand()%10); wait(synch31); counter++; signal(synch12); } } { while (1) { sleep (rand()%10); wait(synch12); counter++; signal(synch23); } } { while (1) { sleep(rand()%10); wait(synch23); counter++; signal(synch31); } } 40

Related


More Related Content