MP4: Schedule Me!

CS 241

Introduction

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. In this MP, you will be writing a library 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.

You will find several files:

• Programming files:
  • 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 the autograder, so any changes you make will be ignored.
  • libpriqueue/libpriqueue.c and 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.
  • 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.
  • libscheduler/libscheduler.c and 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.
  • 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.)

[Part 1]: Priority Queue

To build a scheduler, a fundamental data structure is a priority queue. The first part of this MP requires you to complete libpriqueue, a priority queue library. You will be using this library in your scheduler.

libpriqueue API

To complete libpriqueue, you must implement the functions outlined in libpriqueue.c. These functions are self-descriptive, but a full function outline is provided for you below for each function. In every function, you may assume that all pointers given will be valid, non-NULL pointers.

• priqueue_init()

  void priqueue_init(priqueue_t *q, int(*comparer)(const void *, const void *))

  Initializes the priqueue_t data structure, q.

  Parameters
  • q, a pointer to an instance of the priqueue_t data structure.
  • comparer, a function that compares two elements. The function shall follow this prototype:

    int comparer(const void *elem1, const void *elem2);

    The function must accept two parameters that are pointers to elements, type-casted as void *. These parameters should be cast back to some data type and be compared.

    The return value of this function should represent whether elem1 is considered less than, equal to, or greater than elem2 by returning, respectively, a negative value, zero or a positive value.

    When prioritizing elements in the queue, the zero'th index element must be the minimal element contained in the tree (as defined by the comparer function).

  Assumptions
  • You may assume this function will only be called once per instance of priqueue_t.
  • You may assume this function will be the first function called using an instance of priqueue_t.


• priqueue_offer()

  int priqueue_offer(priqueue_t *q, void *ptr)

  Inserts the specified element into this priority queue.

  Parameters
  • q, a pointer to an instance of the priqueue_t data structure.
  • ptr, a pointer to the data to be inserted into the priority queue. This data must be comparable by the comparer function specified in priqueue_init().
  Returns
  • The zero-based index where ptr is stored in the priority queue, where 0 indicates that ptr was stored at the front of the priority queue.


• priqueue_peek()

  void *priqueue_peek(priqueue_t *q)

  Retrieves, but does not remove, the head of this queue, returning NULL if this queue is empty.

  Parameters
  • q, a pointer to an instance of the priqueue_t data structure.
  Returns
  • The head of the queue, or NULL if the queue is empty.


• priqueue_poll()

  void *priqueue_poll(priqueue_t *q)

  Retrieves and removes the head of this queue, or NULL if this queue is empty.

  Parameters
  • q, a pointer to an instance of the priqueue_t data structure.
  Returns
  • The head of this queue, or NULL if this queue is empty.


• priqueue_at()

  void *priqueue_at(priqueue_t *q, int index)

  Returns the element at the specified position in this list, or NULL if the queue does not contain an index'th element.

  Parameters
  • q, a pointer to an instance of the priqueue_t data structure.
  • index, the zero-based index into the queue. If index == 0, this operation returns the same result as priqueue_peek(). For index values greater than 0, this operation returns the index'th smallest element based on the comparer order.
  Returns
  • The index'th element in the queue, or NULL if the queue does not contain in index'th element.


• priqueue_remove()

  int priqueue_remove(priqueue_t *q, void *ptr)

  Removes all instances of ptr from the queue. This function should not use the comparer function, but check if the data contained in each element of the queue is equal (==) to ptr.

  Parameters
  • q, a pointer to an instance of the priqueue_t data structure.
  • ptr, a pointer which all instances of this pointer should be removed from the list.
  Returns
  • The number of entries removed.


• priqueue_remove_at()

  void *priqueue_remove_at(priqueue_t *q, int index)

  Removes the specified index from the queue, moving later elements up a spot in the queue to fill the gap.

  Parameters
  • q, a pointer to an instance of the priqueue_t data structure.
  • index, the specified zero-based index to remove.
  Returns
  • The element removed from the queue, or NULL if the specified index does not exist.


• priqueue_size()

  int priqueue_size(priqueue_t *q)

  Returns the number of elements in the queue.

  Parameters
  • q, a pointer to an instance of the priqueue_t data structure.
  Returns
  • The number of elements in the queue.


• priqueue_destroy()

  void priqueue_destroy(priqueue_t *q)

  Destroys and frees all the memory associated with q.

  Parameters
  • q, a pointer to an instance of the priqueue_t data structure.
  Assmptions
  • You may assume this function will only be called once per instance of priqueue_t.
  • You may assume this function will be the last function called using an instance of priqueue_t.

[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 the MP.

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

• scheduler_start_up()

  void scheduler_start_up(int cores, scheme_t scheme)

  Initalizes the scheulder.

  Parameters:
  • cores, the number of cores that is available by the scheduler. These cores will be known as core(id=0), core(id=1), ..., core(id=cores-1).
  • scheme, the scheduling scheme that should be used. This value will be one of the six enum values provided in the libscheduler.h file:
    • FCFS for First Come First Served
    • SJF for Shortest Job First (non-preemptive)
    • PSJF for Preemptive Shortest Job First
    • PRI for Priority-based Scheduling (non-preemptive)
    • PPRI for Preemptive Priority-based Scheduling
    • RR for Round Robin
  Assumptions:
  • You may assume this will be the first scheduler function called.
  • You may assume this function will be called only once.
  • You may assume that cores is a positive, non-zero number.
  • You may assume that scheme is a valid scheduling scheme.


• scheduler_new_job():

  int scheduler_new_job(int job_number, int time, int running_time, int priority)

  Called when a new job arrives.

  Parameters:
  • job_number: A globally unique identification number of the job arriving.
  • time: The current time of the simulator.
  • running_time: The total number of time units this job will run before it will be finished.
  • priority: The priority of the job. (The lower the value, the higher the priority.)
  Returns:
  • If the job arriving should be scheduled to run during the next time cycle, return the zero-based index of the core the job should be scheduled on. If another job is already running on the core specified, this will preempt the currently running job.
    If multiple cores are idle, the job should be assigned to the core with the lowest id.
  • Otherwise, return -1.
  Assumptions:
  • You may assume that every job will have a unique arrival time.


• scheduler_job_finished():

  int scheduler_job_finished(int core_id, int job_number, int time)

  Called when a job has completed execution.

  Parameters:
  • core_id: The zero-based index of the core where the job was located.
  • job_number: A globally unique identification number of the job arriving.
  • time: The current time of the simulator.
  Returns
  • If any job should be scheduled to run on the core free'd up by the finished job, return the job_number of the job that should be scheduled to run on core core_id.
  • Otherwise, if the core should remain idle, return -1.
  Notes:
  • The core_id, job_number and time parameters are provided for convenience. You may be able to calculate the values with your own data structure.
  
  
• scheduler_quantum_expired():

  int scheduler_quantum_expired(int core_id, int time)

  When the scheme is set to RR, called when the quantum timer has expired on a core.

  Parameters:
  • core_id: The zero-based index of the core where the quantum has expired.
  • time: The current time of the simulator.
  Returns
  • If any job should be scheduled to run on the core free'd up by the quantum expiration, return the job_number of the job that should be scheduled to run on core core_id.
  • Otherwise, if the core should remain idle, return -1.
  
  
• scheduler_average_waiting_time():

  float scheduler_average_waiting_time()

  Returns the average waiting time of all jobs scheduled by your scheduler.

  Assumptions:
  • This function will only be called after all scheduling is complete (all jobs that have arrived will have finished and no new jobs will arrive).
  
  
• scheduler_average_turnaround_time():

  float scheduler_average_turnaround_time()

  Returns the average turnaround time of all jobs scheduled by your scheduler.

  Assumptions:
  • This function will only be called after all scheduling is complete (all jobs that have arrived will have finished and no new jobs will arrive).
  
  
• scheduler_average_response_time():

  float scheduler_average_response_time()

  Return the average response time of all jobs scheduled by your scheduler.

  Assumptions:
  • This function will only be called after all scheduling is complete (all jobs that have arrived will have finished and no new jobs will arrive).
  
  
• scheduler_clean_up():

  void scheduler_clean_up()

  Free any memory associated with your scheduler.

  Assumptions:
  • This function will be the last function called in your library.
  
  

• scheduler_show_queue():

  void 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.

  In our provided output, we have implemented this function to list the jobs in the order they are to be scheduled. Furthermore, we have also listed the current state of the job (either running on a given core or idle). For example, if we have a non-preemptive algorithm and job(id=4) has began running, job(id=2) arrives with a higher priority, and job(id=1) arrives with a lower priority, the output in our sample output will be:

  2(-1) 4(0) 1(-1)

  This function is not required and will not be graded. You may leave it blank if you do not find it useful.

  
  

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.

Examples

Consider the following simple schedule:

Using the schedule above, step-by-step examples are shown for three different possible running conditions:

• FCFS, 1 core
• FCFS, 2 cores
• RR1, 1 core

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

Lab Report

• What data structure did you use to implement your priority queue?
• Did you find the priority queue useful in your scheduler? How did you use it?
• How did you handle the multiple cores?

Grading, Submission, and Other Details

• 30% for libpriqueue
• 40% for libscheduler running with 1 core
• 30% for libscheduler running with N core