Solved

# Analysis and implementation of scheduling algorithm

Posted on 2008-11-11
Medium Priority
2,243 Views
Purpose :  To bring together various ideas of OS we have learned so far.  Designing a small part of the operating system and dealing with the details of the implementation of the design.  We will also learn to deal with unanticipated problems and work in teams.

Problem Statement : Your team is in charge of implementing and studying the effects of six scheduling algorithms.  The algorithms to be studied are given below.

* First Come First Serve (FCFS)
* Shortest Job Remaining (SJR)
* Round-Robin (RR)
* Shortest Job First (SJF)
* Priority Scheduling (PS)
* Multi-level Feedback Queue Scheduling (MFQ)

In the system you are building, each process arrives one at a time.  Each process is characterized by three parameters : the CPU burst, I/O burst needed and the id of the process.  Assume that you have only one i/o burst and if a process needs an i/o operation, it occurs exactly half way through the CPU burst (for example, process 1 has as its parameters (CPU burst - 10 seconds, I/O burst - 5 seconds, id - p_1), then I/O burst occurs after the process has run for 5 seconds).

You should be able to read the information about processes from a file.  Note that FCFS and SJF are non-preemptive and SJR, RR, MFQ and PS are preemptive.  For the RR algorithm assume the quantum is 3 units. For the MFQ assume there are three Queues. The first queue will have a time quantum of 3, the second with a quantum of 6 and the third will be treated FCFS. Processes in the lower queues will be assigned the CPU only if higher queues are empty.

Keep all units in seconds. Break all ties based on the Bakery Algorithm (the process with the smaller process id number will get ahead). Assume you have infinite instances of I/O devices (i.e. no need to create an I/O queue to schedule I/O). There should be no need for user interaction.

Input should be:executable input_filename number_of_processes snapshot_time_interval (for example \$mysched file1.dat 10 10 - for the executable named mysched with input data in a file called file1.dat with 10 processes and snapshot taken every 10 units of time)

% Sample Input File
% P_ID     CPU_burst    I/O_burst     Priority
0           10              4             2
1            8              2             1
2           12              0             5
3            2              4             4
4            8              3             0
5            6              4             2
6            4              0             5
7           16              7             5
8           14              0             1
9            2             10            1
0
Question by:consolemaster
• 6
• 5

LVL 53

Expert Comment

ID: 22931829
This is your assignment, I gather.

What's your question for us ?
0

Author Comment

ID: 22931880
Sorry, here's what I needed

* You should report the following for each scheduling algorithm :
o Throughput.
o Average waiting time.
o CPU utilization.
o Turn around time.
o Sequence of processes in the CPU.
o Snapshot of the ready queue and I/O queue every 10 seconds.
o Comparison of the six algorithms.
o Your recommendation of which would be the best choice for the given input file.

0

Author Comment

ID: 22931893
It has to implemented in C
0

LVL 53

Expert Comment

ID: 22931897
That "you" refers to you, not us. Those are the questions that you were asked for your assignment.

What's your question for us ? You realize that we can't solve this assignment for you, do you ?
0

Author Comment

ID: 22931910
Here is something that may help.
output.txt
0

Author Comment

ID: 22931920
Yes, I can't solve it. This is the second assignment. I solved the first one which was programming a UNIX Shell using system calls.
0

LVL 53

Expert Comment

ID: 22931921
May help with what ?
0

LVL 53

Expert Comment

ID: 22931928
>> Yes, I can't solve it.

Apart from solving it for you, what is it that we can help you with ? What is your specific problem with this ?
0

Author Comment

ID: 22931985
The problem for me was:

Actually, my dificulty is with the MFQ implementation.
0

LVL 53

Accepted Solution

Infinity08 earned 1500 total points
ID: 22932026
Here's an overview of MFQ :

http://en.wikipedia.org/wiki/Multilevel_Feedback_Queue

And I'm sure your class notes contain further information.

What difficulty do you have ? You need to be a bit clearer when asking a question. We don't have a crystal ball to know what you're seeing and thinking. You need to describe your problem in as much detail as possible.
0

Expert Comment

ID: 22936469
May i asked who gave this assignment it sounds awfully familiar to one i gave to my current students weeks ago. Interestingly enough it was due today i hope you were not expecting someone to just code this for you when it is due about 2 hours from when you asked the question. If you have been needing help with your assignments you may want to attain help from your partner or professor in the future. You may find that they will be more helpful than websites especially ones that are meant to "help" with coding problems not write code for you...
0

LVL 53

Expert Comment

ID: 22937981
Interesting turn of events :)

Prof_Bala, on this site we're quite serious about assignments. We provide guidance, hints and answers to specific questions, but the assignment has to be solved by the asker himself.

http://www.experts-exchange.com/help.jsp#hi21
0

## Featured Post

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Stellar Exchange Toolkit: this 5 in 1 toolkit comes loaded with mega-software tool. Hereâ€™s an introduction to toolsâ€™ usage and advantages:
MSSQL DB-maintenance also needs implementation of multiple activities. However, unprecedented errors can hamper the database management. In that case, deploying Stellar SQL Database Toolkit ensures fast and accurate database and backup repair as welâ€¦