quiz 2

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

disadvantage of avoiding deadlock

Processes may have to wait unnecessarily

advantage of detecting deadlock

can take measure to prevent deadlock in advantage

disadvantage of detection deadlock

cycle doesn't necessarily mean there is a deadlock. deadlock no happen = wasting system resources to search cycle

how mutual exclusion doesn't hold

not required for sharable resources; must hold for nonsharable resources

how hold and wait doesn't hold

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

how no preemption doesn't hold

If a process hold resources requests another resource that cannot be immediately allocated to it, then all resources currently being held are released

how circular wait doesn't hold

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

Deadlock Avoidance general idea

to avoid deadlock from happening by creating safe sequence with banker's algorithm

safe state (in deadlock avoidance)

When a process requests an available resource, system must decide if immediate allocation leaves the system in a safe state

safe sequence

A sequence of resource allocation that ensures deadlock-prevention.

safe state algorithm

sequence of ALL processes in systems such that for each Pi, resources that Pi still request can satisfied by currently available resources + resources held by all Pj, w/ j < I

safe sequence algorithm

System is in safe state if there exists a sequence that includes all processes. Such sequence is called safe sequence

Is Banker algorithm in safe state?

Yes

termination (recovery algorithm)

Abort all deadlocked processes, one process at a time until the deadlock cycle is eliminated

termination (recovery algorithm) orders

How long process has computed, and how much longer to completion

termination (recovery algorithm) orders

Priority of the process

termination (recovery algorithm) orders

Resources the process has used

termination (recovery algorithm) orders

Resources process needs to complete

termination (recovery algorithm) orders

How many processes will need to be terminated

termination (recovery algorithm) orders

Is process interactive or batch?

resource preemption (recovery algorithm) issues

Selecting a victim - minimize cost

resource preemption (recovery algorithm) issues

Rollback - return to some safe state, restart process for that state

resource preemption (recovery algorithm) issues

Starvation - same process may always be picked as victim, include number of rollback in cost factor

Address binding times

Compile, load, and execution

Compile (address binding)

If memory location known a priori, absolute code can be generated; must recompile code if starting location changes

Load (address binding)

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

Execution (address binding)

Binding delayed until run time if the process can be moved during its execution from one memory segment to another. Need hardware support for address maps

Dynamic linking

linking postponed until execution time

Dynamic linking step 1

Small piece of code, stub, used to locate the appropriate memory-resident library routine

Dynamic linking step 2

Stub replaces itself with the address of the routine, and executes the routine

Dynamic linking step 3

Operating system checks if routine is in processes' memory address. If not in address space, add to address space

Dynamic linking benefit

Dynamic linking is particularly useful for implementing shared libraries. .dll for Windows and .so for Linux.

Dynamic loading

A program's module isn't loaded until it is used

Dynamic loading benefit

Useful when large amounts of code are needed to handle infrequently occurring cases

Dynamic loading benefit

No special support from the operating system is required. Implemented through program design + OS can help by providing libraries to implement

virtual address

generated by the CPU

Physical address

address seen by the memory unit

Logical and physical addresses are the same in

compile-time and load-time address-binding schemes

Logical (virtual) and physical addresses differ in

execution-time address-binding scheme

MMU

Memory management unit, Hardware device that maps virtual to physical address at run time

relocation/base register

The value in the relocation register is added to every address generated by user process at time sent 2 memory. Physical Address = Logical Address + contents of relocation register

Swapping

A process can be swapped out of memory to backing store, then brought back into memory for continued execution. Total physical memory space of processes can exceed physical memory

Backing store

fast disk large enough to accommodate copies of all memory images for all users; must provide direct access to these memory images

Roll out, roll in

swapping variant used for priority-based scheduling algorithms; lower-priority process is swapped out so higher-priority process can be loaded and executed

Major part of swap time

transfer time. it's proportional to the amount of memory swapped

ready queue

has ready-to-run processes which have memory images on disk

Does the swapped out process need to swap back in to same physical addresses?

Depends on address binding method. consider pending I/O to / from process memory space