Synchronization

Play an AI-generated podcast conversation about this lesson

Define Mutual Exclusion

A region of code may only be executed by one single thread at a time.

Define Producer-Consumer

One thread produces something that another thread needs to use/consume. we can just use a flag to indicate to another thread that an event has occurred, and we don't necessarily need hardware support for that.

Define Barrier

All threads must finish before moving past this point.

Explain why the following lock implementation is faulty.

                    Thread 0                       Thread 1
time 0: lock: ld R1, &lockvar.       
time 1: bnz R1, lock.                     lock: ld R1, &lockvar
time 2: sti &lockvar, #1                  bnz R1, lock
time 3:                                   sti &lockvar, #1

Both threads can acquire the lock here, because there is no atomicity. Signup and view all the answers

Explain how a test-and-set instruction works.

Read the value stored in memory location M, test the value against a constant, if they match, write the value in register Rx to the memory location M Signup and view all the answers

Write code to implement a mutual exclusion lock using a test-and-set instruction:

lock: t&s R1, &lockvar bnz R1, lock ret unlock: st &lockvar, #0 ret Signup and view all the answers

What are the four metrics used in evaluating lock implementations?

Uncontended Lock Acquisition, Traffic, Fairness, Storage Signup and view all the answers

Fill out the following table for the Test-and-Set lock: as time goes on (Init, t&s1, t&s2, t&s3, t&s2, unlock1, t&s2, t&s3, t&s3, unlock2, t&s3, unlock3) Include answer as an array of values <P1, P2, P3, Bus Request> So the init would be < -, -, -, - > and

< -, -, -, - >, <M, -, -, BusRdX>, <I, M, -, BusRdX>, <I, I, M, BusRdX>, <I, M, I, BusRdX>, <M, I, I, BusRdX>, <I, M, I, BusRdX>, <I, I, M, BusRdX>, <I, I, M,- > <I, M, I, BusRdX> <I, I, M, BusRdX> <I, I, M,- > Signup and view all the answers

Explain the Test and Test and Set Lock implementation. Explain why TTSL reduces traffic but increases uncontended lock acquisition latency.

Used to reduce contention on the lock variable. Basically, instead of issuing t&s instructions over and over again, we can check first to see if the lock variable seems to be available. If it is, then we can actually go ahead and do the t&s instruction and try to acquire the lock.The load instruction and the following branch instruction form a tight loop that keeps reading (but not writing) the address where lockvar is located until the value in the location turns 0. Therefore, while a lock is being held by a processor, other processors do not execute the test-and-set atomic instructions. This prevents repeated invalidations that are useless as they lead to failed lock acquisitions. Only when the lock is released, will the processors attempt to acquire the lock using the atomic instructions. The uncontended lock-acquisition latency is higher than the test-and-set lock implementation due to the extra load and branch instructions. However, the traffic during the time a lock is held is significantly reduced. Only a small fraction of lock acquisition attempts generate traffic. Signup and view all the answers

Write an implementation of a TTSL mutual exclusion lock:

lock: ld R1, &lockvar bnz R1, lock t&s R1, &lockvar bnz R1, lock ret unlock: st &lockvar, #0 ret Signup and view all the answers

Fill out the following table for the TTSL: as time goes on (Init, ld1, t&s1, ld2, ld3, ld2, unlock1, ld2, t&s2, ld3, ld3, unlock2, ld3, t&s3, unlock3) Include answer as an array of values <P1, P2, P3, Bus Request> So the init would be < -, -, -, - > and

< -, -, -, - >, <E, -, -, BusRd>, <M, -, -, - >, <S, S, -, BusRd >, <S, S, S, - >, <M, I, I, BusUpgr >, <S, S, I, BusRd >, <I, M, I, BusUpgr>, <I, S, S, BusRd>, <I, S, S, - >, <I, M, I, BusUpgr>, <I, S, S, BusRd>, <I, I, M, BusUpgr>, <I, I, M, - > Signup and view all the answers

What metric does a Ticket Lock and Array based lock improve on over other lock implementations?

Fairness Signup and view all the answers

Write code to implement ticket lock, and array based queue lock?

ticket_lock_init(int *next_ticket, int *now_serving) { *next_ticket = 0; *now_serving = 0; } ticket_lock_acquire(int *now_serving, int *next_ticket) { my_ticket = fetch_and_incr(next_ticket); while(*now_serving != my_ticket) {} } ticket_lock_release(int *next_ticket, int *now_serving) { (*now_serving)++; } ABQL: ABQL_init(int *next_ticket, int *can_serve) { *next_ticket = 0; for (i = 1; i < MAX_SIZE; i++) { can_serve[i] = 0; can_serve[0] = 1; } } ABQL_acquire(int *next_ticket, int *can_serve) { *my_ticket = fetch_and_incr(next_ticket); while(can_serve[*my_ticket] != 1) {} } ABQL_release(int *can_serve) { can_serve[*my_ticket + 1] = 1; can_serve[*my_ticket] = 0; } Signup and view all the answers

Describe LL/SC.

pair of instructions that give the illusion of atomicity A lock acquisition essentially consists of a load, some instructions like a branch, and then a store. Atomicity guarantees that either all three of these things happen, or none of them do. However, from the point of view of other processors, the only visible instruction is the store instruction. The load/read and branch are only visible to the local processor. So we can create the illusion by cancelling the store if something happens between the load and the store. Store Conditional : The execution of the store instruction is conditional upon a few things that would break the illusion of atomicity. If the address of the store matches the address written in the linked register mentioned below, then the store succeeds. Load Linked: A special load instruction that requires the monitoring of the validity of the block address. When it loads the block into a register, it also writes the address of the block into a special process register called a linked register. This linked register gets cleared when another processor does something that invalidates the block. Signup and view all the answers

Fill out the following table for LL/SC: as time goes on (Init,ll1, sc1, ll2, ll3, ll2, unlock1, ll2, sc2, ll3, ll3, unlock2, ll3, sc3, unlock3) Include answer as an array of values <P1, P2, P3, Bus Request> So the init would be < -, -, -, - > and

< -, -, -, - >, <E, -, -, BusRd>, <M, -, -, - >, <S, S, -, BusRd >, <S, S, S, - >, <S, S, S, BusUpgr >, <M, I, I, BusUpgr >, <S, S, I, BusRd >, <I, M, I, BusUpgr>, <I, S, S, BusRd>, <I, S, S, - >, <I, M, I, BusUpgr>, <I, S, S, BusRd>, <I, I, M, BusUpgr>, <I, I, M, - > Signup and view all the answers

Do Problem 2 in HW2. True if you get answers correct, false otherwise.

True Signup and view all the answers

Synchronization

Choose a study mode

Podcast

Questions and Answers

Define Mutual Exclusion

Define Producer-Consumer

Define Barrier

Explain why the following lock implementation is faulty.

`Thread 0 Thread 1 time 0: lock: ld R1, &lockvar. time 1: bnz R1, lock. lock: ld R1, &lockvar time 2: sti &lockvar, #1 bnz R1, lock time 3: sti &lockvar, #1`

Explain how a test-and-set instruction works.

Write code to implement a mutual exclusion lock using a test-and-set instruction:

What are the four metrics used in evaluating lock implementations?

Fill out the following table for the Test-and-Set lock: as time goes on (Init, t&s1, t&s2, t&s3, t&s2, unlock1, t&s2, t&s3, t&s3, unlock2, t&s3, unlock3) Include answer as an array of values <P1, P2, P3, Bus Request> So the init would be < -, -, -, - > and

Explain the Test and Test and Set Lock implementation. Explain why TTSL reduces traffic but increases uncontended lock acquisition latency.

Write an implementation of a TTSL mutual exclusion lock:

Fill out the following table for the TTSL: as time goes on (Init, ld1, t&s1, ld2, ld3, ld2, unlock1, ld2, t&s2, ld3, ld3, unlock2, ld3, t&s3, unlock3) Include answer as an array of values <P1, P2, P3, Bus Request> So the init would be < -, -, -, - > and

What metric does a Ticket Lock and Array based lock improve on over other lock implementations?

Write code to implement ticket lock, and array based queue lock?

Describe LL/SC.

Fill out the following table for LL/SC: as time goes on (Init,ll1, sc1, ll2, ll3, ll2, unlock1, ll2, sc2, ll3, ll3, unlock2, ll3, sc3, unlock3) Include answer as an array of values <P1, P2, P3, Bus Request> So the init would be < -, -, -, - > and

Do Problem 2 in HW2. True if you get answers correct, false otherwise.

More Like This

Synchronization Tools in Operating Systems

Synchronization Tools in Operating Systems

Process Synchronization

Synchronization in IoT and Embedded Systems

Upgrade to continue

Synchronization

Choose a study mode

Podcast

Questions and Answers

Define Mutual Exclusion

Define Producer-Consumer

Define Barrier

Explain why the following lock implementation is faulty. Thread 0 Thread 1 time 0: lock: ld R1, &lockvar. time 1: bnz R1, lock. lock: ld R1, &lockvar time 2: sti &lockvar, #1 bnz R1, lock time 3: sti &lockvar, #1

Explain how a test-and-set instruction works.

Write code to implement a mutual exclusion lock using a test-and-set instruction:

What are the four metrics used in evaluating lock implementations?

Fill out the following table for the Test-and-Set lock: as time goes on (Init, t&s1, t&s2, t&s3, t&s2, unlock1, t&s2, t&s3, t&s3, unlock2, t&s3, unlock3) Include answer as an array of values <P1, P2, P3, Bus Request> So the init would be < -, -, -, - > and

Explain the Test and Test and Set Lock implementation. Explain why TTSL reduces traffic but increases uncontended lock acquisition latency.

Write an implementation of a TTSL mutual exclusion lock:

Fill out the following table for the TTSL: as time goes on (Init, ld1, t&s1, ld2, ld3, ld2, unlock1, ld2, t&s2, ld3, ld3, unlock2, ld3, t&s3, unlock3) Include answer as an array of values <P1, P2, P3, Bus Request> So the init would be < -, -, -, - > and

What metric does a Ticket Lock and Array based lock improve on over other lock implementations?

Write code to implement ticket lock, and array based queue lock?

Describe LL/SC.

Fill out the following table for LL/SC: as time goes on (Init,ll1, sc1, ll2, ll3, ll2, unlock1, ll2, sc2, ll3, ll3, unlock2, ll3, sc3, unlock3) Include answer as an array of values <P1, P2, P3, Bus Request> So the init would be < -, -, -, - > and

Do Problem 2 in HW2. True if you get answers correct, false otherwise.

More Like This

Synchronization Tools in Operating Systems

Synchronization Tools in Operating Systems

Process Synchronization

Synchronization in IoT and Embedded Systems

Explain why the following lock implementation is faulty.

`Thread 0 Thread 1 time 0: lock: ld R1, &lockvar. time 1: bnz R1, lock. lock: ld R1, &lockvar time 2: sti &lockvar, #1 bnz R1, lock time 3: sti &lockvar, #1`