Assignment 4 CPU Scheduling Solution

    • The Problem

The Simply Irie restaurant thieves are still out there (at least at the time of this writing) and their next target is our own Dining Center. So, one night they break in and steal most of the chairs and tables (no one knows why they didn’t take the Nescafe machines instead). The university does not have enough time to add tables in the DC so they have to do with the few tables left for at least two days. That’s when you realize that the scheduling policies you learned in your CPSC 457 course can be used to reduce some of frustration of scarcity of seats in the DC. Let’s say there are N tables left in the Dining Center. Students come in with some random inter-arrival time and each student sits at one table. If all tables are full, they have to wait in line. Note that the line might build up inde nitely. A student that sits at a table will eat for a speci c amount of time and then leave. Note that the time it takes each students is pre-determined. So each student knows before joining the line how much they are going to take eating. You want to try out di erent scheduling algorithms for sitting students at the tables in the rst day, and compare them and stick with the best one for the second day. The algorithms are compared by these criteria:

    1. Turnaround Time: The time it takes a student from rst sitting at a table until they nish and leave DC. The smaller this number the better.

    2. Waiting time: The total amount of time a student spent outside of dining area (waiting in line). The smaller this number the better.

Here are the scheduling algorithms:

1. FIFO: First student in, is the    rst to be served. Seems pretty fair right?


1


    2. Round-Robin: Each student can’t take more than a speci c time quantum at the table. If they surpass that time slot, they are going to have to get up and wait outside even if they are in the middle of eating (however rude that is).

You need to implement the above algorithms in two separate les: One named round-robin.c or .cpp and the other fo.c or fo.cpp, depending on whether you use C, or C++, respectively.

    • The Input

The input of the program is read from a le. The name of the le is going to be taken from user input. The le1 is structured as follows:

    1. The rst line of the le is a single integer specifying the time quantum size of the round-robin algorithm.

    2. After that, an arbitrary number of lines follow each containing two numbers separated by one space character. The rst number is an integer that denotes the relative timestamp of the student arrival. The rst timestamp is always zero and timestamps increase afterwards. The value of each timestamp, therefore, indicates how long it has been since the previous arrival. The second number is an integer specifying the amount of time it takes that speci c student to eat.

    • The Implementation

You need to solve this problem for number of tables N = 4. Each table has a server which is represented by a thread. You should have at least 5 threads:

    1. One thread reads information about students from the input le and adds them to the Queue. This is the producer.

    2. Four threads for scheduling students and serving them accordingly.

The scheduling, itself, is done using threads (the pthread library). You should have one thread for each dining table, as we have one dining area server responsible for each table. You can implement the Queue using whatever data structure you see t (at this point you must have seen enough examples to be able to make a decent choice (we suggest a doubly linked list). Just be aware of two things:

        1. The data structure should work with sharing, communication and synchronization mechanisms.

        2. The data structure should support in nite (theoretically) queue size.

1the le shall be used for both scheduling algorithms although the quantum is not needed in the FIFO algorithm.


2


    • How to do It

The following are suggested implementation steps:

    1. Start with the student producing thread, that is going to give you an idea of what data structure is suitable for the assignment and how you should implement it. There are two general steps here:

        (a) Creating a student, which requires reading arrival time and eating duration of the student from the input le, and adding the info to a proper data structure that represents a student.

        (b) Adding the newly created student to the Queue. At this stage you will probably encounter the problem of exceeding the size of the allocated queue data structure as you continually add students. There are two solutions for this problem. The simple one is allocating enough memory in the beginning so that you are sure you won’t encounter this issue. The second solution is dynamically allocating new memory regions on the y. Mention in your report if you have used this approach and also mention how and where, to get some bonus points.

    2. After you are nished with the producer, write a very simple scheduler that reads the items added to the Queue by the producer to make sure the communication between the two works correctly. Add the synchronization mechanisms for the Queue as well.

    3. Then you can start implementing the scheduling algorithms one by one. At this point you might start to think about the details of representing each student in the Queue. We suggest you include these details at least:

        (a) A unique ID. This is can be generated automatically using a counter initialized to 0, and incremented before reading each line; i.e. the rst student will have ID = 1, the second 2, and so on.

        (b) How much of eating the student has left.

    4. You might want to start with the FIFO scheduling algorithm since its the easiest one. The scheduling takes place in three general steps:

        (a) Take a student out of the Queue according to the scheduling policy. In the case of FIFO, the Queue acts like a FIFO queue and you need to take the head of the Queue for serving.

        (b) Start the dining process and do busy waiting ( a while loop maybe) until time is up. In the FIFO scheduling algorithm which is non-preemptive, the student will sit at the table and eat until s/he is done, then the student will get out of the dining centre.

3


    (c) In the case of Round-Robin, it might as well be the case that the student’s time slot is up and s/he needs to be preempted. You need to add the student to the Queue again and sit another student at the table. Be aware that any access to the Queue must be synchronized using mutex locks or semaphores.

We advise against using the clock() function for timestamps unless you nd a way around its limitations. It is better to use the chrono library API calls. Also, after reading from the le has nished, your program needs to join with the threads and exit gracefully, deallocating resources.

    • The output

You output will be processed using an interpreter for correction, so make sure you strictly follow the format speci ed. The program is expected to produce lines of output at di erent times:

    1. Whenever a student arrives and joins the Queue, this statement must be printed: Arrive <student ID>
    2. Whenever a student is selected by a scheduling thread to sit at a table, this statement must be printed:

Sit <student ID>

    3. Whenever a student is preempted and put in the line, this statement must be printed: Preempt <student ID>
    4. Whenever a student is  nished and leaves the Dining Center, this must be printed:


Leave <student ID> Turnaround <turnaround time measured> Wait <waiting time measured>

Note that the times speci ed here are in seconds. Just replace whatever is enclosed by <> with the required value, no <> should be in the output. If your timings are o by a couple of milliseconds, you need to round to the closest integer. e.g. 1.99 s should be rounded to 2 seconds.






4


    • Grading

This assignment will carry 25%. In addition to code checking, your program will be tested against some prepared and well designed test les. You can also provide your own test le. Be reminded about the University strict rules on plagiarism and other related details mentioned in the course outline.

    • To Submit

You need to submit source les, executables, along with a Make le that will be used to compile and link your shell. These les should be combined into a tar le that will unpack the les into a directory whose name is your user-id, followed by your surname. The tar le will be submitted on the D2L page of the course.

    • Deadline

April 12, 2022 before 11:55 P.M. Late submission is subject to the regular penalty of 20% for every day or part of the day.
































5