CMPE322 project series is a set of projects that teaches how to construct an operatingsystem, named BUnix (written in institutional colors of Boğaziçi University J ), from scratch. In thefirst project, we learn how to manage processes (tasks) in an operating system for a single CPU (witha single core). For this purpose, we expect from you to implement a round robin scheduler in Clanguage.Round Robin AlgorithmRound robin algorithm is a scheduling algorithm in which the CPU can be interrupted by theoperating system while it executes a process and is forced to switch to the execution of anotherprocess in the ready queue. The interruption occurs after the process consumes its assigned timecalled “time slot”. Then, the scheduler sends this process to the end of the ready queue and executesthe process at the head of this queue. For example, assume that the time slot is 100 milliseconds inBUnix and the operating system has to schedule the following processes using round robin algorithm.You should have noticed that the “total execution time” of a process is not a given parameter; itdepends on the execution of the program code which is explained in the next section.PROCESS NAME ARRIVAL TIME (ms) TOTAL EXECUTION TIME (ms)P1 0 210P2 50 120P3 120 240P4 450 30Table 1 – Example for BUnix Operating System with four processesThe actions we are expect from your scheduler are:Time The Scheduler Action The Ready Queue0 Execute P1 P150 Add P2 to the end of the queue P1 P2100 P1 consumes its time slot; reschedule it and execute P2 P2 P1120 Add P3 to the end of the queue P2 P1 P3200 P2 consumes its time slot; reschedule it and execute P1 P1 P3 P2300 P1 consumes its time slot; reschedule it and execute P3 P3 P2 P1400 P3 consumes its time slot; reschedule and execute P2 P2 P1 P3420 P2 is finished; remove it from the queue and execute P1 P1 P3430 P1 is finished; remove it from the queue and execute P3 P3450 Add P4 to the end of the queue P3 P4530 P3 consumes its time slot; reschedule and execute P4 P4 P3560 P4 is finished; remove it from the queue and execute P3 P3600 P3 is finishedTable 2 – Round robin schedulerThe Process Structure and the Code FilesAs you learned in the lectures, a process contains the program code and its current activity(context). Normally, a program code is a binary file, which contains the instructions that areexecutable by the CPU. However, for the sake of simplicity, we will use text files (*.code) thatrepresent the executable code of the processes in this project. The structure of the text file is shownin Table 3. Each row of the text file represents an instruction in which the first column presents thename of this instruction and the second column is the execution time required by the CPU tocomplete this instruction.INSTRUCTION NAME INSTRUCTION EXECUTION TIME (ms)instruction_1 20instruction_2 50instruction_3 50instruction_4 20instruction_5 30……Exit 10Table 3 – A Text Based Program Code File ExampleEach of the rows is an atomic operation, which means if the CPU starts to execute thisinstruction, it cannot be interrupted to schedule another process until the execution of thatinstruction is completed. Assume that the “time slot” is 100 ms in BUnix and we start executing theprocess with the program code in Table 3. The scheduler should stop the process after“instruction_3” (execution time 120ms), add this process to the end of ready queue, and startexecuting the first process in the queue. Finally, you might have noticed that the last instructionname is “exit” which means that this process should be finalized and it should be removed from thesystem after the exit instruction is executed.In addition to the program code, we need to store the current activity (context) of a processto reschedule this process and continue to execute it with the CPU. Normally, the current activity of aprocess contains different elements such as the registers in the CPU and stack of the process. InBUnix, we just need to store the line number of the last executed instruction before sending thisprocess to the ready queue.Don’t get confused by the names of the instructions. These are not real machine codes and YOU WILLNOT REALLY EXECUTE. The only important thing is that you have to calculate the execution times ofthese instructions correctly. So, you can stop a process, send it back to the ready queue, and runanother process at the right time.The Process Definition FileThe process definition file (definition.ini) is a text file that provides the initial information ofthe processes in the system. The following table shows the structure of this file.Process Name Program Code File Arrival Time (ms)P1 1.code 0P2 3.code 20P3 1.code 130P4 1.code 170………Table 4 – The Process Definition File StructureEach row represents a process in the system. You should have noticed that process names areunique, but more than one process may be assigned to the same program code.The Scheduler CodeThis component is a C code that parses the process definition file and schedules these processesusing the round robin algorithm. The design should have at least the following parts:• The parsing of the “process definition file” and the programming code files.• The process data structure, which includes at least the programming code address (or thefilename) and the last executed line information.• A FIFO queue to implement the ready queue.• A round robin scheduler that maintains the queue.• An output mechanism that generates a file to show the ready queue whenever it is changedby the algorithm. The output file should have the format that is shown in Table 5.[TIME]::HEAD-[Ready Queue]-TAIL100::HEAD—TAIL200::HEAD-P1-P2-TAIL340::HEAD-P2-P3-P1-TAIL450::HEAD-P3-P1-P2-TAIL590::HEAD-P1-P2-P4-P3-TAIL630::HEAD-P2-P4-P3-TAIL790::HEAD-P4-P3-P2-TAIL930::HEAD-P3-P2-P4-TAIL970::HEAD-P2-P4-TAIL1090::HEAD-P4-P2-TAIL1130::HEAD-P2-TAIL1230::HEAD-P2-TAIL1240::HEAD—TAILTable 5 – The Output File FormatDevelopment PlatformYou have to implement your design in the Linux Platform with GCC/G++ Compiler. Westrongly advise you to install Ubuntu which has pre-installed GCC/G++ compiling tools. We will testyour code in this platform and if your compiled code is not compatible with the test platform. Youmight be invited for a demo, if necessary.Provided FilesThe following files are given together with the project:• The process definition file (number of processes and their arrival times will be modifiedto test your code).• Four program code files (number of instructions, their names and their execution timeswill be modified to test your code. Only exception is the last instruction name is always“exit” and its execution time is 10 milliseconds).• The expected output file.• Note: The length of the time slot is a constant value in BUnix operating system (100milliseconds).
CMPE322
[Solved] CMPE322 Project1-AN OPERATING SYSTEM SCHEDULER IMPLEMENTATION
30 $
File Name: CMPE322_Project1-AN_OPERATING_SYSTEM_SCHEDULER_IMPLEMENTATION.zip
File Size: 574.62 KB
Only logged in customers who have purchased this product may leave a review.
Reviews
There are no reviews yet.