代写代考 CSE4100: System Programming

Sogang University
Synchronization: Advanced
CSE4100: System Programming
Youngjae Kim (PhD)

Copyright By PowCoder代写 加微信 powcoder

https://sites.google.com/site/youkim/home
Distributed Computing and Operating Systems Laboratory (DISCOS)
https://discos.sogang.ac.kr
Office: R911, E-mail:
Bryant and O¡¯Hallaron, Computer Systems: A Programmer¡¯s Perspective, Third Edition

Sogang University
Review: Semaphores
¡é Semaphore: non-negative global integer synchronization
variable. Manipulated by P and V operations.
¡ì If s is nonzero, then decrement s by 1 and return immediately.
¡ì If s is zero, then suspend thread until s becomes nonzero and the
thread is restarted by a V operation.
¡ì After restarting, the P operation decrements s and returns control to the caller.
¡ì Increment s by 1.
¡ì If there are any threads blocked in a P operation waiting for s to become non-zero, then restart exactly one of those threads, which then completes its P operation by decrementing s.
¡é Semaphore invariant: (s >= 0) Bryant and O¡¯Hallaron, Computer Systems: A Programmer¡¯s Perspective, Third Edition

Sogang University
Review: Using semaphores to protect shared resources via mutual exclusion
¡é Basic idea:
¡ì Associate a unique semaphore mutex, initially 1, with each shared
variable (or related set of shared variables)
¡ì Surround each access to the shared variable(s) with P(mutex) and
V(mutex) operations
Bryant and O¡¯Hallaron, Computer Systems: A Programmer¡¯s Perspective, Third Edition

Sogang University
Using Semaphores to Coordinate Access to Shared Resources
¡é Basic idea: Thread uses a semaphore operation to notify another thread that some condition has become true
¡ì Use counting semaphores to keep track of resource state and to notify other threads
¡ì Use mutex to protect access to resource ¡é Two classic examples:
¡ì The Producer-Consumer Problem ¡ì The Readers-Writers Problem
Bryant and O¡¯Hallaron, Computer Systems: A Programmer¡¯s Perspective, Third Edition

Sogang University
Producer-Consumer Problem
Producer Consumer thread thread
¡é Common synchronization pattern:
¡ì Producer waits for empty slot, inserts item in buffer, and notifies consumer ¡ì Consumer waits for item, removes it from buffer, and notifies producer
¡é Examples
¡ì Multimedia processing:
¡ì Producer creates MPEG video frames, consumer renders them ¡ì Event-driven graphical user interfaces
¡ì Producer detects mouse clicks, mouse movements, and keyboard hits and inserts corresponding events in buffer
Shared buffer
¡ì Consumer retrieves events from buffer and paints the display Bryant and O¡¯Hallaron, Computer Systems: A Programmer¡¯s Perspective, Third Edition

Sogang University
Producer-Consumer on an n-element Buffer
¡é Requires a mutex and two counting semaphores:
¡ì mutex: enforces mutually exclusive access to the the buffer ¡ì slots: counts the available slots in the buffer
¡ì items: counts the available items in the buffer
¡é Implemented using a shared buffer package called sbuf.
Bryant and O¡¯Hallaron, Computer Systems: A Programmer¡¯s Perspective, Third Edition

Sogang University
sbuf Package – Declarations
#include “csapp.h¡±
typedef struct {
int front;
sem_t mutex;
sem_t slots;
sem_t items;
/* Buffer array */
/* Maximum number of slots */
/* buf[(front+1)%n] is first item */
/* buf[rear%n] is last item */
/* Protects accesses to buf */
/* Counts available slots */
/* Counts available items */
void sbuf_init(sbuf_t *sp, int n);
void sbuf_deinit(sbuf_t *sp);
void sbuf_insert(sbuf_t *sp, int item);
int sbuf_remove(sbuf_t *sp);
Bryant and O¡¯Hallaron, Computer Systems: A Programmer¡¯s Perspective, Third Edition

Sogang University
sbuf Package – Implementation Initializing and deinitializing a shared buffer:
/* Create an empty, bounded, shared FIFO buffer with n slots */
void sbuf_init(sbuf_t *sp, int n)
sp->buf = Calloc(n, sizeof(int));
sp->n = n;
sp->front = sp->rear = 0;
Sem_init(&sp->mutex, 0, 1);
Sem_init(&sp->slots, 0, n);
Sem_init(&sp->items, 0, 0);
/* Clean up buffer sp */
void sbuf_deinit(sbuf_t *sp)
Free(sp->buf);
/* Buffer holds max of n items */
/* Empty buffer iff front == rear */
/* Binary semaphore for locking */
/* Initially, buf has n empty slots */
/* Initially, buf has 0 items */
Bryant and O¡¯Hallaron, Computer Systems: A Programmer¡¯s Perspective, Third Edition

Sogang University
sbuf Package – Implementation Inserting an item into a shared buffer:
/* Insert item onto the rear of shared buffer sp */
void sbuf_insert(sbuf_t *sp, int item)
P(&sp->slots); /* Wait for available slot */
P(&sp->mutex); /* Lock the buffer */
sp->buf[(++sp->rear)%(sp->n)] = item; /* Insert the item */
V(&sp->mutex);
V(&sp->items);
/* Unlock the buffer */
/* Announce available item */ sbuf.c
Bryant and O¡¯Hallaron, Computer Systems: A Programmer¡¯s Perspective, Third Edition

Sogang University
sbuf Package – Implementation Removing an item from a shared buffer:
/* Remove and return the first item from buffer sp */
int sbuf_remove(sbuf_t *sp)
P(&sp->items); /* Wait for available item */
P(&sp->mutex); /* Lock the buffer */
item = sp->buf[(++sp->front)%(sp->n)]; /* Remove the item */
V(&sp->mutex);
V(&sp->slots);
} return item;
/* Unlock the buffer */
/* Announce available slot */
Bryant and O¡¯Hallaron, Computer Systems: A Programmer¡¯s Perspective, Third Edition

Sogang University
Readers-Writers Problem
¡é Generalization of the mutual exclusion problem
¡é Problem statement:
¡ì Reader threads only read the object
¡ì Writer threads modify the object
¡ì Writers must have exclusive access to the object
¡ì Unlimited number of readers can access the object
¡é Occurs frequently in real systems, e.g., ¡ì Online airline reservation system
¡ì Multithreaded caching Web proxy
Bryant and O¡¯Hallaron, Computer Systems: A Programmer¡¯s Perspective, Third Edition

Sogang University
Variants of Readers-Writers
¡é First readers-writers problem (favors readers)
¡ì No reader should be kept waiting unless a writer has already been granted permission to use the object
¡ì A reader that arrives after a waiting writer gets priority over the writer
¡é Second readers-writers problem (favors writers)
¡ì Once a writer is ready to write, it performs its write as soon as possible
¡ì A reader that arrives after a writer must wait, even if the writer is also waiting
¡é Starvation (where a thread waits indefinitely) is possible in both cases
Bryant and O¡¯Hallaron, Computer Systems: A Programmer¡¯s Perspective, Third Edition

Sogang University
Solution to First Readers-Writers Problem
Readers: Writers:
int readcnt; /* Initially = 0 */ sem_t mutex, w; /* Initially = 1 */
void reader(void) {
while (1) {
P(&mutex);
readcnt++;
if (readcnt == 1) /* First in */
V(&mutex);
/* Critical section */ /* Reading happens */
P(&mutex);
readcnt–;
if (readcnt == 0) /* Last out */
V(&mutex);
Bryant and O¡¯Hallaron, Computer Systems: A Programmer¡¯s Perspective, Third Edition
void writer(void)
while (1) {
/* Critical section */
/* Writing happens */

Sogang University
Putting It All Together: Prethreaded Concurrent Server
Client Client
Pool of worker threads
Service client Worker
Accept connections
Master descriptors Buffer
Remove descriptors
Bryant and O¡¯Hallaron, Computer Systems: A Programmer¡¯s Perspective, Third Edition
Service client
Worker thread

Sogang University
Prethreaded Concurrent Server
sbuf_t sbuf; /* Shared buffer of connected descriptors */
int main(int argc, char **argv)
int i, listenfd, connfd;
socklen_t clientlen;
struct sockaddr_storage clientaddr;
pthread_t tid;
listenfd = Open_listenfd(argv[1]);
sbuf_init(&sbuf, SBUFSIZE);
for (i = 0; i < NTHREADS; i++) /* Create worker threads */ Pthread_create(&tid, NULL, thread, NULL); while (1) { clientlen = sizeof(struct sockaddr_storage); connfd = Accept(listenfd, (SA *) &clientaddr, &clientlen); sbuf_insert(&sbuf, connfd); /* Insert connfd in buffer */ echoservert_pre.c Bryant and O¡¯Hallaron, Computer Systems: A Programmer¡¯s Perspective, Third Edition Sogang University Prethreaded Concurrent Server Worker thread routine: void *thread(void *vargp) Pthread_detach(pthread_self()); while (1) { int connfd = sbuf_remove(&sbuf); /* Remove connfd from buf */ echo_cnt(connfd); /* Service client */ Close(connfd); echoservert_pre.c Bryant and O¡¯Hallaron, Computer Systems: A Programmer¡¯s Perspective, Third Edition Sogang University Prethreaded Concurrent Server echo_cnt initialization routine: static int byte_cnt; /* Byte counter */ static sem_t mutex; /* and the mutex that protects it */ static void init_echo_cnt(void) Sem_init(&mutex, 0, 1); byte_cnt = 0; echo_cnt.c Bryant and O¡¯Hallaron, Computer Systems: A Programmer¡¯s Perspective, Third Edition Sogang University Prethreaded Concurrent Server Worker thread service routine: void echo_cnt(int connfd) char buf[MAXLINE]; rio_t rio; static pthread_once_t once = PTHREAD_ONCE_INIT; Pthread_once(&once, init_echo_cnt); Rio_readinitb(&rio, connfd); while((n = Rio_readlineb(&rio, buf, MAXLINE)) != 0) { P(&mutex); byte_cnt += n; printf("thread %d received %d (%d total) bytes on fd %d\n", (int) pthread_self(), n, byte_cnt, connfd); V(&mutex); Rio_writen(connfd, buf, n); echo_cnt.c Bryant and O¡¯Hallaron, Computer Systems: A Programmer¡¯s Perspective, Third Edition Sogang University Crucial concept: Thread Safety ¡é Functions called from a thread must be thread-safe ¡é Def: A function is thread-safe iff it will always produce correct results when called repeatedly from multiple concurrent threads ¡é Classes of thread-unsafe functions: ¡ì Class 1: Functions that do not protect shared variables ¡ì Class 2: Functions that keep state across multiple invocations ¡ì Class 3: Functions that return a pointer to a static variable ¡ì Class 4: Functions that call thread-unsafe functionsJ Bryant and O¡¯Hallaron, Computer Systems: A Programmer¡¯s Perspective, Third Edition Sogang University Thread-Unsafe Functions (Class 1) ¡é Failing to protect shared variables ¡ì Fix: Use P and V semaphore operations ¡ì Example: goodcnt.c ¡ì Issue: Synchronization operations will slow down code Bryant and O¡¯Hallaron, Computer Systems: A Programmer¡¯s Perspective, Third Edition Sogang University Thread-Unsafe Functions (Class 2) ¡é Relying on persistent state across multiple function invocations ¡ì Example: Random number generator that relies on static state static unsigned int next = 1; /* rand: return pseudo-random integer on 0..32767 */ int rand(void) next = next*1103515245 + 12345; return (unsigned int)(next/65536) % 32768; /* srand: set seed for rand() */ void srand(unsigned int seed) next = seed; } Bryant and O¡¯Hallaron, Computer Systems: A Programmer¡¯s Perspective, Third Edition Sogang University Thread-Safe Random Number Generator ¡é Pass state as part of argument ¡ì and, thereby, eliminate global state /* rand_r - return pseudo-random integer on 0..32767 */ int rand_r(int *nextp) *nextp = *nextp * 1103515245 + 12345; return (unsigned int)(*nextp/65536) % 32768; ¡é Consequence: programmer using rand_r must maintain seed Bryant and O¡¯Hallaron, Computer Systems: A Programmer¡¯s Perspective, Third Edition Sogang University Thread-Unsafe Functions (Class 3) ¡é Returning a pointer to a static variable ¡é Fix 1. Rewrite function so caller passes address of variable to store result ¡ì Requires changes in caller and callee ¡é Fix 2. Lock-and-copy ¡ì Requires simple changes in caller (and none in callee) ¡ì However, caller must free memory. Bryant and O¡¯Hallaron, Computer Systems: A Programmer¡¯s Perspective, Third Edition /* lock-and-copy version */ char *ctime_ts(const time_t *timep, char *privatep) char *sharedp; P(&mutex); sharedp = ctime(timep); strcpy(privatep, sharedp); V(&mutex); return privatep; Sogang University Thread-Unsafe Functions (Class 4) ¡é Calling thread-unsafe functions ¡ì Calling one thread-unsafe function makes the entire function that calls it thread-unsafe ¡ì Fix: Modify the function so it calls only thread-safe functionsJ Bryant and O¡¯Hallaron, Computer Systems: A Programmer¡¯s Perspective, Third Edition Sogang University Reentrant Functions ¡é Def: A function is reentrant iff it accesses no shared variables when called by multiple threads. ¡ì Important subset of thread-safe functions ¡ì Require no synchronization operations ¡ì Only way to make a Class 2 function thread-safe is to make it reetnrant (e.g., rand_r ) All functions Thread-safe functions Reentrant functions Thread-unsafe functions Bryant and O¡¯Hallaron, Computer Systems: A Programmer¡¯s Perspective, Third Edition Sogang University Thread-Safe Library Functions ¡é All functions in the Standard C Library (at the back of your K&R text) are thread-safe ¡ì Examples: malloc, free, printf, scanf ¡é Most Unix system calls are thread-safe, with a few exceptions: Thread-unsafe function gethostbyaddr gethostbyname Class Reentrant version 3 asctime_r 3 gethostbyaddr_r 3 gethostbyname_r 3 (none) 3 localtime_r Bryant and O¡¯Hallaron, Computer Systems: A Programmer¡¯s Perspective, Third Edition Sogang University One worry: Races ¡é A race occurs when correctness of the program depends on one thread reaching point x before another thread reaches point y /* A threaded program with a race */ int main() { pthread_t tid[N]; for (i = 0; i < N; i++) Pthread_create(&tid[i], NULL, thread, &i); for (i = 0; i < N; i++) Pthread_join(tid[i], NULL); exit(0); } /* Thread routine */ void *thread(void *vargp) int myid = *((int *)vargp); printf("Hello from thread %d\n", myid); return NULL; Bryant and O¡¯Hallaron, Computer Systems: A Programmer¡¯s Perspective, Third Edition N threads are sharing i Sogang University Race Illustration for (i = 0; i < N; i++) Pthread_create(&tid[i], NULL, thread, &i); Main thread Peer thread 0 myid = *((int *)vargp) ¡é Race between increment of i in main thread and deref of vargp in peer thread: ¡ì If deref happens while i = 0, then OK ¡ì Otherwise, peer thread gets wrong id value Bryant and O¡¯Hallaron, Computer Systems: A Programmer¡¯s Perspective, Third Edition Sogang University Could this race really occur? Main thread Peer thread for (i = 0; i < 100; i++) { Pthread_create(&tid, NULL, thread,&i); ¡é Race Test ¡ì If no race, then each thread would get different value of i ¡ì Set of saved values would consist of one copy each of 0 through 99 Bryant and O¡¯Hallaron, Computer Systems: A Programmer¡¯s Perspective, Third Edition void *thread(void *vargp) { Pthread_detach(pthread_self()); int i = *((int *)vargp); save_value(i); return NULL; Sogang University Experimental Results No Race Multicore server ¡é The race can really happen! Bryant and O¡¯Hallaron, Computer Systems: A Programmer¡¯s Perspective, Third Edition 0 2 4 6 8 101214161820222426283032343638404244464850525456586062646668707274767880828486889092949698 Single core laptop 0 2 4 6 8 101214161820222426283032343638404244464850525456586062646668707274767880828486889092949698 0 2 4 6 8 101214161820222426283032343638404244464850525456586062646668707274767880828486889092949698 Sogang University Race Elimination /* Threaded program without the race */ int main() { pthread_t tid[N]; int i, *ptr; for (i = 0; i < N; i++) { ptr = Malloc(sizeof(int)); Pthread_create(&tid[i], NULL, thread, ptr); for (i = 0; i < N; i++) Pthread_join(tid[i], NULL); /* Thread routine */ void *thread(void *vargp) int myid = *((int *)vargp); Free(vargp); printf("Hello from thread %d\n", myid); return NULL; nd O¡¯Hallaron, Computer Systems: A Programmer¡¯s Perspective, Third Edition ¡é Avoid unintended sharing of state Sogang University Another worry: Deadlock ¡é Def: A process is deadlocked iff it is waiting for a condition that will never be true ¡é Typical Scenario ¡ì Processes 1 and 2 needs two resources (A and B) to proceed ¡ì Process 1 acquires A, waits for B ¡ì Process 2 acquires B, waits for A ¡ì Both will wait forever! Bryant and O¡¯Hallaron, Computer Systems: A Programmer¡¯s Perspective, Third Edition Sogang University Deadlocking With Semaphores int main() { pthread_t tid[2]; Sem_init(&mutex[0], 0, 1); /* mutex[0] = 1 */ Sem_init(&mutex[1], 0, 1); /* mutex[1] = 1 */ Pthread_create(&tid[0], NULL, count, (void*) 0); Pthread_create(&tid[1], NULL, count, (void*) 1); Pthread_join(tid[0], NULL); Pthread_join(tid[1], NULL); printf("cnt=%d\n", cnt); void *count(void *vargp) int id = (int) vargp; for (i = 0; i < NITERS; i++) { P(&mutex[id]); P(&mutex[1-id]); V(&mutex[id]); V(&mutex[1-id]); return NULL; Bryant and O¡¯Hallaron, Computer Systems: A Programmer¡¯s Perspective, Third Edition Tid[0]: P(s0); P(s1); cnt++; V(s0); V(s1); Tid[1]: P(s1); P(s0); cnt++; V(s1); V(s0); Sogang University Deadlock Visualized in Progress Graph P(s0) P(s1) Deadlock state Locking introduces the potential for deadlock: waiting for a condition that will never be true Any trajectory that enters the deadlock region will eventually reach the deadlock state, waiting for either s0 or s1 to become nonzero Other trajectories luck out and skirt the deadlock region Unfortunate fact: deadlock is often nondeterministic (race) Forbidden region for s0 Deadlock region Bryant and O¡¯Hallaron, Computer Systems: A Programmer¡¯s Perspective, Third Edition Forbidden region for s1 Sogang University Avoiding Deadlock Acquire shared resources in same order int main() { pthread_t tid[2]; Sem_init(&mutex[0], 0, 1); /* mutex[0] = 1 */ Sem_init(&mutex[1], 0, 1); /* mutex[1] = 1 */ Pthread_create(&tid[0], NULL, count, (void*) 0); Pthread_create(&tid[1], NULL, count, (void*) 1); Pthread_join(tid[0], NULL); Pthread_join(tid[1], NULL); printf("cnt=%d\n", cnt); exit(0); } void *count(void *vargp) { int id = (int) vargp; for (i = 0; i < NITERS; i++) { P(&mutex[0]); P(&mutex[1]); cnt++; V(&mutex[id]); V(&mutex[1-id]); return NULL; Bryant and O¡¯Hallaron, Computer Systems: A Programmer¡¯s Perspective, Third Edition Tid[0]: P(s0); P(s1); cnt++; V(s0); V(s1); Tid[1]: P(s0); P(s1); cnt++; V(s1); V(s0); Sogang University Avoided Deadlock in Progress Graph P(s1) P(s0) No way for trajectory to get stuck Processes acquire locks in same order Order in which locks released immaterial Forbidden region for s0 Forbidden region 程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com