CIS 657 Programming Assignment 1
Submit two files:
•Create your Assignment 1 document (doc or pdf), follow the instruction and then submit it to the Turnitin link on the blackboard (under Assignments).
•You can submit multiple times before the due.
•After the due, you cannot resubmit newer version.
•Do a “make clean” in code/build.linux, then compress your Nachos folder on the VM, download the compressed file into your local machine and name the compressed file Ass1_yourNetId.zip (Note: Zip only!!). Submit the zipped file to the Assignment Code Submission link of Blackboard.
•You need to submit the entire nachos directory
•We will build and run your nachos, not individual files
•Use naming convention
•When we uncompress your zip file, we want to see your nachos like
Ass1_netid
code
threads
machine
…
•Do not change compiler option in Makefile
•You have to make sure your submission is correctly made
•If you don’t have a confirm email, you should check again.
•You should raise an appeal within a week after grade is posted.
Due: Oct.18 (Friday, end of the day)
Late submission: you will have 2d penalty of your late days.
Follow the Lab1 instruction and create a new fresh Nachos folder.
Overview
The original distribution of Nachos uses the round-robin scheduling with 100 time-ticks. The responsibility of a scheduler in an operating system is to distribute the CPU to tasks (threads in Nachos). RR scheduling is giving the exact same amount of CPU time, so it can be good for interactive applications, not for batch jobs. We need new scheduling for both interactive and batch tasks with a fraction (weight) of CPU time share. Our new scheduling algorithm makes each task to maintain its virtual runtime (= executed time * weight) and picks the task with the smallest virtual time.
In this project you are asked to implement the completely fair scheduler (CFS) scheduling with your own simulated I/O.
Task 1 (30%): You need to design your own I/O simulating input(read)/output(write) operations. These IO operation routines can be used by Nachos threads. Warning: This task has been given to the previous semesters. If you use/copy past semester code, you will fail.
•Write operation: when a thread calls this routine, a new I/O request event is created and set with random amount of waiting time for blocked state. Then the event will be added to the internal I/O queue. Afterwards this request blocks the calling thread (current thread) until your output message is displayed on the screen.
•Read operation: like Write operation, this also creates and sets a new I/O request event with random amount of waiting time. Then the event will be added to the internal I/O queue. The calling thread will be blocked until the parameter of buffer is filled with your own content, and at this moment, you can display a simple message.
•Write waiting(blocking) time << Read waiting(blocking) time•I/O request event structure: you can define your own data structure including I/O type, calling thread, buffer holding data between call and completion of the request, parameters used by I/O routines, completion time (decided by random waiting time), and so on.•I/O request queue: you can keep this as a Kernel’s internal I/O event queue using sorted list by the completion time. You can simulate I/O events using Alarm.•I/O Simulation can be periodically invoked by Alarm. If completion time of a pending I/O is less than or equal to current time, it raises I/O interrupt and then I/O interrupt handler will be invoked.•I/O interrupt handler: You need to implement your own simulated I/O interrupt. When a I/O completes (simulated with Alarm), I/O interrupt is raised. •You have to make sure that the thread state as Ready-to-Run.•At the end of interrupt handling, there should be scheduling.•You need to display appropriate messages. •Kernel can have a new simulated I/O component, so thread functions can call the simulated I/O operations and they will be simulated.•Implement your design of simulated I/O in threads directory and update Makefile.Task 2 (60%): Make your Nachos system run with CFS scheduling (Reference for CFS — https://developer.ibm.com/tutorials/l-completely-fair-scheduler/ ) You can also look at https://www.cs.auckland.ac.nz/software/AlgAnim/red_black.html for red-black tree.Task 3 (10%): Write your own threadtest.cc to prove your implementation working correctly. Quality of your testing cases will be graded.•You need to set random seed (current time is usually used) for simulation.•You need to create meaningful number (> 20) of Nachos Kernel threads in your testing routine.
•CPU-bound threads, IO-bound threads, mixed
•For example, task 1 is only computation for 1 million time ticks, task 2 is consisting of 80% I/O and 20% computation, task 3 is running 50% I/O and 50% computation, …
•You need to display meaningful information to prove your scheduling: context switching, simulated I/O requests, simulated I/O interrupt; dynamic changes of RB tree with I/O requests and aging.
Your document must include the followings:
•Cover Page
•Disclosure Form
•How much time did you spend to do:
•Analyze the problem, determine specifications, and create your design
•Implement the design
•write the program
•Test/debug the program
•Find/fix errors
•Create test cases, and try them out
•List of your files with directory name that you modified or created for this assignment
•Design/your solution for each requirement
•We are looking for your own answers
•Implementation of your solution (Code snippet with good comments) – You can put this with # 5 together
•Do not include Nachos original code
•We want to see your own code/modification
•Should be text (no image/photo of code)
•Testing
•How to run your tests
•What each test case is testing (you need to prove your implementation of each requirement in the following output snapshots)
•Output Snapshots
Testing:
We will build and run your Nachos on the VM. We will also compare the test result with your output. You must test your program on the VM and should provide proper test scenario in your document.
Grading:
•Syntax/Runtime/Logic Errors with proper Makefile [-50, -15]
•Do not change Compiler option
•Name and directory structure of submitted Nachos zip [-10]
•Quality of your report/comments [-50, -5]
•Satisfy all implementation requirements [-50, -5]
•Simulated IO design/class definition/declaration respectively
•CFS implementation using RB Tree
•Garbage collection (handle all created objects at the end) [-10, -5]
•Appropriate thread manipulation (CPU-bound/IO-bound threads) [-30,-5]
•Test case
•Input/output design (meaningful messages to prove your implementation) [-30, -10]
•Output(by Students)/Test(by TAs) [-50]
Reviews
There are no reviews yet.