Operating Systems (2) Flashcards
Instruction Interleaving. When is it okay? When is it not okay?
Instructions from different processes get mixed together in the CPU.
It is okay for this to happen if the shared variables are saved to the same register. It is NOT okay for this to happen if the variables shared are saved on different registers, similar to having two copies of a variable.
How does instruction interleaving affect CPU?
It has no effect to the CPU, as it does not matter where the instructions come through from, nor does its order. The CPU will continue its work (fetch, decode, execute, interrupt).
How does instruction interleaving affect processes?
A process could have a different result than intended, especially if they share a variable.
How can we make sure interleaved processes give consistent results?
By keeping the shared variable saved onto one register.
What are the criteria needed to give consistent results? (Solve the critical section problem)
Mutual exclusion, bounded waiting, progress
Critical Section:
A section of code where variables will be shared with one or more processes.
Progress vs Bounding Waiting
Bounding waiting is when one process has a finite amount of time in an entry loop, and leaves by a trigger in another process. Progress is when all processes have a finite time in an entry loop and will all receive their triggers to move through their entire process.
Bakery Algorithm:
A critical section solution which is useful for multiple processes, and all criteria is met to solve the C.S. The entry loop has two variables with a boolean and an integer (atomic) that must both be set to be stuck waiting. If one process proceeds to the critical section, it will make all other processes wait their turn. When the process exits, it will change one of the variables, allowing another process to enter the critical section. (Software synchronization)
testandSet:
An atomic or uninterruptible method where a variable needed by the C.S. is received, and it’s set to true to return the variable. Multiple processes could create a boolean variable lock if one process has already entered the critical section. The boolean is initialized to false, but if the boolean is already true and sent testAndSet again, it will stay in the waiting loop until it is set to false, by leaving the C.S. (Hardware synchronization)
Semaphores:
Semaphores are a special integer (S) that can be treated like a boolean. It is used in two methods: wait and signal. If a process tries to enter while another is in the C.S. (S would be decremented already), it will be stuck in a wait queue (which checks to see if S is 0 or negative). Signal allows S to return to its initial state and exit the C.S. (OS synchronization) Note: Semaphores can also be used in a Bounded Buffer with it’s integer property.
Bakery Algorithm Advantages and Disadvantages:
It is adaptable for multiple processes. However, wait queue times are not controllable. (Which in turn makes it not very portable, since delay times are different on different systems.)
testandSet Adv. and Dis.:
Great when used with systems that give users access to it, but its neither portable to other systems, and so system specific.
Semaphores Adv. and Dis.:
Is used by many different operating systems and is very well tested by creators of OS’s. But still uses busy waiting.
When are the C.S. solutions efficient/inefficient?
Efficient at following all solution criteria. Inefficient in removing deadlocks completely and reducing the waste of CPU cycles.
What can be done to reduce CPU cycle waste?
By using the blocking method, which sends processes to a wait queue by the wait call, until they are sent into the ready queue by the signal call to eventually be run. (Timing is more controlled this way)
When does deadlocking happen with Semaphores?
It does happen! Page 98 example
Deadlock:
When processes cannot get the resources needed to run, because it is held by another process.
Deadlock conditions:
Mutual Exclusion, no preemption, hold/wait, circular wait.
Safe State:
When processes are not deadlocked. This relates to safe sequence because a safe-sequence of processes keeps the system in a safe state.
Deadlock Prevention: Mutual Exclusion
Helpful by using shared resources only.
Deadlock Prevention: Hold and Wait
Processes must request and acquire all resources before they begin (using system calls), and can only request resources if they have none.
Deadlock Prevention: No-Preemption
If a process has resources and cannot receive any more necessary ones, it will have to release those resources, and can only restart again when it has them all. Preemption of resources can be forced when the OS notices the resources a starting process needs is held by another process.
Deadlock Prevention: Circular wait
By using a number system for the resources, processes would only be able to take higher-numbered resources FIRST, before lower numbered ones.
Deadlock Prevention vs Avoidance
Prevention creates methods to address the issues that causes deadlocks, while avoidance uses the information given to the OS about the required resources to come up with an instruction sequence that will not encounter a deadlock.
