Reference no: EM133751791

Operating Systems

Introduction
Assignment 1 will focus on your understanding and ability to successfully implement, execute and compare the results of a number of scheduling algorithms.

Assignment Task
Write a program that simulates First Come First Serve (FCFS), Shortest Remaining Time (SRT), Multi- level Feedback (Variable) (FBV) and Lottery (LTR) scheduling algorithms. For each algorithm the program should list the order and time of the processes being loaded in the CPU, compute the turnaround time and waiting time for every process, as well as the average turnaround time and average waiting time. The average values will be consolidated in a table for easy comparison (check the sample outputs).

Two sample input data sets and the corresponding outputs have been supplied. Beyond the two sample datasets provided, additional datasets will be used to test your program. The format of the input data will be the same as in the supplied sample files.

Input Data
Each input data set contains the following information (check the sample input files for exact format):
Time for running the dispatcher (KISfl:) which can be zero or a positive integer
For each process:
process id (flIK:) - as a string in the form pn where n is a positive integer 1, 2, 3, ... (in order).
arrival time (6uuHiuv:) - as a non-negative integer representing unit of time
service time (SuvHiuv:) - as a positive integer representing unit of time
number of tickets (Hicevts) - as an positive integer representing the number of tickets the process holds.
A sequence of random numbers to be used (in the given order) only in the lottery (LTR) scheduling algorithm. There should be enough random numbers for the LTR algorithm.

It can be assumed that process Pn will always arrive before or at the same time of process Pn+1; times can be considered to just be whole number ‘time units'.

Dispatcher
It is assumed that the dispatcher is executed to select the next process to run. The dispatcher should behave as follows:
The time to run the dispatcher (context switching time) is fixed and taken as input (KISfl:) from the input file. No other time is wasted in switching between processes other than this.

If the dispatcher starts at t1 and finishes at t2 (i.e. time to run the dispatcher is t2-t1) then in that run it will choose from the processes that have arrived at or before t1. It will not consider any process that arrives after t1 for dispatching in that run.
If a process p1 is interrupted at t1 and another process p2 arrives at the same time t1 then the newly arrived process p2 is added in the ready queue first and the interrupted process p1 is added after that.
If two processes px and py have all other properties same (e.g. arrival time, etc.) then the tie between them is broken using their ID; i.e. px will be chosen before py if x<y.
Scheduling Algorithm Details
Some details about the scheduling algorithms are as follows:
FCFS: Standard FCFS scheduling algorithm. Process tickets is ignored in scheduling.
SRT: Standard SRT scheduling algorithm. Process tickets is ignored in scheduling.
FBV: Standard multi-level (3 levels) feedback algorithm with variable time quanta for different queues. The time quanta in different queues (from highest priority to lowest priority) to be 2, 4, and 4 ms, respectively.
The bottom queue (i.e. the lowest priority queue) is to be treated in round robin fashion. If a process stays (waiting or running) in the lowest priority queue for more than 16 ms then it should be transferred to the highest priority queue again and the whole process repeats for that process.
LTR: Lottery scheduling is a proportional-share scheduling algorithm. Each process has some tickets and the percentage of tickets a process has represents the share of the processor time the process should receive. Now the scheduler holds a lottery to determine which process should get to run next. The process has higher percentage of tickets has a higher chance to win the lottery and should run more often. When a process wins the lottery, it is dispatched for a fixed time quantum of 3 ms.
A piece of code snippet (in C++) is given below to show how to run a lottery to choose the winner. You must use the random numbers (in order) in the input file instead of the .getrandom() function below to select the winner. If a process could not finish its execution within the allotted time quantum, then it will re-enter the queue at the end.
// counter: used to track if we've found the winner yet
int counter = 0;
3
// winner: use some call to a random number generator to
// get a value, between 0 and the total # of tickets
int winner = getrandom(0, totaltickets); 7
// current: use this to walk through the list of jobs
node_t *current = head;
while (current) {
counter = counter + current->tickets;
if (counter > winner){
break; // found the winner
14 }
15 current = current->next;
16 }
17 // 'current' is the winner: schedule it...

Task
In addition to the above simulations, you need to write a report on the CPU scheduling algorithm in modern operating systems.

Objective: The objective of this assignment is to conduct a detailed research and analysis of the CPU scheduling algorithms used in various top operating systems, including Windows, Linux, macOS, Android, and iOS. The emphasis will be on understanding the design choices, strengths, weaknesses, and real-world performance of these algorithms. For each OS, students should investigate the specific scheduling algorithm(s) used, its key features, handling of various types of tasks (e.g. real-time VS non-real-time), load balancing and scalability in multi-core systems, mechanism for fairness and efficiency etc. Students will develop a comprehensive report demonstrating their findings.
Description: In this assignment, you will investigate and analyse the CPU scheduling algorithms implemented in three major operating systems, specifically Windows, Linux and macOS. Your report should provide a comparative analysis, discussing the unique approaches each operating system takes to CPU scheduling, and highlight the implications of these choices on system performance, responsiveness, and user experience.

Report Structure and Length: You report should contain the following sections (i) Introduction (ii) CPU Scheduling in major OS for PCs (iii) Comparative Analysis (iv) Conclusion and (v) References. The length of the report, covering all the sections mentioned before should be 6~10 pages (A4). The report should be written in a formal academic style, with proper citations and references.