Sync Part1 Printable.pdf

Processes Synchronization - Part I Amir H. Payberah [email protected] Sep. 25, 2023 Processes Synchronization 1 / 46 Background I Processes can execute concurrently. I Concurrent access to shared data may result in data inconsistency. I Maintaining data consistency requires mechanisms to ens...

Processes Synchronization - Part I Amir H. Payberah [email protected] Sep. 25, 2023 Processes Synchronization 1 / 46 Background I Processes can execute concurrently. I Concurrent access to shared data may result in data inconsistency. I Maintaining data consistency requires mechanisms to ensure the orderly execution of cooperating processes. https://tinyurl.com/2yjcpx75 2 / 46 Producer-Consumer Problem I The producer-consumer problem. I Having an integer counter that keeps track of the number of items in the buffers. • Initially, counter is set to 0. • • The producer produces a new item: increment the counter The consumer consumes an item: decrement the counter 3 / 46 Producer I Producer while (true) { /* produce an item in next produced */ while (counter == BUFFER_SIZE); /* do nothing */ buffer[in] = next_produced; in = (in + 1) % BUFFER_SIZE; counter++; } 4 / 46 Consumer I Consumer while (true) { while (counter == 0); /* do nothing */ next_consumed = buffer[out]; out = (out + 1) % BUFFER_SIZE; counter--; /* consume the item in next consumed */ } 5 / 46 Race Condition I counter++ could be implemented as register1 = counter register1 = register1 + 1 counter = register1 I counter-- could be implemented as register2 = counter register2 = register2 - 1 counter = register2 I Consider this execution interleaving with count = 5 initially: S0: S1: S2: S3: S4: S5: producer: register1 = counter: register1 = 5 producer: register1 = register1 + 1: register1 = 6 consumer: register2 = counter: register2 = 5 consumer: register2 = register2 - 1: register2 = 4 producer: counter = register1: counter = 6 consumer: counter = register2: counter = 4 6 / 46 What’s The Output? int counter = 0; void* thread_func(void *arg) { counter++; printf("Job %d started.\n", counter); sleep(2); printf("Job %d finished.\n", counter); return NULL; } int main(void) { pthread_t t1, t2; pthread_create(&t1, NULL, &thread_func, NULL); pthread_create(&t2, NULL, &thread_func, NULL); pthread_join(t1, NULL); pthread_join(t2, NULL); return 0; } 7 / 46 What’s The Output? Job Job Job Job 1 2 2 2 started. started. finished. finished. 8 / 46 The Critical-Section (CS) Problem 9 / 46 The Critical-Section Problem (1/2) I Consider system of n processes {p0 , p1 , · · · , pn−1 }. I Each process has CS segment of code. • • Process may be changing common variables, updating table, writing file, etc. When one process in CS, no other may be in its CS. 10 / 46 The Critical-Section Problem (2/2) I Each process must ask permission to enter CS in entry section, may follow CS with exit section, then remainder section. I General structure of process Pi is below: 11 / 46 CS Problem Solution Requirements (1/3) I Mutual Exclusion: if process Pi is executing in its CS, then no other processes can be executing in their CSs. 12 / 46 CS Problem Solution Requirements (2/3) I Progress: if no process is executing in its CS and there exist some processes that wish to enter their CS, then the selection of the processes that will enter the CS next cannot be postponed indefinitely. 13 / 46 CS Problem Solution Requirements (3/3) I Bounded Waiting: a bound must exist on the number of times that other processes are allowed to enter their CSs after a process has made a request to enter its CS and before that request is granted. 14 / 46 CS Solutions I Peterson’s solution I Mutex lock I Semaphore 15 / 46 Peterson’s Solution 16 / 46 Peterson’s Solution I Two-process solution. I The two processes share two variables: • • int turn boolean flag[2] I turn: indicates whose turn it is to enter the CS. I flag: indicates if a process is ready to enter the CS, i.e., flag[i] = true implies that process Pi is ready. 17 / 46 Algorithm for Process Pi 18 / 46 CS Requirements I Provable that the three CS requirement are met: 1. Mutual exclusion is preserved: Pi enters CS only if: either flag[j] = false or turn = i 2. Progress requirement is satisfied. 3. Bounded-waiting requirement is met. 19 / 46 Mutex Locks 20 / 46 Mutex Locks I Protect a CS by first acquire() a lock then release() the lock. • I Calls to acquire() and release() must be atomic. • I Boolean variable indicating if lock is available or not. Usually implemented via hardware atomic instructions. But this solution requires busy waiting. • This lock therefore called a spinlock. 21 / 46 acquire() and release() acquire() { while (!available); /* busy wait */ available = false; } release() { available = true; } 22 / 46 23 / 46 pthread Mutexes I Mutexes are represented by the pthread mutex t object. I pthread mutex lock() locks (acquires) a pthreads mutex. int pthread_mutex_lock(pthread_mutex_t *mutex); I pthread mutex unlock() unlocks (releases) a pthreads mutex. int pthread_mutex_unlock(pthread_mutex_t *mutex); 24 / 46 What’s The Output? int counter = 0; pthread_mutex_t lock; void* thread_func(void *arg) { pthread_mutex_lock(&lock); counter++; printf("Job %d started.\n", counter); sleep(2); printf("Job %d finished.\n", counter); pthread_mutex_unlock(&lock); return NULL; } int main(void) { pthread_t t1, t2; pthread_mutex_init(&lock, NULL); pthread_create(&t1, NULL, &thread_func, NULL); pthread_create(&t2, NULL, &thread_func, NULL); pthread_join(t1, NULL); pthread_join(t2, NULL); pthread_mutex_destroy(&lock); return 0; } 25 / 46 What’s The Output? Job Job Job Job 1 1 2 2 started. finished. started. finished. 26 / 46 Semaphores 27 / 46 Semaphore I Synchronization tool that provides more sophisticated ways (than Mutex locks) for process to synchronize their activities. I Semaphore S: integer variable. I Accessed via two atomic operations: wait() and signal() 28 / 46 wait() and signal() wait(S) { while (S <= 0); // busy wait S--; } signal(S) { S++; } 29 / 46 Counting and Binary Semaphore I Counting semaphore: integer value can range over an unrestricted domain. I Binary semaphore: integer value can range only between 0 and 1. • Same as a mutex lock. 30 / 46 Semaphore Usage (1/2) I Initialize the semaphore to the number of available resources. I Call wait() before using a resource. I Call signal() after releasing a resource. I If S = 0: all resources are used, and processes that wish to use a resource will block until the count becomes greater than 0. 31 / 46 Semaphore Usage (2/2) I Consider P1 and P2 that require C1 to happen before C2. I Create a semaphore S initialized to 0. // Process P1 C1; signal(S); // Process P2 wait(S); C2; I The implementation still suffers from busy waiting. 32 / 46 Semaphore Implementation with no Busy Waiting (1/2) I With each semaphore there is an associated waiting queue. I Each entry in a waiting queue has two data items: • • Value (of type integer). Pointer to next record in the list. typedef struct { int value; struct process *list; } semaphore; 33 / 46 Semaphore Implementation with no Busy Waiting (2/2) I block: place the process invoking the operation on the appropriate waiting queue. I wakeup: remove one of processes in the waiting queue and place it in the ready queue. wait(semaphore *S) { S->value--; if (S->value < 0) { // add this process to S->list; block(); } } signal(semaphore *S) { S->value++; if (S->value <= 0) { // remove a process P from S->list; wakeup(P); } } 34 / 46 Deadlock I Deadlock: two or more processes are waiting indefinitely for an event that can be caused by only one of the waiting processes. I Let S and Q be two semaphores initialized to 1. 35 / 46 Starvation I Starvation: indefinite blocking. I A process may never be removed from the semaphore queue in which it is suspended. I If we remove processes from the list associated with a semaphore in LIFO (last-in, first-out) order. 36 / 46 37 / 46 POSIX Semaphore I sem open() creates a new semaphore or opens an existing one. sem_t *sem_open(const char * name , int oflag , ...); I sem wait() decrements the value of the semaphore. int sem_wait(sem_t *sem); I sem post() increments the value of the semaphore. int sem_post(sem_t *sem); 38 / 46 Parent-Child Example void parent() { sem_t *sem_id = sem_open(sem_name, O_CREAT, 0600, 0); // The parent waits for its child to print sem_wait(sem_id); printf("Parent: Child Printed!\n"); sem_close(sem_id); sem_unlink(sem_name); } void child() { sem_t *sem_id = sem_open(sem_name, O_CREAT, 0600, 0); printf("Child: Hello parent!\n"); sem_post(sem_id); } 39 / 46 Readers and Writers Problem 40 / 46 Readers and Writers Problem (1/3) I A shared data set among a number of concurrent processes: • • Readers: only read the data set; they do not perform any updates. Writers: can both read and write. I Problem: allow multiple readers to read at the same time, only one single writer can access the shared data at the same time. I Shared Data • • • Semaphore rw mutex initialized to 1. Semaphore mutex initialized to 1. Integer read count initialized to 0. 41 / 46 Readers and Writers Problem (2/3) I The writer process. do { wait(rw_mutex); ... /* writing is performed */ ... signal(rw_mutex); } while (true); 42 / 46 Readers and Writers Problem (3/3) I The reader process. do { wait(mutex); read_count++; if (read_count == 1) wait(rw_mutex); signal(mutex); ... /* reading is performed */ ... wait(mutex); read_count--; if (read_count == 0) signal(rw_mutex); signal(mutex); } while (true); 43 / 46 Summary 44 / 46 Summary I Access to shared data I The critical-section problem I Requirements: mutual-exclusion, progress, bounding waiting I CS solutions: • I Peterson solution, mutex lock, semaphore Reader/writer problem 45 / 46 Questions? Acknowledgements Some slides were derived from Avi Silberschatz slides. 46 / 46