代写CSCI 3150、Round-Robin Scheduler代做、代写c++语言、c++编程语言调试

日期：2019-04-24 10:55

2019 Spring, CSCI 3150 – Bonus 2

Contents

1 Introduction 3

1.1 Process States . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

1.2 The Ready Queue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

1.3 Scheduling Processes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

1.4 CPU Scheduler Invocation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

2 The assignment package 5

2.1 Get starter package . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

2.2 Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

2.2.1 os-sim.c . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

2.2.2 process.c . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

2.2.3 student.c . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

3 Your assignment 8

3.1 To begin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

3.2 Your job . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

3.2.1 FCFS Scheduler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

1

3.2.2 Round-Robin Scheduler . . . . . . . . . . . . . . . . . . . . . . . . . 10

3.2.3 Static Priority Scheduling . . . . . . . . . . . . . . . . . . . . . . . . 11

3.3 Check your results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

3.3.1 Run our grader . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

3.3.2 Running statistics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

3.4 Submit your assignment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

4 Grading 15

5 Change Log 15

6 Questions 16

7 Academic Honesty 16

8 General Notes 16

2

1 Introduction

In this assignment, you are requested to implement a CPU scheduler for a (simulated)

OS written by us. Hopefully, you will get some more solid knowledge on scheduling, multithreading,

and synchronization by doing this assignment. We thank Umakishore Ramachandran,

Kevin Han, and Adithya Nott from Georgia Tech when preparing this assignment.

1.1 Process States

In our simulated OS, there are five possible states for a process, which are listed in the

process state t (an enum type variable) in os-sim.h:

NEW - The process is being created, and has not yet begun executing.

READY - The process is ready to execute, and is waiting to be scheduled on a CPU.

RUNNING - The process is currently executing on a CPU.

WAITING - The process has temporarily stopped executing, and is waiting on an I/O

request to complete.

TERMINATED - The process has completed.

There is a field named state in the PCB (Process Control Block 1

, see the definition in

os-sim.h), which must be updated with the current state of the process. The simulated OS

will use this field to collect statistics. Fig. 1 shows the transition of different process states.

1.2 The Ready Queue

On most systems, there are a large number of processes, but only one or two CPUs on which

to execute them. When there are more processes ready to execute than CPUs, processes

must wait in the READY state until a CPU becomes available. To keep track of the processes

waiting to execute, our simulated OS keeps a ready queue where the processes are in READY

state.

1https://en.wikipedia.org/wiki/Process_control_block

3

Figure 1: Process States

Since the ready queue can be accessed by multiple processors, which may add or remove

processes from the ready queue, the ready queue must be protected by some form of

synchronization — for this assignment, it shall be a mutex lock.

1.3 Scheduling Processes

schedule() is the core function of the CPU scheduler. It is invoked whenever a CPU

becomes available for running a process. schedule() must search the ready queue, select a

runnable process, and call the context switch() function to switch that process onto the

CPU.

There is a special process, the idle process, which is scheduled whenever there are no

processes in READY state.

1.4 CPU Scheduler Invocation

There are four events that our simulated OS will invoke schedule():

yield() - A process completes its CPU operations and yields the processor to perform

an I/O request.

wake up() - A process that previously yielded completes its I/O request, and is ready

to perform CPU operations. wake up() is also called when a process in the NEW state

4

becomes runnable.

preempt() - When using a Round-Robin or Static Priority scheduling algorithm, a

CPU-bound process may be preempted before it completes its CPU operations.

terminate() - A process exits or is killed.

The CPU scheduler also contains one other important function: idle(). idle() is called

when the idle process 2

is scheduled. In the real world, the idle process puts the processor

in a low-power mode and waits. For our simulated OS, you will use a pthread condition

variable to block the thread until a process enters the ready queue.

2 The assignment package

2.1 Get starter package

You should have opened a Github account and told us your github account by filling up a

Google form during your assignment 0. So, after logging in your Github account, come here

https://classroom.github.com/a/Vi-drgTh to get a new repo for this assignment. The

new repo should contain the starter package for this assignment.

You are given the following files to implement the simulated OS:

2https://unix.stackexchange.com/questions/361245/what-does-an-idle-cpu-process-do

5

Name Description

/os-sim.c Code for the simulated OS which calls your CPU

scheduler (Don’t touch).

/os-sim.h Header file for the simulator (Don’t touch).

/process.c Descriptions of the simulated processes (Don’t

touch).

/process.h Header file for the process data (Don’t touch).

/student.c This file contains stub functions for your CPU

scheduler (Work on it).

/student.h Header file for your code to interface with the simulated

OS (Don’t touch).

/Makefile Makefile to compile os-sim (Don’t touch).

/grader.py We will run this script to grade your assignment

(Don’t touch).

2.2 Remarks

2.2.1 os-sim.c

The simulated OS is implemented by pThread. One thread per CPU and one thread as

a “supervisor” for our simulation. The CPU threads will simulate the currently-running

processes on each CPU, and the supervisor thread will print output and dispatch events to

the CPU threads. Fig. 2 demonstrates the function calls in the simulated OS.

Since the code you write will be called from multiple threads, the CPU scheduler you

write must be thread-safe! This means that all data structures you use, including your ready

queue, must be protected using mutexes.

The number of CPUs is specified as a command-line parameter to the simulator. For this

assignment, we will simulate an OS with 1, 2, or 4 CPUs.

Also, for assignment purposes, the simulated OS executes much slower than a real system

would. In the real world, a CPU burst might range from one to a few hundred milliseconds,

whereas in this simulator, they range from 0.2 to 2.0 seconds.

6

Figure 2: Function calls in the simluated OS

2.2.2 process.c

This file contains the processes that we will submit to the simulated OS.

We use eight hard-coded simulated processes, five CPU-bound and three I/O-bound, as

shown in following figure. The simulated OS will submit these processes to the ready queue

sequentially, and you need to implement the correct scheduling algorithm to select the next

jobs to run.

For simplicity, we have labeled each starting with a “C” or ”I” to indicate whether it is

CPU-bound or I/O-bound. For this assignment, priorities range from 0 to 10, with 10 being

the highest priority. Note that the I/O-bound processes have been given higher priorities

than the CPU-bound processes.

7

2.2.3 student.c

This file contains the implementation of CPU scheduler.

As we introduced in Section 1.3 and Section 1.4, it contains the core function schedule()

and other five events function yield(), wake up(), preempt(), terminate() and idle().

Besides, the main() is also in this file.

3 Your assignment

3.1 To begin

Make, then run ./os-sim 2, an OS with two CPUs will be simulated and you shall see

something like this:

The simulator generates a Gantt Chart, showing the current state of the simulated OS

at every 100ms interval. The leftmost column shows the current time, in seconds. The next

three columns show the number of Running, Ready, and Waiting processes, respectively. The

next two columns show the process currently running on each CPU. The rightmost column

8

shows the processes which are currently in the I/O queue, with the head of the queue on the

left and the tail of the queue on the right.

As you can see, nothing is executing. This is because the CPU scheduler has not been

implemented yet! Once you complete this assignment, you will see the processes executing

on the CPUs.

3.2 Your job

Your job is to implement the following three CPU scheduling algorithms for the CPU scheduler

in student.c:

First-Come, First Served (FCFS) - Runnable processes are kept in a first-in, firstout

ready queue. FCFS is non-preemptive; once a process begins running on a CPU,

it will continue running until it either completes or blocks for I/O.

Round-Robin (RR) - Similar to FCFS, except preemptive. Each process is assigned

a timeslice when it is scheduled. At the end of the timeslice, if the process is still

running, the process is preempted, and moved to the tail of the ready queue.

Static Priority- The processes with the highest priorities always get the CPU. Lowerpriority

processes may be preempted if a process with a higher priority becomes

runnable.

3.2.1 FCFS Scheduler

Implement the CPU scheduler using the FCFS scheduling algorithm. You may do this

however you like, however, we suggest the following:

Implement a thread-safe ready queue using a linked list. A linked list will allow you to

reuse this ready queue for the Round-Robin and Static Priority scheduling algorithms.

Implement the yield(), wake up(), and terminate() handlers. preempt() is not

necessary for this stage of the assignment. See the overview and the comments in the

code for the proper behavior of these events.

9

Implement idle(). idle() must wait on a condition variable that is signalled whenever

a process is added to the ready queue.

Implement schedule(). schedule() should extract the first process in the ready

queue, then call context switch() to select the process to execute. If there are no

runnable processes, schedule() should call context switch() with a NULL pointer

as the PCB to execute the idle process.

Here are some notes for your implementation:

Remember to update the state field of the PCB. The simulator will read this field to

generate the Running, Ready, and Waiting columns, and to generate the statistics at

the end of the simulation.

There is a field in the PCB, next, which you may use to build linked lists of PCBs.

Four of the five entry points into the scheduler (idle(), yield(), terminate(), and

preempt()) should cause a new process to be scheduled on the CPU. In your handlers,

be sure to call schedule(), which will select a runnable process, and then call

context switch(). When these four functions return, the library will simulate the

process selected by context switch().

context switch() takes a timeslice parameter, which is used for preemptive scheduling

algorithms. Since FCFS is non-preemptive, use -1 for this parameter to give the process

an infinite timeslice.

3.2.2 Round-Robin Scheduler

Add Round-Robin scheduling functionality to your code. You should modify main() to add a

command line option, -r, which selects the Round-Robin scheduling algorithm, and accepts

a parameter, the length of the timeslice. For this assignment, timeslices are measured in

tenths of seconds. E.g.:

./os-sim <# CPUs> -r 5

should run a Round-Robin scheduler with timeslices of 500 ms. While:

./os-sim <# of CPUs>

should continue to run a FCFS scheduler.

10

Table 1: The test cases

test ID parameters Purpose

0 ./os-sim 1 test FCFS with one CPU

1 ./os-sim 2 test FCFS with two CPUs

2 ./os-sim 4 test FCFS with four CPUs

3 ./os-sim 1 -r 1 test RR with one CPU and timeslices of 100ms

4 ./os-sim 2 -r 1 test RR with two CPUs and timeslices of 100ms

5 ./os-sim 1 -r 5 test RR with one CPU and timeslices of 500ms

6 ./os-sim 2 -r 5 test RR with two CPUs and timeslices of 500ms

7 ./os-sim 1 -p test Static Priority with one CPU

8 ./os-sim 2 -p test Static Priority with two CPUs

9 ./os-sim 4 -p test Static Priority with four CPUs

3.2.3 Static Priority Scheduling

Add Static Priority scheduling to your code. Modify main() to accept the -p parameter to

select the Static Priority algorithm. The -r and default FCFS scheduler should continue to

work. The scheduler should use the priority specified in the static priority field of the

PCB. This priority is a value from 0 to 10, with 0 being the lowest priority and 10 being the

highest priority.

For Static Priority scheduling, you will need to make use of the current[] array and

force preempt() function. The current[] array should be used to keep track of the

process currently executing on each CPU. Since this array is accessed by multiple CPU

threads, it must be protected by a mutex. current mutex has been provided for you. The

force preempt() function preempts a running process before its timeslice expires. Your

wake up() handler should make use of this function to preempt a lower priority process

when a higher priority process needs a CPU 3

.

In this part, you will need a priority queue not a First-in-First-out queue as the ready

queue. One suggestion is to extend the linked list implementation you wrote for the FCFS

algorithm. The common approach is to add priority push() or priority pop() function

3

If the new arrived process have the same priority with the lowest priority process which is currently

executing on the CPU, we do not preempt the running process.

11

for the queue.

3.3 Check your results

Before running the grader, please set the CPU number of the virtual machine as 4. Because

the different cpu number will affect the expected range of evaluation metrics (will be described

in following section). The excepted range in the grader is determined according to 4

cpus.

3.3.1 Run our grader

After you have finished the assignment, run grader.py to check whether you can pass the

given test cases. There are 10 test cases which are briefly introduced in Table 1. You have

two ways to run our grader:

python3 grader.py

will run all 10 test cases, while

python3 grader.py i

will only run the i

th test case.

If you correctly finish the assignment and type the following commands:

python3 grader.py

you shall see something like this:

12

Otherwise, the grader will output the fail reason of each test case. All possible reasons

are listed below:

Running timeout (we set a running time limit for each test case)

The number of context switches is not within the valid range

The total execution time is not within the valid range

The total time spent in READY state is not within the valid range

3.3.2 Running statistics

If you successfully complete the assignment, then executing ./os-sim with a set of valid

parameters will print the executed process schedule and its statistics:

1. Number of context switches

2. Total execution time

13

3. Total time spent in READY state

These numbers are a bit non-deterministic. However, there is an expected range for each

number, and we will check whether your numbers are in the given range.

To understand the source of non-deterministic behavior, see the following example. Suppose

there are two CPUs (CPU1 and CPU2) in the simulated OS, and there are two processes

(P1 and P2) to be scheduled. At time 5, process P1 finishes and process P2 arrives. Since in

real world, time is continuous and thus there is no such thing called the “same” time, there

becomes 2 possibilities:

1. P2 arrives before P1 is ’finishing’, so the scheduler schedules P2 to CPU2, and then

schedules idle() to CPU1. There are 2 context switches.

2. P2 arrives after P1 has finished, so if the scheduler schedules P2 to CPU1, then only

1 context switch.

14

3.4 Submit your assignment

Follow the procedure in assignment 1.

Warning: DO NOT change the file names or otherwise you will get 0 marks

4 Grading

1. The TA will fetch and grade your latest version in your repo as of April 25, 2018,

11:00AM. Remember to commit and push before the deadline!

2. 10 test cases in total as listed in Table 1.

3. Passing one test case will earn you 10 marks.

4. If you need help for using pthreads, you can refer to https://computing.llnl.gov/

tutorials/pthreads/ and Google.

5 Change Log

1.0 this document

15

6 Questions

If you have doubts about the assignment, you are encouraged to ask questions on Piazza

using the corresponding tag. Please focus on knowledge. Unhealthy questions/comments

that focus on scores and grades are not encouraged.

If you find any (possible) bugs, send private questions on Piazza to us instead

— otherwise that may cause unnecessary panic among the class if that is not a real bug.

7 Academic Honesty

We follow the University guide on academic honesty against any plagiarism.

8 General Notes

This specification and our grading platform are both based our given course VM. You

should compile, debug and run the assignment program on that VM. So, if you insist

to develop on another platform other than our VM and got any question, test it on

our VM before you ask.

The TA reserves the right to adjust your scores for any request that requires their extra

manual effort.

Unless specified, you should work and fill your code in designated areas. There are

cases that the modification outside the designated area leads to misbehavior of the auto

grader. Proceed with caution and look back the changes if your output is different from

what is shown in the grader.

While we have already tried our best to prepare this assignment, we reserve all the

rights to update the specification and the grading scheme. If there are any mistakes/bugs

which are on ours, the TA will step in and do manual grading to ensure

you get what you deserve. Please respect each other. Any irresponsible, unfair, biased

sentiment would regard as a disciplinary case.

16

If this is a programming assignment, only C is allowed, not even C++. If this is a

scripting assignment, only bash shell script is allowed, not even Python. Furthermore,

for C programming assignments, use the “exit” function parsimoniously because it

might influence the grader as well. Therefore, use “return” instead of “exit” whenever

possible.

Although this is not an algorithm class, you still shouldn’t implement your assignment

with very poor complexity. While the TAs will try their best to run your program

as long as they could, they reserve the right to terminate a test case and regard that

as a failed test case when a program takes unreasonably long time to finish (try to

compare your running time with the TA’s demo if it is given), or until when the TAs

can’t run any longer due to the deadline the TA needs to submit your final scores to

the department.

When grading, the TAs will execute the grader program to run the whole test suite

(which consists of all test cases). The TAs won’t grade each individual test case

separately.

(Frequently Asked) [Output format] If the assignment package includes a demo,

then our grader defines test cases based on the given demo. In that case, your output

shall exactly follow that demo. For example, hypothetically, if our demo outputs a

message like:

command not found

with two spaces between “not” and “found”. Your output shall also match that in

order to pass the test. The good news is that, if our given demo has not implemented

something (e.g., missed certain error checking), you also don’t need to do so. No

test cases would be defined based on something that our demo has not

implemented.

(Frequently Asked) [Scope of error handling] The scope of error checking and

handling shall refer to both our given demo (if given) and our given test cases.

First, the corresponding output message shall exactly follow our demo. Second, you

17

are informed that our demo may have implemented more error checking that what our

grader will test. In that case, it is fine that you implement only the error checking that

is tested by our grader. So, one top tip is:

CHECK THE (SOURCE OF)

TEST CASES BEFORE YOU ASK

(Frequently Asked) [No hidden test case] We are not intended to run any secret/extra

test cases that deliberately break your assignment. That is, WYSIWYG — your

final score shall be generally indicated by what the grader reports when it runs on

the course VM. However, we do reserve the right to run some additional test cases to

avoid any mis-conduct (e.g., hard-coding the results), and/or invite you to explain the

source code to the teaching assistants and adjust the scores accordingly.

We welcome discussions among classmates. But don’t share your assignment with the

others in any means. For example, don’t put your source code in any public venue (e.g,

public repo, your homepage, Facebook). We handle plagiarism strictly. On submitting

this assignment, you are agreed that your code’s copyright belongs to the Chinese

University of Hong Kong. Unless with our written approval, you must not release

your source code and this specification now and forever. If you share your code with

anyone without our written consent, that would regard as a disciplinary case as long

as you are still a CUHK student (i.e., even after this course). If you share your code

with anyone without our written consent after your graduation, that would regard as

a breach of copyright and we reserve all the rights to take the corresponding legal

actions.

Google is your friend. We encourage you use Google for help to do the assignment.

However, if you happen to find any source codes related to this assignment, you still

cannot copy it but use your own way to implement it. You need to put down your list

of source code references as comments in the top of your source code.

18

(Frequently Asked) [Late Policy] TAs will only grade the latest version submitted

before the deadline, no late submission is allowed. It is your responsibility to make

sure you added, committed, and pushed the final version before the deadline. You are

required to check whether your final version is really in Github Classroom.

19