程序代做 Synchronization

Synchronization

The virtual memory of multithreaded applications
static data

Everything here is shared/
visible among all threads
within the same process!
Virtual memory

Also referred to as “producer-consumer” problem Producer places items in shared buffer
Consumer removes items from shared buffer
Recap: Bounded-Buffer Problem

Recap: We need to control accesses to the buffer!
int buffer[BUFF_SIZE]; // shared global
int main(int argc, char *argv[]) {
pthread_t p;
printf(“parent: begin\n”);
// init here
Pthread_create(&p, NULL, child, NULL);
int in = 0;
while(TRUE) {
int item = …;
printf(“parent: end\n”);
void *child(void *arg) {
int out = 0;
printf(“child\n”);
while(TRUE) {
// do something w/ item
return NULL;
buffer[in] = item;
in = (in + 1) % BUFF_SIZE;
int item = buffer[out];
out = (out + 1) % BUFF_SIZE;

Recap: Solving the “Critical Section Problem”
1. Mutual exclusion — at most one process/thread in its critical section
2. Progress—athreadoutsideofitscriticalsectioncannot block another thread from entering its critical section
3. Fairness—athreadcannotbepostponedindefinitelyfrom entering its critical section
4. Accommodatenondeterminism—thesolutionshouldwork regardless the speed of executing threads and the number of processors

Recap: Naive implementation
How many of the following can the naive implementation guarantee for the
producer-consumer problem?
1 Atmostoneprocess/threadinitscriticalsection
2 Athreadoutsideofitscriticalsectioncannotblockanotherthreadfromentering its critical section
3 Athreadcannotbepostponedindefinitelyfromenteringitscriticalsection
4 Thesolutionshouldworkregardlessthespeedofexecutingthreadsandthe number of processors
void Pthread_mutex_lock(volatile unsigned int *lock) { while (*lock == 1) // TEST (lock)
*lock = 1; // SET (lock)
void Pthread_mutex_unlock(volatile unsigned int *lock) {
*lock = 0;

Naive implementation
int buffer[BUFF_SIZE]; // shared global volatile unsigned int lock = 0;
int main(int argc, char *argv[]) {
printf(“parent: begin\n”)c;rashes/halts here?
void *child(void *arg) {
int out = 0;
printf(“child\n”);
while(TRUE) {
Pthread_mutex_lock(&lock);
int item = buffer[out];
out = (out + 1) % BUFF_SIZE; Pthread_mutex_unlock(&lock);
pthread_t p; what if the thread
// init here
Pthread_create(&p, NULL, child, NULL);
int in = 0;
while(TRUE) { }
} // do something w/ item
return NULL;
int item = …;
Pthread_mutex_lock(&lock);
void Pthread_mutex_lock(volatile unsigned int *lock) { while (*lock == 1) // TEST (lock)
buffer[in] = item;
in = (in + 1) % BUFF_SIZE;
all threads can see
what if context switch
*lock = 1;
coherence cache misses? page fault?
Pthread_mutex_unlock(&lock);
happens here?
lock as 0 at this point
printf(“parent: end\n”);
// SET (lock)
void Pthread_mutex_unlock(volatile unsigned int *lock)
*lock = 0; 7

Poll close in
How to achieve preemptive multitasking
A. Exception B. Interrupt
C. System calls
Which of the following mechanism are used to support
preemptive multitasking?

How preemptive multitasking works
After a certain period of time, the timer generates interrupt to force the running process transfer the control to OS kernel
If not — context switch
If yes, return to the process
Setup a timer (a hardware feature by the processor)event
before the process start running
The OS kernel code decides if the system wants to
continue the current process

How to achieve preemptive multitasking
A. Exception B. Interrupt
C. System calls
Which of the following mechanism are used to support
preemptive multitasking?

add %al,(%rax)
add %al,(%rbx)
div %ecx
trap return-from-trap
Three ways to invoke OS handlers
System calls / trap instructions — raised by applications Display images, play sounds
Exceptions — raised by processor itself Divided by zero, unknown memory addresses
Interrupts — raised by hardware Keystroke, network packets
user program
sbb %ecx,0x13(%rcx)
and %cl,(%rbx)
xor $0x19,%al
add %edx,(%rbx)
add 0x1bad(%eax),%dh
add %al,(%eax)
decb 0x52(%edi)
in $0x8d,%al
mov %eax,0x101c
lea -0x2bb84(%ebx),%eax
mov %eax,-0x2bb8a(%ebx)
lgdtl -0x2bb8c(%ebx)
lea -0x2bf3d(%ebx),%eax
push $0x10
return from …… exception handler ……
return from interrupt handler
…… …… …… ……
kernel/privileged mode

Poll close in
Disable interrupts?
How many of the following can the disable interrupts guarantee for the
producer-consumer problem?
1 Atmostoneprocess/threadinitscriticalsection
2 Athreadoutsideofitscriticalsectioncannotblockanotherthreadfromentering its critical section
3 Athreadcannotbepostponedindefinitelyfromenteringitscriticalsection
4 Thesolutionshouldworkregardlessthespeedofexecutingthreadsandthe number of processors

Disable interrupts?
How many of the following can the disable interrupts guarantee for the
producer-consumer problem?
1 Atmostoneprocess/threadinitscriticalsection
— threads on other processors can still run
2 Athreadoutsideofitscriticalsectioncannotblockanotherthreadfromentering its critical section
3 Athreadcannotbepostponedindefinitelyfromenteringitscriticalsection
— you can only disable the interrupt on the current processor
— now many of them can go…
4 Thesolutionshouldworkregardlessthespeedofexecutingthreadsandthe number of processors

We must use atomic instructions
int buffer[BUFF_SIZE]; // shared global volatile unsigned int lock = 0;
int main(int argc, char *argv[]) {
pthread_t p;
printf(“parent: begin\n”);
// init here
Pthread_create(&p, NULL, child, NULL);
int in = 0;
while(TRUE) {
int item = …;
Pthread_mutex_lock(&lock);
void *child(void *arg) {
int out = 0;
printf(“child\n”);
while(TRUE) {
Pthread_mutex_lock(&lock);
int item = buffer[out];
out = (out + 1) % BUFF_SIZE; Pthread_mutex_unlock(&lock); // do something w/ item
return NULL;
buffer[in] = item;
in = (in + 1) % BUFF_SIZE;
void Pthread_mutex_lock(volatile unsigned int *lock) { while (*lock == 1) // TEST (lock)
*lock = 1; // SET (lock)
— the lock must be updated atomically
void Pthread_mutex_unlock(volatile unsigned int *lock)
what if context switch
Pthread_mutex_unlock(&lock);
happens here?
printf(“parent: end\n”);
*lock = 0; 16

We must use atomic instructions
int buffer[BUFF_SIZE]; // shared global volatile unsigned int lock = 0;
int main(int argc, char *argv[]) {
void *child(void *arg) {
int out = 0;
printf(“child\n”);
while(TRUE) {
Pthread_mutex_lock(&lock);
int item = buffer[out];
out = (out + 1) % BUFF_SIZE; Pthread_mutex_unlock(&lock);
pthread_t p;
printf(“parent: begin\n”);
// init here
Pthread_create(&p, NULL, child, NULL);
int in = 0;
while(TRUE) {
int item = …;
Pthread_mutex_lock(&lock);
buffer[in] = item;
in = (in + 1) % BUFF_SIZE;
static inline uint x/c/hgd(ovosloamteitlheinugnswi/gnietdemint *addr, unsigned int new}val) {
uint result;return NULL;
asm vola}tile(“lock; xchgl %0, %1” : “+m” (*addr), “=a” (result) : “1” (newval) : “cc”);
Pthread_mutex_unlock(&lock);
printf(“parent: end\n”);
void Pthread_mutex_lock(volatile unsigned int *lock) {
// what code should go here?
void Pthread_mutex_unlock(volatile unsigned int *lock) {
// what code should go here?
return result; exchange the content in %0 and %1 a prefix to xchgl that locks the whole cache line

We must use atomic instructions
int buffer[BUFF_SIZE]; // shared global volatile unsigned int lock = 0;
int main(int argc, char *argv[]) {
void *child(void *arg) {
int out = 0;
printf(“child\n”);
while(TRUE) {
Pthread_mutex_lock(&lock);
int item = buffer[out];
out = (out + 1) % BUFF_SIZE; Pthread_mutex_unlock(&lock);
pthread_t p;
printf(“parent: begin\n”);
// init here
Pthread_create(&p, NULL, child, NULL);
int in = 0;
while(TRUE) {
int item = …;
Pthread_mutex_lock(&lock);
buffer[in] = item;
in = (in + 1) % BUFF_SIZE;
static inline uint x/c/hgd(ovosloamteitlheinugnswi/gnietdemint *addr, unsigned int new}val) {
printf(“parent: end\n”);
while (xchg(lock, 1) == 1); }
void Pthread_mutex_unlock(volatile unsigned int *lock) {
xchg(lock, 0); 18
uint result;return NULL;
asm vola}tile(“lock; xchgl %0, %1” : “+m” (*addr), “=a” (result) : “1” (newval) : “cc”);
return result;
Pthread_mutex_unlock(&lock);
void Pthread_mutex_lock(volatile unsigned int *lock) {

Semaphores

A synchronization variable
Access granted if val > 0, blocked if val == 0 Maintain a list of waiting processes
can proceed
Semaphores
Has an integer value — current value dictates if thread/process

Semaphore Operations
sem_wait(S)
if S > 0, thread/process proceeds and decrement S
if S == 0, thread goes into “waiting” state and placed in a special
sem_post(S)
if no one waiting for entry (i.e. waiting queue is empty), increment S otherwise, allow one thread in queue to proceed

Semaphore Op Implementations
sem_init(sem_t *s, int initvalue) {
s->value = initvalue;
sem_post(sem_t *s) {
s->value++;
wake_one_waiting_thread(); // if there is one
sem_wait(sem_t *s) {
while (s->value <= 0) put_self_to_sleep(); // put self to sleep s->value–;

Semaphore operations must operate atomically
set, etc.)
Atomicity in Semaphore Ops
Requires lower-level synchronization methods requires (test-and-
Most implementations still require on busy waiting in spinlocks •
What did we gain by using semaphores?
Easier for programmers Busy waiting time is limited

Poll close in
Adding Synchronization?
What variables to use for this problem?
int main(int argc, char *argv[]) {
int buffer[BUFF_SIZE]; // shared global sem_t filled, empty;
pthread_t p;
printf(“parent: begin\n”);
// init here
Pthread_create(&p, NULL, child, NULL); int in = 0;
Sem_init(&filled, 0);
Sem_init(&empty, BUFF_SIZE); while(TRUE) {
int item = …;
Sem_wait(&W);
buffer[in] = item;
in = (in + 1) % BUFF_SIZE; Sem_post(&X);
printf(“parent: end\n”);
void *child(void *arg) {
int out = 0;
printf(“child\n”);
while(TRUE) {
Sem_wait(&Y);
int item = buffer[out];
out = (out + 1) % BUFF_SIZE; // do something w/ item Sem_post(&Z);
return NULL;

int main(int argc, char *argv[]) {
int buffer[BUFF_SIZE]; // shared global sem_t filled, empty;
pthread_t p;
printf(“parent: begin\n”);
// init here
Pthread_create(&p, NULL, child, NULL); int in = 0;
Sem_init(&filled, 0);
Sem_init(&empty, BUFF_SIZE); while(TRUE) {
int item = …;
Sem_wait(&W);
buffer[in] = item;
in = (in + 1) % BUFF_SIZE; Sem_post(&X);
printf(“parent: end\n”);
void *child(void *arg) {
int out = 0;
printf(“child\n”);
while(TRUE) {
Sem_wait(&Y);
int item = buffer[out];
out = (out + 1) % BUFF_SIZE; // do something w/ item Sem_post(&Z);
return NULL;
Adding Synchronization?
What variables to use for this problem?

Poll close in
Are semaphores good enough?
How many of the following statements are correct regarding semaphores
implemented through atomic instructions?
1 Semaphorescanonlysupportlimitedamountofconcurrency/threads
2 Semaphorescanworkcorrectlyifoneofthethreadsgointoafaultystate
3 Semaphoresdonotpreventdeadlocksituations
4 Athreadenteringitscriticalsectionprotectedby(a)semaphore(s)maynotbe able to make meaningful progress during a scheduling quanta

Are semaphores good enough?
How many of the following statements are correct regarding semaphores
implemented through atomic instructions?
1 Semaphorescanonlysupportlimitedamountofconcurrency/threads
2 Semaphorescanworkcorrectlyifoneofthethreadsgointoafaultystate
3 Semaphoresdonotpreventdeadlocksituations
4 Athreadenteringitscriticalsectionprotectedby(a)semaphore(s)maynotbe able to make meaningful progress during a scheduling quanta

RCU Usage In the Linux Kernel: Eighteen
Years Later
Paul E. McKenney (Facebook), (Google), and -Wickize (MIT CSAIL) ACM SIGOPS Operating Systems Review Vol. 54, No. 1, August 2020, pp. 47–63.

Poll close in
RCU: Read-copy-update
• Considerthefollowinglinked-liststructure
How many of the following statements are true (or can be done) if we use RCU to traverse/update the data structure appropriately?
1 Anyrunningthreadcantraversethelinkedlistwithoutwaitingforalock
2 RCUcanonlyallowasmanyconcurrentreadingthreadsasthenumberofhardwarethreads(i.e.,numberofprocessorthreads).
3 IfathreadisremovingBfromthelistandreplacingBwithanewnodeE,Bcanonlybephysicallyremovedifallprecedingthreads traversing the linked list have completed
4 RCUisanimplementationofwait-freesynchronization

RCU: Read-copy-update
• Considerthefollowinglinked-liststructure
How many of the following statements are true (or can be done) if we use RCU to traverse/update the data structure appropriately?
1 Anyrunningthreadcantraversethelinkedlistwithoutwaitingforalock
2 RCUcanonlyallowasmanyconcurrentreadingthreadsasthenumberofhardwarethreads(i.e.,numberofprocessorthreads).
3 IfathreadisremovingBfromthelistandreplacingBwithanewnodeE,Bcanonlybephysicallyremovedifallprecedingthreads traversing the linked list have completed
4 RCUisanimplementationofwait-freesynchronization

API Name C Equivalent
rcu_read_lock() = rcu_read_unlock() rcu_assign_pointer(p, x) rcu_dereference(p) synchronize_rcu()
Simply disable/re-enable interrupts
Wait for existing RCU critical sections to complete

RCU: Read-copy-update
• Considerthefollowinglinked-liststructure
How many of the following statements are true (or can be done) if we use RCU to traverse/update the data structure appropriately?
1 Anyrunningthreadcantraversethelinkedlistwithoutwaitingforalock—Yes—justdisableinterrupt,deterministicoperations
2 RCUcanonlyallowasmanyconcurrentreadingthreadsasthenumberofhardwarethreads(i.e.,numberofprocessorthreads).
— Yes, because there are only these many processor available & all are running since interrupt are disabled
3 IfathreadisremovingBfromthelistandreplacingBwithanewnodeE,Bcanonlybephysicallyremovedifallprecedingthreads traversing the linked list have completed
4 RCUisanimplementationofwait-freesynchronization

Poll close in
Why disabling interrupts
How many of the following statements describing the reason why
rcu_read_lock disable interrupts
1 Guaranteemutualexclusionsforreads
2 Guaranteemutualexclusionsforupdates
3 Guaranteeallreaderscanruntofinishwithoutbeingcontextswitchedout 4 Simplifiestheimplementationofupdates

Why disabling interrupts
How many of the following statements describing the reason why
rcu_read_lock disable interrupts
1 Guaranteemutualexclusionsforreads
— (1) Does not help & (2) It’s never a goal of RCU 2 Guaranteemutualexclusionsforupdates—(1)Doesnothelp&(2)Youneedlocks
3 Guaranteeallreaderscanruntofinishwithoutbeingcontextswitchedout
4 Simplifiestheimplementationofupdates
— Yes — but why we need to guarantee this?
— Here is the reason!!!

rcu_read_lock
Processor #1
rcu_read_lock
synchronize_rcu
synchronize_rcu
RCU Update
rcu_read_unlock rcu_read_lock
rcu_read_unloc
synchronize_rcu
rcu_read_unlock
Processor #2
Processor #3 Processor #4
rcu_read_lock
synchronize_rcu
rcu_read_lock
rcu_read_unlock
synchronize_rcu
spinlock rcu_assign_pointer(p, x)
spin_unlock

程序代写 CS代考加微信: powcoder QQ: 1823890830 Email: powcoder@163.com

Related Posts