Operating System代写:CS354 Process Scheduling

代写操作系统作业,实现作业调度算法。

Objectives

The objective of this lab is to give you an idea about how process scheduling works. You will implement earliest deadline first scheduler.

What to do?

Setup Xinu

The tarball you have to use is lab1-Xinu-code-BeagleBoneBlack.tar.gz. Make sure you copy /homes/cs354/www/lab1-Xinu-code-BeagleBoneBlack.tar.gz and not the old one as some additional code snippets are provided in the new tar which will be used for grading. Follow the updated XINU Setup tutorial.

Implement Scheduler

You will implement a new scheduling policy for XINU. You will be implementing dynamic scheduling algorithm used in real-time operating systems. The aim is to make the system more predictable in terms of when a particular process will be executed. In the standard priority based round robin scheduler used in XINU, there are no guarantees. If an old lower priority process exists, it might starve if there are higher priority processes that are added and do not give the old process time to execute. This is not acceptable in situations where you have a deadline by which a job should be executed. Let’s call such jobs as bounded jobs.

There are three components that characterize a bounded job :

  1. The arrival time
  2. The execution time (Time the process has to execute for)
  3. The deadline (Time by which this process should finish its execution)

Until there are any bounded jobs in the system in ready mode, the OS should not fallback to the original priority based scheduler. Only if there are no bounded jobs left, that it should fallback to normal priority based scheduler.

Earliest Deadline First Scheduler

The aim is to find a schedule that completes all jobs before their deadline. We will be implementing Earliest Deadline First (EDF) to attain this. The OS should select the process with closest deadline to execute first. If two jobs have the same deadline, chose the one which has the longest execution time. Before making a plan, all the jobs should be created. After that it should come up with a plan for executing these jobs. To prevent replanning again and again, you will not accept any new bounded jobs for the duration while your bounded jobs are executing.

The strategy in a nutshell is as follows :

  1. Select the job with the earliest deadline.
  2. If two jobs have the same deadline, select the one with the longest execution time.
  3. If two jobs have same deadline and same execution time, select the job that was created first.

The following examples will help clear this out. Assume there are following bounded jobs :

job1, execution_time : 10, deadline : 100
job2, execution_time : 20, deadline : 80
job3, execution_time : 50, deadline : 90
job4, execution_time : 70, deadline : 160
job5, execution_time : 30, deadline : 190

Let’s assume that the arrival time for all jobs is the same as t = 0.
The plan should be :

job2 ( 0 - 20 ), job3 ( 20 - 70 ), job1 ( 70 - 80 ), job4 ( 80 - 150 ), job5 ( 150 - 180 )

Note that a job’s schedule time should not matter on whether the job can be completed or not. For example, look at the following jobs :

job1, execution_time : 20, deadline : 100
job2, execution_time : 20, deadline : 80
job3, execution_time : 50, deadline : 90
job4, execution_time : 10, deadline : 100
job5, execution_time : 30, deadline : 120

In such a case, the job should run for whatever time it can before the deadline and then should be killed.

In this case, the plan should be :

job2 ( 0 - 20 ), job3 ( 20 - 70 ), job1 ( 70 - 90 ), job4 ( 90 - 100 ), job5 ( 100 - 120 )

Note here that there was a clash between job1 and job4, we select the one with with longest execution time. Hence job1 is selected first.

Now let’s consider a case where both deadline and execution time clash.

job1, execution_time : 10, deadline : 100
job2, execution_time : 20, deadline : 80
job3, execution_time : 50, deadline : 90
job4, execution_time : 10, deadline : 100
job5, execution_time : 30, deadline : 120

In such a case, we select the job based on creation order if both deadline and execution time are same.

In this case, the plan should be :

job2 ( 0 - 20 ), job3 ( 20 - 70 ), job1 ( 70 - 80 ), job4 ( 80 - 90 ), job5 ( 90 - 120 )

Here, between job1 and job4, we selected job1 as job1 was created first.

Another case that is possible is when a job can’t be scheduled at all. Consider the following jobs :

job1, execution_time : 20, deadline : 100
job2, execution_time : 20, deadline : 80
job3, execution_time : 60, deadline : 90
job4, execution_time : 70, deadline : 100
job5, execution_time : 30, deadline : 130

The plan should be :

job2 ( 0 - 20 ), job3 ( 20 - 80 ), job4 ( 80 - 100 ), job5 ( 100 - 130 ), job1 "cannot schedule"

System Call Implementations

Assume that at max 25 bounded jobs will be submitted. Not more than that.

1
int rt_create(void *funcaddr, uint32 size, uint32 execution_time, uint32 deadline, char *name, int32 arg)

  • To be implemented in /system/rt_create.c

This is a replacement for create system call. Please add two new arguments : the execution time and the deadline. These are in msecs.

  1. Execution time : The time for which the job is to be executed. This will act as the time quantum that will be given to this job when it becomes a running process.
  2. Deadline : This is the time by which the job should have completed. For simplicity sake, this is not absolute time, but time with reference to resume time.

rt_create does the following things :

  1. Validates the arguments. Deadline should be greater than the execution_time, they can’t be 0, etc.
  2. creates the necessary XINU metadata related to the process (by invoking old create).
  3. Maintains extra data to keep track of all bounded jobs to be scheduled on rt_plan_and_resume.

Note

  • rt_create makes sure that it does not accept any other bounded job while a current bounded job plan is being executed. This means that if you submitted some jobs and did rt_plan_and_resume, the OS should not accept any new bounded job unless all those jobs are done. The rt_create call should return SYSERR (Xinu provides SYSERR as a macro to return in case of failure).
  • rt_create accepts only 1 int32 argument to be passed to the func. Pass this to the create call.

int rt_plan_and_resume()

  • To be implemented in /system/rt_plan_and_resume.c

This is a variant of resume function for Earliest Deadline First scheduler. This selects all the bounded jobs and plans the complete schedule out. The invocation time of rt_plan_and_resume will be considered as the arrival time for all the bounded jobs. You can think of this time as t = 0 and plan the schedule out. It effectively does the following steps :

  1. Plans the jobs in earliest deadline first fashion.
  2. Plan the time quantum based on the execution time and the deadline.
  3. Print out the plan to the console.
  4. Make the processes ready and start execution of the first process.
  5. If any job can’t be scheduled before it’s deadline, do not include it in the plan and kill them.

The output format is :

<job1_name> <scheduling_time>
<job2_name> <scheduling_time>
<job3_name> <scheduling_time>
<job4_name> "cannot schedule"
<job5_name> "cannot schedule"

Sample case :

job1, execution_time : 20, deadline : 100
job2, execution_time : 20, deadline : 80
job3, execution_time : 60, deadline : 90
job4, execution_time : 70, deadline : 100
job5, execution_time : 30, deadline : 120

Output should be :

job2 : 0
job3 : 20
job4 : 80
job5 : 100
job1 : cannot schedule

Points to note

  • The jobs should be sorted by their scheduling time and the jobs which cannot be scheduled should be sorted on deadline. If the jobs have the same deadline, they should be sorted on creation order.
  • If a bounded job is killed before creating the plan, you should not execute it or include it in the plan.

resched()

Changes in resched include the following :

  1. Use a flag to denote whether bounded jobs are running or not. (This is a suggestion. You can choose your own implementation)
  2. If scheduling a bounded job :
    • Set the quantum based on the plan. (A job will execute till its quantum expires and will not resume after that)
    • If resched happened because of quantum expiry, kill self (the current running bounded job).
    • If resched leads to the current process going out of PR_CURR state, kill self (the current running bounded job).
    • If resched happened because of any other reason, continue with the execution of the same bounded job without checking any other job.
  3. After completing the last bounded job, disable the flag and print “Bounded jobs ended.” Use kprintf to print this.
  4. Schedule the next normal process in the ready queue with normal quantum.

Note

  • All priorities to the default jobs will be less than 100.
  • You can use a large dummy value = 10000 to assign priority to bounded jobs.
  • At the end of each bounded job, call the function hook. The details of hook you can find in /system/hook.c. It is void hook(pid, quantum_left); Pass the pid of the task just finished and the quantum time left when the job gave up CPU. This will be used for grading, so make sure you call hook everytime a bounded job finishes execution from reshched.

Theory Questions

The answers to these questions should be written in lab1answers.txt file. Place it in system/ directory. Here are the questions :

  1. In XINU, why are interrupts raised and what are they used for? Give example of some interrupts in XINU.
  2. In the above Earliest deadline first approach, on collision, we selected the job that has the largest execution time. What if we chose to select the smallest job first. Tell the plan, in the following scenario.
job1, execution_time : 10, deadline : 100
job2, execution_time : 20, deadline : 80
job3, execution_time : 60, deadline : 80
job4, execution_time : 70, deadline : 100
job5, execution_time : 30, deadline : 120

In the following jobs are given, what will be the completely fair scheduler plan?

job1, execution_time : 20
job2, execution_time : 20
job3, execution_time : 60
job4, execution_time : 70
job5, execution_time : 30

Note : the minimum quantum is 10ms.

Turn in

What to Turn in

You have to turn in the entire Xinu source code. Note that we will be running linter on the modified files as discussed on Piazza. It should follow those standards. Also, the warnings on compilation will lead to penalization of marks. Make sure when you compile, there are minimal warnings.