data structure 3

CSC 240

Lab 8

Operating System Job Scheduler

Priority queues are used by operating systems for scheduling jobs on a CPU. For this example, each

iteration of the scheduler will correspond to one cycle of the CPU. Assume each cycle requires one

nanosecond. A job will be assigned a name (i.e. “P1”), a priority, and a length. The value of priority will

be an integer from -19 to 20 such that 20 is the highest priority and -19 is the lowest priority. The value

of length will be an integer from 1 to 100, indicating the number of cycles that are needed to complete

the job. A job cannot be interrupted—once a job is scheduled on the CPU, it runs for a number of cycles

equal to its length. During each cycle, the CPU will process its current job, add new jobs to the queue, sit

and wait until another job is scheduled, or terminate execution (shutdown).

Write a program that simulates this job scheduler.

If there are currently no jobs for the CPU, then the simulator will continue to run until it completes all of

the jobs. If all jobs have been processed, then the simulator will stop running.

The simulator will process 50 jobs, generated with a random priority and length.

Assume it takes approximately 1 to 100 nanoseconds (cycles) for a job to complete.

Assume the interarrival time is 20 nanoseconds (cycles). We can simulate this by generating a random

number of 0 or 1 every 20 nanoseconds (cycles). A 0 would not allow a new job, and a 1 would allow a

new job to be scheduled—essentially flipping a coin.

Run the simulator over a span of 2,700 cycles. Identify the number of jobs that are completed by the

CPU at the end of each test.

Test this simulation 1,000 times over several attempts (no more than 5) to find a benchmark threshold

that will allow for all of the 50 jobs to complete in the shortest amount of time. Keep in mind that you

may or may not need all 2,700 cycles.

Find the average number of jobs in the heap per cycle.

Output the following information after each simulation of 2,700 cycles:

Average number of jobs in the heap per cycle: 4 The scheduler completed all 50 jobs. It took 2700 cycles to complete them.

OR

Average number of jobs in the heap per cycle: 3 The scheduler did not complete all 50 jobs. Jobs processed: 49

Also output the count of complete and incomplete simulations after each test (1,000 simulations/test):

Completed simulations: 939 Incomplete simulations: 61

Write a final report on your findings of at least 250 words.

Tips: Create a Job class, a Scheduler class, and a separate driver to manage the simulation. Use the

provided Lab8_PriorityQueue zipped file found under Extra Files in Content.

class Job{ public: Job(); Job(int, int); int getLength() const; void decrementLength(); int getPriority() const; friend ostream& operator<<(ostream& out, const Job& j); bool operator<(Job otherJob); bool operator>(Job otherJob); bool operator==(Job otherJob); bool operator<=(Job otherJob); private: int length; int priority; };

template <class ItemType> class Scheduler: public PQType<ItemType>{ public: Scheduler(int); int getNumJobs() const; void getCurrentJob(ItemType&); void setCurrentJob(ItemType&); void addJob(ItemType&); void removeJob(ItemType& j); private: int numJobs; ItemType currentJob; };

Resources for Scheduling:

https://courses.engr.illinois.edu/cs438/sp2010/slides/lec15_perf.pdf

https://www.cs.uic.edu/~jbell/CourseNotes/OperatingSystems/6_CPU_Scheduling.html