This assignment introduces the definition of classes, and their use in the implementation and use of a simple linked list. These will then be used to implement some simple scheduling policies.

PROBLEM DESCRIPTION

This assignment will simulate a job scheduler by defining a collection or processes and then choosing which will execute next. There are several possible policies that may be applied to choose what gets to use the CPU, so that problem will be factored out into a separate part of the program.

Here is a very rough sketch of the simulation:

while there are any programs wishing to run in the present or the future
    1) pick a program to run
    2) give it the CPU to run for some time
    3) decide what to do with this process
       (it may be finished now, or may continue to run later)

1) There are many different scheduling policies, but this assignment will simply run the processes in the order in which they appear -- which is very easy to do with a linked list.

2) No Operating System can accurately predict just how much time any process will need to use the CPU. It might have very little work to do, and finishes quickly. Or it may get stuck in an infinite loop and try to run indefinitely. To guard against the latter, one can just put a limit on one process, after which the CPU is taken away and passed to another.

3) If a process is done, it is removed from the system (and we will put a 'Q' at the end of its history). If it still wants to run some more, we will just put it back into the set of processes that wish to use the CPU.

SPECIFICATION DETAILS:

Most of the simulation details above will be handled by these objects and methods:

• Process::runAllows the specified process to run for a little while. One parameter gives an upper limit on the time allowed. One parameter represents the simulation clock, which increases to show the passage of time (depending on how much CPU time this processor uses). And a return parameter indicates what the process wishes to do after it runs -- run some more ('X') or finish ('Q').
• Scheduler::runSchedulerRepresents the overall simulation, as hinted at by the rough pseudocode above. Its parameter list includes a description of all the processes in the system and when they arrived. One parameter specifies the upper time limit for each call toProcess::run, to see the effect that has on overall behavior.

There are also several list-related functions defined to assist with this and later assignments. The contents of each list element would be good to know:

Each list includes a process ID (just a small integer in this project), a time index, and a process state (such as 'X' or '-'). This list will serve three very different purposes in this project:

• Process::logwill record the complete history of each process during the simulation, i.e. the data to be displayed by the code from Homework 1. A sensible simulation should record this information in chronological order.
• Scheduler::readySetwill record the collection of processes currently wishing to use the CPU. The only essential information here is the process ID, which is nothing more than a subscript to an array of Processes.
• Scheduler::futurewill record events that will occur in the simulation's future. For example, not all processes are ready to run at time 0; in later assignments, they will also not be ready to run until certain other operations complete. This list must be kept in chronological order.

HEADER FILES

Header files (.h) will now begin to declare classes and their methods, and source files (.cpp) will implement many of those methods.

Taking a closer look at the class declarations:

proclist.h
This file declares a single-linked list along with an iterator. The ProcList class implements some very simple accessor methods to assist with the simulation. Since this List will often only be used as a queue, the only peeks at the list are at the time values for the time-ordered list of future events. Looking at any other within the list would require use of a ProcIterator.

process.h
This describes a single process that wishes to use the computer system. Every process is assigned an identifier for easy reference -- for this project, this will be nothing more than its assigned subscript in an array. 
The process behavior is represented as a series of alternating usages of the CPU, which may be separated by other devices (in the next assignment). Later, the project will compare various scheduling policies on the same set of processes, so one set of variables will be assigned at process creation time and left unchanged, and some others will record how far it has executed. A log is included to record its complete history. Some simple functions are defined to maintain this log history, and then to provide that history to the displayHistory function.

scheduler.h
This declares the scheduler object, along with some very simple functions regarding the subset of processes that currently wish to use the CPU. These three functions have been isolated, because their behavior will differ for other scheduling policies later in the course. It is strongly recommended to make use of these methods, so that the runScheduler implementation will work equally well with all policies later.

Usually only the accessor methods for a class appear in a header file, but often I will put any very short function in there as well. A function that is implemented within a class definition in C++ becomes an in-line function, meaning that when the compiler encounters a function call, it simply expands the function code in place. This does yield code duplication in the executable file (so should not be done for large functions) -- but it avoids the need to call and return, which would dominate the execution time of a simple accessor method.

Conversely, there are several occasions this semester where a constructor method does NOT appear in the header file, because it is doing considerable work, such as filling arrays.

COMPONENT FILES

Here is a summary of all the files for this assignment:

 

The files to be submitted for this assignment are process.cpp, proclist.cpp, scheduler.cpp and histo.cpp. Include them all within a single dropbox submission.

EXTRA CREDIT OPTION

An important part of the simulation above is to record information for each process about its history. A simple straight-forward implementation may actually insert a few list elements that actually do not contain useful information.

If a process is not given enough allowance to use all the CPU time it desires, then it may have wait and resume later. It is very simple to just make that assumption and insert a list element with the '-' indicating that it will wait.

But on some occasions, no waiting actually occurs (such as if there is no other process in the system). The resulting job history would then have two consecutive elements with the same time index, indicating that the first has no actual duration.

Furthermore, removing these zero-time elements may lead to two consecutive elements describing the same state -- implying a state change when there is none (the second would add no information).

The extra credit assignment then is to remove these unnecessary list elements. A method has been declared (ProcList::condense) for this purpose. Complete it to remove and deallocated unwanted list nodes.

Be sure to place a notice in the ANGEL Message Box to the grader that you have attempted this feature.

The output should be something like

Time:  1000                                         1500
    1    DDDDDDDDDDDDDDDDDDD------XXXXNNNNNNNNNN-XXXXX
    2    -------------------DDDDDDDDDDDDDDDDDDXXXNNNNN

 

 

driver.cpp// A quick driver to test the History Display routine// It just fabricates a single job history to see what it does//#include <iostream>using namespace std;#include "scheduler.h"int main(){Scheduler sched;// make a process schedulerProcess tasks[] =// 3 processes{ Process(0), Process(1), Process(2) };int arrival[] = {0, 40, 80};// arrive at these timescout << "First Come First Served" << endl;sched.runScheduler( tasks, arrival, 3, 500000 );// FIFOdisplayHistory( tasks, 3, 0, 500 );cout << endl << "Quanta of 70" << endl;sched.runScheduler( tasks, arrival, 3, 70 );// RR generousdisplayHistory( tasks, 3, 0, 500 );cout << endl << "Quanta of 10" << endl;sched.runScheduler( tasks, arrival, 3, 10 );// RR stingydisplayHistory( tasks, 3, 0, 500 );}histo.h#include "process.h"// History Displayer// Produces an Ascii-graphic representation of the history for processes// within a simulation of job scheduling.Each history is recorded as a// series of time stamps, represented here as integer time values and// characters representing state.// Paramaters://historyinput Process arrayobjects containing linked lists//with the times and states//(see process.h)//sizeinput intnumber of processes (rows of output)//startinput intbeginning of time frame of interest//stopinput intend of time frame of interest// Pre-Conditions://each linked list concludes with an entry with state 'Q' for completion//'start' and 'stop' are both positive integers, with start < stop//NOTE:'start' or 'stop' may be outside the time ranges in the history// Results://A display of between 20 and 50 printable characters representing//the job history within the time range of interest, using the//characters stored within the given list.Events outside the actualrange//of the job history will be displayed with blanks.void displayHistory( Process history[], int size, int start, int stop );

Function/Method Call Tree for Homework 2Usually when designing a program with multiple functions, it is goodfor the function design to highlight how the functions interact witheach other. It helps in writing a function to know what resources areavailable for use.Since these details were not explicit in the assignmentspeci±cations, I am including them here, which may assist in ±guringout how Homework 2 is organized.Calling FunctionCalled FunctionsPurposedisplayHistoryProcess::getLogObtain data to examineProcList::begin, ProcList::endProcIterator::advanceTraverse the dataProcIterator::time,ProcIterator::stateAccess data for displayProcess::runaddLogRecord changes in process stateScheduler::runScheduler noneReadyIdentify existence of taskaddProcessplace task into ready setchooseProcessselect task from ready setProcList::emptyIdentify existence of unstarted taskProcList::leadTimeIdentify arrival time of next taskProcList::popFrontRemove from future to place intoready setProcList::insertRecord new event to happen infutureProcess::restart, Process::addLog helps to begin simulation (given)Process::runidentify how much time a processusesNOTE: The '::'s above will not appear in your program code. They areonly to identify the functions. To call a method within some otherobject, you will precede the function name with a variable and a .,such as "tasks[i].restart()"In the above functions,-- the iterator in displayHistory() are used on the log obtained fromgetLog.-- all other uses for the linked list used for process histories are

• 1496740531-header files cpp files.docx
• 1496740532-Method call tree.docx

ComputerScienceExpert

(11)

Status NEW Posted 06 Jun 2017 09:06 AM My Price 9.00

-----------

Attachments

file 1496740536-Solutions file 2.docx preview (51 words )

H-----------ell-----------o S-----------ir/-----------Mad-----------am ----------- Th-----------ank----------- yo-----------u f-----------or -----------you-----------r i-----------nte-----------res-----------t a-----------nd -----------buy-----------ing----------- my----------- po-----------ste-----------d s-----------olu-----------tio-----------n. -----------Ple-----------ase----------- pi-----------ng -----------me -----------on -----------cha-----------t I----------- am----------- on-----------lin-----------e o-----------r i-----------nbo-----------x m-----------e a----------- me-----------ssa-----------ge -----------I w-----------ill----------- be----------- qu-----------ick-----------ly -----------onl-----------ine----------- an-----------d g-----------ive----------- yo-----------u e-----------xac-----------t f-----------ile----------- an-----------d t-----------he -----------sam-----------e f-----------ile----------- is----------- al-----------so -----------sen-----------t t-----------o y-----------our----------- em-----------ail----------- th-----------at -----------is -----------reg-----------ist-----------ere-----------d o-----------n -----------THI-----------S W-----------EBS-----------ITE-----------. ----------- Th-----------ank----------- yo-----------u -----------

Not Rated(0)

• Buy Answer