One piece of software that every modern operating system must contain in a scheduler: without one, only one task could be run at a time. You will be writing a library in lab 7 to perform basic scheduling of tasks. Rather than interacting directly with the operating system, we have provided for you a discrete event simulator: we will simulate time, jobs arriving, and jobs running. Your library will inform the scheduler which job should run next. Lab 7 will be on implementing a simulation of different scheduling algorithms of an operating system. We have implemented a priority queue data structure to keep track of the different jobs/processes in the simulation. We will use the priority queue data structure that is given to you for implementing different scheduling policies.

1. Slides
2. Lab Files
3. Example Simulations:
   • Example 1
   • Example 2
   • Example 3
4. Video Discussions:
   
   
   1. Part 1 (Introduction)
      
      
      
      
   2. Part 2 (libpriqueue)
      
      
      
      
   3. Part 3 (libscheduler)
      
      
      
      
   4. Part 4 (Simulation)
      
      
      
      

For this lab, you need to complete the implementation of the libscheduler.c program. You will have to implement the following functions inside libscheduler.c:

scheduler_start_up:	Initalizes the scheduler.
scheduler_new_job:	Called when a new job arrives.
scheduler_job_finished:	Called when a job has completed execution.
scheduler_quantum_expired:	When the scheme is set to RR, called when the quantum timer has expired on a core.
scheduler_average_waiting_time:	Returns the average waiting time of all jobs scheduled by your scheduler.
scheduler_average_turnaround_time:	Returns the average turnaround time of all jobs scheduled by your scheduler.
scheduler_average_response_time:	Returns the average response time of all jobs scheduled by your scheduler.
scheduler_clean_up:	Free any memory associated with your scheduler.
scheduler_show_queue:	This function may print out any debugging information you choose. This function will be called by the simulator after every call the simulator makes to your scheduler.

You will find several files:

• Programming files:
  • src/simulator.c: You should not edit this file. This file is the discrete event simulator that, when ran, will interact with your library. You can find more information on how to run this at the end of this web page. This file will be replaced by our autograder, so any changes you make will be ignored.
  • src/libpriqueue/libpriqueue.c and src/libpriqueue/libpriqueue.h: Files related to the priority queue. You will need to edit both of the files. You can feel free to add any helper functions, but you must implement all the functions where we provide outlines without changing their signatures.
  • src/queuetest.c: A small test case to test your priority queue, independent of the simulator. You may want to create more complex test cases in this file. The file is not used by the autograder.
  • src/libscheduler/libscheduler.c and src/libscheduler/libscheduler.h: Files related to the scheduler. You may need to edit both of the files. You can feel free to add any helper functions, but you must implement all the functions where we provide outlines without changing their signatures.
  • examples.pl: A perl script of diff runs that tests your program aganist the 54 test output files. This file will output differences between your program and the examples.
• Example input files:
  • examples/proc1.csv
  • examples/proc2.csv
  • examples/proc3.csv
• Example output files:
  • examples/proc1-c1-fcfs.out: Sample output of the simulator, using proc1.csv, 1 core, and FCFS scheduling.
  • examples/proc1-c2-fcfs.out: Sample output of the simulator, using proc1.csv, 2 cores, and FCFS scheduling.
  • examples/proc1-c1-sjf.out: Sample output of the simulator, using proc1.csv, 1 core, and SJF scheduling.
  • examples/proc1-c2-sjf.out: Sample output of the simulator, using proc1.csv, 2 cores, and SJF scheduling.
  • examples/proc1-c1-sjf.out: Sample output of the simulator, using proc1.csv, 1 core, and PSJF scheduling.
  • examples/proc1-c2-sjf.out: Sample output of the simulator, using proc1.csv, 2 cores, and PSJF scheduling.
  • ... (View the example directory for the full set.)
Example outputs:
• Example output 1
• Example output 2
• Example output 3

[Part 1]: Priority Queue (GIVEN)

A scheduler needs a fundamental data structure that is a priority queue. You will be using this a priority queue library in your scheduler.

libpriqueue API

Full function descriptions are provided for each function outlined in libpriqueue.c. In every function, you may assume that all pointers given will be valid, non-NULL pointers.

[Part 2]: Scheduler

You will need to implement a multi-core scheduler in a simulated computer. You will be provided with a set of cores to schedule a set of tasks on, much like a real Linux scheduler.

You should use your priority queue you just built to help you complete this part of this lab.

To complete this lab, you must implement the eight functions defined in src/libscheduler/libscheduler.c. These functions are self-descriptive, but a full function outline is provided for you for each function.

Scheduler Details

The simulator will always follow a few, very specific rules. It's not important to understand the specifics of the simulator, but we provide these to help you with debugging:

• All execution of tasks will happen at the very end of a time unit.
• The events in a time unit will occur in this order:
  1. If a job's last unit of execution occurred in the previous time unit, a scheduler_job_finished() call will be made as the first call in the new time unit.
  2. If a job has finished, the quantum timer for the core will be reset. (Therefore, scheduler_quantum_expired() will never be called on a specific core at the same unit that a job has finished.)
  3. In RR, if the quantum timer has expired, a scheduler_quantum_expired() will be called.
  4. If any job arrives at the time unit, the scheduler_new_job() function will be called.
  5. Finally, the CPU will execute the active jobs on each core.

• When multiple cores are available to take on a job, the core with the lowest id should take the job.
• A job cannot be ran on multiple cores in the same time unit. However, a job may start on one core, get preempted, and continue on a different core.
• In PSJF, if the job has been partially executed, schedule the job based on its remaining time (not the full running time).
• In RR, when a new job arrives, it must be placed at the end of the cycle of jobs. Every existing job must run some amount of time before the new job should run.
• In all schemes except RR, if two or more jobs are tied (eg: if in PRI multiple jobs have the priority of 1), use the job with the earliest arrival time. In new_job(), we provided the assumption that all jobs will have a unique arrival time. In RR, when a job is unscheduled as a result of the quantum timer expiring, it must always be placed at the end of the queue.
• Consider a schedule running PPRI on a single core. After some amount of time:
  • A job finished in the last time unit, resulting in a scheduler_job_finished() call to be made to your scheduler. The scheduler returns that job(id=4) should run.
  • In this time unit, a new job also arrived. This results in a scheduler_new_job() call to be made to your scheduler. If the new job has greater priority, it will preempt job(j=4), which was scheduled by scheduler_job_finished(). Now job(id=5) is scheduled to run.
  • Only after all jobs finished and any new job arrives will the CPU execute the task. In this example, job(id=4) was never run on the CPU when it was scheduled by scheduler_job_finished(). When calculating response time, you should not consider job as responded until it runs a CPU cycle.

Compile and Run

make clean
make

./queuetest

./simulator -c <cores> -s <scheme> <input file>

./simulator -c 2 -s fcfs examples/proc1.csv

• FCFS
• SJF
• PSFJ
• PRI
• PPRI
• RR#, where # indicates any numeric value

perl examples.pl

or

make test

• 50% for libscheduler running with 1 core
• 25% for libscheduler running with N core
• 10% for Lab Quiz
• 15% for Demo

Once you have implemented all the functions, you can use the given examples.pl script to test with the given proc.csv files in the examples directory. You should check if your priority queue is giving the right output. You should replace the XXXXXXXs in the Makefile with your KUID. Then, use the "submit" target for preparing submission. Submissions will be through Canvas.

This lab is adopted from Dr. Caccamo's systems programming course at UIUC.

< Back to the Lab Home Page