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)
