CS423 Fall 2022

MP2: Rate-Monotonic CPU Scheduling

1. Goals and Overview

   • In this MP you will learn the basics of Real-Time CPU Scheduling

   • You will develop a Rate Monotonic Scheduler for Linux using Linux Kernel Modules

   • You will implement bound-based Admission control for the Rate Monotonic Sched- uler

   • You will learn the basic kernel API of the Linux CPU Scheduler

   • You will use the slab allocator to improve performance of object memory allocation in the kernel

   • You will implement a simple application to test your Real-Time Scheduler.

2. Introduction

   Several systems that we use every day have requirements in terms of response time (e.g. delay and jitter) and predictability for the safety or enjoyment of their users. For example, a surveillance system needs to record video of a restricted area, the video camera must capture a video frame every 30 milliseconds. If the capture is not properly scheduled, the video quality will be severely degraded.

   For this reason, the Real-Time systems area has developed several algorithms and models to provide this precise timing guarantees as close to mathematical certainty as needed. One of the most common models used is the Periodic Task Model.

   A Periodic Task as defined by the Liu and Layland model [10] is a task in which a job is released after every period P, and must be completed before the beginning of the

   Figure 1: Liu and Layland Periodic Task Model

   next period, referred to as deadline D. As part of the model, each job requires certain processing time C. Figure 1 illustrates this model.

   In this MP you will develop a CPU scheduler for the Liu and Layland Periodic Task Model. The scheduler will be based on the Rate-Monotonic Scheduler (RMS). The RMS is a static priority scheduler, in which the priorities are assigned based on the period of the job: the shorter the period, the higher the priority. This scheduler is preemptive, which means that a task1 with a higher priority will always preempt a task with a lower priority until its processing time has been used.

3. Problem Description

   In this MP you will implement a Real-Time CPU scheduler based on the Rate-Monotonic Scheduler (RMS) for a Single-Core Processor. You will implement your scheduler as a Linux Kernel module and use the Proc filesystem to communicate between the scheduler and the user space applications. Use a single Proc filesystem entry for all the communication (/proc/mp2/status), readable and writable by any user. Our scheduler should implement three operations available through the Proc filesystem:

   • Registration: This allows the application to notify to Kernel module its intent to use the RMS scheduler. The application communicates its registration parame- ters to the kernel module in the following format:

     R,<pid>,<period>,<processing time>

     where <pid> is the integer PID of the process, <period> is the task period, and <processing time> is the task processing time. All times should be in milliseconds and encoded as integers. Notice that the “R” in the string is a literal ‘R’ that denotes this is a registration message.

     1Please note that in this documentation we will use the term application and task interchangeably.

   • Yield: This operation notifies the RMS scheduler that the application has finished its period. After a yield, the application will block until the next period. Yield messages are strings with the following format:

     Y,<pid>

     where <pid> is the integer PID of the process.

   • De-Registration: This allows the application to notify the RMS scheduler that the application has finished using the RMS scheduler.

     D,<pid>

     where <pid> is the integer PID of the process.

     Your Rate-Monotonic scheduler will only register a new periodic application if the application’s scheduling parameters pass through the admission control. The admission control must decide if the new application can be scheduled along with other already admitted periodic applications without missing any deadlines for any of the registered tasks in the system. The admission control should be implemented as a function in your kernel module. Your scheduler does not need to handle cases where the application will use more than the reserved Processing Time (Overrun Cases).

     This scheduler will rely on the Linux Scheduler to perform context switches; there- fore, you should use the Linux Scheduler API. You do not need to handle any low-level functions. Please read Sections 4 and 5 for more information.

     Additionally, an application running in the system should be able to query which applications are registered and also query the scheduling parameters of each registered application. When the entry (/proc/mp2/status) is read by an application, the kernel module must return a list with the PID, Period and Processing Time of each application in the following format:

     <pid 1>: <period 1>, <processing time 1>

     <pid 2>: <period 2>, <processing time 2>

     …

     <pid n>: <period n>, <processing time n>

     You will also develop a simple test application for our scheduler. This application will be a single-threaded periodic application with individual jobs doing some compu- tations. It must do the following in order:

     1. This periodic application must register itself with the scheduler (through admis- sion control). During the registration process it must specify its scheduling pa-

        rameters: The Period of the jobs expressed in milliseconds and Processing Time of each job also expressed in milliseconds.

     2. After the registration the application must read the /proc/mp2/status entry to ensure that its PID is listed. This means the task is accepted.

     3. After this, the application must signal the scheduler that it is ready to start by sending a YIELD message to /proc/mp2/status.

     4. Then the application must initiate the Real-Time Loop, and begin the execution of the periodic jobs. One job is equivalent to one iteration of the Real-Time Loop. After each job, the process should yield via /proc/mp2/status.

     5. At the end of the Real-Time Loop, the application must de-register itself after finishing all its periodic jobs via /proc/mp2/status.

     Below you can find the pseudo-code of the Periodic Application:

     int main()

     {

     REGISTER(PID, Period, JobProcessTime); //Proc filesystem

     list=READ_STATUS(); //ProcFS: Verify the process was admitted

     if (!process in the list) exit 1;

     //setup everything needed for RT loop:

     t0 = gettimeofday(); YIELD(PID); //Proc filesystem

     //this is the real-time loop

     while(exist jobs)

     {

     wakeup_time = gettimeofday() – t0; do_job(); // factorial computation

     YIELD(PID); //ProcFS. JobProcessTime=gettimeofday()- wakeup_time

     }

     DEREGISTER(PID); //ProcFS

     return 0;

     }

     To determine the processing time of a job you can run the application using the Linux scheduler first and measuring the average execution time of one iteration of the Real-Time Loop.

     Additionally, your application can perform a simple computation, we recommend calculating the factorial of a fixed number. This MP is about Real-Time scheduling, so keep the application simple.

4. Implementation Challenges

   Scheduling usually involves 3 challenges that must work all together or you might find yourself with zombie processes or processes that do not obey the RMS policy:

   1. The first challenge involves waking your application when it is ready to run. Rate Monotonic has a very strict release policy and does not allow the job of any appli- cation to run before its period. This means that your application must sleep until the beginning of the period without any busy waiting or you will waste valuable re- sources that can be used to schedule other applications. This challenge clearly states that your applications will have various states in the kernel:

      • READY state in which an application has reached the beginning of the period and a new job is ready to be scheduled.

      • RUNNING state in which an application is currently executing a job. This application is currently using the CPU.

      • SLEEPING state in which an application has finished executing the job for the current period and it is waiting for the next period.

   2. The second challenge involves preempting an application that has higher priority than the current application as soon as this application becomes available to run. This involves triggering a context switch. You will use the Linux Scheduler API for this.

   3. The third challenge is to preempt an application that has finished its current job. To achieve this you will assume that the application always behaves correctly and notifies the scheduler that it has finished its job for the current period. Upon receiv- ing a YIELD message from /proc/mp2/status, the RMS scheduler must put the application to sleep until the next period. This involves setting up a timer and preempting the CPU to the next READY application with the highest priority.

   Figure 2: MP2 Architecture Overview

   From these three challenges, you will need to augment the Process Control Block of each task: You will need to include the application state (READY, SLEEPING, RUNNING), a wakeup timer for each task, and the scheduling parameters of the task, including the period of the application (which denotes the priority in RMS). Also, the scheduler will need to keep a list or a run queue of all the registered tasks so you can pick the correct task to schedule during any preemption point. An additional challenge is performance – CPU scheduler must minimize its overhead. Floating Point arithmetic is very expensive and therefore it must be avoided.

5. Implementation Overview

In this section, we will guide you through the implementation process. Figure 2 shows the basic architecture of our scheduler.

1. The best way to start is by implementing an empty (’Hello World!’) Linux Kernel Module. You should also be able to reuse some of the most generic functions you implemented on MP1, like linked list helper functions and so.