CS 3113 sp 20 Project 3 Advanced scheduling

Due 5/6/20 at 8:00 AM

Final project

This project will serve as your final project. In this project, you will use what you have learned over the course of the semester to simulate a CPU scheduler. This scheduler will run up to 8 execution elemements and each thread will share a location for memory allocation. You need to design the system to read from files holding “instructions” in a round robin style. You will also need to deal with issues of memory allocation and deadlock.

This scheduler will take four parameters:

• an integer (q). This represents the quantum, or the amount of instructions that are run before you have to switch to another process. Valid values will be between 1-8.
• an integer (p). The value is the number of concurrent processes. This value will be between 1-8. In the same directory you will have files with the name 0.ins to possibly 7.ins. These file contain instructions as described below.
• an integer (N). The value is th total possible space
• a string (ALGO). This string represent the allocation algorithm. The possible values for (ALGO) is FIRSTFIT (or BUDDY for extra credit).

The code should be compiled with a Makefile and using the make all command. The make clean command should clear any temporary or executable file. Below is a usage string for executing the program:

    ./project q p N ALGO

The FIRSTFIT technique is described in project 2.

You will “execute” instructions from each of the files, round robin style, in order of their priority (low to high). You will “execute” a maxiumum of (q) instructions before switching to the next, lowest priority file. When the switch occurs, the scheduler remembers the last “successfully” executed statment. When the file is revisited, this instruction is the one that is run again. Memory allocation will only cost one instruction.

Cases when you may execute less than (q) instructions:

• The instructions are complete. In this case, you will skip the file.
• A memory request fails. (See Deadlock below for details.)

Instruction

The instruction set includes the same set of instructions from project project 2. Each instruction is place on one line. If the line starts with a ‘#’ it should be ignored. Each instruction file will be less than 50 lines.

Deadlock

If a memory allocation is unsuccessful, the scheduler should switch to another memory location. When the thread resumes, the memory allocation should be attempted again. That is, the same instruction is re-executed. After the thread is rescheduled, if the memory allocation fails for a second time the thread is declared deadlocked And a DEADLOCK DETECTED should be printed to stdout and execution halted. With each failed memory allocation print the appropriate output (e.g. FAIL REQUEST A n).

Please note that this should count as a successful run of the program. I.e., your program should have an exit code of 0 or EXIT_SUCCESS in this case!

Corner Cases

Dulpicate allocation names/labels are possible. The labels of the allocation should not be checked before allocation or during removal. Allocation do not contain any extra metadata, they do not know which thread allocated or deallocated memory. In the case of duplicates:

• Always remove the “first/earliest” label if more than one allocation exists.

If there is only one thread, a failed request will cause deadlock to be detected and the program should stop. The program should have the following print out:

...
FAIL REQUEST A n
FAIL REQUEST A n
DEADLOCK DETECTED

The FIND command should only return the first, earliest matching results.

The RELEASE commad should only release the first, earliest match.

Extra Credit:

Implement the Buddy System for allocating memory. The buddy system memory allocation scheme is described in Section 10.8.1 of the Operating Systems Concepts text book. The buddy system allocation scheme is used when the string “BUDDY” is passed in as the algorithm.

COLLABORATORS file

This file should contain a pipe separated list describing who you worked with and a small text description describing the nature of the collaboration. This information should be listed in three fields as in the example is below:

Katherine Johnson | kj@nasa.gov, Helped me understand calculations
Dorothy Vaughan | doro@dod.gov, Helped me with multiplexed time management
Stackoverflow | https://example | helped me with a compilation but

README File

The README file should be all uppercase with either no extension or a .md extension. You should write your name in it, and example of how to run it, any bugs that should be expected, and a list of any web or external libraries that are used. The README file should make it clear contain a list of any bugs or assumptions made while writing the program.

Short answer question (IMPORTANT)

In two or more paragraphss describe how changing the quantum (q) can affect the progress of the program. Include this in a section called “Choosing the Quantum”.

Final Report questions

Your submission/release is due on May, 6th at 8am during the final exam time.

Task	Percent
Each command works correctly	80%
readme file is through and descriptive short answer question is correct	20%
Buddy System Tests	+15%
Max Total	115%

Proper Academic Conduct

The code solution to this project must be done individually. Do not copy solutions to this problem from the network and do not look at or copy solutions from others.

Addenda

• 2020-04-23: Fixed due date
• 2020-04-29: Added corner cases clarified allocation cost.
• 2020-04-29: Clarified the one instruction case.
• 2020-05-04: Added statement saying how release and find will only release and return the first and earliest result.
• 2020-05-05: Clarification regarding exit codes when deadlock is detected