Project 3 Advanced scheduling

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. The files will always be of the form p.ins where p is a digit between 0-7.. You will have a maximum of 8 instruction files.
an integer (N). The value is the 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:

    ./project3 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 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 process. 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

Duplicate allocation names/labels are possible. The labels of the allocation should not be checked before allocation or during removal. Allocations 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, an example of how to run the program, 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. Note that you should not be copying code from any website not provided by the instructor. Using any code from previous semesters or students will results in an academic dishonesty violation. You should include directions on how to compile and use your code. You should describe all functions. You should describe any known bugs and cite any sources or people you used for help. Be sure to include any assumptions you make for your solution.

The README must be submitted through Gradescope along with the other files.

Short answer question (IMPORTANT)

In two or more paragraphs describe how changing the quantum (q) can affect the progress of the program. Include this in a section called “Choosing the Quantum”. You will not receive credit if this is not strictly followed.

Grading

To evaluate your code, we generate random test scripts that produce known results. We will verify that the results from your code match expected results.

Include a makefile with the standard targets all and clean. The make all command should create an executable project3.
The make clean target should remove executables and temporary files.

Create a private GitHub repository called cs3113fa22-project3. Add collaborators cegme, jasdehart, and farabee738 by going to Settings > Manage Access. (Or Settings > Collaborators in older version of GitHub).

When you are ready to submit, open the assignment’s submission area on Gradescope. You may make a submission by either uploading directly from your computer or linking to a GitHub repository. Gradescope will allow you to make multiple submissions, and get rapid feedback on those submissions. You will be able to choose to activate a previous submission up until the deadline.

Please make sure that you upload all of the required files.

Final Report questions

Task	Percent
Each command works correctly	80%
`README.md` 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

2022-11-29 Updated to clarify that if an allocation is unsuccessful, it is paused, and the next .ins the file is scheduled.
2022-11-29 Clarified the instruction file names.
2022-11-29 Clarified the test run to be ./project3.
2022-11-22 Updated the name of the instructio files.

Back to projects