程序代写代做代考 x86 Java C assembly kernel graph Carnegie Mellon

程序代写 CS代考 / C语言代写, Java代写代考, kernel, x86汇编代写代考

Carnegie Mellon
Synchronization: Basics
15-213: Introduction to Computer Systems 25th Lecture, April 16, 2020
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 1

Carnegie Mellon
Today
 Threads review  Sharing
 Mutual exclusion  Semaphores
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 2

Carnegie Mellon
Traditional View of a Process
 Process = process context + code, data, and stack
Process context
Code, data, and stack
SP
brk
PC
0
Stack
Shared libraries
Run-time heap
Read/write data
Read-only code/data
Program context:
Data registers Condition codes Stack pointer (SP) Program counter (PC)
Kernel context: VM structures
Descriptor table brk pointer
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
3

Carnegie Mellon
Alternate View of a Process
 Process = thread + (code, data, and kernel context)
Thread (main thread) Code, data, and kernel context
brk
PC
0
Shared libraries
Run-time heap
Read/write data
Read-only code/data
SP
Stack
Thread context: Data registers
Condition codes Stack pointer (SP) Program counter (PC)
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
4
Kernel context: VM structures
Descriptor table brk pointer

Carnegie Mellon
A Process With Multiple Threads
 Multiple threads can be associated with a process
 Each thread has its own logical control flow
 Each thread shares the same code, data, and kernel context  Each thread has its own stack for local variables
 but not protected from other threads  Each thread has its own thread id (TID)
Thread 1 (main thread) Thread 2 (peer thread)
stack 1 stack 2
Shared code and data
shared libraries
run-time heap
read/write data
read-only code/data
Thread 1 context: Data registers Condition codes SP1
PC1
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
5
Thread 2 context: Data registers Condition codes SP2
PC2
0
Kernel context: VM structures
Descriptor table brk pointer

Don’t let picture confuse you!
Thread 1 (main thread) Thread 2 (peer thread)
stack 1 stack 2
Shared code and data
Carnegie Mellon
shared libraries
run-time heap
read/write data
read-only code/data
Thread 1 context: Data registers Condition codes SP1
PC1
Thread 2 context: Data registers Condition codes SP2
PC2
Memory is shared between all threads
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
0
Kernel context: VM structures
Descriptor table brk pointer
6

Carnegie Mellon
Today
 Threads review
 Sharing
 Mutual exclusion
 Semaphores
 Producer-Consumer Synchronization
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 7

Carnegie Mellon
Shared Variables in Threaded C Programs
 Question: Which variables in a threaded C program are shared?
 The answer is not as simple as “global variables are shared” and “stack variables are private”
 Def: A variable x is shared if and only if multiple threads reference some instance of x.
 Requires answers to the following questions:  What is the memory model for threads?
 How are instances of variables mapped to memory?
 How many threads might reference each of these instances?
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 8

Carnegie Mellon
Threads Memory Model: Conceptual
 Multiple threads run within the context of a single process
 Each thread has its own separate thread context  Thread ID, stack, stack pointer, PC, condition codes, and GP registers
 All threads share the remaining process context
 Code, data, heap, and shared library segments of the process virtual address space
 Open files and installed handlers
Thread 1 (private) stack 1
Thread 2 (private) stack 2
shared libraries
run-time heap
read/write data
read-only code/data
Thread 1 context: Data registers Condition codes SP1
PC1
Thread 2 context: Data registers Condition codes SP2
PC2
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 9
Shared code and data

Carnegie Mellon
Threads Memory Model: Actual
 Separation of data is not strictly enforced:
 Register values are truly separate and protected, but…
 Any thread can read and write the stack of any other thread
stack 1
Virtual Address Space
Shared code and data
stack 2
Thread 1 (private)
Thread 2 (private)
shared libraries
run-time heap
read/write data
read-only code/data
Thread 1 context: Data registers Condition codes SP1
PC1
Thread 2 context: Data registers Condition codes SP2
PC2
The mismatch between the conceptual and operation model
is a source of confusion and errors
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 10

Carnegie Mellon
Passing an argument to a thread – Pedantic
int hist[N] = {0};
int main(int argc, char *argv[]) {
long i;
pthread_t tids[N];
for (i = 0; i < N; i++) { long* p = Malloc(sizeof(long)); *p = i; Pthread_create(&tids[i], NULL, thread, (void *)p); } for (i = 0; i < N; i++) Pthread_join(tids[i], NULL); check(); } Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 11 void *thread(void *vargp) { hist[*(long *)vargp] += 1; Free(vargp); return NULL; } void check(void) { for (int i=0; i ./badcnt 10000
OK cnt=20000
linux> ./badcnt 10000
BOOM! cnt=13051
linux>
badcnt.c: Improper Synchronization
cnt should equal 20,000.
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition What went wrong? 27

Carnegie Mellon
Assembly Code for Counter Loop
C code for counter loop in thread i
for (i = 0; i < niters; i++) cnt++; Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 28 Asm code for thread i movq (%rdi), %rcx testq %rcx,%rcx jle .L2 movl $0, %eax .L3: movq cnt(%rip),%rdx addq $1, %rdx movq %rdx, cnt(%rip) .L2: addq $1, %rax cmpq %rcx, %rax jne .L3 Hi : Head Li : Load cnt Ui : Update cnt Si : Store cnt Ti : Tail Carnegie Mellon Concurrent Execution  Key idea: In general, any sequentially consistent* interleaving is possible, but some give an unexpected result!  Ii denotes that thread i executes instruction I  %rdxi is the content of %rdx in thread i’s context i (thread) instri %rdx1 %rdx2 cnt 1 H1 - - 0 1 L1 0 - 0 1 U1 1 - 0 1 S1 1 - 1 2 H2 - - 1 2 L2 - 1 1 2 U2 - 2 1 2 S2 - 2 2 2 T2 - 2 2 1 T1 1 - 2 *For now. In reality, on x86 even non-sequentially consistent interleavings are possible Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 29 OK Carnegie Mellon Concurrent Execution  Key idea: In general, any sequentially consistent interleaving is possible, but some give an unexpected result!  Ii denotes that thread i executes instruction I  %rdxi is the content of %rdx in thread i’s context i (thread) instri %rdx1 %rdx2 cnt 1 H1 - - 0 1 L1 0 - 0 1 U1 1 - 0 1 S1 1 - 1 2 H2 - - 1 2 L2 - 1 1 2 U2 - 2 1 2 S2 - 2 2 2 T2 - 2 2 1 T1 1 - 2 Thread 1 critical section Thread 2 critical section OK Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 30 Carnegie Mellon Concurrent Execution (cont)  Incorrect ordering: two threads increment the counter, but the result is 1 instead of 2 i (thread) instri %rdx1 %rdx2 cnt 1 H1 - - 0 1 L1 0 - 0 1 U1 1 - 0 2 H2 - - 0 2 L2 - 0 0 1 S1 1 - 1 1 T1 1 - 1 2 U2 - 1 1 2 S2 - 1 1 2 T2 - 1 1 Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 31 Oops! Carnegie Mellon Concurrent Execution (cont)  How about this ordering? i (thread) instri %rdx1 %rdx2 cnt 1 H1 0 1 L1 0 2 H2 2 L2 0 2 U2 1 2 S2 1 1 1 U1 1 1 S1 1 1 1 T1 1 2 T2 1  We can analyze the behavior using a progress graph Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 32 Oops! Carnegie Mellon Progress Graphs Thread 2 A progress graph depicts the discrete execution state space of concurrent threads. Each axis corresponds to the sequential order of instructions in a thread. Each point corresponds to a possible execution state (Inst1, Inst2). E.g., (L1, S2) denotes state where thread 1 has completed L1 and thread 2 has completed S2. T2 S2 U2 L2 H2 (L1, S2) H1 L1 U1 S1 T1 Thread 1 Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 33 Carnegie Mellon Trajectories in Progress Graphs Thread 2 T2 S2 U2 L2 H2 A trajectory is a sequence of legal state transitions that describes one possible concurrent execution of the threads. Example: H1, L1, U1, H2, L2, S1, T1, U2, S2, T2 H1 L1 U1 S1 T1 Thread 1 Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 34 Carnegie Mellon Trajectories in Progress Graphs Thread 2 T2 S2 U2 L2 H2 A trajectory is a sequence of legal state transitions that describes one possible concurrent execution of the threads. Example: H1, L1, U1, H2, L2, S1, T1, U2, S2, T2 H1 L1 U1 S1 T1 Thread 1 Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 35 Carnegie Mellon Critical Sections and Unsafe Regions Thread 2 T2 S2 critical section wrt cnt L2 H2 critical section wrt cnt Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition L, U, and S form a critical section with respect to the shared variable cnt Instructions in critical sections (wrt some shared variable) should not be interleaved Sets of states where such interleaving occurs form unsafe regions Thread 1 U2 Unsafe region H1 L1 U1 S1 T1 36 Carnegie Mellon Critical Sections and Unsafe Regions Thread 2 T2 S2 critical section wrt cnt L2 H2 critical section wrt cnt Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition safe U2 Def: A trajectory is safe iff it does not enter any unsafe region Claim: A trajectory is correct (wrt cnt) iff it is safe unsafe Unsafe region H1 L1 U1 S1 T1 Thread 1 37 badcnt.c: Improper Synchronization niters.m main thread1 Carnegie Mellon /* Global shared variable */ volatile long cnt = 0; /* Counter */ int main(int argc, char **argv) { long niters; pthread_t tid1, tid2; niters = atoi(argv[1]); Pthread_create(&tid1, NULL, thread, &niters); Pthread_create(&tid2, NULL, thread, &niters); Pthread_join(tid1, NULL); Pthread_join(tid2, NULL); /* Check result */ if (cnt != (2 * niters)) printf("BOOM! cnt=%ld\n", cnt); else printf("OK cnt=%ld\n", cnt); exit(0); cnt tid1.m i.1 i.2 } badcnt.c /* Thread routine */ void *thread(void *vargp) { long i, niters = *((long *)vargp); for (i = 0; i < niters; i++) cnt++; return NULL; Variable } niters.1 thread2 Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition niters.2 38 badcnt.c: Improper Synchronization /* Thread routine */ void *thread(void *vargp) { long i, niters = *((long *)vargp); for (i = 0; i < niters; i++) cnt++; return NULL; Variable } thread1 Carnegie Mellon /* Global shared variable */ volatile long cnt = 0; /* Counter */ int main(int argc, char **argv) { long niters; pthread_t tid1, tid2; niters = atoi(argv[1]); Pthread_create(&tid1, NULL, thread, &niters); Pthread_create(&tid2, NULL, thread, &niters); Pthread_join(tid1, NULL); Pthread_join(tid2, NULL); /* Check result */ if (cnt != (2 * niters)) printf("BOOM! cnt=%ld\n", cnt); else printf("OK cnt=%ld\n", cnt); exit(0); } badcnt.c cnt tid1.m i.1 main yes* yes no yes no thread2 yes niters.m yes no no no yes no no i.2 no yes niters.1 no yes no Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition niters.2 no no yes 39 Carnegie Mellon Break Time! Check out: Quiz: day 25: Synchronization Basic https://canvas.cmu.edu/courses/31656 Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 40 Carnegie Mellon #include "csapp.h" #define N 2 void *thread(void *vargp); long *pointers[N]; int main(int argc, char *argv[]) { long i; pthread_t tids[N]; Bonus Quiz Question 6: for (i = 0; i < N; i++) Pthread_create(&tids[i], NULL, thread, (void *) i); sleep(1); // Sleep-#1 for (i = 0; i < N; i++) printf("Thread id %u has local value %ld\n", (int) tids[i], *pointers[i]); for (i = 0; i < N; i++) Pthread_join(tids[i], NULL); return 0; void *thread(void *vargp) { long myid = (long) vargp; pointers[myid] = &myid; sleep(2); // Sleep-2 return NULL; } If the statement labeled "Sleep #1" is kept, the main thread might have a segmentation fault when referencing "pointers“?  True?  False? } Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 41 Carnegie Mellon Today  Threads review  Sharing  Mutual exclusion  Semaphores  Producer-Consumer Synchronization Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 43 Carnegie Mellon Enforcing Mutual Exclusion  Question: How can we guarantee a safe trajectory?  Answer: We must synchronize the execution of the threads so that they can never have an unsafe trajectory.  i.e., need to guarantee mutually exclusive access for each critical section.  Classic solution:  Semaphores (Edsger Dijkstra)  Other approaches (out of our scope)  Mutex and condition variables (Pthreads)  Monitors (Java) Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 44 Carnegie Mellon Semaphores  Semaphore: non-negative global integer synchronization variable. Manipulated by P and V operations.  P(s)  If s is nonzero, then decrement s by 1 and return immediately.  Test and decrement operations occur atomically (indivisibly)  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.  V(s):  Increment s by 1.  Increment operation occurs atomically  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 45

Carnegie Mellon
Semaphores
 Semaphore: non-negative global integer synchronization variable
 Manipulated by P and V operations:
 P(s): [ while (s == 0) wait(); s–; ]
 Dutch for “Proberen” (test) V(s): [ s++; ]
 Dutch for “Verhogen” (increment)
 OS kernel guarantees that operations between brackets [ ] are
executed indivisibly
 Only one P or V operation at a time can modify s.
 When while loop in P terminates, only that P can decrement s
 Semaphore invariant: (s >= 0)
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 46

Carnegie Mellon
C Semaphore Operations Pthreads functions:
#include
int sem_init(sem_t *s, 0, unsigned int val);} /* s = val */
int sem_wait(sem_t *s); /* P(s) */
int sem_post(sem_t *s); /* V(s) */
CS:APP wrapper functions:
#include “csapp.h”
void P(sem_t *s); /* Wrapper function for sem_wait */ void V(sem_t *s); /* Wrapper function for sem_post */
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 47

Carnegie Mellon
/* Global shared variable */
volatile long cnt = 0; /* Counter */
int main(int argc, char **argv)
{
long niters;
pthread_t tid1, tid2;
niters = atoi(argv[1]); Pthread_create(&tid1, NULL,
thread, &niters);
Pthread_create(&tid2, NULL,
thread, &niters);
Pthread_join(tid1, NULL);
Pthread_join(tid2, NULL);
/* Check result */
if (cnt != (2 * niters))
printf(“BOOM! cnt=%ld\n”, cnt);
else
printf(“OK cnt=%ld\n”, cnt); exit(0);
}
badcnt.c
/* Thread routine */
void *thread(void *vargp)
{
long i, niters =
*((long *)vargp);
for (i = 0; i < niters; i++) cnt++; return NULL; } badcnt.c: Improper Synchronization Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 48 How can we fix this using semaphores? Carnegie Mellon Using Semaphores for Mutual Exclusion  Basic idea:  Associate a unique semaphore mutex, initially 1, with each shared variable (or related set of shared variables).  Surround corresponding critical sections with P(mutex) and V(mutex) operations.  Terminology:  Binary semaphore: semaphore whose value is always 0 or 1  Mutex: binary semaphore used for mutual exclusion  P operation: “locking” the mutex  V operation: “unlocking” or “releasing” the mutex  “Holding” a mutex: locked and not yet unlocked.  Counting semaphore: used as a counter for set of available resources. Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 49 Carnegie Mellon goodcnt.c: Proper Synchronization  Define and initialize a mutex for the shared variable cnt: volatile long cnt = 0; /* Counter */ sem_t mutex; /* Semaphore that protects cnt */ sem_init(&mutex, 0, 1); /* mutex = 1 */  Surround critical section with P and V: for (i = 0; i < niters; i++) { P(&mutex); cnt++; V(&mutex); } goodcnt.c Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 50 linux> ./goodcnt 10000
OK cnt=20000
linux> ./goodcnt 10000
OK cnt=20000
linux>
Warning: It’s orders of magnitude slower than badcnt.c.

Carnegie Mellon
goodcnt.c: Proper Synchronization  Define and initialize a mutex for the shared variable cnt:
volatile long cnt = 0; /* Counter */
sem_t mutex; /* Semaphore that protects cnt */
sem_init(&mutex, 0, 1); /* mutex = 1 */
 Surround critical section with P and V:
for (i = 0; i < niters; i++) { P(&mutex); cnt++; V(&mutex); } Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 51 Function Time (ms) niters = 106 goodcnt.c lbinaudxc>n.t/goodcngtoo1d00c0n0t OK cnt=20000
Warning: It’s orders of magnitude slower than badcnt.c.
12.0 450.0
linux> ./goodcnt 10000
OK cnt=20000
linux>
Slowdown
1.0
37.5

Carnegie Mellon
Why Mutexes Work
Thread 2
T2
V(s)
S2
U2 L2 P(s)
H2
H1 P(s) L1 U1 S1 V(s) T1 Initially
Provide mutually exclusive access to shared variable by surrounding critical section with P and V operations on semaphore s (initially set to 1)
Unsafe region
-1 0
1000
Thread 1
s= 1
52
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition

Carnegie Mellon
Why Mutexes Work
Thread 2
T2
V(s)
S2
U2 L2 P(s)
H2
H1 P(s) L1 U1 S1 V(s) T1 Initially
Provide mutually exclusive access to shared variable by surrounding critical section with P and V operations on semaphore s (initially set to 1)
Semaphore invariant
creates a forbidden region that encloses unsafe region and that cannot be entered by any trajectory.
0
s= 1
53
1000
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
Unsafe region
-1
Thread 1

Carnegie Mellon
Why Mutexes Work
Thread 2
T2
V(s)
S2
U2 L2 P(s)
H2
H1 P(s) L1 U1 S1 V(s) T1 Initially
Provide mutually exclusive access to shared variable by surrounding critical section with P and V operations on semaphore s (initially set to 1)
Semaphore invariant
creates a forbidden region that encloses unsafe region and that cannot be entered by any trajectory.
Unsafe region
0
0
01
s= 1
54
1000
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
Thread 1

Carnegie Mellon
Why Mutexes Work
Thread 2
11000011
T2
V(s)
S2
U2 L2 P(s)
H21 1 0 0 0 0 1 1 Initially H1 P(s) L1 U1 S1 V(s) T1
s= 1
Provide mutually exclusive access to shared variable by surrounding critical section with P and V operations on semaphore s (initially set to 1)
Semaphore invariant
creates a forbidden region that encloses unsafe region and that cannot be entered by any trajectory.
11000011
0 0
Forbidden region
0 0
-1 -1 -1 -1 -1 -1 -1 -1
Unsafe region
-1 -1 -1 -1 -1 -1 -1 -1
00 00
00 00
00 00
11000011
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
55
Thread 1

Carnegie Mellon
Binary Semaphores – For Mutual Exlusion
 Mutex is special case of semaphore
 Value either 0 or 1
 Pthreads provides pthread_mutex_t
 Operations: lock, unlock
 Recommended over general semaphores when
appropriate
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 56

goodmcnt.c: Mutex Synchronization  Define and initialize a mutex for the shared variable cnt:
for (i = 0; i < niters; i++) { pthread_mutex_lock(&mutex); cnt++; pthread_mutex_unlock(&mutex); } Function Time (ms) niters = 106 goodcnt.c badcnt 12.0 linux> ./goodmcnt 10000
OK cnt=20000
linux> ./goodmcnt 10000
OK cnt=20000
linux>
goodcnt
450.0
37.5
Carnegie Mellon
volatile long cnt = 0; /* Counter */
pthread_mutex_t mutex;
pthread_mutex_init(&mutex, NULL); // No special attributes
 Surround critical section with lock and unlock:
goodmcnt
214.0
Slowdown 1.0
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
17.8
57

Carnegie Mellon
Today
 Threads review
 Sharing
 Mutual exclusion
 Semaphores
 Producer-Consumer Synchronization
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 58

Carnegie Mellon
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.  Use binary semaphores to notify other threads.
 The Producer-Consumer Problem
 Mediating interactions between processes that generate
information and that then make use of that information
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 59

Carnegie Mellon
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 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
 Consumer retrieves events from buffer and paints the display
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 60
shared buffer

Carnegie Mellon
Producer-Consumer on 1-element Buffer
 Maintain two semaphores: full + empty
full
0
empty
1
full
1
empty
0
empty buffer
full buffer
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 61

Carnegie Mellon
Producer-Consumer on 1-element Buffer
#include “csapp.h”
#define NITERS 5
void *producer(void *arg);
void *consumer(void *arg);
struct {
int buf; /* shared var */
sem_t full; /* sems */
sem_t empty;
} shared;
int main(int argc, char** argv) {
pthread_t tid_producer;
pthread_t tid_consumer;
/* Initialize the semaphores */
Sem_init(&shared.empty, 0, 1);
Sem_init(&shared.full, 0, 0);
/* Create threads and wait */
Pthread_create(&tid_producer, NULL,
producer, NULL);
Pthread_create(&tid_consumer, NULL,
consumer, NULL);
Pthread_join(tid_producer, NULL);
Pthread_join(tid_consumer, NULL);
return 0; }
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 62

Carnegie Mellon
Producer-Consumer on 1-element Buffer
Initially: empty==1, full==0
Producer Thread Consumer Thread
void *producer(void *arg) {
int i, item;
for (i=0; i= n)
error();
if (++rear >= n) rear = 0;
buf[rear] = v;
items++;
}
int remove()
{
if (items == 0) error();
if (++front >= n) front = 0;
int v = buf[front];
items–;
return v;
}
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 68

Carnegie Mellon
Producer-Consumer on an n-element Buffer P1 Between 0 and n elements C1
  
Pn Cm
 Requires a mutex and two counting semaphores:
 mutex: enforces mutually exclusive access to the buffer and counters  slots: counts the available slots in the buffer
 items: counts the available items in the buffer
 Makes use of general semaphores  Will range in value from 0 to n

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 69

Carnegie Mellon
sbuf Package-Declarations
#include “csapp.h”
typedef struct {
int *buf;
/* Buffer array */ /* Maximum number of slots */ /* buf[front+1 (mod n)] is first item */ /* buf[rear] is last item */ /* Protects accesses to buf */
int n;
int front;
int rear;
sem_t mutex;
sem_t slots; /* Counts available slots */
sem_t items; /* Counts available items */
} sbuf_t;
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
70
sbuf.h

Carnegie Mellon
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; /* Buffer holds max of n items */ sp->front = sp->rear = 0; /* Empty buffer iff front == rear */ Sem_init(&sp->mutex, 0, 1); /* Binary semaphore for locking */ Sem_init(&sp->slots, 0, n); /* Initially, buf has n empty slots */ Sem_init(&sp->items, 0, 0); /* Initially, buf has zero items */
}
/* Clean up buffer sp */
void sbuf_deinit(sbuf_t *sp)
{
Free(sp->buf);
}
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
71
sbuf.c

Carnegie Mellon
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);
P(&sp->mutex);
if (++sp->rear >= sp->n)
sp->rear = 0; sp->buf[sp->rear] = item; V(&sp->mutex); V(&sp->items);
/* Wait for available slot */
/* Lock the buffer */
/* Increment index (mod n) */
/* Insert the item */ /* Unlock the buffer */ /* Announce available item */
sbuf.c
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 72

Carnegie Mellon
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)
{
int item;
P(&sp->items);
P(&sp->mutex);
if (++sp->front >= sp->n)
sp->front = 0;
item = sp->buf[sp->front];
V(&sp->mutex);
V(&sp->slots);
return item;
}
/* Wait for available item */
/* Lock the buffer */
/* Increment index (mod n) */
/* Remove the item */
/* Unlock the buffer */
/* Announce available slot */
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 73
sbuf.c

Carnegie Mellon
Demonstration
 See program produce-consume.c in code directory
 10-entry shared circular buffer
 5 producers
 Agent i generates numbers from 20*i to 20*i – 1.  Puts them in buffer
 5 consumers
 Each retrieves 20 elements from buffer
 Main program
 Makes sure each value between 0 and 99 retrieved once
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 74

Carnegie Mellon
Summary
 Programmers need a clear model of how variables are shared by threads.
 Variables shared by multiple threads must be protected to ensure mutually exclusive access.
 Semaphores are a fundamental mechanism for enforcing mutual exclusion.
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 75

Related Posts