代写代考 COMP 3430 Guderian

Operating Systems
COMP 3430 Guderian

Atomic operations Bounded Buffer

test-and-set
More like… do a swap… atomically. This is psuedocode:
int TestAndSet(int *old_ptr, int new) {
int old = *old_ptr; // store old value at old_ptr *old_ptr = new; // Set our value
return old; // return the old value

This is a baffling piece of code
void lock(lock_t *lock) {
while (TestAndSet(&lock->flag, 1) == 1) ; // spin-wait (do nothing)
lock->flag = 0; //clean up

This is a baffling piece of code
void lock(lock_t *lock) {
while (TestAndSet(&lock->flag, 1) == 1) ; // spin-wait (do nothing)
lock->flag = 0; //clean up
Trying to set a 1 (true)

This is a baffling piece of code
void lock(lock_t *lock) {
while (TestAndSet(&lock->flag, 1) == 1) ; // spin-wait (do nothing)
lock->flag = 0; //clean up
Trying to set a 1 (true)
But got back a 1 (true)
That didn¡¯t change the value of the lock! Next time will also be a 1

Compare-and-swap
More understandable
Do a comparison, swap if the value was what we expected it to be

Pseudocode
int CAS(int* test, int old, int new){
int temp = *old;
if (*test == old){ *test = new;
return temp; }

How it is generally seen
Return true if swapped. Generally we are using 0=false, 1=true, so semantically the same.
bool CAS(int* test, int old, int new){ if (*test == old){
*test = new;
return true; }
return false; }

Use in locking
The lock looks familiar to TAS locking
// attempt to set a value. Loop while we can’t
void lock(lock_t *lock) {
while (CAS(&lock->flag, 0, 1) == 1) ; // spin-wait (do nothing)
Some other process sets the flag to 0 when done their CS

LoadLinked, StoreConditional is very similar to CAS, with more hardware support for some optimizations.

fetch-and-add
Imagine i++… but atomically… and it returns the value before the increment
int myTurn = fetchAndAdd(&countingLock) while (turn != myTurn) {}
turn++; // pass to next

Spin class
Spin lock wrap up
Even with optimizations, spin locks do not perform well
Questions about them?

Bounded buffer
Another case of growing an idea And, common issue in OSes
Q: Where have we seen a bounded buffer?

The 1010 solution
We have new things added to the queue, and consumers taking them out.
So… lock the whole thing!

The 1010 solution
We have new things added to the queue, and consumers taking them out.
So… lock the whole thing! Course-grain locking

The 1010 solution
We have new things added to the queue, and consumers taking them out.
So… lock the whole thing! Course-grain locking Ick

We¡¯re not in 1010

We¡¯re not in 1010
We¡¯re still spinlocking

Use a semaphore
aka a condition variable. But, generally, three operations:
For mutex we use 0 and 1.

Use a semaphore
aka a condition variable. But, generally, three operations:
A. initialize: initialize with a non-zero number
For mutex we use 0 and 1.

Use a semaphore
aka a condition variable. But, generally, three operations:
A. initialize: initialize with a non-zero number the # of concurrent tasks that can access
For mutex we use 0 and 1.

Use a semaphore
aka a condition variable. But, generally, three operations:
A. initialize: initialize with a non-zero number the # of concurrent tasks that can access
B. wait: decrement the value of the semaphore, block if the value is negative
C. signal: increment the value if value <= 0, unblock a waiting task. For mutex we use 0 and 1. Use a semaphore aka a condition variable. But, generally, three operations: A. initialize: initialize with a non-zero number the # of concurrent tasks that can access B. wait: decrement the value of the semaphore, block if the value is negative C. signal: increment the value if value <= 0, unblock a waiting task. if value > 0, there¡¯s no waiting tasks! For mutex we use 0 and 1.

Do we need to lock to add?
Add one, signal the consumer there is one ready. Consumer locks the buffer… and consumes

Semaphore solution v2
Use 2 locks, one for the in pointer, one for consuming
The producer can signal the consumer that work is available

Producer v2
sema lock; // initialized to 1 sema numdata; // initialized to 0 void produce(){
v = getNewData();
lock.wait()
buffer[in] = v;
lock.signal();
numdata.signal();

Consumer v2
Wait for signal to consume
int consume(){
numdata.wait();
x = buffer[out++];
return x; }

Semaphore solution v2

Semaphore solution v2
Mutex? Yes

Semaphore solution v2
Mutex? Yes
Cool? Yes!

Semaphore solution v2
Mutex? Yes
Cool? Yes!
Finite buffer, could get filled.

Semaphore solution v2
Mutex? Yes
Cool? Yes!
Finite buffer, could get filled. Solvable with more locks (of course)

Semaphore solution v3
What about just locking the ends?
Can we be more efficient by not locking the buffer at all?

Producer v3
sema inlock;
void produce(){
v = getNewData();
inlock.wait()
buffer[in] = v;
inlock.signal();

Consumer v3
sema outlock;
int consume(){
outlock.wait();
x = buffer[out++]; // also check if we’re over-running in outlock.signal();

Consumer v3
sema outlock;
int consume(){
outlock.wait();
x = buffer[out++]; // also check if we’re over-running in outlock.signal();
Can we safely read in?

Comparison v3

Comparison v3
Correct/Mutex?

Comparison v3
Correct/Mutex? Yes

Comparison v3
Correct/Mutex? Yes
Aggressive locking?

Comparison v3
Correct/Mutex? Yes
Aggressive locking? No

Comparison v3
Correct/Mutex? Yes
Aggressive locking? No
Efficient?

Comparison v3
Correct/Mutex? Yes
Aggressive locking? No
Efficient? Mmm… no

So, three solutions to do the same thing?
Yes! They all have some benefit, and show how we can look at the problem, and see different solutions!
And, it demonstrates signaling/semaphores!

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

Related Posts