CSCI51.01 LT2: Deadlocks, Memory Management, File Management, and Mass Storage Structures

Deadlock

Indefinite blocking of processes waiting for resources.

Resource Contention

Competition among processes for limited resources.

Coffman Conditions

Four conditions necessary for deadlock occurrence.

Mutual Exclusion

Resource held in non-shareable mode by one process.

Hold and Wait

Process holds resources while waiting for more.

No Preemption

Resources can only be released voluntarily by processes.

Circular Wait

Processes form a cycle waiting for each other's resources.

Deadlock Prevention

Avoid deadlock by preventing necessary conditions from holding.

Deadlock Avoidance

Requires the system to have a priori information about the future resource needs of processes to make allocation decisions that avoid deadlock.

Deadlock Detection and Recovery

Allow deadlocks to occur, then detect them and take action to recover.

Ostrich Algorithm

Ignore deadlocks when they are rare and costly.

System Resource Allocation Graphs

Visual representation of resource allocation in a system.

Request Edge

Indicates a process requesting a resource in graphs.

Assignment Edge

Shows resource assigned to a process in graphs.

Wait-For Graph

Graph indicating processes waiting for resources held by others.

Cycle in Wait-For Graph

Indicates the presence of a deadlock.

Resource Allocation

Distribution of resources among processes in a system.

Starvation

Process indefinitely waiting for resources due to scheduling.

Total Ordering

Sequentially ordering resource types to prevent circular wait.

Resource Enumeration

Assigning a unique order to resource types.

Resource Utilization

Efficiency of resource usage in a system.

System Throughput

Rate of process completion in the system.

Hybrid Approaches

Combines methods for effective deadlock management.

Deadlock Avoidance

Requires the system to have a priori information about the future resource needs of processes to make allocation decisions that avoid deadlock.

Safe State

State where resources can be allocated without deadlock.

Unsafe State

State where deadlock may occur if resources allocated.

Resource Allocation Graph

Graph showing resource requests and allocations.

Request Edge

Represents future resource requests in allocation graph.

Assignment Edge

Indicates allocated resources in allocation graph.

Banker's Algorithm

Prevents deadlock by ensuring safe resource allocation.

Detection Algorithm

Identifies deadlocks through periodic system checks.

Wait-For Graph

Graph indicating processes waiting for resources.

Cycle in Graph

Indicates a deadlock in resource allocation.

Process Termination

Aborting processes to resolve deadlocks.

Resource Preemption

Taking resources from processes to resolve deadlocks.

Hybrid Approach

Combines multiple methods for deadlock management.

Critical Resources

Resources likely involved in deadlocks.

Dynamic Loading

Loads subroutines into memory only when called.

Dynamic Linking

Uses pointers to routines in Dynamic Link Libraries.

Overlays

Keeps necessary instructions in memory, overwriting others.

Logical Address

Address generated by CPU for program execution.

Physical Address

Actual memory address used by hardware.

Memory Management Unit (MMU)

Maps logical addresses to physical addresses.

Swapping

Moves processes between main memory and storage.

Roll Out

Swapping a process from memory to disk.

Roll Out

Moving a process to secondary storage.

Roll In

Moving a process back to main memory.

Context Switch Time

Time taken to switch between processes.

Fast Secondary Storage

Essential for efficient process swapping.

Candidates for Swapping

Waiting processes suitable for memory swapping.

Unix Swapping

Disabled normally, enabled when memory is low.

Windows Swapping

Partial swapping controlled by the user.

Contiguous Allocation

Single continuous memory block for each process.

Non-Contiguous Allocation

Memory scattered across multiple blocks for processes.

Single-Partition Allocation

OS resides in high or low memory.

Multiple-Partition Allocation

Fixed-sized partitions hold one process each.

Dynamic Partitions

Allocates blocks as processes arrive, creating holes.

First-Fit Algorithm

Allocates the first sufficiently large hole.

Best-Fit Algorithm

Allocates the smallest sufficient hole.

Worst-Fit Algorithm

Allocates the largest available hole.

External Fragmentation

Sufficient total memory exists, but it's not contiguous, so a process cannot be allocated memory.

50% Rule

Next 0.5N blocks lost to fragmentation.

Internal Fragmentation

Unused space within allocated memory partitions.

Compaction

Moves processes to eliminate external fragmentation.

Paging

Divides memory into fixed-size blocks called pages.

Segmentation

Divides memory into variable-sized segments.

Segmentation with Paging

Combines segmentation and paging features.

Page Table

Maps pages to frames in memory.

Shared Pages

Read-only code shared among processes.

Segment Table

Maps segments with base and limit addresses.

Dynamic Loading

Loads subroutines only when needed.

Dynamic Linking

Uses stubs as pointers to DLL routines.

Overlays

Keeps necessary instructions in memory only.

Logical Address

Generated by CPU, also called virtual address.

Physical Address

Generated by MMU, requires hardware mapping.

Swapping

Moves processes to secondary memory when needed.

Contiguous Allocation

Processes occupy continuous memory blocks.

Fragmentation

Inefficient memory use due to allocation methods.

External Fragmentation

Sufficient total memory exists, but it's not contiguous, so a process cannot be allocated memory.

Internal Fragmentation

Free space exists within an allocated partition that a process doesn't use.

Compaction

Moves processes to create contiguous memory blocks.

Non-Contiguous Allocation

Uses paging or segmentation for memory allocation.

Paging

Non-Contiguous Allocation Method whose disadvantage is that Internal fragmentation may occur if a page is not fully occupied.

Shared Pages

Non-self-modifying code accessed by multiple processes.

Segmentation

Divides logical memory into intuitive segments.

File System

Provides mechanism for online storage and access to both data and programs

File Attributes

Properties like name, type, and size.

File Operations

Actions like create, read, delete, and truncate.

Access Methods

Ways to access data: sequential, direct, indexed.

Directory Structure

Organizes files into partitions or volumes.

File Protection

Controls operations via permissions and access groups.

Linked Allocation

Files as linked lists of disk blocks.

FAT

Stores links between blocks in a table.

Indexed Allocation

Index block contains pointers to all file blocks

Advantages of Indexed Allocation

No external fragmentation, supports direct access.

Disadvantages of Indexed Allocation

Overhead of maintaining the index block.

Unix inode

Stores pointers and indirect references for files.

Bit Vector/Map

Bit array indicating block allocation status.

Advantages of Bit Vector

Simple implementation for free space management.

Disadvantages of Bit Vector

Inefficient if not kept in memory.