Void Swap (boolean *a, boolean *b){

do {

boolean temp = *a;

key = TRUE;

*a = *b;

while ( key == TRUE)

*b = temp:

Swap (&lock,

}

&key );

critical section lock = FALSE;

remainder section } while (TRUE);

Semaphore: Synchronization tool that does not require busy waiting

◦ Standard operations:←thesearet wait() and signal() he only operations that can access semaphore S

Can have counting (unrestricted range) and binary (0 or 1) semaphores

Deadlock: Two or more processes are waiting indefinitely for an event that can be caused by only one of the waiting processes (most OSes do not prevent or deal with deadlocks)

Can cause starvation and priority inversion (lower priority process holds lock needed by higher-priority process)

Ch.6 – Process Synchronization Continued

Other synchronization problems include Bounded-Buffer Problem and Readers-Writers Problem

Monitor is a high-level abstraction that provides a convenient and effective mechanism for process synchronization

Only one process may be active within the monitor at a time

Can utilize condition variables to suspend a resume processes (ex: condition x, y;)

x.wait() – a process that invokes the operation is suspended until x.signal()

x.signal() – resumes one of processes (if any) that invoked x.wait()

Can be implemented with semaphores

Ch.7 – Deadlocks

Deadlock Characteristics: deadlock can occur if these conditions hold simultaneously

Mutual Exclusion: only one process at a time can use a resource

Hold and Wait: process holding one resource is waiting to acquire resource held by another process

No Preemption: a resource can be released only be the process holding it after the process completed its task

Circular Wait: set of waiting processes such that P_n-1 is waiting for resource from P_n, and P_n is waiting for P₀ ▪ “Dining Philosophers” in deadlock

Ch.8 – Main Memory

Cache sits between main memory and CPU registers

Base and limit registers define logical address space usable by a process

Compiled code addresses bind to relocatable addresses

Can happen at three different stages

Compile time: If memory location known a priori, absolute code can be generated

Load time: Must generate relocatable code if memory location not known at compile time

Execution time: Binding delayed until run time if the process can be moved during its execution

Memory-Management Unit (MMU) device that maps virtual to physical address

Simple scheme uses a relocation register which just adds a base value to address

Swapping allows total physical memory space of processes to exceed physical

m emory

Def: process swapped out temporarily to backing store then brought back in for continued execution

Backing store: fast disk large enough to accommodate copes of all memory images

Roll out, roll in: swapping variant for priority-based scheduling.

Lower priority process swapped out so that higher priority process can be loaded

Solutions to Dynamic Storage-Allocation Problem:

First-fit: allocate the first hole that is big enough

Best-fit: allocate the smallest→smallesthole leftoverthatisbigholeenough (must search entire list)

Worst-fit: allocate the→largest leftoverhole(searchhole entire list)

External Fragmentation: total memory space exists to satisfy request, but is not contiguous

Reduced by compaction: relocate free memory to be together in one block ▪ Only possible if relocation is dynamic