Answered step by step
Verified Expert Solution
Question
1 Approved Answer
2. Reader Writer Spinlock (Challenge) This problem is intended to be somewhat harder than the others. You will implement a multiple-reader, single-writer lock as a
2. Reader Writer Spinlock (Challenge) This problem is intended to be somewhat harder than the others. You will implement a multiple-reader, single-writer lock as a spinlock. Here is the description: struct sharedlock { int value; // when the lock is created, value is initialized to a }; It allows multiple readers OR one single writer, and there are four functions: reader_acquire(struct sharedlock*) reader_release (struct sharedlock*) writer_acquire(struct sharedlock*) writer_release(struct sharedlock*) We have given you the first of these, and your task is to write the last three of these. Each of these three functions only needs to be a single line of code. When the lock is unlocked (no readers or writers holding the lock), its value is 0. When there are one or more readers holding the lock (that is, multiple threads have completed reader_acquire() but have not called reader_release), the lock's value equals the number of readers. When the lock is held by a writer (i.e., a thread has made it past writer_acquire but has not called writer_release), its value is - 1. We are unconcerned here with fairness, efficiency, or starvation; just write something that is safe and that eventually allows a waiting thread, reader or writer, to make progress, even though a waiting writer may have to wait until there are no readers. Assume that the lock is never acquired by an interrupt handler, so you don't need to worry about enabling and disabling interrupts. You may also assume that the hardware provides sequential consistency. You will likely need to call two atomic primitives, described below: int cmpxchg_val(intaddr, int oldval, int newval): This is an atomic operation that compares oldval to addr, and if the two are equal, it sets saddr = newval. It returns the old contents of addr. void atomic_decrement(int* arg): This atomically performs *arg = *arg - 1. (We also include their pseudocode and inline assembly implementations in an appendix. However, you do not need this appendix material to do the problem.) // we are giving you the code for the first of the four functions: void reader_acquire(struct sharedlock* lock) { int curr_val; while (1) { // spin while a writer owns the lock while ((curr_val = lock->value) == -1) {} assert(curr_val >= e); // try to atomically increment the count, based on our best // guess of how many readers there had been. if we were // wrong, keep looping. if we got it right, then we // succeeded in incrementing the count atomically, and we // can proceed. if (cmpxchg_val(&lock->value, curr_val, curr_val + 1) == curr_val) break; // lock -> value now contains curr_val + 1 } Write the other three functions! (Again, each needs only a single line of code.) 2. Reader Writer Spinlock (Challenge) This problem is intended to be somewhat harder than the others. You will implement a multiple-reader, single-writer lock as a spinlock. Here is the description: struct sharedlock { int value; // when the lock is created, value is initialized to a }; It allows multiple readers OR one single writer, and there are four functions: reader_acquire(struct sharedlock*) reader_release (struct sharedlock*) writer_acquire(struct sharedlock*) writer_release(struct sharedlock*) We have given you the first of these, and your task is to write the last three of these. Each of these three functions only needs to be a single line of code. When the lock is unlocked (no readers or writers holding the lock), its value is 0. When there are one or more readers holding the lock (that is, multiple threads have completed reader_acquire() but have not called reader_release), the lock's value equals the number of readers. When the lock is held by a writer (i.e., a thread has made it past writer_acquire but has not called writer_release), its value is - 1. We are unconcerned here with fairness, efficiency, or starvation; just write something that is safe and that eventually allows a waiting thread, reader or writer, to make progress, even though a waiting writer may have to wait until there are no readers. Assume that the lock is never acquired by an interrupt handler, so you don't need to worry about enabling and disabling interrupts. You may also assume that the hardware provides sequential consistency. You will likely need to call two atomic primitives, described below: int cmpxchg_val(intaddr, int oldval, int newval): This is an atomic operation that compares oldval to addr, and if the two are equal, it sets saddr = newval. It returns the old contents of addr. void atomic_decrement(int* arg): This atomically performs *arg = *arg - 1. (We also include their pseudocode and inline assembly implementations in an appendix. However, you do not need this appendix material to do the problem.) // we are giving you the code for the first of the four functions: void reader_acquire(struct sharedlock* lock) { int curr_val; while (1) { // spin while a writer owns the lock while ((curr_val = lock->value) == -1) {} assert(curr_val >= e); // try to atomically increment the count, based on our best // guess of how many readers there had been. if we were // wrong, keep looping. if we got it right, then we // succeeded in incrementing the count atomically, and we // can proceed. if (cmpxchg_val(&lock->value, curr_val, curr_val + 1) == curr_val) break; // lock -> value now contains curr_val + 1 } Write the other three functions! (Again, each needs only a single line of code.)
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started