Assignment Help| In this project you will be simulating some of the work performed by an operating system
In this project you will be simulating some of the work performed by an operating system (albeit at a super high level). Specifically you will track the simulated processes that currently need to run and then schedule them to run on the CPU according to a given set of rules.
Introduction:
In “process.h” you should complete the struct process. Each process has the following data:
• An identifier (i.e., processName)
• The data that belongs to that process (i.e., a processData struct)
• A priority of either FOREGROUND or BACKGROUND
• You can add other data that will help in simulating the schedule.
· E.g knowing on which step number the process was added to the queue may be useful.
In “multilevelQueueScheduler.h” you should complete the struct schedule. Each schedule should have the following data:
• A queue of FOREGROUND processes
• A queue of BACKGROUND processes
• You can add other data that will help in simulating the schedule.
· E.g. knowing the number of time steps since the start of the simulation may be useful
Code: createSchedule (1 point)
Mallocs and returns a new schedule. Be sure to also create queues for your schedule and initialize any other data in your schedule struct.
Code: isScheduleUnfinished (1 point)
Returns true if given schedule has any processes in either of its queues.
Code: addNewProcessToSchedule (4 points)
You are passed a process identifier and a priority You should create a process containing that data as well as the processData associated with it (call “initializeProcessData” to get this data). Once you have the process created, you should add it to the appropriate queue in the schedule.
Code: runNextProcessInSchedule (10 points)
This function calls “runProcess” on the next process in your schedule. See below for a description of the rules which you use to decide which process is next in line to be run. The numSteps variable you pass “runProcess” should contain the minimum of the following two numbers:
• the number of steps before a BACKGROUND is promoted
• if this is a FOREGROUND process, the number of steps until this process is moved to the back of the queue according to the round-robin schedule
The “driver.c” code repeatedly calls this function until there are no processes left in the schedule. There are important helper methods in “processSimulator.c” so be sure to read through them. Below are the rules for which process to run:
(1) If there exists a FOREGROUND process in the schedule then no BACKGROUND process is run.
(2) Rules for running a FOREGROUND process:
(a) The queue follows a round-robin schedule scheme. In particular, a FOREGROUND process can run for at most 5 time steps. After it has been run for a total of 5 time steps you should move it to the back of the FOREGROUND queue.
(b) If this process is complete, remove it from the queue and free the process as well as its process data.
(3) Rules for running BACKGROUND processes:
(a) The queue follows a FCFS (first-come, first-serve) schedule scheme. Processes are completed in the order they were added to the queue. In particular, the process at the front of the BACKGROUND queue remains there until it either finishes or is promoted.
(b) If this process is complete, remove it from the queue and free the process as well as its process data.
(4) Every process that has remained in the BACKGROUND queue for 50 time steps is promoted to being a FOREGROUND process (i.e, move it to the rear of the FOREGROUND queue).
(5) The simulated process will return a string containing the name of another process or a NULL. Either way you do not need to do anything with the value except return it.
Code: freeSchedule (1 point)
Free all of the memory associated with the given schedule .
Analysis: Priority Queue (3 points)
Suppose we combined the FOREGROUND and BACKGROUND queues from part one into a single priority queue.
• Would the asymptotic runtime of scheduleProcess be increased, decreased, or say the same?
• Specifically, what is the new asymptotic runtime of scheduleProcess?
• Justify your reasoning for this runtime in one to two sentences. The answer depends on how you setup your priority queue so this justification is important.
Deliverables:
Your solution to the code portion of the project should be submitted as “multilevelQueueScheduler.c”, “multilevelQueueScheduler.h”, and “process.h”. The analysis portion should be submitted as separate .pdf file.
To receive full credit, your code must compile and execute. You should use valgrind to ensure that you do not have any memory leaks.
Getting started: The provided code is deliberately obtuse (especially “processSimulator.c”). You should focus less on how the my functions specifically work and more on what they do and where to call them in your functions (hints to this were given in the function comment headers so be sure to read them). When in doubt try running your code! Don’t be afraid to add print statements to help you better understand what data is being stored in a struct or passed by a function.
MultilevelQueueScheduler.h
#ifndef _multilevelQueueScheduler_h
#define _multilevelQueueScheduler_h
#include <stdlib.h>
#include <stdbool.h>
#include <limits.h>
#include "process.h"
#include "queue.h"
#include "processSimulator.h"
/* struct schedule (only accessed in student written code)
*
* Data related to the order the processes should be scheduled
* foreQueue and backQueue are the FOREGROUND and BACKGROUND queues respectively.
*
* Hint: It may also help to track the number of time steps that have been processed so far.
*/
typedef struct schedule
{
Queue *foreQueue;
Queue *backQueue;
//TODO: Put the data for your schedule program here!
} schedule;
schedule* createSchedule( );
bool isScheduleUnfinished( schedule *ps );
void addNewProcessToSchedule( schedule *ps, char *processName, priority p );
char* runNextProcessInSchedule( schedule *ps );
void freeSchedule( schedule *ps );
#endif
Process.H
#ifndef _process_h
#define _process_h
typedef enum priority { FOREGROUND, BACKGROUND } priority;
/* DO NOT directly access any data inside of a processData struct */
typedef struct processData{ int heap[ 30 ]; char PN21[ 21];char TLN [4 ];} processData ;
/* struct process (only accessed in student written code)
*
* The data associated with a specific process.
* At minimum you need to track the process name,
* and the processData struct returned by initializeProcessData,
*
* Hint: It may help to store how many time steps happened before
* a process was added to the schedule.
*
* You may also want to track the number of steps remaining until your FOREGROUND process is moved to the back of the queue.
*/
typedef struct process
{
//TODO: Put the data for your process here!
} process;
#endif
MultilevelQueueScheduler.c
#include <stdlib.h>
#include "multilevelQueueScheduler.h"
int min( int x, int y );
static const int STEPS_TO_PROMOTION = 50;
static const int FOREGROUND_QUEUE_STEPS = 5;
/* createSchedule
* input: none
* output: a schedule
*
* Creates and return a schedule struct.
*/
schedule* createSchedule( ) {
/* TODO: initialize data in schedule */
return NULL; /* TODO: Replace with your return value */
}
/* isScheduleUnfinished
* input: a schedule
* output: bool (true or false)
*
* Check if there are any processes still in the queues.
* Return TRUE if there is. Otherwise false.
*/
bool isScheduleUnfinished( schedule *ps ) {
/* TODO: check if there are any process still in a queue. Return TRUE if there is. */
return false; /* TODO: Replace with your return value */
}
/* addNewProcessToSchedule
* input: a schedule, a string, a priority
* output: void
*
* Create new process with the provided name and priority.
* Add that process to the appropriate queue
*/
void addNewProcessToSchedule( schedule *ps, char *processName, priority p ) {
/* TODO: complete this function.
The function "initializeProcessData" in processSimulator.c will be useful in completing this. */
free( processName ); /* TODO: This is to prevent a memory leak but you should remove it once you create a process to put processName into */
}
/* runNextProcessInSchedule
* input: a schedule
* output: a string
*
* Use the schedule to determine the next process to run and for how many time steps.
* Call "runProcess" to attempt to run the process. You do not need to print anything.
* You should return the string received from "runProcess". You do not need to use/modify this string in any way.*/
char* runNextProcessInSchedule( schedule *ps ) {
/* TODO: complete this function.
The function "runProcess", "promoteProcess", "loadProcessData", and "freeProcessData"
in processSimulator.c will be useful in completing this.
You may want to write a helper function to handle promotion */
char *ret = NULL;
//int numSteps = 0;
/* TODO: Delete the following printf once you get the infinite loop fixed */
printf("IMPORTANT NOTE: There will be an intinite loop in runNextProcessInSchedule if you get isScheduleUnfinished and addNewProcessToSchedule working correctlyn");
/* TODO: Uncomment the code below to dequeue elements from the two Queues and break your code out of the infinite loop
if( !isEmpty(ps->foreQueue) )
dequeue(ps->foreQueue);
else if( !isEmpty(ps->backQueue) )
dequeue(ps->backQueue);
*/
/* your call to runProcess will look something like this: */
// bool b = runProcess( /* name of process */, &ret, &numSteps );
return ret; /* This will be the char* that runProcess stores in ret when you call it. */
}
/* freeSchedule
* input: a schedule
* output: none
*
* Free all of the memory associated with the schedule.
*/
void freeSchedule( schedule *ps ) {
/* TODO: free any data associated with the schedule as well as the schedule itself.
the function "freeQueue" in queue.c will be useful in completing this. */
}
int min( int x, int y ){
if( x<y )
return x;
return y;
}
Driver.c
#include <stdlib.h>
#include <stdio.h>
#include <stdbool.h>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include "queue.h"
#include "multilevelQueueScheduler.h"
#include "processSimulator.h"
void testFile( const char dataFile[], char *(*f)( char *));
int getRuntime(char* processName);
priority getPriority(char* processName);
int main( int argc, char *argv[] )
{
int i = 0;
char *testData[] = {"F|NEW|00|12|10|04|00",
"B|LNG|00|10|07|03|00",
"F|SMP|00|30|08|31|00",
"F|RPD|00|09|03|32|00",
"F|VID|00|40|99|01|00"};
schedule *ps = createSchedule();
char *name;
//Call addNewProcessToSchedule for all of the starting processes
for( i=0; i<5; i++){
char *temp = (char *)malloc(strlen(testData[i])+1);
strcpy( temp, testData[i] );
addNewProcessToSchedule( ps, temp, getPriority(temp) );
}
printf( "n" );
//Simulate time steps until the schedule is finished (i.e. all work finished for all processes)
while( isScheduleUnfinished( ps ) ){
name = runNextProcessInSchedule( ps );
if( name!= NULL )
addNewProcessToSchedule( ps, name, getPriority(name) );
printf( "n" );
}
freeSchedule( ps );
return 0;
}
int getRuntime(char* processName){
char runtimeString[3];
int runtime;
int p = abs((int)getPriority(processName)-1);
//Read runtime from the 4th |-separated value in the string
sscanf(processName, "%*[^|]|%*[^|]|%*[^|]|%[^|]", runtimeString);
sscanf(runtimeString, "%d", &runtime);
return max(runtime/powInt(2,p),1);
}
priority getPriority(char* processName){
char priorityString[2];
priority p;
//Read runtime from the 1st |-separated value in the string
sscanf(processName, "%1[^|]", priorityString);
if( !strcmp(priorityString, "F") )
p = FOREGROUND;
else if( !strcmp(priorityString, "B") )
p = BACKGROUND;
else{
fprintf(stderr, "invalid priorityn");
exit(-1);
}
return p;
}
processSimulator.h
#ifndef _processSimulator_h
#define _processSimulator_h
#include <stdlib.h>
#include <stdbool.h>
#include "process.h"
processData* initializeProcessData( char *processName );
bool runProcess( char *pName, char **ppSystemCall, int *pNumSteps );
void freeProcessData( );
void promoteProcess( char *pName, processData *pData );
void loadProcessData( processData *pData );
int max( int a, int b );
int powInt( int a, int b );
#endif
processSimulator.c
#include <stdlib.h>
#include <stdbool.h>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include "processSimulator.h"
char* runProcessForOneTimeStep( char *pName );
bool authenticationRAM( char *pName );
bool authentication( char *pName, processData *pData );
void startProcess( char *pName, processData *pData );
static int time = 1;
static int nameNum = 0;
static processData *RAM = NULL;
/* initializeProcessData
* input: the process name
* output: initialized data for the process
*
* Initialize the data for a process.
* Call this when a process is first added to your queue
*/
processData* initializeProcessData( char *processName ){
processData* pData = (processData*)malloc(sizeof(processData));
char temp[21];
char intStr[3];
char *priorityName;
int i;
if( pData==NULL ){
fprintf(stderr, "initializeProcessData: Unable to allocate data.");
exit(-1);
}
for(i=0; i<21; i++)
pData->PN21[i] = 0;
strncpy( pData->PN21, processName, 20 );
//printf("%sn",processName);
sscanf( processName, "%*[^|]|%20s", temp );
sscanf( temp, "%3[^|]|%20s", pData->TLN, temp );
for( i=0; i<=4; i++ ){
//printf("%sn",temp);
sscanf( temp, "%2[^|]|%20s", intStr, temp );
sscanf( intStr, "%d", &pData->heap[i] );
}
while( i<=26 ){
pData->heap[i]=0;
i++;
}
pData->heap[6] = pData->heap[2];
pData->heap[10]=25;
pData->heap[7] = processName[0]=='B';
pData->heap[8]=pData->heap[4];
pData->heap[1] = max(pData->heap[1]/powInt(2,abs(pData->heap[7]-1)),1);
pData->heap[10]=pData->heap[10]<<1;
pData->heap[11]=time;
if( pData->heap[7] ){
priorityName = "BACKGROUND";
}
else{
priorityName = "FOREGROUND";
}
printf( "Process data created: %s-%d (%s for %d steps)n", pData->TLN, pData->heap[0], priorityName, pData->heap[1] );
return pData;
}
/* runProcess
* input: the process name and a pointer to an int that contains the number of steps to run for
* output: a bool which is true if the process finished and false if it is still incomplete
*
* return by reference:
* 1) stores at pNumSteps the number of steps run prior to the process finishing or a system call
* 2) stores at ppSystemCall a string which is the name of a process which is started by this one OR NULL if no process is started
*
* Attempts to run the process currently loaded in RAM for k time steps.
* If this process makes a system call the execution it will set ppSystemCall to that process's name, otherwise it sets ppSystemCall to NULL.
* If the process completes or a system call occurs runProcess suspends execution of this process and it writes the number of steps completed at *pNumSteps.
*/
bool runProcess( char *pName, char **ppSystemCall, int *pNumSteps ){
int i = 0;
*ppSystemCall = NULL;
if( !authenticationRAM( pName ) ){
exit(-1);
}
printf( "Attempting to run process: %s-%d for %d stepsn", RAM->TLN, RAM->heap[0], *pNumSteps );
while( i<*pNumSteps && *ppSystemCall == NULL && RAM->heap[5]<RAM->heap[1] ){
*ppSystemCall = runProcessForOneTimeStep( pName );
i++;
}
*pNumSteps = i;
if( RAM->heap[5]>=RAM->heap[1] && i==0 ){
printf( "ERROR - Attempting to run process that has already completed: %s-%dn", RAM->TLN, RAM->heap[0] );
exit(-1);
}
else if( RAM->heap[5]==RAM->heap[1] ){
printf( "Process completed after %d steps: %s-%dn", i, RAM->TLN, RAM->heap[0] );
return true;
}
else if( *ppSystemCall != NULL )
printf( "Execution interrupted after %d steps: %s-%dn", i, RAM->TLN, RAM->heap[0] );
return false;
}
/* loadProcessData
* input: a processData to be loaded into RAM
* output: a string
*
* Prints out message saying which data was evicted and which was loaded. If the given data is already loaded nothing is printed.
* In the real world the RAM can contain data from multiple processes but we're keeping it simple :)
*/
void loadProcessData( processData *pData ){
if( pData != RAM ){
if( RAM != NULL )
printf( "Process data evicted: %s-%d (run for %d/%d steps so far)n", RAM->TLN, RAM->heap[0], RAM->heap[5], RAM->heap[1] );
RAM = pData;
printf( "Process data loaded: %s-%d (run for %d/%d steps so far)n", RAM->TLN, RAM->heap[0], RAM->heap[5], RAM->heap[1] );
}
}
/* promoteProcess
* input: the process name and the process data
* output: a string
*
* Prints out message indicating a BACKGROUND process is being promoted to FOREGROUND
*/
void promoteProcess( char *pName, processData *pData ){
if( authentication( pName, pData ) ){
if( pData->heap[7] ) {
pData->heap[7] = 0;
if( !(time-pData->heap[11]-pData->heap[10]) )
printf( "Process promoted: %s-%d (run for %d/%d steps so far)n", pData->TLN, pData->heap[0], pData->heap[5], pData->heap[1] );
else if( time-pData->heap[11]-pData->heap[10]<0 )
printf( "ERROR - Process promoted %d step(s) too soon: %s-%d (run for %d/%d steps so far)n", -1*(time-pData->heap[11]-pData->heap[10]), pData->TLN, pData->heap[0], pData->heap[5], pData->heap[1] );
else
printf( "ERROR - Process promoted %d step(s) too late: %s-%d (run for %d/%d steps so far)n", time-pData->heap[11]-pData->heap[10], pData->TLN, pData->heap[0], pData->heap[5], pData->heap[1] );
}
else{
printf( "ERROR - Attempting to promote foreground process: %s-%d (run for %d/%d steps so far)n", pData->TLN, pData->heap[0], pData->heap[5], pData->heap[1] );
}
}
}
/* freeProcessData
* input: void
* output: void
*
* Frees the processData currently loaded in RAM. Call this after a process has run to completion.
* Reports errors if it was run the incorrect number of steps.
*/
void freeProcessData( ){
printf( "Process data deleted: %s-%d (run for %d/%d steps)n", RAM->TLN, RAM->heap[0], RAM->heap[5], RAM->heap[1] );
if( RAM->heap[1]>RAM->heap[5] ){
printf( "ERROR - Process deleted with %d steps left to do: %s-%dn", RAM->heap[1]-RAM->heap[5], RAM->TLN, RAM->heap[0] );
}
if( RAM->heap[5]>RAM->heap[1] ){
printf( "ERROR - Process run for %d steps more than was required: %s-%dn", RAM->heap[5]-RAM->heap[1], RAM->TLN, RAM->heap[0] );
}
if( RAM->heap[7] && (time-RAM->heap[11]-RAM->heap[10]>0) )
printf( "ERROR - Background process was not promoted: %s-%dn", RAM->TLN, RAM->heap[0] );
free(RAM);
RAM = NULL;
}
/************************ Code below this point is internal use only ************************/
/* runProcessForOneTimeStep
* input: the process name and the process data
* output: a string
* FOR INTERNAL USE ONLY
*
* Simulates the given process for one time step.
* If it makes a system call to another process it will return that process's name, otherwise it returns NULL.
*/
char* runProcessForOneTimeStep( char *pName ){
char *ret = NULL;
printf( "%4d - Running process: %s-%dn", time, RAM->TLN, RAM->heap[0] );
RAM->heap[5]++;
//printf( "heap[5]: %dn", pData->heap[5] );
RAM->heap[6]--;
if( RAM->heap[6]==0 && RAM->heap[3]>1 ){
ret = (char *)malloc(21);
startProcess(ret, RAM);
RAM->heap[6] = RAM->heap[2];
}
time++;
return ret;
}
/* startProcess
* FOR INTERNAL USE ONLY
*/
void startProcess( char *pName, processData *pData ){
char temp[7][4];
int i;
if( pData->heap[3]%2==1 && pData->PN21[0]=='F' )
strcpy(temp[0],"B");
else if( pData->heap[3]%2==1 && pData->PN21[0]=='B' )
strcpy(temp[0],"F");
else{
temp[0][0] = pData->PN21[0];
temp[0][1] = '';
}
strcpy( temp[1], pData->TLN );
nameNum++;
sprintf( temp[2], "%d", (nameNum)%100 );
sprintf( temp[3], "%d", pData->heap[1] );
sprintf( temp[4], "%d", pData->heap[2] );
sprintf( temp[5], "%d", max(pData->heap[3]/2,1) );
sprintf( temp[6], "%d", pData->heap[9] );
strcpy( pName, "" );
for( i=0; i<6; i++ ){
strcat( pName, temp[i] );
strcat( pName, "|" );
}
strcat( pName, temp[i] );
pData->heap[8]++;
pData->heap[9]+=pData->heap[1]/pData->heap[2];
}
/* authenticationRAM
* FOR INTERNAL USE ONLY
*/
bool authenticationRAM( char *pName ){
if( pName==NULL ){
fprintf(stderr, "ERROR - Authentication failed - pName is NULL.n");
return false;
}
else if( RAM == NULL ){
fprintf(stderr, "ERROR - Authentication failed - data was not loaded into RAM (be sure to call loadProcessData).n");
return false;
}
else if( RAM->PN21==NULL ){
fprintf(stderr, "ERROR - Authentication failed - data in RAM may have been corrupted.n");
return false;
}
else if( strcmp(pName, RAM->PN21) ){
fprintf(stderr, "ERROR - Authentication failed - incorrect data was loaded into RAM (be sure to call loadProcessData).n");
return false;
}
return true;
}
/* authentication
* FOR INTERNAL USE ONLY
*/
bool authentication( char *pName, processData *pData ){
if( pName==NULL ){
fprintf(stderr, "ERROR - Authentication failed - pName is NULL.n");
return false;
}
else if( pData == NULL ){
fprintf(stderr, "ERROR - Authentication failed - pData is NULL.n");
return false;
}
else if( pData->PN21==NULL ){
fprintf(stderr, "ERROR - Authentication failed - data in pData may have been corrupted.n");
return false;
}
else if( strcmp(pName, pData->PN21) ){
fprintf(stderr, "ERROR - Authentication failed - mismatch of data associated with pName and pData.n");
return false;
}
return true;
}
/* max
* FOR INTERNAL USE ONLY
*/
int max( int a, int b ){
if(a>b)
return a;
else
return b;
}
/* powInt
* FOR INTERNAL USE ONLY
*/
int powInt( int a, int b ){
int product = 1;
while( b>0 ){
product*=a;
b--;
}
return product;
}
queue.h
#ifndef _queue_h
#define _queue_h
#include <stdlib.h>
#include <stdio.h>
#include <stdbool.h>
#include "process.h"
typedef struct process* queueType;
typedef struct LLNode
{
queueType qt; //queueType contained in this node
struct LLNode *pNext; //pointer to the next node in the linked list
} LLNode;
typedef struct Queue
{
LLNode *qFront; //pointer to the first element of the queue
LLNode *qRear; //pointer to the last element of the queue
} Queue;
Queue *createQueue( );
void freeQueue( Queue *pq );
queueType getNext( Queue *pq );
queueType dequeue( Queue *pq );
void enqueue( Queue *pq, queueType qt );
bool isEmpty( Queue *pq );
#endif
queue.c file
#include "queue.h"
/* createQueue
* input: none
* output: a pointer to a queue (this is malloc-ed so must be freed eventually!)
*
* Creates a new empty queue and returns a pointer to it.
*/
Queue *createQueue( )
{
Queue *pq = (Queue *)malloc( sizeof(Queue) );
if( pq!=NULL )
{
pq->qFront = NULL;
pq->qRear = NULL;
}
return pq;
}
/* freeStack
* input: a pointer to a Queue
* output: none
*
* frees the given Queue pointer. Also, you should remember to free the elements in the linked list!
*/
void freeQueue( Queue *pq )
{
free(pq);
}
/* getNext
* input: a pointer to a Queue
* output: a pointer to process
*
* Returns the process stored at the front of the Queue. It does not remove the element from the queue.
*/
queueType getNext( Queue *pq )
{
if( isEmpty( pq ) )
{
/* no element to return */
return NULL;
}
return pq->qFront->qt;
}
/* dequeue
* input: a pointer to a Queue
* output: a pointer to process
*
* Dequeues and returns the process stored at the front of the Queue. It does not free the dequeue-ed element.
*/
queueType dequeue( Queue *pq )
{
LLNode *temp;
queueType qt;
if( isEmpty( pq ) )
{
/* no element to return */
return NULL;
}
temp = pq->qFront;
pq->qFront = pq->qFront->pNext;
if( pq->qFront==NULL ){
pq->qRear=NULL;
}
qt = temp->qt;
free(temp);
return qt;
}
/* enqueue
* input: a pointer to a Queue, a queueType
* output: none
*
* Inserts the process on the rear of the given Queue.
*/
void enqueue( Queue *pq, queueType qt )
{
LLNode *node = (LLNode*)malloc(sizeof(LLNode));
if(node==NULL){
fprintf( stderr, "enqueue: Failed to allocate memory");
exit(-1);
}
node->pNext=NULL;
node->qt = qt;
if( isEmpty(pq) ){
pq->qFront = node;
pq->qRear = node;
return;
}
pq->qRear->pNext = node;
pq->qRear = node;
}
/* isEmpty
* input: a pointer to a Queue
* output: a boolean
*
* returns TRUE if the Queue is empty and FALSE otherwise
*/
bool isEmpty( Queue *pq )
{
if( pq->qFront==NULL && pq->qRear==NULL )
{
return true;
}
else if( pq->qFront==NULL || pq->qRear==NULL )
{
fprintf( stderr, "isEmpty: Queue had inconsistent values for front and rear.n" );
exit(-1);
}
return false;
}