quiz 2

What is a critical region?

What is a critical region?

A part of the program where the shared memory is accessed

What characteristics are required of a solution to the critical section problem?

Mutual Exclusion, Progress, Bounded Waiting

Mutual Exclusion for critical section problem

If process Pi is executing in its critical section, then no other processes can be executing in their critical sections

Progress for critical section problem

If no process is executing in its critical section and there are some want to enter their cs, then selection of the process that will enter next can't postpone indefinitely

Bounded Waiting for critical section problem

A bound must exist on # times other processes allowed to enter critical sections after process made request to enter critical section/before that request is granted

Bounded Waiting for critical section problem

Assume that each process executes at a nonzero speed

Bounded Waiting for critical section problem

No assumption concerning relative speed of the N processes

What is a race condition?

outcome of execution depends upon order of access

How does a race condition occur?

2 thread access 1 shared variable

What is the definition of deadlock?

a process indefinitely waits for a resource that is held by another process

What are the four conditions necessary for a deadlock to occur?

Mutual Exclusion, Hold and Wait, No Preemption, Circular Wait

Mutual Exclusion

not required for sharable resources; must hold for nonsharable resources

Hold and Wait

must guarantee that whenever a process requests a resource, it does not hold any other resources

Hold and Wait

Require process to request/be allocated all its resources before starting execution, or allow it to request resource only when process has none

Hold and Wait Disadvantage

Low resource utilization; starvation possible

No Preemption

If process holding some resources requests another resource that cannot be immediately allocated to it, then all resources currently being held release

No Preemption

Preempted resources are added to the list of resources for which the process is waiting

No Preemption

Process will be restarted only when it can regain its old resources, as well as the new ones that it is requesting

Mutual Exclusion Disadvantage

unwise to allow user process to this ability (should be privileged) Only works on a single CPU system.

Circular Wait

impose total ordering of all resource types, and require that each process requests resources in an increasing order of enumeration

Circular Wait

Invalidating the circular wait condition is most common.

Circular Wait

Simply assign each resource (i.e. mutex locks) a unique number.

Circular Wait

Resources must be acquired in order.

What is a safe sequence?

sequence of processes that not leads to deadlock state and fulfilling requests with available resources

How does a safe sequence prevent deadlock?

If a system is in safe state, no deadlocks

Difference between contiguous and non-contiguous allocation of memory?

contiguous allocate consecutive blocks of memory, non-contiguous allocate separate block of memory to file/process

Advantages of contiguous allocation?

No space need to determine next block location,

Advantages of contiguous allocation?

Sequential access required min head movement,

Advantages of contiguous allocation?

File descriptors are easy 2 implement,

Advantages of contiguous allocation?

Easily implemented

What is the idea behind address translation?

enabling private IP networks using unregistered IP addresses to go online

What is a virtual address?

generated by the CPU and also called logical address

What is a physical address

address seen by the memory unit

What is internal fragmentation?

allocated memory being slightly larger than requested memory; this size difference is memory internal to a partition, but not being used

What is external fragmentation?

total memory space exists to satisfy a request, but it is not contiguous

What is the idea behind paging?

break each process into individual pages

Advantages of Paging

NO external fragmentation, Fast to allocate and free, Simple to swap-out portions of memory to disk

Disadvantages of paging

Internal fragmentation, Assigning different levels of protection to different classes of data items not feasible.

Disadvantages of contiguous allocation?

Finding contiguous space for a new file may be impossible

Disadvantages of contiguous allocation?

Programmer must specify size before hand

Disadvantages of contiguous allocation?

External fragmentation occurs

What are the ways to deal with very large page tables efficiently?

use special fast-lookup hardware cache called translation look-aside buffers (TLBs)

What is Effective Access time?

(weighted) average time it takes to get a value from memory

What is Effective Access Time function?

EAT = (202) * 1-hit ratio + 102 * hit ratio

Briefly explain the Banker's algorithm.

allocate resources to process considering availability of resource and predetermined maximum need of process.

Producer-Consumer Problem

Producer process produces information in buffer that is consumed by a consumer process

Bounded Buffer Solution

many producers and consumers share 1 buffer

critical region

accessing shared memory or file

Race Condition

results when several threads try to access and modify the same data concurrently

how a race condition occurs

when two threads access a shared variable at the same time

nonpreemptive kernels

process cannot be preempted while in kernel/supervisor mode. Must wait until return to user mode or yields CPU

preemptive kernel

process can be preempted while in kernel mode

preemptive kernel example

Linux starting with version 2.6, Solaris, Windows 7/8/10

preemptive kernel advantage

sys-calls do not block the entire system

preemptive kernel disadvantage

introduces more complexity to the kernel code

non-preemptive kernel advantage

less difficult to design

non-preemptive kernel disadvantage

It can lead to starvation especially for those real-time tasks

Peterson's Solution

a classic software-based solution to the critical-section problem which has to two processes that alternate execution between critical sections/remainder sections

atomic instruction

allow us to either test-and-modify the content of a word, or two swap the contents of two words atomically/uninterruptibly

Test and Set (atomic instruction)

test memory word and set value

Swap (atomic instruction)

swap contents of two memory words

Semaphores

Synchronization tool that provides more sophisticated ways for process to synchronize their activities.

Wait() (semaphore)

wait function has an argument called S, while S is less or equal to 0, S decreases by 1.

signal() (semaphore)

signal function has an argument called S. S increments by 1.

How wait() is used

blocks the calling process until one of its child processes exits or a signal is received

How signal() is used

call the func function if the process receives a signal signum

Counting semaphore

integer value can range over an unrestricted domain

Binary semaphore

aka mutex lock, integer value can range only between 0 and 1; can be simpler to implement

Semaphore as General Synchronization Tool can...

implement a counting semaphore S as a binary semaphore

Busy-waiting

While a process is in its critical section, any other process that tries to enter its critical section must loop continuously in the call to acquire().

busy-waiting advantage

thread has the processor and can resume immediately after the wait is finished

busy-waiting disadvantage

waste of resource

spinlocks

Mutual exclusion mechanism in which a process executes in an infinite loop waiting for the value of a lock variable to indicate availability.

spinlock advantage

threads get the chance to take advantage of their full runtime quantum

spinlock disadvantage

while waiting to acquire a lock, it wastes time that might be productively spent elsewhere

mutex locks

Protect a critical section by first acquire() a lock then release() the lock

how binary semaphore is used

control access to a single resource and can implement as counting semaphore

how counting semaphore is used

coordinate access to resources and can implement as binary semaphore

how mutex lock is used

declare a lock variable of type Mutex, then execute the Lock() method of that lock, then execute the Unlock() method of the lock.

When binary semaphore is used

when users are controlling access to shared device, like using a printer

Resource-Allocation Graph

A graph representing processes and resource instances in a system. Directed edges represent resource requests and allocations.

monitor

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

difference between semaphore and monitor

semaphore's signal and wait increase/decrease, monitor's signal and wait doesn't, and m is higher lvl proc sync tool

condition variable

enables a thread to efficiently wait for a change to shared state protected by a lock

Bounded buffer solution using semaphores (producer)

produces item, has others wait for semaphore, then puts item in buffer, then locks the semaphore

Bounded buffer solution using semaphores (consumer)

has others wait for semaphore, move item to consumed, then locks semaphore before consuming it

Reader/Writer solution using semaphores (reader)

has others wait, then go to first line and has writer to stop writing, then reads it, then read count decreases and locks it

Reader/Writer solution using semaphores (writer)

wait for semaphore then writes the thing, then locks it

Dining Philosophers solution using monitor

imposes the restriction that a philosopher may pick up her chopsticks only if both of them are available

How resource allocation graph has deadlock

when its in cycle and processes wait forever

Ignoring deadlocks

Reboot the system when there's a deadlock. E.g. Ostrich

Preventing deadlocks

Invalidate one of the four necessary conditions for deadlock.

Preventing deadlock example

safe sequence

Avoiding deadlock

requires that each process declare the maximum number of resources of each type that it may need, banker algorithm/resource allocation graph.

detecting deadlock

Periodically invoke an algorithm that searches for a cycle in the graph. e.g. resource allocation graph If there is a cycle, there exists a deadlock

advantages of ignoring deadlock

simple and straightforward, easy to implement

disadvantage of ignoring deadlock

reboot = breaks other programs

advantage of preventing deadlock

easy to understand

disadvantage of preventing deadlock

Low resource utilization; starvation possible

advantage of avoiding deadlock

eliminates deadlocks