OS Deadlocks and Memory Management

Deadlocks

Deadlock

When processes cannot proceed due to resource contention

4 Conditions of Deadlock

1. Mutual exclusion
2. Hold and wait
3. No preemption
4. Circular wait

Mutual Exclusion

• At least one non-shareable resource
• Additional requests for resource delayed
• Back and forth of "Who's gonna access it?"

Hold and Wait

• Process holds at least one resource

• Waiting to get resources held by other processes

EX. P1 holding R1, P1 wants R2 but it's held by P2.
For P1 to access R2, P2 should release R2. If too much waiting, deadlock

No Preemption

• Resources only released by process after completing its task

EX. P1 wants R2, but if OS is non-preemptive, it has to wait for P2 to release R2

Circular Wait

• Set of processes { P0, P1, …, Pn }
• P0 waiting for P1, P1 waiting for P2, … Pn-1 waiting for Pn
• Pn waiting for P0

System Resource Allocation Graphs

Graph representing processes and resources with directed edges.

System Resource Allocation Graphs Symbols

1. Processes - Circle

2. Resources - Square w/ dots

3. Request Pi 🡪 Rj

4. Assignment Rj 🡪 pi

Methods for Handling Deadlocks

1. Prevention / Avoidance - Ensure system cannot have deadlocks
2. Allow deadlocks then recover
3. Ostrich Algorithm - Ignore deadlocks

Deadlock Prevention

• Eliminate at least one condition

Disadvantages:

• Low resource utilization

• Less throughput (keep getting interrupted)

Prevention for Mutual exclusion

• Needed for non-shareable resources but not for shareable ones

• Can't prevent mutex for all resources: some intrinsically non-shareable

Prevention for Hold and wait

• Guarantee that process does not hold a resource when requesting another

EX. allocate all resource before execution

Prevention for No preemption

• When request not granted, process must release all resources it's holding

• Restarted only if it regains old and new resources

Prevention for Circular wait

• Impose ordering of resources

• Require process to request resource in increasing number

• If process holds Ri, it can request another, Rj > Ri

• If process holds Rj and requests Ri, it must release Rj

Safe state

• May allocate resources (up to maximum) in some order with no deadlock
• Over-allocation: system unsafe

Deadlock Avoidance

• Needs information on how processes will request resources
• Includes claim edge (future request) denoted by P ---> R
• Request granted only if no cycle is formed
• Single instance resources only

Banker's Algorithm

• Ensure bank doesn't over-allocate cash
• Check if still in safe state to allocate resources
• If not safe, won't allocate since it might enter an unsafe state

Deadlock Detection

• Algorithm to check for deadlocks and recover

Single instance resource
Use Wait-For graph
Several instances
Uses time-varying data structures found in Banker's Algorithm

Detection algorithm depends on what 2 factors?

• How often is a deadlock likely to occur?
• How many processes are affected by the deadlock?

What deadlock detection do we use for single instance resource?

Wait-for graph

What deadlock detection do we use for several instances?

Time-varying data structures found in Banker's Algorithm

Wait-For Graph

Graph showing processes waiting for resources held by others.

What happens when you terminate processes?

• Abort all in deadlock
• Partial termination but which one?

What happens when you preempt resources?

Consider victim and starvation

Hybrid Approach

• Combined use of basic methods
• Assumes resources are grouped
• Diff. method for each group

Memory Management

• Large array of words with unique address
• Memory sharing
• Memory management algorithms vary

Memory sharing

Several processes in main memory to improve utilization and response

Types of Memory Address

1. Symbolic
2. Relocatable
3. Absolute

Symbolic Memory Address

Variables

Relocatable Memory Address

offset + 100

Absolute Memory Address

Physical addresses
Ex: 255, 254

3 Forms of Efficient Memory Use

1. Dynamic loading
2. Dynamic linking
3. Overlays

Dynamic loading

• Subroutines not loaded until called (unused until never loaded)
• Saves space

EX. Code has math library included (# include math.h). When loaded, it doesn't load whole library, only when called by code

Dynamic linking

• Uses stub as pointer to routine in DLL
• May waste disk space
• Not required to link actual module with program, just give dynamic link (reference) to compiler

EX. Windows has dynamic link library
EX. UNIX has shared objects (dynamic libraries)

Overlays

• Keeps only needed instructions in memory

EX. Code w/ 1000+ lines, don't want to put all that into main memory. So get only needed instructions and keep those in memory

(Overlays) What do you do if no more space?

Overwrite previous instructions that are not needed anymore

Logical address are generated by while Physical Address are generated by _

Logical - CPU

Physical - Memory Management Unit (MMU)

Logical address

• Not entirely occupied by physical memory

• Abstract or change the view of physical address so virtual code can see addresses in their own way

Another name for logical address

Virtual address

Physical address

Physical location in memory hardware where data is stored

What determines how logical and physical addresses are connected? And what is needed for this?

OS

Mapping scheme requires hardware support (MMU) to convert to physical

Swapping

• Used with insufficient memory
• Needs a fast secondary memory for efficiency

Why does Roll out (swap out) and roll in (swap to MM) increase context switch time?

Because context-switching is between main memory and CPU so if you context switch AND swap, CPU relies on process being in main memory then it will increase switch time

What happens when a process is swapped out?

Process is removed from main memory and placed on secondary memory by the scheduler

Context Switch vs Swapping

Context Switch - CPU and main memory

Swapping - main memory & secondary memory

What are good candidates for swapping out?

Waiting processes

• Get from Job queue
• Check which processes are waiting the longest, swap them out then after some time, swap it back in
• Doing this reduces their wait time
• Swap is not permanent

What is the modified version of swapping used in Unix?

• Swapping normally disabled
• Enabled when memory runs out

What is the swapping in Microsoft Windows?

Partial swapping

• Current program swapped out
• User determines swap rather than scheduler

2 Types of Memory Allocation Methods

1. Contiguous
2. Non Contigious

Contiguous Memory Allocation

Process occupies a single continuous block

Contiguous Memory Allocation Algorithms

1. Single-partition
2. Multiple-partition

Single-partition

• OS code either in high or low memory

• Must protect from user codes (uses relocatable addressing or offset so it doesn't overlap given reserved memory addresses)

Types of Multiple-partition Algorithms

1. Fixed
2. Dynamic

Fixed (Multiple-partition Algorithms)

• 1 partition = 1 process
• Multiprogramming limited to number of partitions

Dynamic (Multiple-partition Algorithms)

• Starts with one large hole (that part becomes free)
• Processes arrive and are allocated a block
• Holes become available as processes terminate

What are the algorithms for dynamic storage allocation problem?

1. First-fit - get first hole big enough for process
2. Best-fit - get smallest hole that is big enough
3. Worst-fit - get largest hole

Which algorithm is the fastest?

First-fit

Which algorithm is best for storage utilization?

Best-fit

2 Types of Fragmentation

1. Internal
2. External

External Fragmentation

• Free memory is scattered in small blocks
• Enough memory exists but not contiguous
• Allocation algorithm affects fragmentation

50% Rule in External Fragmentation

Given N allocated blocks, the next 0.5N blocks will be lost due to fragmentation (1/3 unusable memory)

Internal Fragmentation

Allocated memory has unused space within a block due to fixed-size allocation

How to solve external fragmentation?

Compaction (not always possible)

May be combined with swapping

Compaction Algorithms

1. Move processes to one end
2. Create big hole in middle

Types of Non-contiguous Allocation

1. Paging
2. Segmentation
3. Segmentation with paging

Paging

• Fixed-size blocks
• Process address is broken down into pages
• Page table does conversion

What is the size of the process based on? (paging)

Size of process is based on how many pages

What is the size of a frame?

Frame is same size as page to avoid external fragmentation

Pages translate into _?

Pages (logical) translate into frames (physical)

Physical Address

Actual location in memory hardware.

Fragmentation in Paging

• Solves external fragmentation
• Internal fragmentation is present 🡪 page may not be fully occupied

What is the worst case for fragmentation in paging?

n pages + 1 byte

Wasted: page size - 1 byte

Page Table Structure

• Page table storage is system-specific
• Most map one page table per process
• More context-switch time bc need to store page tables in PCB

Shared Pages

• Non-self-modifying code (read-only)
• Only one copy is stored in memory but accessed by many

What happens to the access when you share a page?

• Everyone can access that page to store data but you can't modify it, can only read
• Similar to threads sharing common data within process

What are examples of shared pages? Where are they used?

compilers, editors

Used in time-sharing environment

Segmentation

• Divides logical memory into segments
• More intuitive view of memory (e.g. program divided into segments of different lengths)
• Logical View of Segmentation

Segmentation Hardware

• Two-dimensional to one-dimensional mapping
• Segment table
• Similar to paging except for variable size
• Intel x86 based on segmentation

What does an entry in the segment table consist of?

segment base (starting address) and limit (segment length)

Segmentation with paging

• Solves external fragmentation problem of pure segmentation

• Each segment composed of several equal-sized pages

File System

• Most visible aspect of OS
• Provides mechanism for online storage and access to data and programs
• Mapped on physical devices (usually nonvolatile)

File Basics: Attribute

Name
Type
Location
Size
Security
Date/Time
User ID

File Basics: Operations

• Create

• Write

• Read

• Reposition within file

• Delete

• Truncate (change contents of file without deleting it or changing its location)

File Basics: Types of Access Methods

1. Direct
2. Sequential
3. Indexed

Access Methods: Direct

Direct access to a file block

Access Methods: Sequential

• Contents accessed sequentially
• Most basic way of file access
• Used by compilers and editors
• Pointer is made, which links to file's base address

In sequential access, what happens if user wishes to read the 1st word of file?

Pointer gives it to them and raises its value to next word

In sequential access, how is the data in the file evaluated?

In order that it appears in file and so it's easy to access a file's data

Access Methods: Indexed

• Variant of direct access

• Maintains an index w/ address

• OS searches for address in index which points to the block

Directory Structure: How are file systems structured?

• File system divided into partitions or volumes (PC and Mac)

• Each partition contains info about files (directory, FAT, etc.)

Directory Structure: Types of Logical Schemes

1. Single-level
2. Two-level
3. Tree-structured
4. Acyclic graph
5. General graph

Single-level Logical Scheme

• Everything in one directory, easy to do
• Since everything in one directory, no duplicate file names

In a Single-level Logical Scheme, if multiple users have access, how will you divide the files?

Prefixing file names with usernames to avoid name conflicts

• many ways to do this, this is just 1 solution

Two-level Logical Scheme

• Masterfile directory comprised of different users then each user has a file directory
• Every directory comes from master file directory

True or False: In Two-level Logical Scheme, you can access files of other users

FALSE

• Isolated file directories per user
• Can't access files of other users

Tree-structured Logical Scheme

• Different directories have sub directories

• 1 parent per child

• Root directory on top that spans to other directories

True or False: In a Tree-structured Logical Scheme, you can have subdirectories

TRUE

Can have files or subdirectories under

Acyclic graph Logical Scheme

• Extension of tree structure but not as strict as tree
• No cycles
• Enables logical grouping and use of files across multiple locations

Which logical scheme permits shared subdirectories? And how does it do it?

Acyclic graph Logical Scheme

via Links

How do Acyclic graphs save space?

Users can share files without duplication