Programming Assignment #3 Due Date: November 3, 1999




Дата канвертавання26.04.2016
Памер47.56 Kb.

CMPS 352 Operating Systems Fall 1999

Programming Assignment #3

Due Date: November 3, 1999

The third programming assignment is to use concurrent processes and shared memory to simulate the scheduling of a computer system. The scheduling consists of a job scheduler and a CPU scheduler and a ready queue. The job scheduler and CPU scheduler are implemented as two processes, and the ready queue is shared by the two processes and its size is five (5). We assume that the running process stays in the ready queue also when it is being executed.




  1. The CPU scheduler schedules the processes in the ready queue using the First-Come-First-Serve scheduling algorithm. To simulate the execution time of the current running process, the CPU scheduler delays itself using the delay procedure that is provided in the sample program. For example, the execution time of the current process is 3, then the CPU scheduler should delay itself for 3 seconds by calling delay(3).

  2. The job scheduler schedules jobs from an input file. The input file is passed as a command-line parameter. The input contains three integers: the first number represents the submission time of the process, the second number the process ID, and the third number the execution time. The jobs are in non-decreasing order of submission time.

  3. The job scheduler should not try to insert a job into the ready queue until the job has been submitted. When the ready queue is full and a new job has been submitted, the job scheduler checks for an empty slot in the ready queue once each second.

  4. The CPU scheduler shall not stop running until there is no process in the ready queue and no more jobs in the input file. The list is the ready queue and each node represents a process control block. In next assignment, we will put the ready queue and its related data items into shared memory segments, which will be shared by a CPU scheduler and a job scheduler.

  5. For each job, the job scheduler prints its ID (process ID in the input), burst time, submission time, and the time at which the process is inserted in the ready queue.

  6. For each process scheduled for execution, the CPU scheduler prints the process ID, burst time, and execution time. When a process completes execution, the CPU scheduler prints the process ID, and the time at which the process completed its execution.

  7. You may find that the two processes need a common time reference. One possible implementation is to declare an integer that is shared by the two processes. The CPU scheduler initializes it to –1 and waits there until the job scheduler is started and then it changes the time from –1 to 0. The CPU scheduler increases the time by 1 when a real second passes by. There are two places in the CPU scheduler for updating the time. One is when the CPU scheduler waits on an empty ready queue. It checks the ready queue for processes once a second (delay(1)). Thus, It may increase the time after each delay. The other is when a process is being executed. For example, if the execution time of the process is 3 seconds, then you may want to delay three times with 1 second each. After each delay, the time is increased by one. The JOB scheduler can check against this time reference to determine whether a process should be appended in the ready queue or not.

Name your source files as “asgn3_userID_cpu.cpp” and “asgn3_userID_job.cpp” for the cpu scheduler and job scheduler, respectively. Replace userID with your real userID of your CS account. Do not use capital letters in the file name. Make sure your program is named as specified.


Your program should print a header and footer as illustrated below in both processes.

Header


============================================

CMPS352 Assignment 4 – Yaodong Bi

--------------------------------------------

Footer


=============== Yaodong Bi =================

To submit your assignment, email me (bi@cs.uofs.edu) and ATTACH your source file to the email. The subject of your email should appear like “CMPS352 Assignment 3 – Your first name then last name”. For example, if I submitted my program, the subject would appear as “CMPS352 Assignment 3 – Yaodong Bi”.

--------------------------------------------------------------------------

The Shared declaration

The Shared declaration is to define a shared memory segment.

The shared memory segment is an array of N (the first parameter) elements

of the type specified in the brackets. The key of the shared memory

segment is specified as the second parameter. The variable is a pointer

to the first element of the array. For example:

Shared bufPtr(10, 800)

An array of 10 nodes of type Node will be defined as a shared memory

segment. the key is 800. The bufPtr is a pointer pointing to the first

node of the array.
The signal Function

The operating system communicates with processes with signals. For

example, when ctrl+C is pressed on the keyboard, the operating system sends

a SIGINT signal to the running process on that xterm. Another example is

that, when a timer interrupt (which was set up by the running process) is

received, the OS sends a SIGALRM signal to the process. Signals can be

considered as interrupts/traps to the running process.
A process can specify how to handle a signal by specify a signal

handler for it. Thus when the signal occurs, the process will be interrupted

and the handler will be executed. When the handler (a function) returns,

the process will continue from where it was left, just like an interrupt.

The signal function is used to specify a handler for a signal. For example,

in this program, when a SIGLARM occurs, function wakeup (which does nothing)

is specified as the handler: signal(SIGLARM, wakeup); when a ctrl+C (SIGINT)

is received, function cleanup is the handler: signal(SIGINT, cleanup).


If a handler is not specified, the process will be terminated by the

operating system as default.


The exit function

The exit(int) function will terminates the execution of the calling

process. This function is used in the cleanup handler. So when this handler

is called (ctrl+C is pressed), the Consumer will terminated.


The pause function

The pause() function will halt the execution of the calling process.

This process will not be executed until a signal is received.
The alarm(seconds) function

The alarm(seconds) will set a timer for "seconds". When the timer

runs out, a SIGALRM signal will be sent to the process who called the

alarm function.


The delay(seconds) function

This function is designed with alarm, pause, and signal functions.

The function calls the alarm function to set up a timer for "seconds" and

then use the pause function to halt. When a SIGALRM occurs, wakeup will

be called which is specified as the handler for SIGALRM. When the wakeup

function returns, the process will continue from the pause function in

the delay function. Since there is not statement after "pause", the

delay function will return back to the caller.

*=======================================================================*/
/*=========================== prod-99f.cpp ============================*

Program Name: prod-99f.cpp

Class: Operating Systems, Fall 1999

Author: Yaodong Bi

Date: 10/19/1999
Enviornment: FreeBSD (Unix) GNU C++ compiler

Compilation: g++ -o prod prod-99f.cpp

Input: Integer and character tuples from keyboard

Output: No output

Description: This program should be run after the consumer has been

started.


This program (producer) reads from an input file, which

is passed as a commnd parameter and sends the input to

the shared memory.

*=======================================================================*/

#include

#include "Shared.H"

#include

#include


struct NODE

{

int value;



char c;

struct NODE *next;

};

typedef struct NODE Node;


struct HEADER

{

Node *head;



Node *tail;

};

typedef struct HEADER Header;


/* declare function/procedure prototypes */

int input(int*, char*);

void append(Header*, Node*);

Node* remove(Header*);

void delay(unsigned);

void wakeup(int);

void cleanup(int);
const int bufSize=5;
/*=======================================================================*

* Main Program *

*=======================================================================*/

main(int argc, char *argv[]) {

FILE *fileIn; /* file pointer to the input file */

Node *nodePtr;

int value;

char c;
Shared freeBuf(bufSize, 800); /* declare bufSize # of nodes */

Shared

freeHeader(1, 801); /* header for free node list */

Shared

dataHeader(1, 802); /* header for the ready queue */


signal(SIGINT, cleanup);
if (argc != 2) {

printf("\nUsage: %s inile\n", *argv);

exit(1);

}
if ((fileIn = fopen(argv[1], "r")) == NULL) {

printf("Input file %s error!\n", argv[1]);

exit(1);


}
while (fscanf(fileIn, "%d %c", &value, &c) != EOF) {

while ((nodePtr = remove(freeHeader)) == NULL) delay(1);

nodePtr->value = value;

nodePtr->c = c;

nodePtr->next = NULL;
delay(value); /* delay for value */

append(dataHeader, nodePtr);

}
}
/*=======================================================================*

* append Function *

*=======================================================================*/

void append(Header *headerPtr, Node *newPtr)

{

if (headerPtr->head == NULL) {



headerPtr->head = headerPtr->tail = newPtr;

}

else {



headerPtr->tail->next = newPtr;

headerPtr->tail = newPtr;

}

}
/*=======================================================================*



* Delete Function *

* Delete the first node in the list *

*=======================================================================*/

Node* remove(Header* headerPtr)

{

Node *tmpPtr;



if (headerPtr->head == NULL) {

return NULL;

}

if (headerPtr->head == headerPtr->tail) {



tmpPtr = headerPtr->head;

headerPtr->head = headerPtr->tail = NULL;

}

else {


tmpPtr = headerPtr->head;

headerPtr->head = headerPtr->head->next;

}

return tmpPtr;



}
// This function will delay the calling process for

// sec seconds. If sec is zero, it returns immediately.

void delay(unsigned sec)

{

if (sec > 0) {



signal(SIGALRM, wakeup);

alarm(sec); // set a timer for sec seconds

pause(); // pause the calling process.

}

}


// Signal handler for SIGALRM (timer interrupt) sginal.

void wakeup(int)

{

}
// Signal handler for SIGINT (ctrl+c) signal.



void cleanup(int)

{

Shared bufPtr(bufSize, 800);



Shared
freeHeader(1,801);

Shared

dataHeader(1,802);


// Call the remove function to remove the shared

// memory segment from the system.

bufPtr.remove();

freeHeader.remove();

dataHeader.remove();
exit(1);

}

/*=========================== cons-99f.cpp ============================*



Program Name: cons-99f.cpp

Class: Operating Systems, Fall 1999

Author: Yaodong Bi

Date: 10/19/1999


Enviornment: FreeBSD (Unix) GNU C compiler

Compilation: g++ -o cons cons-99f.cpp

Input: No input

Output: Display the data in the shared memory

Description: This program (consumer) should already be executed

before the producer.

This consumer read from the shared memory data that is

sent by the producer.

*=======================================================================*/

#include

#include "Shared.H"

#include

#include
struct NODE

{

int value;



char c;

struct NODE *next;

};

typedef struct NODE Node;


struct HEADER

{

Node *head;



Node *tail;

};

typedef struct HEADER Header;


/* declare function/procedure prototypes */

void append(Header*, Node*);

Node* remove(Header*);

void delay(unsigned);

void wakeup(int);

void cleanup(int);

void print(Header*);
const int bufSize=5;
/*=======================================================================*

* Main Program *

*=======================================================================*/

main()


{

Node *nodePtr;


Shared freeBuf(bufSize, 800); /* declare bufSize # of nodes */

Shared

freeHeader(1, 801); /* header for free node list */

Shared

dataHeader(1, 802); /* header for the ready queue */
signal(SIGINT, cleanup);
freeHeader->head = freeHeader->tail = NULL;

dataHeader->head = dataHeader->tail = NULL;


/* link the five nodes in shared memory into the free node list */

nodePtr = freeBuf;

for (int i=0; i<5; i++) {

append(freeHeader, nodePtr);

nodePtr++; /* move nodePtr to next node */

}

while ((nodePtr = remove(dataHeader)) == NULL) delay(1);



while (nodePtr->value != 0) {

printf("Value = %d, char = %c\n", nodePtr->value, nodePtr->c);

append(freeHeader, nodePtr);
while ((nodePtr = remove(dataHeader)) == NULL) delay(1);

}
cleanup(1);

}
/*=======================================================================*

* append Function *

*=======================================================================*/

void append(Header *headerPtr, Node *newPtr)

{

if (headerPtr->head == NULL) {



headerPtr->head = headerPtr->tail = newPtr;

}

else {



headerPtr->tail->next = newPtr;

headerPtr->tail = newPtr;

}

}
/*=======================================================================*



* Delete Function *

* Delete the first node in the list *

*=======================================================================*/

Node* remove(Header* headerPtr)

{

Node *tmpPtr;



if (headerPtr->head == NULL) {

return NULL;

}

if (headerPtr->head == headerPtr->tail) {



tmpPtr = headerPtr->head;

headerPtr->head = headerPtr->tail = NULL;

}

else {


tmpPtr = headerPtr->head;

headerPtr->head = headerPtr->head->next;

}

return tmpPtr;



}
// This function will delay the calling process for

// sec seconds. If sec is zero, it returns immediately.

void delay(unsigned sec)

{

if (sec > 0) {



signal(SIGALRM, wakeup);

alarm(sec); // set a timer for sec seconds

pause(); // pause the calling process.

}

}


// Signal handler for SIGALRM (timer interrupt) sginal.

void wakeup(int)

{

}
// Signal handler for SIGINT (ctrl+c) signal.



void cleanup(int)

{

// Declare the two shared memory segments.



Shared bufPtr(bufSize, 800);

Shared

freeHeader(1,801);

Shared

dataHeader(1,802);
// Call the remove function to remove the shared

// memory segment from the system.

bufPtr.remove();

freeHeader.remove();



dataHeader.remove();
exit(1);

}


База данных защищена авторским правом ©shkola.of.by 2016
звярнуцца да адміністрацыі

    Галоўная старонка