Technische Universitt Mnchen
Chip Multicore Processors
Tutorial 5
S. Wallentowitz
Institute for Integrated Systems Theresienstr. 90 Building N1 www.lis.ei.tum.de
Technische Universitt Mnchen
Task 4.2: FiFo Implementation
In this task you will implement a FiFo memory in software.
a) Implement a (capacity bound) FiFo as circular buffer by using an array. b) Allow the parallel access to the FiFo by multiple threads using locks. c) Is it possible to use two locks for parallel access by reading and writing threads? d) Use a (POSIX) condition variable for synchronization. e) Can you implement this data structure in a non-blocking fashion? If not, how can you change the data structure to allow for it? f) Is it possible to implement an (unbounded) FiFo by using a linked list and without locking?
Chip Multicore Processors Tutorial 5 2 S. Wallentowitz
Institute for Integrated Systems
Technische Universitt Mnchen
FiFo Implementation
int data[N]; unsigned int start; unsigned int end; void enqueue(int d) { while(((end+1)%N)==start)) {} data[end] = d; end = (end+1)%N; } int dequeue() { int d; while(end==start) {} d=data[start]; start=(start+1)%N; return d; }
Chip Multicore Processors Tutorial 5 3 S. Wallentowitz
Institute for Integrated Systems
Technische Universitt Mnchen
Repetition: Lock with Mutex
void enqueue(int d) { mutex_lock(&lock); while(((end+1)%N)==start)) {} data[end] = d; end = (end+1)%N; mutex_unlock(&lock); } int dequeue() { int d; mutex_lock(&lock); while(end==start) {} d=data[start]; start=(start+1)%N; mutex_unlock(&lock); return d; }
Chip Multicore Processors Tutorial 5 4 S. Wallentowitz Institute for Integrated Systems
Technische Universitt Mnchen
Repetition: Lock with Mutex, solve starvation issue
void enqueue(int d) { mutex_lock(&lock); while(((end+1)%N)==start)) { mutex_unlock(&lock); mutex_lock(&lock); } data[end] = d; end = (end+1)%N; mutex_unlock(&lock); } int dequeue() { int d; mutex_lock(&lock); while(end==start) { mutex_unlock(&lock); mutex_lock(&lock); } d=data[start]; start=(start+1)%N; mutex_unlock(&lock); return d; }
Chip Multicore Processors Tutorial 5 5 S. Wallentowitz
Institute for Integrated Systems
Technische Universitt Mnchen
Reader and Writer Lock
void enqueue(int d) { while(((end+1)%N)==start)) {} while(end==start) {} data[end] = d; d=data[start]; end = (end+1)%N; int dequeue() { int d;
start=(start+1)%N;
} return d; }
Chip Multicore Processors Tutorial 5 6 S. Wallentowitz
Institute for Integrated Systems
Technische Universitt Mnchen
cond_wait(cond_t*,mutex_t*) cond_signal(cond_t*) cond_broadcast(cond_t*)
Condition Variable
void enqueue(int d) { mutex_lock(&rlock); if(((end+1)%N)==start)) { cond_wait(&wcond,&rlock); } data[end] = d; end = (end+1)%N; cond_signal(&rcond); mutex_unlock(&rlock); }
int dequeue() { int d; mutex_lock(&wlock); if(end==start) { cond_wait(&rcond,&wlock); } d=data[start]; start=(start+1)%N; cond_signal(&wcond); mutex_unlock(&wlock); return d; }
Chip Multicore Processors Tutorial 5 7 S. Wallentowitz
Institute for Integrated Systems
Technische Universitt Mnchen
Non-Blocking implementation
void enqueue(int d) { while(((end+1)%N)==start)) {} data[end] = d; end = (end+1)%N; } int dequeue() { int d;
while(end==start) {}
d=data[start]; start=(start+1)%N;
return d;
}
Chip Multicore Processors Tutorial 5 8 S. Wallentowitz Institute for Integrated Systems
Technische Universitt Mnchen
Non-Blocking implementation: Dequeue
int dequeue() { int d; int tmp; while(end==start) {} do { tmp = start; d=data[tmp]; } while(cas(start,tmp,(tmp+1)%N)); return d; }
Chip Multicore Processors Tutorial 5 9 S. Wallentowitz
Institute for Integrated Systems
Technische Universitt Mnchen
Non-Blocking implementation: Dequeue
int dequeue() { int d; int tmp; do { tmp = start; if (tmp==end) continue; d = data[tmp]; } while(cas(start,tmp,(tmp+1)%N)); return d; }
Chip Multicore Processors Tutorial 5 10 S. Wallentowitz
Institute for Integrated Systems
Technische Universitt Mnchen
Non-Blocking implementation: Enqueue
void enqueue(int d) { int tmp; do { tmp = end; if(((tmp+1)%N)==start)) continue; data[tmp] = d; } while(end,tmp,(tmp+1)%N); }
Chip Multicore Processors Tutorial 5 11 S. Wallentowitz
Institute for Integrated Systems
Technische Universitt Mnchen
Non-Blocking implementation: Enqueue
void enqueue(int d) { int tmp; do { tmp = end; if(((tmp+1)%N)==start)) continue; } while(end,tmp,(tmp+1)%N); data[tmp] = d; } int dequeue() { int d; int tmp; do { tmp = start; if (tmp==end) continue; d = data[tmp]; } while(cas(start,tmp,(tmp+1)%N)); return d; }
Chip Multicore Processors Tutorial 5 12 S. Wallentowitz
Institute for Integrated Systems
Technische Universitt Mnchen
Unbounded FiFo: Linked List
Chip Multicore Processors Tutorial 5 13 S. Wallentowitz
Institute for Integrated Systems
Technische Universitt Mnchen
Thinkable Solutions for Linked-List FiFo
Simple, fast, and practical non-blocking and blocking concurrent queue algorithms, M. Michael, M. Scott, PODC '96 A Pragmatic Implementation of Non-blocking Linked-lists, T. Harris, LNCS 2180 Chip Multicore Processors Tutorial 5 14 S. Wallentowitz
Institute for Integrated Systems
Technische Universitt Mnchen
Task 5.1: Semaphores
Explain the principle of semaphores. How do semaphores relate to mutexes?
Chip Multicore Processors Tutorial 5 15 S. Wallentowitz
Institute for Integrated Systems
Technische Universitt Mnchen
Semaphore
queue Q; int count;
Generalized concept for critical sections
Multiple resources available Allow multiple threads to enter section Mutex as binary semaphore init(int N) { count=N; } acquire() { count=count-1; if (count<0) { Q.enqueue(myself); suspend(); } }
Avoid starvation by queue of waiting threads Two basic functions
acquire(): Acquire resource, or Wait if not sufficient resources Historic name: P() (prolaag) release(): Release resource Wake up next waiting thread Historic name: V() (verhoogen)
release() { count=count+1; if(!Q.empty()) { wakeup(Q.dequeue()); } }
Chip Multicore Processors Tutorial 5 16 S. Wallentowitz
Institute for Integrated Systems
Technische Universitt Mnchen
Task 5.2: Readers-Writers Problem
The Readers-Writers Problem is a concurrency problem. A shared ressource is used by threads reading from it and others writing from it. No thread should access the ressource while it is written, but it is allowed that several readers read from the resource concurrently. Develop an optimal solution to this problem using semaphores.
Chip Multicore Processors Tutorial 5 17 S. Wallentowitz
Institute for Integrated Systems
Technische Universitt Mnchen
Readers-Writers Problem
void read(){ // the read action } void write() { // the write action }
Chip Multicore Processors Tutorial 5 18 S. Wallentowitz
Institute for Integrated Systems
Technische Universitt Mnchen
Readers-Writers Problem, mutex solution
semaphore sem = 1; void read(){ acquire(sem); // the read action release(sem); } void write() { acquire(sem); // the write action release(sem); }
Chip Multicore Processors Tutorial 5 19 S. Wallentowitz
Institute for Integrated Systems
Technische Universitt Mnchen
Readers-Writers Problem, 1. Solution
semaphore rsem = 1; semaphore wsem = 1; void read(){ acquire(rsem); // the read action release(rsem); } void write() { acquire(wsem); // the write action release(wsem); }
Chip Multicore Processors Tutorial 5 20 S. Wallentowitz
Institute for Integrated Systems
Technische Universitt Mnchen
Readers-Writers Problem, 1. Solution
semaphore rsem = 1; semaphore wsem = 1; void read(){ acquire(rsem); acquire(wsem); // the read action release(wsem); release(rsem); } void write() { acquire(wsem); // the write action release(wsem); }
Chip Multicore Processors Tutorial 5 21 S. Wallentowitz
Institute for Integrated Systems
Technische Universitt Mnchen
Readers-Writers Problem, 1. Solution
int counter = 0; void read(){ acquire(rsem); counter++; if(counter==1) acquire(wsem); release(rsem); // the read action acquire(rsem); counter--; if(counter==0) release(wsem); release(rsem); } void write() { acquire(wsem); // the write action release(wsem); }
Chip Multicore Processors Tutorial 5 22 S. Wallentowitz
Institute for Integrated Systems
Technische Universitt Mnchen
Readers-Writers Problem, 2. Solution
void read(){ acquire(mutex2); acquire(rsem); acquire(mutex0); rcount++; if(rcount==1) acquire(wsem); release(mutex0); release(rsem); release(mutex2); // the read action acquire(mutex0); rcount--; if(rcount=0) release(wsem); release(mutex0); } int wcount=0,rcount=0; semaphore mutex0=1,mutex1=1,mutex2=1; semaphore wsem=1,rsem=1;
void write() { acquire(mutex1); wcount++; if(wcount==1) acquire(rsem); release(mutex1); acquire(wsem); // the write action release(wsem); acquire(mutex1); wcount--; if(wcount==0) release(rsem); release(mutex1); }
Chip Multicore Processors Tutorial 5 23 S. Wallentowitz
Institute for Integrated Systems
