Operating Systems

Process

A program in execution that consists of program code text section current activity including PC and registers stack containing temporary data and heap for dynamic memory

Process State NEW

The process is being created

Process State READY

The process is waiting to be assigned to a processor

Process State RUNNING

Instructions are being executed

Process State WAITING

The process is waiting for some event to occur such as IO completion

Process State TERMINATED

The process has finished execution

PCB Process Control Block

Data structure containing process state process ID program counter CPU registers CPU scheduling info memory management info accounting info and IO status info

Context Switch

Switching the CPU from one process to another by saving the state of the old process and loading the saved state for the new process

Context Switch Time

Pure overhead where the system does no useful work while switching typically 1-10 microseconds

Thread

A basic unit of CPU utilization comprising a thread ID program counter register set and stack that shares code data and files with other threads in the same process

Thread Benefits

Responsiveness resource sharing economy cheaper than process creation and scalability can utilize multicore processors

Many-to-One Thread Model

Multiple user-level threads mapped to single kernel thread where one thread blocking causes all to block rarely used today

One-to-One Thread Model

Each user-level thread maps to a kernel thread providing more concurrency used by Windows and Linux

Many-to-Many Thread Model

Multiple user-level threads mapped to multiple kernel threads allowing flexible thread management

User Threads

Threads managed by user-level thread library without kernel support

Kernel Threads

Threads supported and managed directly by the operating system

IPC Interprocess Communication

Mechanism for processes to communicate and synchronize their actions using shared memory or message passing

Shared Memory IPC

Processes share a region of memory for communication which is fast but requires synchronization to avoid race conditions

Message Passing IPC

Processes communicate by exchanging messages via send and receive operations handled by the OS

Direct Communication

Processes must name each other explicitly using send P message and receive Q message

Indirect Communication

Messages are sent and received from mailboxes or ports using send A message and receive A message

Blocking Send

Sender is blocked until the message is received by the receiver or mailbox

Non-blocking Send

Sender sends the message and continues execution immediately

Blocking Receive

Receiver blocks until a message is available

Non-blocking Receive

Receiver retrieves either a valid message or null and continues

Critical Section

Segment of code where a process may change common variables update a table or write a file

Critical Section Problem

Design a protocol so that when one process is executing in its critical section no other process can execute in its critical section

Mutual Exclusion

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

Progress Requirement

If no process is executing in its critical section and some processes wish to enter their critical section then the selection of the next process cannot be postponed indefinitely

Bounded Waiting

A bound must exist on the number of times other processes are allowed to enter their critical sections after a process has made a request to enter

Race Condition

Situation where several processes access and manipulate shared data concurrently and the outcome depends on the order of execution

Peterson's Solution

Software solution to critical section problem for two processes using shared variables flag array and turn variable

Memory Barrier

Instruction that forces any change in memory to be propagated made visible to all other processors

Test-and-Set Instruction

Hardware instruction that atomically tests and modifies the content of a word returning the original value and setting new value to true

Compare-and-Swap Instruction

Hardware instruction that atomically compares a value with an expected value and swaps with new value only if they match

Mutex Lock

Synchronization tool that provides mutual exclusion with acquire and release operations also called spinlock due to busy waiting

Semaphore

Integer variable accessed only through two atomic operations wait and signal used for process synchronization

Binary Semaphore

Semaphore with integer value that ranges only between 0 and 1 similar to mutex lock

Counting Semaphore

Semaphore with integer value that can range over an unrestricted domain

Wait Operation on Semaphore

Decrements the semaphore value and blocks the process if value becomes negative also called P operation

Signal Operation on Semaphore

Increments the semaphore value and wakes up a blocked process if any also called V operation

Monitor

High-level synchronization construct that provides mutual exclusion and condition variables for process synchronization

Condition Variable

Variable within a monitor that allows processes to wait for certain conditions using wait and signal operations

Bounded Buffer Problem

Synchronization problem with n buffers where producer produces items and consumer consumes items requiring semaphores empty full and mutex

Readers-Writers Problem

Synchronization problem where multiple readers can read simultaneously but writers need exclusive access using semaphores rw_mutex and mutex with read_count

Dining Philosophers Problem

Synchronization problem where 5 philosophers alternate between thinking and eating requiring 2 chopsticks to eat solved using semaphores or monitor

Deadlock

Situation where a set of processes are blocked because each process is holding a resource and waiting for another resource held by another process

Mutual Exclusion Deadlock Condition

Only one process at a time can use a resource

Hold and Wait Deadlock Condition

A process holding at least one resource is waiting to acquire additional resources held by other processes

No Preemption Deadlock Condition

A resource can be released only voluntarily by the process holding it after completing its task

Circular Wait Deadlock Condition

A set of waiting processes exists such that P0 waits for P1 P1 waits for P2 and Pn waits for P0

Resource Allocation Graph

Directed graph with vertices for processes and resources and edges for request and assignment used to detect deadlocks

Deadlock Prevention

Ensure that at least one of the four necessary deadlock conditions cannot hold by invalidating one condition

Deadlock Avoidance

System has additional a priori information about resource requests and uses algorithms to ensure system never enters unsafe state

Safe State

System state where there exists a sequence of all processes such that each process can obtain needed resources execute and terminate

Unsafe State

System state that may lead to deadlock but deadlock is not guaranteed

Banker's Algorithm

Deadlock avoidance algorithm that checks if granting a resource request leaves the system in a safe state before allocation

Available Vector

Vector of length m indicating number of available resources of each type

Max Matrix

n x m matrix where Max i j equals k means process Pi may request at most k instances of resource type Rj

Allocation Matrix

n x m matrix where Allocation i j equals k means Pi is currently allocated k instances of Rj

Need Matrix

n x m matrix where Need i j equals Max i j minus Allocation i j representing remaining resource needs

Safety Algorithm

Algorithm to determine if system is in safe state by finding a sequence where each process can finish

Resource Request Algorithm

Algorithm to determine if a resource request can be granted immediately by checking if request is less than need and available

Deadlock Detection

Allow system to enter deadlock state then use detection algorithm to identify deadlocked processes

Wait-for Graph

Simplified resource allocation graph for single instance resources where Pi to Pj means Pi is waiting for Pj

Deadlock Recovery Process Termination

Abort all deadlocked processes or abort one process at a time until deadlock cycle is eliminated

Deadlock Recovery Resource Preemption

Select a victim process rollback to safe state and restart considering cost to minimize impact

Logical Address

Address generated by the CPU also referred to as virtual address

Physical Address

Address seen by the memory unit the actual location in main memory

Memory Management Unit MMU

Hardware device that maps virtual addresses to physical addresses at runtime

Base Register

Contains the smallest physical address value for a process

Limit Register

Contains the range of logical addresses that must be less than the limit register for protection

Dynamic Loading

Routine is not loaded into memory until it is called providing better memory utilization

Dynamic Linking

Linking postponed until execution time using stubs to locate library routines useful for shared libraries

Contiguous Memory Allocation

Each process is contained in a single contiguous section of memory

External Fragmentation

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

Internal Fragmentation

Allocated memory may be slightly larger than requested memory with unused space internal to a partition

First-Fit Allocation

Allocate the first hole that is big enough from the list of free holes

Best-Fit Allocation

Allocate the smallest hole that is big enough producing the smallest leftover hole

Worst-Fit Allocation

Allocate the largest hole producing the largest leftover hole

Compaction

Shuffle memory contents to place all free memory together in one large block to reduce external fragmentation

Paging

Memory management scheme that permits physical address space of a process to be noncontiguous dividing memory into fixed-sized frames

Frame

Fixed-sized block of physical memory typically 512 bytes to 16 MB

Page

Fixed-sized block of logical memory same size as a frame

Page Table

Data structure used by virtual memory system to store mapping between virtual addresses and physical addresses

Page Number

Part of logical address used as an index into the page table

Page Offset

Part of logical address combined with base address to define the physical memory address

TLB Translation Lookaside Buffer

Special fast-lookup hardware cache also called associative memory used to speed up address translation

Effective Access Time

Average time to access memory considering TLB hit ratio calculated as hit_ratio times TLB_time plus miss_ratio times memory_access_time

Hierarchical Paging

Page table is divided into multiple levels to reduce memory required for page tables

Hashed Page Table

Virtual page number is hashed into a page table with chains for collision resolution used for address spaces greater than 32 bits

Inverted Page Table

One entry for each real page of memory tracking which process owns each physical page reducing memory for page tables

Segmentation

Memory management scheme that supports user view of memory as a collection of variable-sized segments

Segment Table

Maps two-dimensional logical addresses to physical addresses with base and limit for each segment

Virtual Memory

Separation of logical memory from physical memory allowing execution of processes not completely in memory

Demand Paging

Pages are loaded into memory only when they are needed during execution reducing I/O and memory requirements

Page Fault

Interrupt that occurs when a process accesses a page not currently in memory

Valid-Invalid Bit

Bit in page table entry where v means page is in memory and i means page is not in memory

Page Fault Steps

Trap to OS check if valid reference find free frame swap page into frame reset page table restart instruction

Pure Demand Paging

Start process with no pages in memory causing page fault on first instruction