This OS scheduler simulates how a CPU manages the execution of multiple processes using fundamental operating system concepts. It recreates a realistic multi process environment using interprocess communication and scheduling algorithms.
The scheduler determines the execution order of processes based on their status and manages them using a data structure that tracks whether each process is Running, Ready, or Blocked (doing I/O, using other resources than CPU or waiting on unavailable resources). Upon creation, each process transitions through these states, closely mimicking real-world OS behavior.
Developed in C for the Linux platform, the project utilizes POSIX APIs including message queues and shared memory to coordinate process execution and synchronization of the system.
This was the final project for the CMPS303 - Operating Systems Course.
The system consists of four main components. The Process Generator, the Clock, the Scheduler and Child Processes.
- Reads process data from an input text file and creates PCB (Process Control Block) for each process read.
- Prompts the user to select the scheduling algorithm and specify the time quantum if Round Robin is chosen.
- Initializes the Clock and Scheduler processes, and passes the selected algorithm and quantum to the Scheduler.
- Sends each process to the Scheduler via a message queue at its corresponding arrival time, as tracked by the Clock.
- Acts as the system’s global time reference.
- Broadcasts the current time to all components (e.g. Process Generator and Scheduler) using shared memory.
- Synchronizes all processes to ensure consistent execution and coordinated event logging.
-
Serves as the brain of the system, making all key decisions regarding process execution.
-
Receives processes from the Process Generator via the message queue shared with the Process Generator.
-
Responsible for memory allocation and deallocation for processes using the buddy system algorithm with a total memory size of 1024 bytes.
-
Manages process execution using the chosen scheduling algorithm.
-
For each scheduled process, creates a separate Process (child process) to simulate actual process execution.
-
Controls execution using signals such as SIGCONT (to resume) and SIGSTOP (to pause), simulating CPU time allocation.
-
Tracks and switches between processes, enforcing the time quantum and mimicking preemptive multitasking.
-
After a process completes, it is properly reaped to free system resources and avoid leaving zombie processes.
-
Maintains detailed logs of process timings and memory allocation for analysis.
-
Ensures proper cleanup of all used system resources such as shared memory and message queues after the simulation ends.
- Emulates a real running process created via
fork()by the Scheduler. - Executes for its assigned runtime duration.
- Started, Resumed and Stopped by Scheduler using signals.
- Sends a signal to the Scheduler upon completion to notify it for cleanup.
- The Scheduler reaps the process to free system resources and avoid zombies.
The following data structures were implemented to support the scheduling and memory management components:
• Circular Queue: Used to store Process Control Blocks (PCBs) for Round Robin (RR) scheduling, enabling efficient enqueue and dequeue operations in a cyclic manner.
• Priority Queue: Used to store PCBs for Highest Priority First (HPF) scheduling, ensuring processes with the highest priority are selected first.
• Buddy Memory System: Implemented as a binary tree to manage dynamic memory allocation for PCBs, allowing efficient allocation and deallocation of memory blocks in powers of two.
• Selects the PCB with the highest priority from the Priority Queue.
• Enqueues PCBs with the highest priority first, then dequeues them one by one without preemption.
• Result: Ensures high-priority processes execute first, maintaining strict priority ordering.
• Processes are enqueued in a Circular Queue and executed for a fixed time quantum.
• If a new process arrives at preemption time, it is enqueued before the current process, ensuring fair scheduling.
• Result: Provides equitable CPU time distribution among processes.
• Selects the process with the shortest remaining time from the queue.
• Preempts the current process if a new process with a shorter remaining time arrives.
• Result: Minimizes average waiting time by prioritizing processes closest to completion.
• Implemented to manage memory allocation for PCBs.
• Uses a binary tree where each node represents a memory block, with sizes as powers of two (e.g., 256, 512, 1024 bytes).
• Allocation: When a PCB requests memory (e.g., 256 bytes), the system finds the smallest free block of at least the requested size (rounded to the next power of two). If the block is larger, it is split into two equal "buddy" blocks, and the process continues recursively until a suitable block is found. The block is then marked as allocated, storing the PCB’s ID and address range.
• Deallocation: When a PCB’s memory is freed, the block is marked as free. The system checks if its buddy block is also free and, if so, merges them into a larger block. This process repeats up the tree, reducing fragmentation.
• Result: Efficiently allocates and deallocates memory for PCBs, minimizing external fragmentation by maintaining power-of-two block sizes. The system supports dynamic memory needs of processes, as demonstrated by allocating 256-byte blocks for multiple PCBs and correctly handling deallocations without overwriting existing allocations.
The following assumptions were made during implementation:
• SRTN: When two processes have the same remaining time, the process already running continues to avoid unnecessary context switches.
• Buddy System: Memory requests are rounded up to the next power of two to fit the buddy system’s block structure. The minimum block size is assumed to be sufficient for the smallest PCB memory requirement.
Prompts the user to:
- Select the scheduling algorithm.
- Enter the time quantum (only required if Round Robin is selected).
Supports the following CPU scheduling algorithms:
-
SRTN (Shortest Remaining Time Next)
Preemptive version of SJF (Shortest Job First) that always selects the process with the shortest remaining running time. -
HPF (Non Preemptive Highest Priority First)
Schedules processes based on static priority values (lower value = higher priority). -
RR (Round Robin)
Time sliced scheduling with a configurable quantum, simulating preemptive multitasking.
Clean separation between the Process Generator, Scheduler, Process and Clock, each implemented as an independent process to simulate a real OS environment.
Simulates actual process behavior by forking child processes, with execution controlled using SIGSTOP and SIGCONT signals.
Employs POSIX APIs including message queues and shared memory for efficient and safe interprocess communication.
Allocates and tracks memory usage for each process using the buddy managment system. If no sufficient memory is available for a process, this process is deferred using a Memory Waiting Priority Queue (the lower the memory required, the higher the priority).
Logs include process execution order, state transitions, memory allocations, and statistics such as average waiting time and CPU utilization which are useful for performance analysis.
Includes a custom test generator file named test_generator.c to create edge-case and stress-test scenarios.
Cleans up system resources after execution by detaching shared memory, removing message queues and reaping zombie processes.
- George Ayman
- Mark Maged Nageh
- Mohamed Ahmed Mahmoud
- Omar Ahmed Reda
RR-Demo.mp4
- Windows with WSL (Windows Subsystem for Linux) enabled
- GCC (GNU Compiler Collection)
- Clone the Repository
git clone https://github.com/3atar2004/OS-Scheduler
- Navigate to the project directory
cd FolderName
-
Open the project folder in your preferred IDE
Recommended: Visual Studio Code with WSL extension for smooth Linux integration
-
Open a new Ubuntu (WSL) terminal and write the following commands
-
You can view or edit the process data in
processes.txt⚠️ Keep the format unchanged -
To generate new processes test cases using the test generator
gcc test_generator.c -o test_generator.out ./test_generator.out -
run the following command
make run -
Observe output in
memory.log,scheduler.log,scheduler.perffor logging and analysis.