Operating System Scheduler and Memory Management Simulator

Project Block Diagram

This project is a multi-process operating system simulator that implements several CPU scheduling algorithms alongside a virtual memory management unit with demand paging. The system is built using System V IPC mechanisms and follows a modular architecture where the scheduler, clock, process generator, and individual processes execute as separate coordinated processes.

Overview

The simulator models a complete operating system scheduling pipeline from process admission to termination. It supports both single-queue and distributed scheduling architectures, integrated with a Memory Management Unit (MMU) that handles virtual-to-physical address translation, page faults, and NRU (Not Recently Used) page replacement.

Key capabilities include:

Multi-Algorithm Scheduling: Highest Priority First (HPF), Round Robin (RR), First-Come First-Served (FCFS), and a distributed FCFS master with work stealing.
Virtual Memory: Demand paging with a 32-frame physical memory and 64-page virtual address space per process.
Process Synchronization: Tick-level synchronization between the generator, scheduler, and clock via shared memory and message queues.
Comprehensive Logging: Per-event scheduler logs and aggregated performance metrics.

System Architecture

The system is composed of four primary runtime entities:

Process Generator (process_generator.c): Reads process definitions from an input file, prompts the user for scheduling configuration, spawns the system clock and scheduler, and dispatches processes to the scheduler at their arrival times.
System Clock (clk.c): Maintains a global simulated time counter in a shared memory segment that all processes attach to for synchronized execution.
Scheduler (scheduler.c): The central dispatcher that receives the selected algorithm and parameters, polls for incoming processes, and delegates tick-level decisions to the appropriate algorithm implementation.
Process Worker (process.c): A simulated user process that executes tick-by-tick, reads memory access requests from a per-process file, and communicates them to the scheduler via shared memory.

Supporting modules include the MMU, request reader, PCB hash table, multiple queue implementations, and IPC helpers.

Core Components

Process Generator

The generator is the system bootstrapper. It performs the following:

Parses the process input file (processes.txt), skipping comments and validating fields.
Presents an interactive menu for algorithm selection and parameter input.
Creates the system message queue and forks the clock and scheduler processes.
Enters a time-synchronized loop where processes are sent to the scheduler via message queue (mtype=1) when their arrival time is reached.
Sends a per-tick synchronization message (mtype=4) to the scheduler to indicate that all arrivals for the current tick have been dispatched.
Sends a global completion message (mtype=3) when all processes have been injected, then waits for the scheduler to finish.

System Clock

The clock module allocates a single shared memory integer (SHKEY = 300) and increments it every simulated second. All other processes attach to this segment via initClk() and read the current time via getClk(). The clock cleans up its shared memory on SIGINT.

Scheduler Dispatcher

The main scheduler attaches to the message queue created by the generator and performs initialization in the following order:

Receives the control message (mtype=2) containing the scheduling algorithm type and its parameters.
Initializes the algorithm-specific data structures via a strategy pattern (scheduler_type.c).
Enters the main loop, blocking on the per-tick synchronization message (mtype=4) from the generator.
Polls for incoming process messages (mtype=1) and enqueues them.
Checks for terminated processes via SIGCHLD, updates PCBs, and logs completion.
Invokes the algorithm-specific onClockTick handler.
Determines system completion when the generator is done and no ready or running processes remain.

Process Worker

Each simulated process is forked by the scheduler and executes process.out with its remaining time and process ID as arguments. Its execution loop:

Synchronizes with the system clock.
Decrements remaining time on each tick.
Reads memory requests from requests_{pid}.txt and publishes the next request to shared memory (REQUESTS_SHM_KEY_BASE).
Blocks on SIGUSR1 between ticks and resumes on SIGCONT.
Exits with its accumulated waiting time as the status code upon completion.

Scheduling Algorithms

The scheduler uses a unified strategy interface where the active algorithm is selected at runtime. All algorithms maintain a ready queue, a running process pointer, and a disk wait queue for memory-blocked processes.

Highest Priority First (HPF)

Uses a priority-ordered queue where lower numeric values indicate higher priority.
Tie-breaking is performed by arrival time.
Preemptive: If a newly arrived process has a strictly higher priority than the currently running process, the running process is stopped via SIGTSTP and returned to the ready queue.

Round Robin (RR)

Maintains a circular queue of ready processes.
Quantum (nParam1): The number of ticks a process executes before being preempted.
K-Parameter (nParam2): Every K completed quantums, the MMU clears all reference (R) bits across physical frames to support the NRU replacement algorithm.
When the quantum expires and other processes are waiting, the running process is stopped and enqueued. If it is the only process, it receives a new quantum.
Integrated with the MMU: processes that incur page faults are moved to the disk wait queue and resumed automatically when the disk operation completes.

First-Come First-Served (FCFS)

Standard FIFO queue implemented as a doubly-linked list.
Processes run to completion without preemption.
Supports FCFSPopTail to enable work-stealing operations in the distributed variant.

Distributed FCFS with Work Stealing

This architecture introduces a master scheduler that load-balances across two independent child FCFS schedulers.

Master Responsibilities:

Routes incoming processes to the child with the lower queue count.
Maintains shared memory segments for each child tracking COUNT and TOTALLOAD.
Every N ticks (check interval), evaluates the load difference between the two children.
If the difference exceeds threshold M, initiates a work-stealing sequence:
- Sends MSG_CMD_STEAL_FROM to the overloaded child (victim).
- Sends MSG_CMD_STEAL_TO to the underloaded child (thief).
Applies a 3-tick stealing penalty during which no further stealing is attempted.
Synchronizes children using semaphores (SEM_KEY_SCHEDULER_1, SEM_KEY_SCHEDULER_2).

Child Scheduler Responsibilities:

Receives forwarded processes from the master via the routing message queue (FCFS_ROUTING_MSG_KEY).
On MSG_CMD_STEAL_FROM, pops the tail of its FCFS queue and sends the stolen PCB to the thief via a dedicated stolen-process message.
On MSG_CMD_STEAL_TO, blocks until it receives the stolen PCB and enqueues it.
Updates the master's shared memory with its current count and total load after every tick.
Handles termination messages from the master and acknowledges with MSG_ACK_TERMINATE.

Memory Management Subsystem

The MMU implements a paged virtual memory system with demand paging and a global frame pool.

Physical and Virtual Memory Layout

Physical Memory: 512 bytes divided into 16-byte pages, yielding 32 physical frames.
Virtual Address Space: Up to 64 virtual pages per process.
Page Table: Each process is assigned one physical frame to store its page table. Page table frames are marked non-evictable.

Page Table Entry

Each entry tracks:

nPhysicalFrameIdx: 5-bit index into physical memory.
bIsValid: Valid bit.
nR_bit: Referenced bit (used by NRU).
nM_bit: Modified bit (used by NRU and write-back).

NRU Page Replacement

When a free frame is needed and none exist, the MMU invokes the NRU algorithm:

Classifies all data frames into four classes based on (R << 1) | M:
- Class 0: (R=0, M=0)
- Class 1: (R=0, M=1)
- Class 2: (R=1, M=0)
- Class 3: (R=1, M=1)
Selects the first frame found in the lowest non-empty class.
If the victim has M=1 (dirty), a write-back to disk is required, and the victim process is blocked.

Page Fault Handling

A page fault occurs when a process accesses a virtual page whose valid bit is clear. The handler:

Allocates a physical frame (evicting via NRU if necessary).
If a dirty victim was evicted, marks it for write-back and blocks the victim process.
Loads the requested page from disk.
Disk Wait Times:
- 10 ticks for a standard page load.
- 20 ticks if a dirty page must be written back first.
The faulted process is moved to the disk wait queue (pDiskQueue), stopped via SIGTSTP, and automatically returned to the ready queue when its disk timer reaches zero.

Memory Request Flow

The process worker reads data/requests/requests_{pid}.txt and writes the next request (virtual page and access type) to request shared memory.
During its tick, the scheduler inspects the shared request.
The MMU checks the page table. If valid, it updates the R and M bits and records the reference time.
If invalid, the fault handler executes, logging the event to memory.log.

Inter-Process Communication

Mechanism	Key / ID	Purpose
Message Queue	`SCHEDULER_MSG_KEY = 400`	Process dispatch (mtype=1), algorithm config (mtype=2), global done (mtype=3), tick sync (mtype=4)
Shared Memory	`SHKEY = 300`	System clock integer
Shared Memory	`REQUESTS_SHM_KEY_BASE = 500`	Process-to-scheduler memory request buffer
Shared Memory	`FCFS_MASTER_SHM_KEY_1 = 6001`	Child 1 metrics (count, totalLoad)
Shared Memory	`FCFS_MASTER_SHM_KEY_2 = 6002`	Child 2 metrics (count, totalLoad)
Message Queue	`FCFS_ROUTING_MSG_KEY = 5000`	FCFS master-to-child routing and stealing protocol
Semaphores	`SEM_KEY_SCHEDULER_1 = 7001`	Child 1 tick synchronization
Semaphores	`SEM_KEY_SCHEDULER_2 = 7002`	Child 2 tick synchronization

Message Types

stSchedulerMessage (mtype=1): Carries a stProcess from generator to scheduler.
stControlMessage (mtype=2/3/4): Carries algorithm selection, parameters, and done signals.
stForwardMessage: Used by FCFS master to forward a PCB to a child.
stStealMessage: Used during work stealing to transfer a PCB from victim to thief.
stSignalMessage: Used for steal commands and termination acknowledgments.

Process Lifecycle

Admission: The generator creates a stProcess and sends it to the scheduler. The scheduler wraps it in a stPCB with nPID = -1.
First Dispatch: The scheduler selects the process and calls startProcess(), which forks the worker executable. The PCB is inserted into the global hash table.
Running: The worker runs tick-by-tick. The scheduler sends SIGUSR1 or SIGCONT each tick to grant CPU time.
Preemption: For RR and HPF, the scheduler stops the process with SIGTSTP, records the last activity time, and returns it to the ready queue.
Blocking: If the process incurs a page fault, the scheduler stops it and places it in the disk wait queue.
Resumption: When the disk timer expires, the process is moved from the disk queue back to the ready queue.
Termination: The worker exits. The SIGCHLD handler captures the exit status (waiting time) and marks the PCB as TERMINATED. The scheduler logs the finish event and, for RR, deallocates the process's page table and frames.

Directory Structure

├── clk.c                       # Emulated system clock
├── process_generator.c         # Bootstrap and process injection
├── scheduler.c                 # Main scheduling dispatcher
├── scheduler_type.c / .h       # Algorithm strategy pattern and scheduler struct
├── process.c                   # Simulated user process worker
├── process_management.c / .h   # Fork, start, and stop primitives
├── MMU.c / .h                  # Memory management, paging, and NRU
├── request_reader.c / .h       # Per-process memory request file parser
├── requests_ipcs.c / .h        # Request shared memory creation and attachment
├── queue.c / .h                # Priority queue for HPF
├── RR_Queue.c / .h             # Circular queue for Round Robin
├── fcfs_queue.c / .h           # Doubly-linked FIFO queue for FCFS
├── fcfs_master.c / .h          # Distributed FCFS master logic
├── fcfs_shceduler.c            # FCFS child scheduler executable
├── fcfs_master_shm.c / .h      # Shared memory helpers for FCFS master
├── fcfs_scheduler_msg_types.h  # Message type definitions for FCFS protocol
├── fcfs_constants.h            # IPC keys for FCFS subsystem
├── sem_helpers.c / .h          # Semaphore P/V operations
├── pcb_hashtable.c / .h        # PID-to-PCB hash table
├── pcb_type.h                  # Process Control Block definition
├── process_type.h              # Process metadata (arrival, runtime, priority, base, limit)
├── message_types.h             # IPC message structure definitions
├── logger.c / .h               # Event logging and performance statistics
├── normal_queue.c / .h         # FIFO disk wait queue
├── common_types.h              # Access type enumeration (READ, WRITE, IDLE, TERMINATE)
├── headers.h                   # Common system includes and clock accessors
├── scheduling_constants.h      # Algorithm type constants
└── test_generator.c            # Utility to generate random process sets

Input Specifications

Process Definition File (`processes.txt`)

#id arrival runtime priority
1   1       6       3
2   2       4       1
3   5       2       2

For RR processes, each line additionally includes base and limit:

#id arrival runtime priority base limit
1   1       6       3       0    10

Fields:

id: Unique process identifier.
arrival: Simulation tick at which the process arrives.
runtime: Total CPU time required.
priority: Lower values indicate higher priority.
base: Starting disk address for the process's virtual memory image.
limit: Number of virtual pages in the process's address space.

Memory Request File (`requests_{pid}.txt`)

#time address mode
0     0x10    r
2     0x25    w

Fields:

time: The process runtime tick at which the request is issued.
address: Hexadecimal virtual address.
mode: r for read or w for write.

Build and Execution

Compile the system components:

gcc -o clk.out clk.c
gcc -o process.out process.c request_reader.c requests_ipcs.c
gcc -o scheduler.out scheduler.c scheduler_type.c \
    queue.c RR_Queue.c fcfs_queue.c fcfs_master.c \
    hpf.c logger.c pcb_hashtable.c process_management.c \
    MMU.c normal_queue.c sem_helpers.c fcfs_master_shm.c -lm
gcc -o process_generator.out process_generator.c

Run the simulator:

./process_generator.out processes.txt

The generator will prompt for the scheduling algorithm and its parameters. The clock, scheduler, and process workers will execute automatically, producing log files in the working directory.

Output and Logging

Scheduler Event Log (`scheduler.log`)

Records every state transition with the following columns:

At time X process Y started/stopped/resumed/finished arr W total Z remain Y wait K

On termination, additional metrics are appended:

TA X WTA Y.ZZ

Performance Summary (`scheduler.perf`)

Generated after all processes complete:

CPU utilization: Percentage of total elapsed time spent executing processes.
Avg WTA: Average weighted turnaround time.
Avg Waiting: Average waiting time.
Std WTA: Standard deviation of weighted turnaround time.

Memory Log (`memory.log`)

Records memory subsystem events:

PageFault upon VA {address} from process {id}
Free Physical page {idx} allocated
Swapping out page {idx} to disk
At time {t} disk address {d} for process {id} is loaded into memory page {p}.

Algorithm Configuration Parameters

Algorithm	Parameter 1	Parameter 2
HPF	Unused	Unused
RR	Quantum (time slices per turn)	K (quantums between R-bit clears)
FCFS Master	M (load difference threshold for stealing)	N (tick interval between steal checks)

Design Notes

Tick Synchronization: The generator and scheduler coordinate on a per-tick basis using message type 4 to ensure that processes are only dispatched and scheduled after the generator has finished scanning the current time's arrivals.
Work Stealing Safety: The FCFS master uses a stealing penalty cooldown to prevent thrashing and ensures that steal operations are atomic from the master's perspective by sending paired commands to the victim and thief.
Memory Consistency: The MMU synchronizes R-bits between the physical frame metadata and the owning process's page table entries. The RR scheduler clears all R-bits every K quantums to ensure the NRU algorithm sees recent reference history.
Resource Cleanup: All modules implement cleanup handlers for SIGINT that detach shared memory, destroy semaphores, remove message queues, and free allocated PCBs and queues.

Name		Name	Last commit message	Last commit date
BlockDiagram		BlockDiagram
include		include
src		src
.clang-format		.clang-format
.gitattributes		.gitattributes
.gitignore		.gitignore
Makefile		Makefile
README.md		README.md
log.md		log.md
processes.txt		processes.txt

Latest commit

History

Folders and files

Repository files navigation