Operating Systems- Cpu Simulation - Threads -Scheduling

CIS*3110 Assignment 2: Example 1 Input File 2 3 7 1 2 1 0 3 1 10 20 2 10 20 3 10 2 5 2 1 50 10 2 50 2 2 1 0 1 1 100 2 50 2 1 100 20 2 100   Round Robin Scheduling with Quantum = 50 Ready Queue Time thread enters the Ready Q Thread ID (process, thread, burst) Time thread enters CPU 0 P1 T1 B1 0 0 P2 T1 B1 (50 units only) 17 5 P1 T2 B1 74 30 P1 T1 B2 127 50 P2 T2 B1 (50 units only) 144 67 P2 T1 B1 (remaining 50 units) 197 134 P1 T2 B2 254 157 P1 T1 B3 307 194 P2 T2 B1 (remaining 50 units) 324 394 P2 T2 B2 (50 units only) 394 444 P2 T2 B2 (remaining 50 units) 444 CPU Scheduling Time Thread ID Time in CPU Context Switch Time Thread Finished 0 P1 T1 B1 10 7 17 P2 T1 B1 50 7 74 P1 T2 B1 50 3 127 P1 T1 B2 10 7 144 P2 T2 B1 50 3 197 P2 T1 B1 50 7 X 254 P1 T2 B2 50 3 X 307 P1 T1 B3 10 7 X 324 P2 T2 B1 50 394 P2 T2 B2 50 444 P2 T2 B2 50 X Totals 430 44 Thread Information Thread ID Enters System Starts Executing Finishes Executing Turnaround Time Process 1 Thread 1 0 0 317 317 Process 1 Thread 2 5 74 304 299 Process 2 Thread 1 0 17 247 247 Process 2 Thread 2 50 144 494 444   Total  Time  Required  =  494  units   Average  Turnaround  Time  is  326.7  units   CPU  Utilization  is  87%   Thread  1  of  Process  1:        arrival  time:  0        service  time:  30  units,  I/O  time:  40  units,  turnaround  time:  317  units,  finish  time:  317  units     Deborah Stacey Deborah Stacey 405.5 units Thread  2  of  Process  1:        arrival  time:  5        service  time:  100  units,  I/O  time:  10  units,  turnaround  time:  299  units,  finish  time:  304  units   Thread  1  of  Process  2:        arrival  time:  0        service  time:  100  units,  I/O  time:  0  units,  turnaround  time:  247  units,  finish  time:  247  units   Thread  2  of  Process  2:        arrival  time:  50        service  time:  200  units,  I/O  time:  20  units,  turnaround  time:  444  units,  finish  time:  494  units     CIS*3110 Assignment 2: Example 1 Input File 2 3 7 1 2 1 0 3 1 10 20 2 10 20 3 10 2 5 2 1 50 10 2 50 2 2 1 0 1 1 100 2 50 2 1 100 20 2 100   FCFS Scheduling Ready Queue Time thread enters the Ready Q Thread ID (process, thread, burst) Time thread enters CPU 0 P1 T1 B1 0 0 P2 T1 B1 17 5 P1 T2 B1 124 30 P1 T1 B2 177 50 P2 T2 B1 194 184 P1 T2 B2 301 207 P1 T1 B3 354 314 P2 T2 B2 371 CPU Scheduling Time Thread ID Time in CPU Context Switch Time Thread Finished 0 P1 T1 B1 10 7 17 P2 T1 B1 100 7 X 124 P1 T2 B1 50 3 177 P1 T1 B2 10 7 194 P2 T2 B1 100 7 301 P1 T2 B2 50 3 X 354 P1 T1 B3 10 7 X 371 P2 T2 B2 100 X Totals 430 41 Thread Information Thread ID Enters System Starts Executing Finishes Executing Turnaround Time Process 1 Thread 1 0 0 364 364 Process 1 Thread 2 5 124 351 346 Process 2 Thread 1 0 17 117 117 Process 2 Thread 2 50 194 471 421   Total  Time  Required  =  471  units   Average  Turnaround  Time  is  312  units   CPU  Utilization  is  91.3%   Thread  1  of  Process  1:        arrival  time:  0        service  time:  30  units,  I/O  time:  40  units,  turnaround  time:  364  units,  finish  time:  364  units   Thread  2  of  Process  1:        arrival  time:  5        service  time:  100  units,  I/O  time:  10  units,  turnaround  time:  346  units,  finish  time:  351  units   Thread  1  of  Process  2:        arrival  time:  0        service  time:  100  units,  I/O  time:  0  units,  turnaround  time:  117  units,  finish  time:  117  units   Thread  2  of  Process  2:        arrival  time:  50        service  time:  200  units,  I/O  time:  20  units,  turnaround  time:  421  units,  finish  time:  471  units     Deborah Stacey Deborah Stacey 417.5 units CIS*3110 Operating Systems (Winter 2021) Assignment #2: CPU Simulation Requirements and Specifications Objective The goal of this assignment is to develop a CPU scheduling algorithm that will complete the execution of a group of multi-threaded processes in an OS that understands threads (kernel threads). Since a real implementation of your scheduling algorithm is not feasible, you will implement a simulation of your CPU scheduling algorithm. Each process will have 1-50 threads; each of the threads has its own CPU and I/O requirements. The simulated scheduling policy is on the thread level. While your simulation will have access to all the details of the processes that need to execute, your CPU scheduling algorithm CANNOT take advantage of future knowledge. Specification Given a set of processes to execute with CPU and I/O requirements, your CPU simulator will simulate the execution of the threads based on your developed CPU scheduling policies (FCFS and RR). Your simulation will collect the following statistics: • the total time required to execute all the threads in all the processes • the CPU utilization (NOT the CPU efficiency) • the average turnaround time for all the processes • the service time (or CPU time), I/O time and turnaround time for each individual thread Your simulation structure should be a next event simulation. The next event approach to simulation is the most common simulation model. At any given time, the simulation is in a single state. The simulation state can only change at event times, where an event is defined as an occurrence that may change the state of the system. Events in this CPU simulation are the following: • thread arrival • the transition of a thread state (e.g. when an interrupt occurs due to a time slice, the thread moves from running state to ready state) Each event occurs at a specified time. Since the simulation state only changes at an event, the clock can be advanced to the next most recently scheduled event (the meaning of next event simulation model). Events are scheduled via an event queue. The event queue is a sorted queue which contains "future" events; the queue is sorted by the time of these "future" events. The event queue is initialized to contain the arrival of all threads. The main loop of the simulation consists of processing the next event, perhaps adding more future events in the queue as a result, advancing the clock, and so on until all threads have terminated. Simulation Execution Your simulation program will be invoked as: $ ./simcpu [-d] [-v] [-r quantum] < input_file where • -d stands for detailed information • -v stands for verbose mode • –r indicates Round Robin scheduling with the given quantum (an integer) You can assume only these flags will be used with your program, and that they will appear in the order listed. The output for the default mode (i.e., no flags) or with flags is defined in the output format section. Note: the flags may be used separately or together. Input Format The simulator input includes: • number of processes that require execution • the thread switch overhead time (i.e., the number of time units required to switch to a new thread in the SAME process) • the process switch overhead time (i.e., the number of time units required to switch to a new thread in a DIFFERENT process) • for each process o the number of threads o the arrival time for each thread o the number of CPU execution bursts each thread requires (the CPU execution bursts are separated by the time it takes for the thread to do I/O) o the CPU time and the I/O time You should assume an infinite number of I/O devices. In other words, threads do not need to wait to do I/O. You should also assume that no overhead is associated with placing a thread on, or removing a thread from, an I/O device (e.g., no overhead is associated with an "interrupt" to indicate I/O completion). Since a thread must exit from the system while in the executing state, the last task of a thread is a CPU burst. All simulation parameters are integers. Your simulator obtains these parameters from the input file, which is in the following format. number_of_processes thread_switch process_switch process_number(1) number_of_threads(1) thread_number(1) arrival_time(1) number_of_CPU(1) 1 cpu_time io_time 2 cpu_time io_time ... number_of_CPU(1) cpu_time thread_number(2) arrival_time(2) number_of_CPU(2) 1 cpu_time io_time 2 cpu_time io_time … number_of_CPU(2) cpu_time ... ... thread_number(n) arrival_time(n) number_of_CPU(n) 1 cpu_time io_time 2 cpu_time io_time … number_of_CPU(n) cpu_time process_number(2) number_of_threads(2) thread_number(1) arrival_time(1) number_of_CPU(1) 1 cpu_time io_time 2 cpu_time io_time ... number_of_CPU(1) cpu_time thread_number(2) arrival_time(2) number_of_CPU(2) 1 cpu_time io_time 2 cpu_time io_time … number_of_CPU(2) cpu_time ... ... thread_number(n) arrival_time(n) number_of_CPU(n) 1 cpu_time io_time 2 cpu_time io_time … number_of_CPU(n) cpu_time The following is an example input file to the CPU simulation: 2 3 7 1 4 1 0 6 1 15 400 2 18 200 3 15 100 4 15 400 5 25 100 6 240 2 12 4 1 4 150 2 30 50 3 90 75 4 15 3 27 4 1 4 400 2 810 30 3 376 45 4 652 4 28 7 1 37 100 2 37 100 3 37 100 4 37 100 5 37 100 6 37 100 7 37 2 2 1 0 3 1 150 2 2 4 5 3 22 2 1 1 1 50 where • 2 3 7 : 2 is the number of processes, 3 is the number of time units required to switch to a new thread in the same process, 7 is the number of time units required to switch to a new thread in a different process • 1 4 : 1 is the process number and 4 is the number of threads • 1 0 6 : 1 is the thread number, 0 is the arrival time, 6 is the number of CPU execution bursts that each thread requires • 1 15 400, 2 18 200, 3 15 100, 4 15 400, 5 25 100, 6 240 : where 1 is the thread number and 15 is the CPU time and 400 is the I/O time and the last thread only has CPU time (burst) This example has 2 processes. Process 1 has 4 threads and Process 2 has 2 threads. Output Format In default mode (i.e., no flags are given), the simulator adopts a FCFS scheduling policy and the output of the simulator consists of • the total time required to execute the threads in all processes to completion • the average turnaround time of the processes • the CPU utilization As an example: $ ./simcpu < input_file FCFS Scheduling Total Time required is 344 time units Average Turnaround Time is 27.9 time units CPU Utilization is 94% In detailed information mode (i.e., -d flag is given), the output of the simulation consists of • the total time required to execute the threads in all the processes • the average turnaround time for all the processes • the CPU utilization • the arrival time, service time, I/O time, turnaround time and finish time for each thread For example, $ ./simcpu -d –r 10 < input_file Round Robin Scheduling (quantum = 10 time units) Total Time required is 140 units Average Turnaround Time is 9.2 time units CPU Utilization is 100% Thread 1 of Process 1: arrival time: 0 service time: 32 units, I/O time: 3 units, turnaround time: 45 units, finish time: 45 units Thread 2 of Process 1: arrival time: 5 service time: 102 units, I/O time: 15 units, turnaround time: 135 units, finish time: 140 units Thread 1 of Process 2: arrival time: 10 service time: 22 units, I/O time: 3 units, turnaround time: 45 units, finish time: 55 units In verbose mode, the output of the simulation includes the scheduling decisions and the switching of the threads. Specifically, the output includes every event that occurs, the time of the event, and the state transition: At time X: Thread {id} of Process {id} moves from {state} to {state} For example: At time 0: Thread 1 of Process 1 moves from new to ready At time 7: Thread 1 of Process 1 moves from ready to running … Each state transition should be given as above on a separate line (be sure to include events that occur at the same time). Since we do not include swapping in our simulation, the state of a thread can only be in one of five states: new, ready, running, blocked, or terminated. Summary information about each thread (as in detailed information mode) should be given after a thread has terminated.