Code in C. The files are at the bottom

Hints: The simplest solution to the starvation prevention will use a recursive approach to determine the right queue for thread selection. int scheduleNextThread();

The main.c file is :

#include "testlib.h"

#include "scheduler.h"

#include

#define test_scheduleNextThread(should) ({ \

int scheduled = scheduleNextThread(); \

printf("%s line %d: Next Thread: %d ", __FILE__, __LINE__, scheduled); \

test_equals_int(scheduled, should); \

})

int main()

{

test_start("scheduler.c");

initScheduler();

startThread(0, 5);

startThread(1, 4);

startThread(2, 2);

startThread(3, 4);

startThread(4, 3);

startThread(5, 4);

startThread(6, 2);

startThread(7, 0);

test_scheduleNextThread(-1);

// Let's assume we idle some time.

onThreadReady(1);

test_scheduleNextThread(1);

// Let's assume Thread 1 is running here.

onThreadPreempted(1);

test_scheduleNextThread(1);

// Let's assume Thread 1 is still running here.

// Thread 1 decides to do some Disk IO.

onThreadWaiting(1);

test_scheduleNextThread(-1);

// Assume we idle some time.

// Suddenly, thread 1 gets the data from the disk.

onThreadReady(1);

test_scheduleNextThread(1);

// Now thread 1 is running.

// Thread 0 and 7 get ready.

onThreadReady(0);

onThreadReady(7);

// Thread 1 is still running and gets preempted.

onThreadPreempted(1);

test_scheduleNextThread(0);

// Now thread 0 is running.

for (int i = 0; i

onThreadPreempted(0);

test_scheduleNextThread(0);

}

onThreadPreempted(0);

// Now we have scheduled thread 0 five times.

// This means that a lower priority thread should be scheduled next.

test_scheduleNextThread(1);

// The whole thing should repeat until thread 1 was scheduled 5 times.

// Then thread 7 should be scheduled.

// You can write the test for this yourself.

return test_end();

}

The Makefile is:

CC= gcc

LD= ld

CFLAGS= -g -W -Wall -Werror -std=c99

TARGET= scheduler

SRC= scheduler.c testlib.c main.c

OBJ= $(SRC:.c=.o)

scheduler: $(OBJ)

$(CC) -o $@ $(OBJ)

.PHONY: $(TARGET)-solution.o

$(TARGET)-sol: $(subst $(TARGET),$(TARGET)-solution,$(OBJ))

$(CC) -o $@ $^

$(TARGET)-solution.o:

@test -f $(TARGET)-solution.c \

|| { echo "Please download solution." >&2; false; }

$(CC) $(CFLAGS) -c $(TARGET)-solution.c

%.o: %.c

$(CC) $(CFLAGS) -c $

clean:

rm -rf $(TARGET) $(TARGET)-sol *.o

The scheduler.c is:

#include "scheduler.h"

#include

#include

#include

typedef struct _QueueItem {

/*

* The data of this item.

*/

int data;

/*

* The next item in the queue.

* NULL if there is no next item.

*/

struct _QueueItem *next;

} QueueItem;

typedef struct _Queue {

/*

* The first item of the queue.

* NULL if the queue is empty.

*/

QueueItem *head;

/*

* The last item of the queue.

* undefined if the queue is empty.

*/

QueueItem *tail;

} Queue;

typedef enum _ThreadState {

STATE_UNUSED = 0, // This entry in the _threads array is unused.

STATE_READY, // The thread is ready and should be on a ready queue for

// selection by the scheduler

STATE_RUNNING, // The thread is running and should not be on a ready queue

STATE_WAITING // The thread is blocked and should not be on a ready queue

} ThreadState;

typedef struct _Thread {

int threadId;

ThreadState state;

/*

* Range: 0 ... HIGHEST_PRIORITY (including)

* HIGHEST_PRIORITY is highest priority

*/

int priority;

} Thread;

Thread _threads[MAX_THREADS] = {{0}};

/* TODO: Add global variables if needed. */

/*

* Adds a new, waiting thread.

*/

int startThread(int threadId, int priority)

{

if (((threadId = MAX_THREADS) ||

(_threads[threadId].state != STATE_UNUSED)) ||

(priority HIGHEST_PRIORITY)) {

return -1;

}

_threads[threadId].threadId = threadId;

_threads[threadId].state = STATE_WAITING;

_threads[threadId].priority = priority;

return 0;

}

/*

* Append to the tail of the queue.

* Does nothing on error.

*/

void _enqueue(Queue *queue, int data)

{

(void)queue;

(void)data;

// TODO: Implement

}

/*

* Remove and get the head of the queue.

* Return -1 if the queue is empty.

*/

int _dequeue(Queue *queue)

{

(void)queue;

// TODO: Implement

return -1;

}

void initScheduler()

{

// TODO: Implement if you need to initialize any global variables you added

}

/*

* Called whenever a waiting thread gets ready to run.

*/

void onThreadReady(int threadId)

{

(void)threadId;

// TODO: Implement

}

/*

* Called whenever a running thread is forced of the CPU

* (e.g., through a timer interrupt).

*/

void onThreadPreempted(int threadId)

{

(void)threadId;

// TODO: Implement

}

/*

* Called whenever a running thread needs to wait.

*/

void onThreadWaiting(int threadId)

{

(void)threadId;

// TODO: Implement

}

/*

* Gets the id of the next thread to run and sets its state to running.

*/

int scheduleNextThread()

{

// TODO: Implement

*(int *)0 = 1;

return -1;

}

#if 0

int main() {

// Initially empty queue (head and tail is NULL)

Queue q = {NULL,NULL};

_enqueue( &q, 42 );

_enqueue( &q, 99 );

int x = _dequeue( &q );

printf("Expect: 42, and I got: %d ", x);

x = _dequeue( &q );

printf("Expect: 99, and I got: %d ", x);

}

#endif

The scheduler.h is:

#ifndef SCHEDULER_H

#define SCHEDULER_H

/*

* The maximum priority.

*/

#define HIGHEST_PRIORITY 5

/*

* Maximum number of threads

*/

#define MAX_THREADS 20

void initScheduler();

void onThreadReady(int threadId);

void onThreadPreempted(int threadId);

void onThreadWaiting(int threadId);

int scheduleNextThread();

int startThread(int threadId, int priority);

#endif

The testlib.c is:

#include

#include

#include "testlib.h"

#define test_failed_expected(type, should, is, file, line) { \

printf("%s line %d: Expected " type ", but got " type " ", file, line, should, is); \

had_error = 1; }

int had_error = 0;

void _test_failed_message(char *message, char *file, int line) {

printf("%s line %d: %s ", file, line, message);

}

void test_start(char *filename) {

printf("Starting to test %s... ", filename);

}

void _test_equals_int64(int64_t is, int64_t should, char* file, int line) {

if (is != should) {

test_failed_expected("%"PRIu64, should, is, file, line);

}

}

void _test_equals_int(int is, int should, char* file, int line) {

if (is != should) {

test_failed_expected("%d", should, is, file, line);

}

}

void _test_failed() {

had_error = 1;

}

void _test_equals_string(char* is, char* should, char* file, int line) {

if (strcmp(is, should) != 0) {

test_failed_expected("\"%s\"", should, is, file, line);

}

}

int test_end() {

if (had_error) {

printf("You have errors in your solution, please fix them. ");

} else {

printf("All test cases passed. This does not mean your solution is correct. ");

}

return had_error;

}

The testlib.h is:

#ifndef TESTLIB_H

#define TESTLIB_H

#include

void test_start(char *filename);

#define test_equals_int(is, should) _test_equals_int(is, should, __FILE__, __LINE__);

void _test_equals_int(int is, int should, char* file, int line);

#define test_equals_int64(is, should) _test_equals_int64(is, should, __FILE__, __LINE__);

void _test_equals_int64(int64_t is, int64_t should, char* file, int line);

#define test_equals_string(is, should) _test_equals_string(is, should, __FILE__, __LINE__);

void _test_equals_string(char* is, char* should, char* file, int line);

#define test_failed_message(message) _test_failed_message(message, __FILE__, __LINE__);

void _test_failed_message(char *message, char *file, int line);

int test_end();

#endif

P-Question 4.1: Priority Scheduler Download the template p1 for this assignment from Canvas. You may only modify and upload the file schoduler. c. Priority scheduling, assigns each scheduling, cntity (i.e., a process or thread) a priority. For each priority the scheduler has a ready queue into which ready threads with the respective priority are enqueued. The scheduler always selects the first thread from the non-cmpty ready queue of the hiphest priority. If multiple threads have the same priority (i.e., a queue contains more than one thread). the scheduler cmploys round robin scheduling, within the queue. Refer to the lecture slides for more details. In this assignment, you will replace the simple FIFO scheduler from assignment 3 with a more complex priority scheduler. We assume in the following that all thread control blocks are stored in a static array. The thread ID is the index of a thread in that array. The scheduler queues store only the thread ID. You can reuse the queue implementation from the previous assignment, A sample solution for that queue will be published after the late submission deadline f Wednesday 23:59). a. Implement/modify the event handler functions, which set the supplied thread's state and if necessary add the thread to the appropriate ready queuc. Set the 0ueueiten's data field to the thread s id. - void onthreaditeady (int. threadid) is callod if a thread in walting state becomes ready (c.f.s. thread was blocked on an 1/0 operation, and the 1/O operation has finished). The thread needs to be placed in the appropriate runqueuc. - void onthreadpreempted (int. threadid) is callod if a thread that was running was precmpted. It also nceds to be placed in the right runqueuc, as it is ready to continue. - void onthreadwaiting (int throadd) is called when a thread blocks (c.g. on an I/O operation). Such a thread cnters the waiting state and will not be part of any runqueuc. b. Implement the priority scheduling policy. with an additional rule for the prevention of starvation. Your scheduling function should perform the following basic operations whenever a new thread needs to be sclected: - Find the ready qucue with the hiphest priority that contains a ready thread - Remove the first thread from the qucue, updates its state and returns its thread id C. Add starvation prevention to the scheduler usingthe following additional rule: - If a thread with priority P has becn sclected for four times without sclecting a thread with a lower priority. then instead of selecting a thread with priority P again, the. scheduler will resort to the next lower priority queuc that (1) is not empty and (2) docs not break this starvation ruke fi.e. excceding the 4 times maximum without. scheduling lower priority threads). - Example: Assume that 0 is the lowest, 5 is the highest priority, and you have threads with prioritics 1,2 and 4 ; these threads do not block, i.c after running, they immediately return to the ready qucuc. In this casc, the schedule will be 44442444424444244442444414