12/04/2022, 09:24 Exam/Concurrency – COMP3231/COMP9201/COMP3891/COMP9283
Concurrency
1. Concurrency
1. What is a race condition? Give an example.
Copyright By PowCoder代写 加微信 powcoder
2. What is a critical region? How do they relate to
controlling access to shared resources?
3. What are four requirements of any solution to
the critical sections problem? Why are the
requirements needed?
4. Why is turn passing a poor solution to the
critical sections problem?
5. Interrupt disabling and enabling is a common
approach to implementing mutual exclusion.
What are its advantages and disadvantages?
6. What is a test-and-set instruction? How can it be
used to implement mutual exclusion? Consider using a fragment of pseudo-assembly language aid your explanation.
7. What is the producer-consumer problem? Give an example of its occurrence in operating systems.
8. A semaphore is a blocking synchronisation primitive. Describe how they work with the aid of pseudo-code. You can assume the existence of a thread_block() and a thread_wakeup() function.
9. Describe how to implement a lock using semaphores.
10. What are monitors and condition variables?
What is a race condition? Give an example.
A race condition occurs when there is an uncoordinated concurrent access to shared resources (e.g. memory or device registers), which leads to deadlocks, lost work or incorrect and inconsistent program behaviour.
An example would be two process updating a counter simultaneously. Say the counter has a value of 1. Ideally this would happen: Process A reads that counter is 1. Process A increments the counter from 1 to 2. Process B reads that counter is 2. Process B increments the counter from 2 to 3.
However, this can also happen: Process A reads that counter is 1. Process B reads that counter is 1. Process A increments the counter from 1 to 2. Process B increments the counter from 1 to 2, overwriting process A’s value of counter (also 2).
What is a critical region? How do they relate to controlling access to shared resources?
A critical region is an area of code where shared resources are accessed. As a result, we need to coordinate access to the critical region in order to ensure that the outcome of our code is deterministic. This usually means ensuring that the shared resources are not changed or viewed by other threads while one thread is executing inside the critical region.
https://wiki.cse.unsw.edu.au/cs3231cgi/Exam/Concurrency
12/04/2022, 09:24 Exam/Concurrency – COMP3231/COMP9201/COMP3891/COMP9283
What are four requirements of any solution to the critical sections problem? Why are the requirements needed?
Mutual Exclusion: No two processes simultaneously in critical region.
No assumptions about the speeds or the number of CPUs.
Progress: No process running outside its critical region may block another process. Bounded: No process waits forever to enter its critical region.
Why is turn passing a poor solution to the critical sections problem?
A thread must wait for its turn, even if the other thread is doing something unrelated. If different threads use the critical region at different rates, performance is limited by the most infrequent user, i.e. the system progresses at the rate of the slowest thread. If one thread no longer needs its turns, the other thread may not progress.
Interrupt disabling and enabling is a common approach to implementing mutual exclusion. What are its advantages and disadvantages?
Advantages:
It’s easy and efficient on a uniprocessor.
Disadvantages:
Doesn’t work on multiprocessors as other processors can access resources in parallel. Only works in the kernel.
Slows interrupt response time. Blocks all other processes even if they don’t use the protected shared memory.
What is a test-and-set instruction? How can it be used to implement mutual exclusion? Consider using a fragment of pseudo-assembly language aid your explanation.
Test-and-set is an atomic instruction (meaning uninterruptable) which copies a lock and returns its original value. Then, if the lock is 0, this means it was unlocked, so test-and-set will set the lock to 1 (to lock it). Otherwise, if the lock is 1, this means that someone else is holding the lock.
Pseudo-assembly code for lock_acquire and lock_release:
lock_acquire:
tsl register, lock
‘register’
cmp register, 0
jne lock_acquire
lock, so loop
lock_release:
move lock, 0
// try to set the lock, and copy the lock to
// was lock zero?
// if it was non zero, we didn’t get the
// return to caller, critical region entered
// set lock to zero to release it.
https://wiki.cse.unsw.edu.au/cs3231cgi/Exam/Concurrency
12/04/2022, 09:24 Exam/Concurrency – COMP3231/COMP9201/COMP3891/COMP9283
Therefore test-and-set can be used to implement a lock variable, which can be used to implement mutual exclusion.
What is the producer-consumer problem? Give an example of its occurrence in operating systems.
The producer-consumer problem is a problem that involves filling and depleting a bounded buffer. The producer inserts entries into the buffer as long as it is not full. The consumer must retrieve data from the buffer as long as it is not empty. Transactions on the buffer itself may require a mutual exclusion.
Example: IO buffering.
Buffer is bounded by its size.
When the user process is reading, the IO device is the producer and the user process is the consumer. Similarly, when the user process is writing, the IO device is the consumer and the user process is the producer.
A semaphore is a blocking synchronisation primitive. Describe how they work with the aid of pseudo-code. You can assume the existence of a thread_block() and a thread_wakeup() function.
A semaphore has two operations:
P (proberen/decrement/wait) atomically reduces a counter by 1. If the counter is now negative, the current thread blocks until the counter is at least 0.
V (verhogen/increment/signal) atomically increases a counter by 1. It wakes one thread sleeping on this semaphore, if any.
Pseudocode:
P (semaphore sem) {
sem.count–
if (sem.count < 0) {
sleep the current thread.
enqueue(curthread, sem.queue)
thread_sleep(curthread)
V (semaphore sem) {
sem.count++;
if (sem.count <= 0) {
processes, wake one up.
thread = dequeue(sem.queue)
the queue.
thread_wakeup(thread)
// If count becomes negative,
// Add this thread to semaphore
// If there are blocked
// Wake up process at the head of
Describe how to implement a lock using semaphores.
We can implement a lock using a semaphore by initialising the semaphore to 1. The count of a semaphore is effectively the number that may be allowed before preventing more in, so if it is
https://wiki.cse.unsw.edu.au/cs3231cgi/Exam/Concurrency
12/04/2022, 09:24 Exam/Concurrency - COMP3231/COMP9201/COMP3891/COMP9283
1, it acts as a lock. For example:
semaphore sem = sem_create("sem", 1);
// Initialise semaphore.
// Decrement semaphore or acquire lock.
critical_region();
// Increment semaphore or release lock.
What are monitors and condition variables?
Monitors are a programming language construct designed to simplify control of concurrent access. Code related to a shared resource (and the shared resource itself) is placed in a monitor, then the compiler ensures that there is only one thread executing inside the monitor at a time. When thread calls monitor method while monitor is processing another thread, it is queued and sleeps until other thread exits monitor.
Condition variables are entities used within monitors to block and wait for an event, the operations 'wait' waits for the event to occur and 'signal' operation is used to generate the event. The thread invoking 'wait' sleeps until another thread wakes it with 'signal'. Additionally, one thread can 'broadcast' or signal all blocked threads to wake up.
Exam/Concurrency (last edited 2019-05-13 09:00:31 by KevinElphinstone)
https://wiki.cse.unsw.edu.au/cs3231cgi/Exam/Concurrency
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com