GA.2250讲解、讲解C++设计程序

日期：2024-02-20 07:38

Programming Assignment #2 (Lab 2): Scheduler / Dispatcher Professor Hubertus Franke
Class CSCI-GA.2250-001 Spring 2024
In this lab we explore the implementation and effects of different scheduling policies discussed in class on a set of
processes/threads executing on a system. The system is to be implemented using Discrete Event Simulation (DES)
(http://en.wikipedia.org/wiki/Discrete_event_simulation). In discrete-event simulation, the operation of a system is represented as a
chronological sequence of events. Each event occurs at an instant in time and marks a change of state in the system. This implies
that the system progresses in time through defining and executing the events (state transitions) and by progressing time discretely
between the events as opposed to incrementing time continuously (e.g. don’t do “sim_time++”). Events are removed from the
event queue in chronological order, processed and might create new events at the current or future time. Note that DES has nothing
to do with OS, it is just an awesome generic way to step through time and simulating system behavior that you can utilize in many
system simulation scenarios.
You are not implementing this as a multi-program or multi-threaded application. By using DES, a process is simply the PCB
object that goes through discrete state transitions. In the PCB object you maintain the state and statistics of the process as any OS
would do. In reality, the OS doesn’t get involved during the execution of the program (other than system calls), only at the
scheduling events and that is what we are addressing in this lab.
Any process essentially involves processing some data and then storing / displaying it (on Hard drive, display etc). (A process
which doesn’t store/display processed information is practically meaningless). For instance: when creating a zip file, a chunk of
data is first read, then compressed, and finally written to disk, this is repeated until all of the file is compressed. Hence, an
execution timeline of any process will contain alternating discrete periods of time which are either dedicated for processing
(computations involving CPU aka cpuburst) or for doing IO (aka ioburst). For this lab assume that our system has only 1 CPU core
without hyperthreading - meaning that only 1 process can run at any given time; all processes are single threaded - i,e, they are
either in compute/processing mode or IO mode. These discrete periods will therefore be non-overlapping. There could be more
than 1 process running (concurrently) on the system at a given time though, and a process could be waiting for the CPU, therefore
the execution timeline for any given process can/will contain 3 types of non-overlapping discrete time periods representing (i)
Processing / Computation, (ii) Performing IO and (iii) ready to execute but waiting to get scheduled on the CPU.
The simulation works as follows:
Various processes will arrive / spawn during the simulation. Each process has the following 4 parameters:
1) Arrival Time (AT) - The time at which a process arrives / is spawned / created.
2) Total CPU Time (TC) - Total duration of CPU time this process requires
3) CPU Burst (CB) – A parameter to define the upper limit of compute demand (further described below)
4) IO Burst (IO) - A parameter to define the upper limit of I/O time (further described below)
The processes during its lifecycle will follow the following state diagram :
Initially when a process arrives at the system it is put into CREATED state. The processes’ CPU and the IO bursts are statistically
defined. When a process is scheduled (becomes RUNNING (transition 2)) the cpu_burst is defined as a random number between
[ 1 .. CB ]. If the remaining execution time is smaller than the cpu_burst compute, reduce it to the remaining execution time. When
a process finishes its current cpu_burst (assuming it has not yet reached its total CPU time TC), it enters into a period of IO (aka
BLOCKED) (transition 3) at which point the io_burst is defined as a random number between [ 1 .. IO ]. If the previous CPU burst
was not yet exhausted due to preemption (transition 5), then no new cpu_burst shall be computed yet in transition 2 and you
continue with the remaining cpu burst.
The scheduling algorithms to be simulated are:
FCFS, LCFS, SRTF, RR (RoundRobin), PRIO (PriorityScheduler) and PREemptive PRIO (PREPRIO). In RR, PRIO and
PREPRIO your program should accept the time quantum and for PRIO/PREPRIO optionally the number of priority levels maxprio
as an input (see below “Execution and Invocation Format”). We will test with multiple time quantums and maxprios, so do not
make any assumption that it is a fixed number. The context switching overhead is “0”.
You have to implement the scheduler as “objects” without replicating the event simulation infrastructure (event mgmt or
simulation loop) for each case, i.e. you define one interface to the scheduler (e.g. add_process(), get_next_process()) and
Programming Assignment #2 (Lab 2): Scheduler / Dispatcher Professor Hubertus Franke
Class CSCI-GA.2250-001 Spring 2024
implement the schedulers using object oriented programming (inheritance). The proper “scheduler object” is selected at program
starttime based on the “-s” parameter. The rest of the simulation must stay the same (e.g. event handling mechanism and
Simulation()). The code must be properly documented. When reading the process specification at program start, always assign a
static_priority to the process using myrandom(maxprio) (see above) which will select a priority between 1..maxprio. A process’s
dynamic priority is defined between [ 0 .. (static_priority-1) ]. With every preemption (quantum expiration or PREPRIO) the
dynamic priority decreases by one. When “-1” is reached the prio is reset to (static_priority-1). Please do this for all schedulers
though it only has implications for the PRIO/PREPRIO schedulers as all other schedulers do not take priority into account.
However uniformly coding and calculating this will enable a simpler and scheduler independent state transition implementation.
A few things you need to pay attention to when you implement the scheduler
All: When a process returns from I/O its dynamic priority is reset to (static_priority-1).
Round Robin: you should only regenerate a new CPU burst, when the current one has expired. Note you should decrement the
priority in the preemptions (shared with PRIO/PREPRIO), but immediately reset it to static-1 to match the verbose output.
SRTF: schedule is based on the shortest remaining execution time, not shortest CPU burst and is non-preemptive
PRIO/PREPRIO: same as Round Robin plus: the scheduler has exactly maxprio priority levels [0..maxprio-1], maxprio-1 being the
highest. Please use the concept of an active and an expired runqueue and utilize independent process queues at each prio level as
discussed in class. When “-1” is reached the process’s dynamic priority is reset to (static_priority-1) and it is enqueued into the
expired queue. When the active queue is empty, active and expired are switched.
Preemptive Prio (E) refers to a variant of PRIO where processes that become active will preempt a process of lower priority.
Remember, runqueue under PRIO is the combination of active and expired.
Input Specification
The input file provides a separate process specification in each line: AT TC CB IO. You can make the assumption that the input
file is well formed and that the ATs are not decreasing. So no fancy parsing is required. It is possible that multiple processes have
the same arrival times. Then the order at which they are presented to the system is based on the order they appear in the file.
Simply, for each input line (process spec) create a process object, create a process-create event and enter this event into the event
queue. Then and only then start the event simulation. Naturally, when the event queue is empty the simulation is completed.
We make a few simplifications:
(a) all time is based on integers not floats, hence nothing will happen or has to be simulated between integer numbers;
(b) to enforce a uniform repeatable behavior, a file with random numbers is provided (see NYU brightspace attachment) that
your program must read in and use (note the first line defines the count of random numbers in the file) a random number is
then created by using (don’t make assumptions about the number of random numbers):
“int myrandom(int burst) { return 1 + (randvals[ofs] % burst); }” // yes you can copy the code
You should increase ofs with each invocation and wrap around when you run out of numbers in the file/array. It is therefore
important that you call the random function only when you have to, namely for transitions 2 and 3 (with noted exceptions)
and the initial assignment of the static priority.
(c) IOs are independent from each other, i.e. they can commensurate concurrently without affecting each other’s IO burst time.
Execution and Invocation Format:
Your program should follow the following invocation: