COP 4610 Exam 2 Wang

Monitor

A lock + condition variables

Lock

provides mutual exclusion to shared data.

a lock provides two operations

-Acquire()

-Release()

Condition Variable

provides a queue for waiting threads inside a critical section

each conditional variable

-consists of a queue of threads

-Provides three operations

**wait()

**Signal()

**Broadcast()

Hoare vs. Mesa Monitors

Hoare Monitors (used in most textbooks)

-Signal() transfers the CPU directly to a waiting thread.

Mesa Monitors (used in most real operating systems)

-Signal() only puts a waiting thread on the scheduler's ready queue

-By the time the waken thread gets the CPU, the waiting condition may no longer be true and needs to be retested.

Semaphores VS Monitors

We can't quite implement monitors with semaphores.

Condition variables only work inside a lock

-using semaphores inside a lock may deadlock

Condition variables have no history, but semaphores have

-Signal() with an empty queue does nothing

**A subsequent Wait() will wait

-V() increments semaphore

**A subsequent P() will not wait

-Wait() will always wait

-P() might not wait

Deadlock

Occur when threads are waiting for resources with circular dependencies.

Deadlock implies starvation

Preemptable Resource

EX- CPU

can be resolved by reallocation of resources

Nonpreemptable Resource

A resource that cannot be taken away from its current owner without causing computation to fail

Starvation

a thread waits indefinitely

Checkpointing

taking snapshots of system states from time to time

Four Conditions for Deadlocks

limited access (lock-protected resources)

no preemption (if someone has the resource, it cannot be taken away)

wait while holding (holding a resource while requesting and waiting for the next resource)

circular chain of requests

Banker's Algorithm

-A thread states its maximum resource needs in advance.

-The OS allocates resource dynamically as needed. A thread waits if granting its request would lead to deadlocks.

-A request can be granted if some sequential ordering of threads is deadlock free.

Deadlock Recovery Techniques

• Scan the resource allocation graph

• Detect circular chains of requests

• Recover from the deadlock

Interprocess Communication

Processes communicate among address spaces.

-Bug stream ex. pipe

-Message passing (send/receive)

-File system (read and write)

-Shared memory

Direct

-send(P1, message);

-receive(P2, message);

-One-to-one communication

Indirect

-Mailboxes or ports

-send(mailbox_A, message);

-receive(mailbox_A, message);

-Many-to-many communication

System Call

A user process asks the OS to do something on the process's behalf.

Hardware-Supported Mechanisms

Address translation

Dual-mode operation

Software-Supported Mechanisms

Strong Typing

Software Fault Isolation

Steps to switch between kernel and user spaces

-Creates a process and initialize the address space

-Loads the program into the memory

-Initializes translation tables

-Sets the HW pointer to the translation table

-Sets the CPU to user mode

-Jumps to the entry point of the program

Context switching between processes vs. threads

Unlike context switching among threads, to switch among processes

-Need to save and restore pointers to translation tables

To resume process execution

-Kernel reloads old register values

-Sets CPU to user mode

-Jumps to the old program counter

Segment

A logically contiguous memory region

External Fragmentation

memory wasted because the available memory is not contiguous for allocation

Internal Fragmentation

allocated pages are not fully used

Translation Lookaside Buffers

Store recently translated memory addresses for short-term reuses

base and bound translation

• Each process is loaded into a contiguous region of physical memory

• Processes are protected from one another

• Each process "thinks* that it owns a dedicated machine, with memory addresses from 0 to bound.

• An OS can move a process around

--By copying bits