Concurrency Flashcards
Define the term race condition and give an example.
A race condition is a piece of code that modifies a shared variable across two or more threads.
A global counter being update, for example, without any concurrency control.
A colleague argues that, “concurrency control is easy since all we need to do is allow processes to disable interrupts”.
What would such an approach achieve and why is it a bad idea?
If a process could selectively disable interrupts whenever it liked, it would be able to run for as long as it liked without being interrupted by anything. No hardware, software, scheduler etc would be able to stop it.
Explain the implementation of a semaphore. Your semaphore must not rely on busy-wait. In your answer describe how atomicity can be achieved
in the semaphore operations.
Busy-wait sempahores just use while loops to wait for the resource to increase again. A wait-signal semaphore is more sophisticated.
It still has a resource counter, but also a list of process control blocks. When a process calls wait(), the process counter is decremented. If this takes it below zero, then the process adds itself to the list of waiting blocks and starts blocking. Obviously, if i > 0 then it just keeps going with a ‘secured’ lock.
When another process calls signal(), the resource counter is incremented. If this brings it above zero, then remove the waiting process from the list of PCBs and unblock it.
Show how semaphores are used to implement each of the following:
Mutual exclusion.
Task ordering (ensure A happens before B) between threads.
A shared database allowing concurrent access to read-only
threads but where exclusive access is granted to update threads.
A mutex can be thought of as a ‘binary semaphore’. The above explanation still stands, but ‘i’, the resource counter, will be initially set to 1. So only a single process may use it.
Task ordering not examined any more. But could use synchronisation to lock a global ‘ordering’ value.
Two semaphores, one for reading one for writing.
Explain how condition variables are used in a monitor. In your answer explain three possibilities for the behaviour of signal().
In the ‘shared data’ bubble of the monitor diagram, there is a condition queue. This stores a list of processes waiting on a condition x,y,z.. etc.
When a process is waiting on a condition variable that is in a condition queue (because another process came before it), it can only be released by that process in front of it calling .signal().
Say Q is waiting on a condition held by P. When P signals, either;
1) P leaves monitor immedieately
2) If mode is ‘signal and wait’, P will wait for Q to exit monitor
3) if mode is ‘signal and continue’, Q will still wait for P to exit the monitor
For the following code draw the tree of processes that are created and state
how many calls to execve are made.
int id = fork();
if(id){
fork();
char *env[] = { NULL };
char *args[] = { "ls", NULL };
execve("/bin/ls",args,env);
fork();
}Parents are the only ones that receive a value for fork(), so the if statement will only be executed once.
The first fork(); will spawn an additional child process, bring the total to one parent with two children.
Execv will be executed only be the parent and that newly created child, a total of two times.
The final fork() is never called (assuming execve is successful) as execve replaces the current process image with a new one, in this case ls.
Explain each of the following statements:
(i) “multi-threading makes sharing easy”
(ii) “multi-threading makes it difficult to write correct programs”
(iii) “multi-threading can improve performance”
i) It makes sharing too easy. encourages cross-thread communication through shared global variables that can often lead to race-conditions and inconsistent states.
ii) If you aren’t using the correct tools (mutex, semaphores, monitors) then it can be difficult to construct programs that don’t interfere cross-thread.
iii) Multi-threading, applied correctly to a problem, can improve performance by splitting work across multiple cores of a CPU. Implemented poorly can be as slow, or slower than a single threaded application.
Explain the difference between a binary semaphore and a counting
semaphore. Give an example of the use of each.
Binary semaphore is a mutex. It only has a resource counter that is either on or off. Used for mutual exclusion of variables.
Counting semaphore has a limited, but > 1, number of concurrent accesses allowed. Often used to implement reader-writer databases with multiple readers, combined with a mutex for writers.
Describe two scenarios that can lead to race conditions within the kernel.
The two mentioned in the lectures are ‘Kernel Logging’ and ‘Kernel IP Routing Tables’.
The logging is an example of producer-consumers / bounded buffers, as you have single units ‘lines’ being written to the log and single units ‘lines’ being removed and taken to a file, or stdout.
The routing tables are an example of reader-writer.
Define the term spin-lock and show how an atomic instruction is used to
implement a spin-lock.
A spinlock or ‘busy-wait’ lock just waits for a resource to be free, is only on multicore systems. An atomic type, atomic_t, can be used to implement an atomic integer for a spin lock.
while(atomic_int < 0) {}
// do stuff
Windows turns these spin locks into kernel mutex’s after a while.
Explain where it is appropriate to use a spin-lock and why.
Multithreaded systems. Spin locks don’t get preempted on wait, so they can avoid costly context-switching (always the answer!). If spinlock held for too long, things get weird. It no longer makes sense to hold one for a massive duration. Switch to a mutex.
Not appropriate on single-core systems.
A Linux-based system stores its firewall rules in a table in the kernel. Every
time a packet arrives or is sent on a network interface the table is checked for a
matching rule. Occasionally new rules need to be added to the table. Describe,
in words and pseudo-code, a concurrency control solution for this data
structure that ensures consistency and maximises parallelism.
IP routing tables are a reader-writer problem. Writers want an exclusive lock, readers want to be able to guarantee consistency when reading rules in order (probably).
writer {
wait(write_lock)
write()
signal(write_lock)
}
reader {
wait(reader_lock)
readercount++
if (readercount == 1)
wait(writer_lock)
signal(reader_lock)
read()
wait(reader_lock)
readercount--
if (readercount == 0)
signal(writer_lock)
signal(reader_lock)
}
the locks are a pair of mutexes. readercount is an int.
Explain the following terms:
(i) Critical section [1 mark]
(ii) Race condition [1 mark]
(iii) Preemptible kernel
Critical Section is a piece of code that accesses or modifies shared variables
A race condition occurs when two or more threads modify a shared variable concurrently.
A preemptible kernel is one that can be interrupted, except during critical sections.
Describe two ways a kernel can implement a mutual exclusion lock to ensure
that a critical section in device driver code cannot be interrupted. Discuss
strengths and weaknesses of each approach.
Spinlock could be used. This spinlock will busy-wait until the resource (the critical section lock) is free. Spinlocks are good for short waits, but lose their context-switching-prevention value after some time.
Binary semaphores (mutexes) are better for longer critical sections, as they allow the thread to be preempted by going to sleep as soon as they fail to acquire the lock.
The MissionVision home entertainment system has three important resources:
a camera, a microphone, and a wireless network adapter. The OS will only
allow the camera and the microphone to be accessed by a single process at any
given time, and they have to be locked before use. The network adapter can be
used by a maximum of five separate processes at once. The entertainment
system comes with three applications: a video conferencing program, an online
multiplayer game with voice chat, and a blogging app which records and
streams video in real time.
Is it possible for a deadlock to occur in this scenario? Justify your answer using
any diagrams you find useful, and explain any assumptions you make.
The necessary conditions for deadlock are;
Mutex
Hold and Wait
Circular Wait
Lack of Pre-emption
In the description we have Mutex, as they need to be locked before use. We have Hold and Wait, as more than one process wants to use a mutex’d variable, and a diagram would show that we have circular wait.
The only missing ingredient is pre-emption. If the system supported kernel pre-emption then we wouldn’t have a problem. If it doesn’t, then yes the conditions for deadlock are satisfied and thus it may occur.
