COSC 6384: Real-Time Systems Spring 2004 Power-Conserving Real-Time Scheduling Assignment #2 Due date: March 22, 2004, midnight In this assignment, you will design and implement a scheduler for scheduling real-time, periodic tasks on a uniprocessor system that can vary its speed continuously from 20% to 100% (full speed). For example, a task with c = 5 ms takes 5 ms to complete when the processor is running at full speed, but it it needs 25 ms when the processor is running at 20% speed. The goal is to run at the slowest speed possible to conserve power while meeting the deadlines of every task. Note that switching from one speed to another takes a constant amount of time S (in ms) from the CPU. The tasks have rendezvous and critical section constraints. You will need to check that the periodic tasks with rendezvous constraints are compatible. You may assume that the scheduler itself runs on another CPU (so the scheduler does not consume CPU time for running tasks). There is a constant context-switching overhead R (in ms) between tasks (but not between blocks in the same task, of course). task-nameX is a string of alphabetical characters and numbers. num-blocksX indicates the number of blocks in a task. c(i,j), d(i), and p(i) are respectively the computation time, deadline, and period of task i, block j. cs(i,j) = 0 if the block is not a critical section. cs(i,j) = 1 if the block is a critical section. The format of the input to your scheduler is as follows: N /* number of tasks */ S /* a constant (in ms) - overhead in switching speeds */ R /* a constant (in ms) - overhead in context-switching */ task-name1 num-blocks1 ((c(1,1),cs(1,1)), (c(1,2),cs(1,2)),...,(c(1,num-blocks1),cs(1,num-blocks1))) d(1) p(1) task-name2 num-blocks2 ((c(2,1),cs(2,1)), (c(2,2),cs(2,2)),...,(c(2,num-blocks2),cs(2,num-blocks2))) d(2) p(2) : : task-nameN num-blocksN ((c(N,1),cs(N,1)), (c(N,2),cs(N,2)),...,(c(N,num-blocksN),cs(N,num-blocksN))) d(N) p(N) task-name rendezvous task-name after block1,...,blockM : : task-name rendezvous task-name after block1,...,blockM Note that deadline and period are specified at the end of each task's specification. Assume all tasks arrive at time 0. The output consists of a feasible schedule using a Gantt Chart/Timing Diagram representation, showing the tasks blocks scheduled and the CPU speed. If no feasible schedule exists even at full CPU speed, indicate the task(s) whose deadlines cannot be satisfied. You may use C, C++, Java, or other programming languages to implement the scheduler. You may also use a graphics package to help plot the timing diagrams. Several input cases will be used to test your program. Your grade will be based on correctness, efficiency and documentation.