18+19 Flashcards
What is the data race problem? What is a critical section?
This can occur when multiple processes/threads are accessing the same data/memory location and at least one of them is modifying the data. This can lead to the data being modified before it is supposed to. To prevent this certain parts of the cooperating processes are not interleaved(interrupted). The critical section is the special protected sections.
What are the critical section requirements?
Mutual exclusion(only one process executing critical section at a time). Bounded waiting(When a process becomes ready to enter its critical section, there must be a bound on how many times other processes can enter their critical sections Progress(no process executing a non-critical section can stop a process from entering its critical section, and the decision to enter a critical section cannot be indefinitely postponed.)
What is Peterson’s algorithm?
Have a flag and a turn, for a process to enter its critical section its flag must be set to true and the turn must be its turn.
What does synchronisation hardware do?
provide special atomic instructions which cannot be interrupted.
What is the CAS function?
An atomic instruction CAS(o, a, n) checks if the value at address a is o, write the value n to address a and return true, otherwise return false. It can be used to implement locking systems.
How does test and set work?
Begin with a variable called lock, set to false. Now have a while loop that checks to see if it is set to false. If it is, set the lock and do critical section. If not, wait till it is. Don’t forget to unset the lock when done.
What is a semaphore?
An integer variable that can only be accessed via two atomic instructions, Wait(S): wait while S is less than or equal to 0. Decrease S by 1 Signal(S): increase S by 1.
They are commonly used in synchronisation.
How can we reduce busy waiting for a semaphore?
Use a process queue.
What are common semaphore values?
1 for mutex, 0 for process synchronization, > 1 for concurrent processes/threads. Note that semaphores can get negative values, in which case it tells us how many processes are waiting.
What is a monitor? What is it in java?
A high level language construct to make synchronisation easier for programmers. In java the synchronized keyword is used, this is done using a lock.
What is a deadlock and how can it be fixed?
This can occur when a process with control of the lock can’t do what is required, locking out other processes while getting nothing done. This can be fixed using wait and notify. Wait lets a thread go into wait set and unlocks the lock, notify causes an arbitrary thread to be picked from the object’s wait list.
What does a deadlock require?
This occurs when every process is waiting for an event that can only be caused by another process in the set. They require mutual exclusion, at least one process to hold a resource and one waiting, no preemption(resource can only be released by process holding it), and circular wait(waiting in circular fashion).
What is a resource allocation graph? How can this be used to detect deadlocks?
Graph containing: process nodes , resource nodes. Request edges connect a process to a resource, an assignment edge represents a resource has been given to a process. When a request is granted the request edge is transformed ot an assignment edge. When a resource is released the assignment edge is deleted.
If the graph contains no cycles the system is not deadlocked, if the graph contains a cycle with only one instance of each resource involved the system is deadlocked, otherwise it might be.
How can we prevent deadlocks?
Stop one of: mutual exclusion( not feasible in most cases) Hold and wait(force process to be given all resources before starting execution, or can only request resources when has none, bas utilisation and starvation). No preemption(allow processes to preempt resources held by other processess, requires saveable state). Circular wait(impose total ordering of all resource types).
What is a safe state?
A system is in a safe state if there is a process sequence so that each process gets all the resources it wants, using only the resources currently free and the collection of resources requested by all processes before it. We can be safe if we execute the processes in this sequence.
What is an algorithm for deadlock avoidance?
for environment where there is only one instance of each resource type:
Add claim edge to resource allocation graph, this indicates a process may request the resource in the future. If this would lead to an unsafe state don’t allow this to upgrade to an assignment edge.
When might we want to check for deadlocks? What can we do to fix it?
Whenever CPU utilisation falls below some threshold. We could then either abort all deadlocked processes, abort one at a time, preempt resources one at a time or restart affected processes
