Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
CSCI 4210 — Operating Systems
Simulation Project Part II (document version 1.0)
Processes and CPU Scheduling
Overview
• This assignment is due in Submitty by 11:59PM EST on Wednesday, April 3, 2024
• This project is to be completed either individually or in a team of at most two students; teams
are formed in the Submitty gradeable, but do not submit any code until we announce that
auto-grading is available
• Note that you can change teams from Part I to Part II
• Beyond your team (or yourself if working alone), do not share your code; however, feel free
to discuss the project content and your findings with one another on our Discussion Forum
• To appease Submitty, you must use one of the following programming languages: C, C++,
Java, or Python (be sure you choose only one language for your entire implementation)
• You will have 16 penalty-free submissions, after which a small penalty will be applied
• You can use at most three late days on this assignment; in such cases, each team member
must use a late day
• Given that your simulation results might not entirely match the expected output on Submitty,
we will cap your auto-graded grade at 50 points even though there will be more than 50
auto-graded points available in Submitty; this should help you avoid the need to handle
unusual corner cases, which are not an important aspect of this project
• All submitted code must successfully compile and run on Submitty.
• If you use C or C++, your program must successfully compile via gcc or g++ with no warning
messages when the -Wall (i.e., warn all) compiler option is used; we will also use -Werror,
which will treat all warnings as critical errors; the -lm flag will also be included.
• For source file naming conventions, be sure to use *.c for C and *.cpp for C++; in either
case, you can also include *.h files
• If you use Java, name your main Java file Project.java, do not use the package directive
• For Python, you must use python3; be sure to name your main Python file project.py
• For Java and Python, be sure no warning messages or extraneous output occur during com-
pilation/interpretation
• Please “flatten” all directory structures to a single directory of source files before submitting
your code
2
Project specifications
For Part II of our simulation project, you will simulate an operating system given the set of processes
pseudo-randomly generated in Part I. The overall focus will again be on processes, assumed to be
resident in memory, waiting to use the CPU. Memory and the I/O subsystem will not be covered
in depth in either part of this project.
Conceptual design — (from Part I)
A process is defined as a program in execution. For this assignment, processes are in one of the
following three states, corresponding to the picture shown further below.
• RUNNING: actively using the CPU and executing instructions
• READY: ready to use the CPU, i.e., ready to execute a CPU burst
• WAITING: blocked on I/O or some other event
RUNNING
STATE
READY
STATE
WAITING (on I/O)
STATE
+-----+ +---------------------+
| | +-------------------+ | |
| CPU | <== | | | | | | I/O Subsystem |
| | +-------------------+ | |
+-----+ <<< queue <<<<<<<<< + ------------------------------- +
Processes in the READY state reside in a queue called the ready queue. This queue is ordered
based on a configurable CPU scheduling algorithm. You will implement specific CPU scheduling
algorithms in Part II of this project.
All implemented algorithms (in Part II) will be simulated for the same set of processes, which
will therefore support a comparative analysis of results. In Part I, the focus is on generating useful
sets of processes via pseudo-random number generators.
Back to the conceptual model, when a process is in the READY state and reaches the front of the
queue, once the CPU is free to accept the next process, the given process enters the RUNNING
state and starts executing its CPU burst.
After each CPU burst is completed, if the process does not terminate, the process enters the
WAITING state, waiting for an I/O operation to complete (e.g., waiting for data to be read
in from a file). When the I/O operation completes, depending on the scheduling algorithm, the
process either (1) returns to the READY state and is added to the ready queue or (2) preempts
the currently running process and switches into the RUNNING state.
Note that preemptions occur only for certain algorithms.
3
Algorithms — (Part II)
The four algorithms that you must simulate are first-come-first-served (FCFS); shortest job first
(SJF); shortest remaining time (SRT); and round robin (RR). When you run your program, all
four algorithms are to be simulated in succession with the same set of processes.
Each algorithm is summarized below.
First-come-first-served (FCFS)
The FCFS algorithm is a non-preemptive algorithm in which processes simply line up in the ready
queue, waiting to use the CPU. This is your baseline algorithm.
Shortest job first (SJF)
In SJF, processes are stored in the ready queue in order of priority based on their anticipated CPU
burst times. More specifically, the process with the shortest predicted CPU burst time will be
selected as the next process executed by the CPU.
Shortest remaining time (SRT)
The SRT algorithm is a preemptive version of the SJF algorithm. In SRT, when a process arrives,
if it has a predicted CPU burst time that is less than the remaining predicted time of the currently
running process, a preemption occurs. When such a preemption occurs, the currently running
process is simply added to the ready queue.
Round robin (RR)
The RR algorithm is essentially the FCFS algorithm with time slice tslice. Each process is given
tslice amount of time to complete its CPU burst. If the time slice expires, the process is preempted
and added to the end of the ready queue.
If a process completes its CPU burst before a time slice expiration, the next process on the ready
queue is context-switched in to use the CPU.
For your simulation, if a preemption occurs and there are no other processes on the ready queue,
do not perform a context switch. For example, given process G is using the CPU and the ready
queue is empty, if process G is preempted by a time slice expiration, do not context-switch process G
back to the empty queue; instead, keep process G running with the CPU and do not count this as
a context switch. In other words, when the time slice expires, check the queue to determine if a
context switch should occur.