Synchronization PDF

Section 6: Synchronization Tools Operating System Concepts – 8th Edition, Silberschatz, Galvin and Gagne ©2009  Processes/Threads Synchronization Synchronization problems such as the Critical- Section Problem...

Section 6: Synchronization Tools Operating System Concepts – 8th Edition, Silberschatz, Galvin and Gagne ©2009  Processes/Threads Synchronization Synchronization problems such as the Critical- Section Problem Synchronization solutions: Hardware instructions Mutex locks Binary semaphores Counting semaphores Monitors Synchronization Examples Operating System Concepts – 8th Edition 6.2 Silberschatz, Galvin and Gagne ©2009  Objectives Introduce the critical-section problem, whose solutions can be used to ensure the consistency of shared data Present software and hardware synchronization primitives Describe different synchronization problems and solution approaches using synchronization primitives Operating System Concepts – 8th Edition 6.3 Silberschatz, Galvin and Gagne ©2009  Background/Motivation Cooperating processes have concurrent access to shared data: Threads: data section Processes: shared memory segment This sharing may result in data inconsistency (variables get values which cannot have occurred according to the algorithm) Maintaining data consistency requires mechanisms to ensure the orderly execution of cooperating threads Operating System Concepts – 8th Edition 6.4 Silberschatz, Galvin and Gagne ©2009  Race conditions/critical sections Operating System Concepts – 8th Edition 6.5 Silberschatz, Galvin and Gagne ©2009  The data consistency problem Data consistency problem: Ensuring data are consistent with the program semantic int sum = 0; thread(k..l){ memory int local-sum = 0; int temp; int i; for (i=k;ivalue++; if (S->value < 0) { if (S->value list; S->list; block(); } wakeup(P); } } } Operating System Concepts – 8th Edition 6.39 Silberschatz, Galvin and Gagne ©2009  Blocking Semaphores Negative semaphore values indicate the number of threads waiting on that semaphore Semaphore queues can be implemented as FIFO queue Operating System Concepts – 8th Edition 6.40 Silberschatz, Galvin and Gagne ©2009  Semaphores in Linux Linux has 3 different types of semaphores: 1- System V IPC semaphores and 2- Posix semaphores: named and unnamed Operating System Concepts – 8th Edition 6.41 Silberschatz, Galvin and Gagne ©2009  System V semaphores System V semaphores derive from Unix OSs, where they are part of inter- processes communication through shared memory segments System V semaphores are objects in the kernel (not in the user space), thus a system V semaphore can be used for inter-process synchronization System V semaphore commands: semget() returns the semid of a semaphore (an integer). semid is an index in a kernel array of semaphores semop() takes as argument a semid and a semaphore operation (such as increase, decrease or 0) All system V commands are system calls System V calls are costly because require context switches Operating System Concepts – 8th Edition 6.42 Silberschatz, Galvin and Gagne ©2009  System V semaphores The bash command ipcs –ls give the kernel configuration for system V semaphores The bash commands ipcs –s check on existing system V semaphores System V semaphores are persistent, they exist even after the processes have exited, must be explicitly removed using the command ipcrm –s semid System V semaphores are not much in use now, particularly for threads synchronization, because they are costly and complicated to use See C program semV.c for system V semaphore declarations Operating System Concepts – 8th Edition 6.43 Silberschatz, Galvin and Gagne ©2009  Named Posix semaphores There are two types of Posix semaphores: named and unnamed Named semaphores are created and deleted using commands sem_open(name) and sem_unlink(name) which creates a semaphore with id “name” and delete a semaphore with id “name” Named Posix semaphores are actual files in the file system and can be shared by multiple unrelated processes The id “name” is actually a file name See the program semNamed.c for an example of creating a named semaphore. The result will be a file stored in /dev/shm Actually /dev/shm is a simulation of a file directory files in /dev/shm are stored in main memory, rather than permanent storage on the hard disk This is why the declaration of the semaphore is sem_t *mutex_sem, i.e. a pointer to an object of type sem_t, the value return by sem_open() is indeed an address Operating System Concepts – 8th Edition 6.44 Silberschatz, Galvin and Gagne ©2009  Unnamed Posix semaphores Unnamed semaphores can be used across threads or across processes, in practice they are much more used in the context of multi-threading programming If synchronizing threads, they must be declared as global variables accessible to all threads If synchronizing processes, they must be declared in a shared memory segments shared by all the processes that are synchronized by the semaphore First, must declared a global variable of type sem_t such as sem_t sem The main unnamed commands are: int sem_init(sem_t *sem, int pshared, unsigned int value); initializes the semaphore. pshared indicates whether the semaphore is shared between threads (0) or processes (1). value specifies the initial value for the semaphore Operating System Concepts – 8th Edition 6.45 Silberschatz, Galvin and Gagne ©2009  Unnamed Posix semaphores The main unnamed commands are: int sem_post(sem_t *sem); increments (unlocks) the semaphore. If the semaphore's value consequently becomes greater than zero, then another thread blocked in a sem_wait() call will be woken up and proceed to lock the semaphore. int sem_wait(sem_t *sem); decrements (locks) the semaphore. If the semaphore currently has the value zero, then the call blocks until either it becomes possible to perform the decrement (i.e., the semaphore value rises above zero) int sem_destroy(sem_t *sem); See the program semUnNamed.c for an example of application of this type of semaphores All Posix semaphore commands are function calls Operating System Concepts – 8th Edition 6.46 Silberschatz, Galvin and Gagne ©2009  Category of semaphores In all OSs, there are two categories of semaphores: Binary semaphore – semaphores that can only take 2 values, 0 and 1. Counting semaphore – the value of the semaphore can have a wider range Operating System Concepts – 8th Edition 6.47 Silberschatz, Galvin and Gagne ©2009  Binary and counting semaphores The value of a binary semaphore is either 0 or 1 while a counting semaphore can take other values Examples of counting semaphore declarations in Linux, Windows and Java: Linux; sem_init(semName,0,8); (no difference between binary and counting) Windows: CreateSemaphore( NULL, // default security attributes INIT_COUNT, // initial value of the semaphore, 0 0 means there is a thread blocked on the next binary semaphore If next_count !> 0, then signal(mutex), let another thread enters the monitor The thread suspend itself on the x condition wait(x_sem) Operating System Concepts – 8th Edition 6.75 Silberschatz, Galvin and Gagne ©2009  Implementation of fct signal() The operation x.signal() can be implemented as: if (x_count > 0) { next_count++; signal(x_sem); wait(next); //thread block itself because 2 threads cannot execute in same time next_count--; } x_count > 0 means there is at least one thread suspended on condition x, signal(x_sem) wake up one thread The thread that executes signal() suspend itself on the binary semaphore next Operating System Concepts – 8th Edition 6.76 Silberschatz, Galvin and Gagne ©2009  Full implementation of monitors Variables semaphore mutex; // (binary, initially = 1) semaphore next; // (binary, initially = 0) int next_count = 0; // number of threads waiting to exit the monitor Each method P will be replaced by wait(mutex); //lock the monitor … body of P; … if (next_count > 0) signal(next) //unlock a thread else signal(mutex); //unlock the monitor Operating System Concepts – 8th Edition 6.77 Silberschatz, Galvin and Gagne ©2009  Condition Variables: Example Programmers don’t care about the implementation of the condition variables, just use them correctly For instance, in the producer-consumer problem, we should block a producer thread when the buffer is full or the consumer thread when the buffer is empty Two condition variables are needed: full and empty When the producer finds the buffer full, it does a wait() on condition variable “full” This action causes the calling thread to block, and allows another thread that had been previously prohibited from entering the monitor to enter now When the consumer finds the buffer empty, it does a wait() on condition variable “empty” This action causes a thread that was blocked in the monitor to resume activity Operating System Concepts – 8th Edition 6.78 Silberschatz, Galvin and Gagne ©2009  Monitor class for producer/consumer monitor ProducerConsumer condition full, empty; int count = 0; method add(); if (count == N) wait(full); // if buffer is full, block put_item(item); // put item in buffer count = count + 1; // increment count of full entries if (count == 1) signal(empty); // if buffer was empty, wake consumer method remove(); if (count == 0) wait(empty); // if buffer is empty, block remove_item(item); // remove item from buffer count = count - 1; // decrement count of full entries if (count == N-1) signal(full); // if buffer was full, wake producer end monitor; Operating System Concepts – 8th Edition 6.79 Silberschatz, Galvin and Gagne ©2009  Threads for producer/consumer Thread 1 Producer(); while (TRUE) { make_item(item); // make a new item ProducerConsumer.add; // call add method in monitor } Thread 2 Consumer(); while (TRUE) { ProducerConsumer.remove; // call method remove in monitor consume_item; // consume an item } Operating System Concepts – 8th Edition 6.80 Silberschatz, Galvin and Gagne ©2009  Posix condition variables Posix has condition variables which can be used in C programs. Synchronization commands for condition variables, wait() and signal(), behave the same way as those described earlier for monitor classes Posix condition variables are declared as follow: pthread_cond_t name-of-cond-var The Posix wait() fct for condition variables is defined as follow: int pthread_cond_wait(pthread_cond_t *c, pthread_mutex_t *m); The fct is called as follow: pthread(&c, &mutex); The pthread_cond_wait() has a Posix mutex parameter; it is assumed this mutex is initially locked by the thread calling wait() Upon calling the fct pthread_cond_wait(), the calling thread is suspended, placed in a waiting queue associated with the condition variable, and then the mutex is unlocked Operating System Concepts – 8th Edition 6.81 Silberschatz, Galvin and Gagne ©2009  Posix condition variables The Posix signal() fct for condition variables is defined as follow: int pthread_cond_signal ( pthread_cond_t * cond ); This fct is called by a thread to wake up one of the suspended threads on the condition variable cond When a suspended thread wakes up (after some other thread has signaled it), it must re-acquire the lock. The condition variables are initialized using the fct int pthread_cond_init ( pthread_cond_t *cond , const pthread_condattr_t * attr ); And used as follow pthread_cond_init(&c,NULL) where NULL is default initialization values Operating System Concepts – 8th Edition 6.82 Silberschatz, Galvin and Gagne ©2009  Simulating monitors with Posix conditions The C code condition.c shows how to simulate monitors in a C code upon using POSIX mutexes and condition variables. The program condition.c has one fct, thread() that is made a critical section using pthread_mutex_lock() at the entry and pthread_mutex_unlock() at the exit condition.c creates 3 threads calling the same thread() fct, the state ofa global variable done is not as it should be, thus all 3 threads get suspended on the condition variable cond1 A fourth thread is created after the state of variable done has been modified and is as what the program expects it to be That fourth thread awake one of the 3 suspended threads, the awaked thread then awake a second suspended thread, etc Operating System Concepts – 8th Edition 6.83 Silberschatz, Galvin and Gagne ©2009  End of Section 6 Operating System Concepts – 8th Edition, Silberschatz, Galvin and Gagne ©2009  Inter-processes communication: Shared Memory Segments Operating System Concepts – 8th Edition 6.85 Silberschatz, Galvin and Gagne ©2009  Examples of IPC Systems - POSIX POSIX Shared Memory Process first creates shared memory segment segment_id = shmget(IPC_PRIVATE, size, S IRUSR | S IWUSR); Process wanting access to that shared memory must attach to it shared_memory = (char *) shmat(segment_id, NULL, 0); Operating System Concepts – 8th Edition 6.86 Silberschatz, Galvin and Gagne ©2009  Examples of IPC Systems - POSIX Now the process could write to the shared memory sprintf(shared_memory, "Writing to shared memory"); When done a process can detach the shared memory from its address space shmdt(shared memory); Operating System Concepts – 8th Edition 6.87 Silberschatz, Galvin and Gagne ©2009  shmget int shmget(key_t key, size_t size, int flags); First parameter is the name (selected by programmer) of the segment (similar to file pathname). If key does not exist and IPC_CREATE specified in flags, then segment with “key” as identifier is created IPC_PRIVATE for the first parameter means the segment cannot be shared with other processes except children or invited, since the identifier of the segment is the value returns by shmget Operating System Concepts – 8th Edition 6.88 Silberschatz, Galvin and Gagne ©2009  shmget int shmget(key_t key, size_t size, int flags); Return value of shmget is an integer selected by the OS that identifies the shared ms, child processes must use the IPC identifier to access the share ms See flags for the description of the third argument Operating System Concepts – 8th Edition 6.89 Silberschatz, Galvin and Gagne ©2009  shmget Memory segment identifiers belong to the OS Must be explicitly de-allocated using shmctl( ) **** ipcrm and ipcs to get information on shared memory segments For example, ipcs –l give you info on shared memory limits Use the command ulimit –a to get information on linux processes limitations This command gives information about the computer architecture: /bin/cat /proc/cpuinfo | /bin/egrep 'processor|model name|cache size|core|sibling|physical' Operating System Concepts – 8th Edition 6.90 Silberschatz, Galvin and Gagne ©2009  Shared-memory Server #define SHMSZ 128 #include main() { char c;int shmid;key_t key; char *shm; key = 5678; shmid = shmget(key, SHMSZ, IPC_CREAT | 0666); Operating System Concepts – 8th Edition 6.91 Silberschatz, Galvin and Gagne ©2009  Shared-memory Server while (*shm != '*') sleep(1); exit(0); } Operating System Concepts – 8th Edition 6.92 Silberschatz, Galvin and Gagne ©2009  Shared-memory client #define SHMSZ 128 main() { int shmid; key_t key; char *shm, *s; key = 5678; (shmid = shmget(key, SHMSZ, 0666) Operating System Concepts – 8th Edition 6.93 Silberschatz, Galvin and Gagne ©2009  Shared-memory client printf("*%s*\n", shm); *shm = '*'; exit(0); } Operating System Concepts – 8th Edition 6.94 Silberschatz, Galvin and Gagne ©2009