Due date:   11:59pm, Sun day , June  11 , 2023 , submitted via g it

Objectives

This assignment has several objectives: (i) to reinforce your understanding of process management; (ii) to reinforce your understanding of scheduling; and (iii) to provide additional practice in C programming and understanding specifications.

Preparation :

1.    Complete Assignment 0 or ensure that the tools you would need to complete it are installed.

2.    Review the Assignment 1 specification.  Assignment 2 builds on Assignment 1

3.    Complete Assignment 1 and/or review the provided solution to Assignment 1

4.    Clone your assignment repository:

https://git.cs.dal.ca/courses/2023-summer/csci-3120/assignment-2/????.git

where ???? is your CSID.

5.    Copy either your own solution or the provided solution for Assignment 1 as a starting point for As- signment 2 as Assignment 2 builds on Assignment 1.  A solution will be accessible on May 24 from Brightspace.

The repository has the same structure and caveats as Assignment 1.

Background

Operating systems typically run multiple programs at the same time. An OS simulation should include the execution of multiple programs. To this end, we will extend our simple simulator to run multiple program execution descriptions (“processes”) with a variety of different scheduling algorithms.  The simulator will model a system with a single processor and track the state of the processes as well as compute the total waiting time for each process.  The simulation can be parameterized by the quantum size (the maximum number of ticks a running process is allotted), as well as which scheduling algorithm to use: (i) round robin; (ii) shortest job first; (iii) or multilevel queues (priority with pre-emption). The simulator will take as input a Process Description, which includes the above parameters and the Program Execution Description for one or more programs (from Assignment 1).

Problem Statement

Write a program execution simulator that reads in a process description and simulates a system running the specified processes. Your program must be compiled to an executable called prosim.  Your program will read in a process description and output the states of the processes as the simulation runs. After the simulation, output the amount of time each process spent running, blocked, and waiting.

Input

Your program will read its input from stdin.  The input will consist of a process description, which is de- scribed as follows :  The first line consists of two integers, specifying the number of processes, NumProcs, to simulate and the quantum length, Quantum, in clock ticks of the simulated system.  I.e.,

This is followed by NumProcs program execution descriptions, where the format is identical to that of Assignment 1, except that the first line of each program description has an additional integer denoting the priority of the corresponding process in the simulation.  I.e., the first line of the program execution descriptions is of the form :

where Name is the name of the corresponding process, Size is the number of primitives in this program execution description, and Priority specifies the priority of the process.   If Priority is nonnegative, then this is treated as the priority of the process, where a lower value indicates a higher priority.  If all priorities are the same, this results in round robin scheduling. If priorities are different, this results in priority-based scheduling.  If Priority is -1, then the process is scheduled according to the time remaining in the current DOOP primitive, which is a simplified form of Shortest Job First scheduling.

Processing

Priority Queues

Your simulator will need two priority queues to implement the simulation.

•    A ready queue to manage the ready processes

•    A blocked queue to manage the blocked processes

Both queues can be instances of the same basic priority queue implementation.   It is strongly recom- mended that the queues order the processes in increasing order of priority values. I.e., a process with priority 2 would be ahead of a process with priority 5.   If two processes have the same priority, then the process that was enqueued first should be ahead of the process that was enqueued second.  Priorities can be represented as nonnegative integers.  It is recommended to use a basic linked list implementation.

The Simulation

A simulation will consist of three phases:

Load and Admission

1.    Read in the program descriptions, where each program description describes the execution of a process in the simulation.

2.    Assign Process IDs to the processes.  The first program description is assigned Process ID 1, the second to Process ID 2, etc.

3.    Initialize the state of each process to New.

4.    Add each process to the scheduler :

a.     Locate the first DOOP, BLOCK, or HALT to be executed in each process.

b.    If the primitive is a DOOP, the process state changes to Ready and the process is added to the ready queue.

c.     If the primitive is a BLOCK, the process state changes to Blocked and the process is added to the blocked queue.

d.    If the primitive is a HALT, the process state changes to Finished.

The Main Simulation Loop

Each iteration of the main simulation loop corresponds to one clock tick of the system clock.  The clock is just an integer variable that is incremented at the end of each iteration.  The loop should run until all processes are in the Finished state. Each iteration of the loop should do the following:

1. Remove processes from the blocked queue that are ready to be unblocked. For each removed process

a.     Determine the next operation of the process:

i.    If DOOP, the process is inserted into the ready queue and its state becomes Ready.

ii.    If BLOCK, the process in inserted into the blocked queue and its state becomes Blocked.

iii.    If HALT, the process’ state becomes Finished.

b.    Determine if the current running process needs to be pre-empted by a higher priority process that became ready.

2. Update Running process, if a process is currently in a Running state,

a.     Decrement the amount of time it has remaining in its DOOP operation.

b.    Decrement the amount of time remaining in its quantum.

c.    If either the amount of time in its DOOP operation or its quantum is 0, or the current process is to be pre-empted by a higher priority process, determine the next operation of the process, DOOP, BLOCK, or HALT, and insert them into the appropriate queue

i.    If DOOP, the process is inserted into the ready queue and its state becomes Ready.

ii.    If BLOCK, the process in inserted into the blocked queue and its state becomes Blocked.

iii.    If HALT, the process’ state becomes Finished.

3. Select next process to run, if no process is currently running.

a.    Select the next process from the ready queue.

b.    Reset the amount of time the process has to the CPU quantum.

c.    Set the process state to Running.

Note: whenever a process’ state is set, the current time, process, and state need to be outputted.  Please see the Output Section of the assignment.

Print out Summary

Once the main loop completes, print out the process summary for each process in the system in Process ID order. The simulator will need to keep track of the amount of time that each process spends (i) running (ii) blocked; and (iii) waiting in the ready queue.  Please see Output Section of the assignment.

Scheduling Algorithms and Priority Queues

The simulator simulates three different types of scheduling algorithms: (i) Round Robin; (ii) Priority-based with pre-emption; and (iii) Shortest Job First.

Round Robin Scheduling and Priority-based Scheduling

If the priority of a process nonnegative, then that is the priority to be used when inserting the process into the ready queue.  The understanding is that a lower priority value indicates a higher priority.  If all processes have the same priority then this becomes round-robin scheduling as processes will be ordered in the ready queue in the same order as they arrive.  If the priorities are different, then processes with lower priority values should be ahead of processes with higher priority values. Note: If a process with a higher priority than the current running process becomes ready, then it pre-empts the running process.

Shortest Job First Scheduling

If a process has a negative value as its priority, then shortest job first scheduling should be used.   That is, the process’s priority is simply the amount of time (clock ticks) remaining in its current DOOP operation. So, a process that has 2 clock ticks left in a DOOP will be scheduled a head of a process that has 5 clock ticks left in its DOOP.  I.e., The only thing that changes from priority-based scheduling is that the priority is the remaining time in the current DOOP.

The Blocked Queue

Here is a helpful hint:   The blocked queue is also a priority queue. When inserting processes into the blocked queue, use the (current time + length of BLOCK) as the priority.  This will order processes accord- ing to their wake-up time and allow you to easily identify which processes need to be removed from the blocked queue at each clock tick.

Output

All output should be performed to stdout.  The output must be exactly as specified.  When a process’s state is modified, output:

where Time is the current time in clock ticks, zero padded to 5 digits, PID is the process id, and State is one of new, ready, running, blocked, or finished.  Each output should be on a separate line and terminated by new line. (See example.)

When the simulation completes, the simulator should output a summary line for each process of the form:

where

• run_time is the sum ticks of all DOOPs performed by the process.

• block_time is the sum ticks of all BLOCKs performed by the process.

• wait_time is the sum ticks that the process spent in the ready queue.

Summaries should be outputted in order of PIDs and should be terminated by new lines.  (See examples.)

Example 1: Single Process

Example 2 : Two Processes, Priority-based Scheduling

Example 3: Two Processes, Shortest Job First

Assignment Submission

Submission and testing are done using Git, Gitlab, and Gitlab CI/CD. You can submit as many times as you wish, up to the deadline.  Every time a submission occurs, functional tests are executed, and you can view the results of the tests.   To submit use the same procedure as Assignment 1.

Hints and Suggestions

•    Use the provided solution or your own solution as a starting point.

•    Use a simple linked list implementation for a priority queue.  Be sure to test it well.

•    Start on this assignment early.   The sample solution is approximately 150 lines of additional code and

100 lines for a priority queue implementation.

•    The sample solution puts the main simulation loop in separate file for ease of understanding.

Grading

The assignment will be graded based on three criteria:

Functionality : “Does it work according to specifications?” . This is determined in an automated fashion by running your program on a number of inputs and ensuring that the outputs match the expected outputs. The score  is determined  based on the  number of tests that your  program passes. So, if your program passes t/T tests, you will receive that proportion of the marks.

Quality of Solution: “Is it a good solution?” This considers whether the approach and algorithm in your solution is correct. This is determined by visual inspection of the code. It is possible to get a good grade on this part even if you have bugs that cause your code to fail some of the tests.

Code Clarity : “Is it well written?” This considers whether the solution is properly formatted, well documented, and follows coding style guidelines. A single overall mark will be assigned for clarity. Please see the Style Guide in the Assignment section of the course in Brightspace.

If your program does not compile, it is considered non-functional and of extremely poor quality, mean- ing you will receive 0 for the solution.