G52OSC Coursework:
Process Scheduling, Operating System APIs, Threading, and Concurrency
Overview
The goal of this coursework is to make use of operating system APIs (specifically, the POSIX API in Linux) and simple concurrency directives to implement a jobs scheduling system, e.g. for scheduling process/thread. You will implement different scheduling algorithms and use a linear bounded buffer of fixed size to queue jobs.
Completing all tasks will give you a good understanding of:
Basic process/thread scheduling algorithms and evaluation criteria for process scheduling
The use of operating system APIs in Linux
The implementation of linear bounded buffers of a fixed size
Critical sections, semaphores and mutual exclusion
The basics of concurrent/parallel programming using an operating system’s functionalities
To maximise your chances of completing this coursework successfully (and to give you the best chance to get a good mark), it is divided into multiple tasks, each one of them getting gradually more difficult as you go through them. The later tasks will build upon the experience and knowledge you have gained in the preceding tasks.
You are asked to rigorously stick to the naming conventions for your source code and output files. The source files are named reqX.c, the output files should be named reqX.txt, with X being the number of the requirement (on occasions followed by a letter for the different sub-requirements). When marking your code, we may compile it automatically using scripts. Ignoring the naming conventions above may end up being detrimental to us getting your code working (and could result in loosing marks).
Coding Your Coursework
Your code MUST compile and run on the school’s servers (e.g. bann.cs.nott.ac.uk). It will be tested/marked on these machines, and we cannot account for potential differences between, e.g., Apple and Linux users. You can compile your code using the GNU C-compiler using the command gcc
Copying Code and Plagiarism
You may freely copy and adapt any code samples provided in the lab exercises or lectures. You may freely copy code samples from the Linux/POSIX websites, which has many examples explaining how to do specific tasks. This coursework assumes that you will do so and doing so is a part of the coursework. You are therefore not passing someone else’s code off as your own, thus doing so does not count as plagiarism. Note that some of the examples provided omit error checking for clarity of the code. Error checking may however be necessary in your code.
You must not copy code samples from any other source, including another student on this or any other course, or any third party. If you do so then you are attempting to pass someone else’s work off as your own and this is plagiarism. The university takes plagiarism extremely seriously and this can result in getting 0 for the coursework, the entire module, or potentially much worse.
Getting Help
You MAY ask Geert De Maere, Isaac Triguero, or any of the lab helpers for help in understanding coursework requirements if they are not clear (i.e. what you need to achieve). Any necessary clarifications will then be added to the Moodle page or posted on the coursework forum so that everyone can see them.
You may NOT get help from anybody to actually do the coursework (i.e. how to do it), including ourselves or the lab helpers. You may get help on any of the code samples provided, since these are designed to help you to do the coursework without giving you the answers directly.
Background Information
All code should be implemented in C and tested/runnable on the school’s Linux servers (e.g. bann.cs.nott.ac.uk). An additional tutorial on compiling source code in Linux using the GNU c-compiler can be found on the Moodle page.
Additional information on programming in Linux, the use of POSIX APIs, and the specific use of threads and concurrency directives in Linux can be found, e.g., here: http://richard.esplins.org/static/downloads/linux_book.pdf
It is our understanding that this book was published freely online by the authors and that there are no copyright violations because of this.
Additional information on the bounded buffer problem can be found in, e.g.:
o Tanenbaum, Andrew S. 2014 Modern Operating Systems. 4th ed. Prentice Hall Press, Upper
Saddle River, NJ, USA., Chapter 2, section 2.3.4
o Silberschatz, Abraham, Peter Baer Galvin, Greg Gagne. 2008. Operating System Concepts. 8th
ed. Wiley Publishing, Chapter 4 and 5
o Stallings,William.2008.OperatingSystems:InternalsandDesignPrinciples.6thed.PrenticeHall
Press, Upper Saddle River, NJ, USA, Chapter 5
Requirements
Task 1: Basic Process Scheduling
Your task is to implement two different process scheduling algorithms: First Come First Served and priority queues (which use Round Robin within the priority levels). Part of the code is provided on the Moodle pages and includes:
A function that generates a pre-defined number of jobs and stores them in a two dimensional array of integers. Each job is characterised by four different properties:
o The job index, i.e. an integer starting at 0, ending at NUMBER_OF_JOBS – 1
o The burst time, i.e. the time that the job requires on the CPU to completion
o The remaining time, i.e., the proportion of the burst time that is left after the job has finished
its time slice on the CPU. You will most likely need this in your implementation of priority queues.
o The priority value, i.e. a number in the range [0-9] that indicates the priority of the job. The lower the number the more priority the job is assigned.
A function to simulate the runtime of jobs – simulateJob(int time). Your code should run this function to simulate the time that the job would take on the CPU every time a job is selected.
Print functions to list all or individual jobs on the screen.
The final version of your code should:
Implement the calculation of the average turnaround time and average response time, and print the results on the screen.
Implement two different scheduling algorithms. The code and output for the two different algorithms are respectively saved in:
a) req1a.c, req1a.txt: for the first come first served algorithm.
b) req1b.c, req1b.txt: for the priority queues. Please use a time slice of 25 for the output file.
Generate output that resembles the example provided on Moodle (assuming 1000 jobs instead of the 10 jobs in the example provided). Note that we will explicitly check that the output file you submit is
different from the example provided on Moodle and is indeed generated by your own code.
Note: the random generator will provide a “fixed sequence’’ of numbers. This is due to a default seed being used to initialise the random generator. Using the same default seed every time will result in the same sequence of random numbers being generated. Using a different seed will generate a different sequence. Seeding the random generator often helps with debugging, and is therefore good practice.
Please stick rigorously to the naming conventions, including capitalisation etc.
Task 2: Unbounded Buffer with binary semaphores (a.k.a. producer/consumer problem)
Implement an “imaginary unbounded buffer’’ with a single producer and a single consumer. The producer adds jobs to the buffer, the consumer removes jobs from the buffer (provided that elements are available). Different implementations are possible, but we are asking you to use only binary semaphores in your implementation. This corresponds to the first “implementation” discussed in the lecture slides (in which a semaphore is used to delay the consumer by putting it to sleep if no elements are available in the buffer).
The final version of your code should include:
A producer thread that generates a predefined number of elements (e.g. NUMBER_OF_JOBS = 1000), and increments a shared counter that keeps track of the number of elements in the “imaginary buffer” (i.e., you do not have to declare/implement a buffer in this requirement, e.g. there is no need to define an array of an unbounded size)
A consumer function that removes elements and decrements the shared counter for every element removed
A visualisation function that displays the exact number of elements currently in the buffer on the screen every time an element is added to or removed from the buffer.
The code to:
o Define and initialise all semaphores that you require (note that you are only allowed to use
binary semaphores)
o Createtheproducer/consumerthreads
o Join the consumer/producer threads with the main thread (preventing the main thread from
ending before the consumers/producers have completed)
o GenerateoutputthatresemblestheexampleprovidedonMoodle(assuming1000jobsinstead of the 10 jobs in the example provided). Note that we will explicitly check that the output file you submit is different from the example provided on Moodle and is indeed generated by your own code.
Name your source file req2.c, and the output file req2.txt. Please stick rigorously to the naming conventions, including capitalisation, etc.
Task 3: Bounded Buffer with binary semaphores
This task builds on task 2 above. You are requested to implement a first in first out (or first come first served – FCFS) fixed size linear bounded buffer of characters with a single producer and a single consumer. The producer adds ‘*’ characters at the end of the buffer (provided that there are empty spaces available), the consumer removes ‘*’ characters from the start of the buffer (provided that elements are available). Different implementations are possible, but we are asking you to use only binary semaphores to manage the synchronization of your implementation.
The final version of your code should include:
A one dimensional array of characters of a fixed size representing the bounded buffer (note that the size of your array must be significantly smaller than the number of elements you are generating, e.g. 100 elements in size vs. 1000 elements generated).
A producer function that generates a predefined number of elements (e.g. NUMBER_OF_JOBS = 1000) and adds them to the end of the buffer as soon as space is available.
A consumer function that removes elements from the start of the buffer (one at a time) and shifts the remaining elements in the buffer forward.
A visualisation function that displays the exact contents of the buffer (i.e., the exact number of elements currently in the buffer) on the screen every time an element is added to or removed from the buffer.
All semaphores have the correct value when your code terminates, and their values are printed on screen using a format
The code to:
Declare all required semaphores and initialise them to the correct values
Create the producer/consumer threads
Make sure that all producer and consumer threads are joined with the main thread to prevent the
main thread from finishing before the consumers/producers have ended
Generate output similar to the example provided on Moodle for this requirement, but for 1000 jobs
instead of 10.
Name your source file req3.c, and the output file req3.txt. Please stick rigorously to the naming conventions,
including capitalisation, etc.
Task 4: multiple consumers and a single producer
You are asked to extend the code developed in task 3. You are allowed to use at most one counting semaphore (but as many binary semaphores as you like) to implement a new version of the linear fixed size bounded buffer problem with multiple consumers and a single producer.
Name your source file req4.c, and the output file req4.txt. Please stick rigorously to the naming conventions, including capitalisation, etc.
The final versions of your code should:
Declare all required semaphores and initialise them to the correct values (note that you can use at most one counting semaphore)
Make sure that the producer and consumers are created in a correct manner and able to run in parallel
Make sure that the producer and all consumer threads are joined with the main thread to prevent the main thread from finishing before the producer/consumers have ended
All threads end gracefully, i.e., you do not just “kill” them but instead make sure that they are not blocked on semaphores when all elements have been produced/consumed
As before, all semaphores have the correct value when your code terminates, and their values are printed on screen using a format
Generate output similar to the example provided on Moodle for this requirement, but for 1000 jobs instead of 10.
You will find that this task requires you to think carefully about the values of your semaphores, when to wait for them, when to increment them, when they block, etc. You may find it helpful to write a function that prints the values of the semaphores on the screen to help you with writing/debugging the code.
Task 5: FCFS with Bounded Buffer
You are asked to extend the code from task 4 (or task 3 if you did not manage to complete task 4) by integrating your implementation of the first come first served algorithm (task 1a) into it. The consumers will remove jobs from the start of the list, shift all remaining elements in the list forward, and “run’’ the job (using the simulateJob(int iTime) function). The producer generates jobs and adds them to the end of the bounded buffer. At the current point in time, we’d expect you to implement the buffer as a two dimensional array of integers and a fixed size. The final version of your code should:
Define all required semaphores and initialise them to the correct values
Run/create all producer and consumer threads and make sure that they run in parallel
Call the simulateJob(int iTime) function every time a job is selected by one of the consumers
Calculate the average response time and average turnaround time and print them on the screen when
all jobs have finished
Generate output similar to the example provided on Moodle for this requirement, but for 1000 jobs
instead of 10
Synchronise all critical sections in a correct and efficient manner, and only when strictly necessary
Restrict the critical sections to the smallest possible code set(s)
Call your code req5.c and the output req5.txt (assume 1000 jobs). Please stick rigorously to the naming conventions, including capitalisation etc.
Task 6: priority queues integration
You are asked to extend the code from task 4 (or task 3 if you did not manage to complete task 4) by integrating the priority queues algorithm from task 1b. The producers add jobs to the end of the list, the consumer removes
elements from the start of the list. Note that jobs that have not fully completed in the “current run’’ (i.e. the remaining time was larger than the time slice) must be added to the end of the queue/buffer again. At the current point in time, we ask you to implement this algorithm using a two dimensional array of a fixed size, and shift the later elements forward whenever one of the consumers removes an element from the list/buffer. Run the simulateJob(int Time) function every time a job is selected by one of the consumers. The final version of your code should:
Define at most one counting semaphore and as many binary semaphores as you need, and initialise them to the correct values
Create a single producer and multiple consumers and make sure that they run in parallel
Call the simulateJob(int iTime) function every time a job is selected by one of the consumers
Calculate the average response time and average turnaround time and print them on the screen when
all jobs have finished
Generates output that resembles the example provided on Moodle (assume 1000 jobs)
Synchronise all critical sections in a correct manner, and only when strictly necessary
A correct implementation of the priority queue algorithm
Restrict the critical sections to the smallest possible code set(s)
Include code to calculate the average response time/turnaround time and display it on the screen when
all jobs have finished.
Call your code req6.c and the output req6.txt (assume 1000 jobs). Please stick rigorously to the naming
conventions, including capitalisation etc.
Submission
Create a single .zip file containing all your source code and output files in one single directory (use your username as the name of the directory, e.g. psyXXX). If you have completed all parts of the coursework successfully, the directory should contain:
req1a.c, req1a.txt, req1b.c, req1b.txt
req2.c, req2.txt
req3.c, req3.txt
req4.c, req4.txt
req5.c, req5.txt
req6.c, req6.txt
The deadline for submission is 3pm, Monday 28th November
Marking criteria
The focus on this coursework is on operating systems and concurrency, e.g. the use of operating system APIs and the correct synchronisation of your code. It is not on programming skills i.e., you will be mainly assessed on these concepts, not on the extra bells and whistles you have included in your code. In fact, they often make it more difficult to analyse the solution, and hence over complicating your code may actually be detrimental.
In each case the marking will take into account your exact implementation, the correctness of the algorithms/logic, and the efficiency of your code (in particular with respect to the synchronisation). To assess criteria, we will analyse, compile and run the submitted code and look for specific inefficiencies.
When considering how this will be marked, please be aware that it is important that:
A) We can compile and run your program on the school’s servers without modification (i.e. if programming on an Apple device, please verify that your code compiles and runs on the school’s servers).
B) Your program does not crash, go into deadlock, or cause segmentation faults (by addressing unallocated memory)
C) We can understand the code that you have written. I.e., you did not overcomplicate your code and have added sufficient documentation to enable us to understand your code.
D) We understand why you wrote the code in the way that you did. Again use the documentation to explain this.
E) Your code/logic is correct and that synchronisation is appropriate.
F) Your code does not unnecessarily complicated or inefficient.
G) You have demonstrated your understanding of threading, synchronisation, and the use of operating
system APIs.
Note that not all requirements will receive an equal proportion of the marks.