CSE 3430 Pt3

Operating System

Software (a program!) that converts hardware into a useful form for applications:

Make sure the system operates (1) correctly, (2) efficiently, and (3) in an easy to

use manner

Virtualization

Make the system behave so that each application can

run as though it has certain critical resources all to itself;run as though it has certain critical resources all to itself;

i.e., make the system work so that each aplication cani.e., make the system work so that each aplication can

run as though it hasrun as though it has exclusive useexclusive use of each criticalof each critical

resource in the system, such as the CPU, main memory,resource in the system, such as the CPU, main memory,

and disk (Make it look like there'sand disk (Make it look like there's no sharing, evenno sharing, even

though there always isthough there always is).).

 For example, make each application run as though itFor example, make each application run as though it

has exclusive use of the CPU, exclusive use of all ofhas exclusive use of the CPU, exclusive use of all of

main memory, and exclusive use of disk (even thoughmain memory, and exclusive use of disk (even though

no application has exclusive use of these

Concurrency

Many events are occurring simultaneously and may interact with oneare occurring simultaneously and may interact with one another

Persistence

Preserve information permanently (even when

power goes off)power goes off)

Process

An execution stream in the context of a

process execution state. It represents a running (active) program that the OS can pause and resume.

Execution Stream

• Stream (sequence) of executing instructions

• Running piece of code

Process Execution State

everything that the running code can affect or be affected by, including all registers, address space (code, heap, stack), and open files.

Process vs. Program

A program is static code and data stored on disk, while a process is a dynamic instance of that code and data executing in memory.

Process API (Interfaces/Actions)

• Create

• Destroy

• Wait (this means wait on another process to

finish

running)

Process Creation

The OS loads the program’s code and static data into memory, allocates stack and heap space, sets up I/O (stdin, stdout, stderr), and creates a process control block (PCB).

What must be done for a process to start execution

Once everything is in memory, the OS must schedule the process and start it at its entry point (the first instruction in main()).

Three Process States

Ready – everything needed to run is in memory, but not executing on the CPU

Running – process is executing instructions on the CPU

Blocked – process is waiting for an event (e.g., I/O, lock)

CPU Time-Sharing

only one process uses the CPU at a time, but the OS rapidly switches between processes to give each the illusion of having its own CPU

Direct Execution

process runs directly on hardware with no restrictions

Limited Direct Execution

process runs directly on hardware, but OS and hardware retain control via privilege levels, system calls, and interrupts

Problems with Direct Execution

Access memory or disk it should not,

Run forever without giving up the CPU,

Perform slow operations (e.g., I/O) and waste CPU time

How Limited Direct Execution Is Provided

Status bit / privilege levels (user mode vs. kernel mode)

System calls (traps)

Interrupts and exceptions

Interrupt

raised by hardware devices (e.g., timer, disk)

Exception

caused by the currently executing instruction

Trap (Type of Exception)

instruction does not re-execute after OS handles it (used for system calls, errors)

Fault (Type of Exception)

instruction re-executes after OS fixes the problem

Why the CPU Changes Mode from User to Kernel

Only the CPU can safely change the mode bit to kernel mode; otherwise user processes could change it themselves.

The CPU does this on interrupts and exceptions.

Returning from Kernel Mode to User Mode

The OS changes the mode bit back to user mode and simultaneously loads the next user instruction into the program counter

What User Processes cannot do

User processes cannot:

Perform general memory access

Perform disk I/O

Execute privileged instructions (e.g., changing the PC)

What Happens If a User Process Violates Restrictions

The CPU traps to the OS, and the process is terminated (e.g., segmentation fault).

How the CPU Is Taken Away from a Process

The OS regains control using a timer interrupt, which forces a switch back to kernel mode so the dispatcher can run.

Context Switch

saves the execution state of one process and restores another.

Saved/restored data includes all registers (PC, stack pointer, status register), stored in the PCB.

Problems with Cooperative (Voluntary) Multitasking

Processes may not voluntarily give up the CPU, leading to CPU hogging or system lockup.

No modern OS uses this approach

True Multitasking

guarantees the OS regains control using periodic timer interrupts, allowing fair CPU sharing among processes.

Ready to Running

process is scheduled on the CPU

Running to Ready

process is descheduled (e.g., time slice expires)

Running to Blocked

process initiates I/O or waits for an event

Blocked to Ready

I/O or event completes

Scheduler Optimization Parameters

Minimize:

Turnaround time – time from arrival to completion

Response time – time until process first runs

Waiting time – time spent in ready queue

Overhead – context-switch cost

Maximize:

Throughput – jobs completed per unit time

Resource utilization – keep CPU and disk busy

Fairness – equal CPU share over time

Turnaround Time

= completion_time − arrival_time

Response Time

= first_run_time − arrival_time

Waiting Time

= completion_time − arrival_time − run_time

FIFO/FCFS

run jobs in arrival order (non-preemptive)

SJF

run job with smallest run time (non-preemptive)

STCF

run job with least remaining time (preemptive)

RR

rotate jobs using fixed time slices (preemptive)

Convoy Effect

Short jobs wait behind long jobs

Convoy Effect (Schedulers subject to the convoy effect)

FIFO / FCFS

SJF

Why RR Gives Better Response Time

RR schedules processes quickly using short time slices, allowing interactive jobs to run early instead of waiting behind long jobs.

Time Quantum (Time Slice)

the fixed amount of CPU time a process may run before being preempted in RR scheduling.

When RR Is Worse Than FIFO

RR has worse average turnaround time than FIFO when all jobs have equal length due to frequent context switches.

I/O and CPU Scheduling

When a process performs I/O, it becomes blocked, and the scheduler runs another ready process so the CPU is not idle.

MLFQ (Multi-Level Feedback Queue)

uses multiple priority queues with round-robin scheduling at each level. Higher-priority queues preempt lower ones.

Use of History in MLFQ

MLFQ uses past behavior (CPU burst history) to predict future behavior and adjust process priority.

Goals of the MLFQ Scheduler

Good response time for interactive jobs

Good turnaround time for batch jobs

General-purpose scheduling without knowing run time

Problems with MLFQ and Solutions

Problems:

Inflexibility – processes that change behavior may be stuck at low priority

Starvation – low-priority jobs may never run

Solutions:

Priority boosting – periodically raise all jobs to top priority

Shared Data Storage

Shared data must be stored on the heap. It cannot be stored on the stack, because stacks are private to each thread.

Thread

a sequence of execution that is separate from other execution sequences within the same process.

Each Thread Has

A thread ID (tid)

A register set, including PC, IR, stack pointer, and data registers (e.g., rax)

How Multithreaded Processes Improve Performance

Multithreaded processes can run multiple threads simultaneously on different CPU cores, allowing the process to complete work faster.

Critical Section (Critical Section Code)

Code that accesses shared data

Mutual Exclusion

the requirement that at most one process or thread may execute critical section code at any given time.

Indeterminate Output

occurs when running the same program twice with the same input produces different output.

Why Mutual Exclusion Is Important

Guaranteeing mutual exclusion prevents multiple threads from accessing shared data simultaneously and prevents indeterminate output.

Binary Semaphore

stores one of two values: 0 or 1.

Its operations are:

semWaitB (P): blocks if value is 0; if 1, sets it to 0 and proceeds

semSignalB (V): wakes a blocked process if one exists; otherwise sets value to 1

semWaitB (P)

blocks if value is 0; if 1, sets it to 0 and proceeds

semSignalB (V)

wakes a blocked process if one exists; otherwise sets value to 1

Using a Binary Semaphore as a Lock

A binary semaphore initialized to 1 can act as a lock:

semWaitB is used to acquire the lock before entering the critical section

semSignalB is used to release the lock after leaving the critical section

This guarantees only one thread executes the critical section at a time

File

an array of persistent bytes that can be read and written. _____s are necessary because main memory, registers, and caches lose data when power is turned off.

Inode Number

Advantage: Simple and efficient for the OS

Disadvantage: Arbitrary and not meaningful to humans

Path (String) Name

Advantage: Human-readable and organized using directories

Disadvantage: Expensive due to directory traversal on every access

File Descriptor

Advantage: Efficient access using cached inode data in memory

Disadvantage: Only valid while the file is open

Block

the unit of allocation for files on disk.

Methods Used to Allocate Blocks for Files

Contiguous allocation

Small number of extents

Linked allocation

File-Allocation Table (FAT)

Contiguous Allocation

File stored in consecutive blocks

Metadata: starting block + file size

Fast sequential and random access

Suffers from external fragmentation, hard to grow

Small Number of Extents

File stored in several contiguous regions

Metadata: small array of (starting block, size) pairs

Reduces fragmentation, allows limited growth

Linked Allocation

File stored as a linked list of blocks

Metadata: first block; each block stores pointer to next

No external fragmentation, easy growth

Very poor random access, pointer overhead

File-Allocation Table

Linked allocation using a centralized table

Metadata: first block + FAT table

Faster random access than linked allocation

FAT can be cached in memory; table size scales with disk size

Motivations for Virtualization of Memory

Support multiprogramming (many processes at once)

Prevent processes from corrupting the OS or each other

Give each process the illusion of a private address space

Four Goals of Multiprogramming

Transparency – processes are unaware memory is shared

Protection & Privacy – processes cannot access others’ memory

Efficiency – minimize wasted memory (fragmentation)

Sharing – allow controlled sharing between cooperating processes

What Is in a Process Address Space

Code

Heap

Stack

Static vs. Dynamic Parts of Address Space

Dynamic: Heap, Stack

Static: Code

Time sharing (of memory)

Only one process is in main memory at a time; other processes are swapped to disk to avoid address conflicts. Does not work well because swapping on every context switch causes extremely poor performance

Dynamic relocation (base + bounds)

The MMU adds a base register to each logical address and checks it against a bounds register to ensure protection and correct relocation.

Segmentation

Divides a process’s address space into logical segments (code, heap, stack), each with its own base and bounds.

Paging

Divides memory into fixed-size pages and maps virtual pages to physical page frames using a page table

Advantages / Disadvantages of Base + Bounds

Advantages

Simple and fast

Provides protection

Supports relocation

Disadvantages

Requires contiguous allocation

Wastes unused space (heap–stack gap)

No partial sharing

Virtual to Physical Translation with Segmentation

Segment bits select base/bounds pair

Offset is checked against bounds

Offset is added to base to get physical address

If offset ≥ bounds → error

Advantages / Disadvantages of Segmentation

Advantages

Independent growth of heap and stack

Fine-grained protection

Supports sharing

Disadvantages

Each segment must be contiguous

External fragmentation

Page Size

Always 2ⁿ bytes (power of two)

Virtual Page vs. Physical Page Size

They must be the same size

Fundamental Idea of Paging

Break address space and physical memory into fixed-size pages

Eliminate need for contiguous allocation

How Paging Works

Virtual address → VPN + offset

VPN mapped to physical frame via page table

Offset copied directly

Virtual Address Bits with Paging

Most significant bits: Virtual Page Number (VPN)

Least significant bits: Page Offset

Fragmentation Eliminated by Paging

External fragmentation

Fragmentation Still Possible with Paging

Internal fragmentation

VPN to PPN Translation

Performed using the page table

Page Table

Data structure that maps virtual page numbers to physical page frames

Virtual to Physical Address Translation

Use VPN to index page table

Get physical frame number

Append offset to form physical address

Page Tables Storage

In main memory (OS memory)

Data Stored in Page Table Entries (PTEs)

Physical frame number

Valid bit

Present bit

Protection bits (r/w/x)

Reference bit

Dirty bit

Advantages of Paging

No external fragmentation

Easy allocation and freeing

Supports virtual memory

Allows partial process residency in RAM

Disadvantages of Paging

Internal fragmentation

Large memory overhead for page tables

How Paging Allows More Virtual Memory Than RAM

Only small portions of each process’s address space are in RAM

Typically 2–3% of a process is resident at a time

Paging In

Copying a page from disk to RAM so a process can access it