Simulate the scheduler component of an Operating System

faisalnet5 · #1 13-Feb-2008, 09:19

Hi everyone...i am actually new in the world of C. Now the thing is i got an assignment as my class project where i have to write the code to simulate the scheduler component of an Operating System by C. As a processing model my professor selected the example of line at the bank: which involves the use of a single queue but multiple tellers (Processoers).

Can anyone please help me or guide me. I am seeing dark around myself.

Regards

davekw7x · #2 13-Feb-2008, 10:06

Quote:

Originally Posted by faisalnet5

...new in the world of C...assignment...to write the code to simulate...

Obviously, you are not at the beginning of an introductory programming course. So, in order to, maybe, get some clues as to how anyone might be able to offer some suggestions, I have a few questions for you:

What is the subject of the class? (Queuing theory or what?) What department? (Computer Science? Engineering? What?)

What are the prerequisites for the class? (Mathematics? Computer Science? Programming? What?)

What is your programming background? (CS Major? Math Major? What?) Since you are new to C, could you tell us about which languages you have had before?

What references to you have from class? (Textbook(s)? Web Reference(s)? What?)

Regards,

Dave

faisalnet5 · #3 13-Feb-2008, 10:32

Hello Dave...Thanks for ur concern. Look the subject of the class is “Operating System”. And it is offered by the Computer Science Department. Yah the prequisite for this course was Programming and my background is Information Technology. I have done C, Java, a little bit Perl, PHP and Prolog. The text book for this course my Prof. is using “Operating System-3rd Edition by Gary Nutt”.

My problem is I know C but I didn't work much on the C-Structure. Specially the kind of project I have right now. In the project the Prof. Ask me to create a C program that simulates the Scheduler component of an Operating System. The scheduler will be based upon a real-life situation such as A line at the Bank: Which involves the use of a single queue but multiple tellers (Processors).

It will be great if I can see some samples about how to write Schedulers with various processes by C language. Then I guess I can go on...

Regards

#4 13-Feb-2008, 11:57

Quote:

Originally Posted by faisalnet5

Hi everyone...i am actually new in the world of C. Now the thing is i got an assignment as my class project where i have to write the code to simulate the scheduler component of an Operating System by C. As a processing model my professor selected the example of line at the bank: which involves the use of a single queue but multiple tellers (Processoers).

Can anyone please help me or guide me. I am seeing dark around myself.

Regards

Wow...this is a bit of a strange assignment from the perspective of the "processing model." Typically it is easier to think of a single processor "model" with multiple queues where various tasks are managed by their positions in the various queues. For example, some tasks may be blocked, others may be ready to run and others may be in transition between ready to run from being loaded or exiting.

Logically, if one thinks of the line of people waiting to be serviced as "tasks" and the tellers as being "processors," then "in real life" it wouldn't be a very efficient multi-processor operating system.

I suppose that those tasks in the queue are always ready to run and simply are waiting on a processor to service them. This is almost exactly backwards of "real" OS design. Where the "tellers" are tasks in various states of their execution of the work they've been given to do by their code and the "line" is really a "ready-to-run" task queue waiting for processor time. Even in the situation where there is a dual core processor, there may simply be "two lines."

Any way...interesting problem/challenge. I'd probably start by creating the data structures needed to represent the various elements in the system. If you follow the model of the bank line, then I'd name these structures based on their physical representation of their "place" in the model you've been given. For example: "Teller" "Customer" "Line" Where Teller perhaps displays the "Customer.Number" and the "Customer" then "exits." The "OS" then provides the Teller with a new Customer from the Line.

Maybe something like this:

CPP / C++ / C Code:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <errno.h>

typedef char BOOL;
#define TRUE    1
#define FALSE   0

typedef struct Customer
{
    unsigned int id;
    BOOL         wasServiced;
} CUSTOMER;

typedef struct Teller
{
    unsigned int id;
    BOOL         isServicingCustomer;
    CUSTOMER*    pCustomer;
} TELLER;

void showState( TELLER* pTellers, unsigned int nTellers, CUSTOMER* pCustomers, unsigned int nCustomers )
{
    unsigned int ui;
    for( ui = 0; ui < nTellers; ui++ )
    {
        printf( "Teller %d ", pTellers[ui].id );
        if( pTellers[ui].isServicingCustomer )
        {
            printf( " Servicing Customer %d.\n", pTellers[ui].pCustomer->id );
        }
        else
        {
            printf( " is available for the next Customer.\n" );
        }
    }
    for( ui = 0; ui < nCustomers; ui++ )
    {
        printf( "Customer %d ", pCustomers[ui].id );
        if( pCustomers[ui].wasServiced )
        {
            printf( " was serviced.\n" );
        }
        else
        {
            printf( " is awaiting service.\n" );
        }
    }
}

void doWork( TELLER* pTellers, unsigned int nTellers )
{
    unsigned int ui;
    for( ui = 0; ui < nTellers; ui++ )
    {
        if( pTellers[ui].isServicingCustomer )
        {
            printf( "Teller %d Serviced Customer %d\n", pTellers[ui].id, pTellers[ui].pCustomer->id );
            pTellers[ui].pCustomer->wasServiced = TRUE;
            pTellers[ui].isServicingCustomer = FALSE;
        }
    }
}

void schedule( TELLER* pTellers, unsigned int nTellers, CUSTOMER* pCustomers, unsigned int nCustomers )
{
    unsigned int ui, uj;
    for( ui = 0; ui < nCustomers; ui++ )
    {
        if( pCustomers[ui].wasServiced == TRUE )
        {
            continue;
        }
        for( uj = 0; uj < nTellers; uj++ )
        {
            if( pTellers[uj].isServicingCustomer == TRUE ) // next available teller
            {
                continue;
            }
            else
            {
                pTellers[uj].isServicingCustomer = TRUE;
                pTellers[uj].pCustomer = &pCustomers[ui];
                break;
            }
        }
    }
    doWork( pTellers, nTellers );
}

void reschedule( CUSTOMER* pCustomers, unsigned int nCustomers )
{
    unsigned int ui;
    for( ui = 0; ui < nCustomers; ui++ )
    {
        if( pCustomers[ui].wasServiced )
        {
            pCustomers[ui].wasServiced = FALSE;
        }
    }
}

char menu()
{
    printf( "R - Reschedule\n" );
    printf( "C - Continue Execution\n" );
    printf( "S - Show Current State\n" );
    printf( "Q - Quit\n" );
    printf( "\n" );

    return getchar();
}

int cleanup( TELLER* pTellers, CUSTOMER* pCustomers )
{
    int rc = 0;
    if( pTellers != NULL )
    {
        free( pTellers );
        pTellers = NULL;
    }
    else
    {
        rc = EINVAL;
    }
    if( pCustomers != NULL )
    {
        free( pCustomers );
        pCustomers = NULL;
    }
    else
    {
        rc = EINVAL;
    }
    return rc;
}

#define COUNT_TELLERS       10
#define COUNT_CUSTOMERS     100

int main()
{
    char        c;
    int         i;
    TELLER*     pTellers    = (TELLER*)calloc( sizeof( TELLER ), COUNT_TELLERS ); // create tellers
    CUSTOMER*   pCustomers  = (CUSTOMER*)calloc( sizeof( CUSTOMER ), COUNT_CUSTOMERS ); // create customers
    if( pTellers != NULL && pCustomers != NULL )
    {
        for( i = 0; i < COUNT_TELLERS; i++ )
        {
            pTellers[i].id = i + 1;
        }
        for( i = 0; i < COUNT_CUSTOMERS; i++ )
        {
            pCustomers[i].id = i + 1;
        }
        while( 1 )
        {
            c = menu();
            switch( c )
            {
            case 'R':
            case 'r':
                reschedule( pCustomers, COUNT_CUSTOMERS );
                break;
            case 'C':
            case 'c':
                schedule( pTellers, COUNT_TELLERS, pCustomers, COUNT_CUSTOMERS );
                break;
            case 'S':
            case 's':
                showState( pTellers, COUNT_TELLERS, pCustomers, COUNT_CUSTOMERS );
                break;
            case 'Q':
            case 'q':
                return cleanup( pTellers, pCustomers );
            default:
                break;
            }
        }
    }
    return cleanup( pTellers, pCustomers );
}

Output:

Code:

R - Reschedule
C - Continue Execution
S - Show Current State
Q - Quit

c
Teller 1 Serviced Customer 1
Teller 2 Serviced Customer 2
Teller 3 Serviced Customer 3
Teller 4 Serviced Customer 4
Teller 5 Serviced Customer 5
Teller 6 Serviced Customer 6
Teller 7 Serviced Customer 7
Teller 8 Serviced Customer 8
Teller 9 Serviced Customer 9
Teller 10 Serviced Customer 10
R - Reschedule
C - Continue Execution
S - Show Current State
Q - Quit

R - Reschedule
C - Continue Execution
S - Show Current State
Q - Quit

c
Teller 1 Serviced Customer 11
Teller 2 Serviced Customer 12
Teller 3 Serviced Customer 13
Teller 4 Serviced Customer 14
Teller 5 Serviced Customer 15
Teller 6 Serviced Customer 16
Teller 7 Serviced Customer 17
Teller 8 Serviced Customer 18
Teller 9 Serviced Customer 19
Teller 10 Serviced Customer 20
R - Reschedule
C - Continue Execution
S - Show Current State
Q - Quit

R - Reschedule
C - Continue Execution
S - Show Current State
Q - Quit

c
Teller 1 Serviced Customer 21
Teller 2 Serviced Customer 22
Teller 3 Serviced Customer 23
Teller 4 Serviced Customer 24
Teller 5 Serviced Customer 25
Teller 6 Serviced Customer 26
Teller 7 Serviced Customer 27
Teller 8 Serviced Customer 28
Teller 9 Serviced Customer 29
Teller 10 Serviced Customer 30
R - Reschedule
C - Continue Execution
S - Show Current State
Q - Quit

R - Reschedule
C - Continue Execution
S - Show Current State
Q - Quit

c
Teller 1 Serviced Customer 31
Teller 2 Serviced Customer 32
Teller 3 Serviced Customer 33
Teller 4 Serviced Customer 34
Teller 5 Serviced Customer 35
Teller 6 Serviced Customer 36
Teller 7 Serviced Customer 37
Teller 8 Serviced Customer 38
Teller 9 Serviced Customer 39
Teller 10 Serviced Customer 40
R - Reschedule
C - Continue Execution
S - Show Current State
Q - Quit

R - Reschedule
C - Continue Execution
S - Show Current State
Q - Quit

s
Teller 1  is available for the next Customer.
Teller 2  is available for the next Customer.
Teller 3  is available for the next Customer.
Teller 4  is available for the next Customer.
Teller 5  is available for the next Customer.
Teller 6  is available for the next Customer.
Teller 7  is available for the next Customer.
Teller 8  is available for the next Customer.
Teller 9  is available for the next Customer.
Teller 10  is available for the next Customer.
Customer 1  was serviced.
Customer 2  was serviced.
Customer 3  was serviced.
Customer 4  was serviced.
Customer 5  was serviced.
Customer 6  was serviced.
Customer 7  was serviced.
Customer 8  was serviced.
Customer 9  was serviced.
Customer 10  was serviced.
Customer 11  was serviced.
Customer 12  was serviced.
Customer 13  was serviced.
Customer 14  was serviced.
Customer 15  was serviced.
Customer 16  was serviced.
Customer 17  was serviced.
Customer 18  was serviced.
Customer 19  was serviced.
Customer 20  was serviced.
Customer 21  was serviced.
Customer 22  was serviced.
Customer 23  was serviced.
Customer 24  was serviced.
Customer 25  was serviced.
Customer 26  was serviced.
Customer 27  was serviced.
Customer 28  was serviced.
Customer 29  was serviced.
Customer 30  was serviced.
Customer 31  was serviced.
Customer 32  was serviced.
Customer 33  was serviced.
Customer 34  was serviced.
Customer 35  was serviced.
Customer 36  was serviced.
Customer 37  was serviced.
Customer 38  was serviced.
Customer 39  was serviced.
Customer 40  was serviced.
Customer 41  is awaiting service.
Customer 42  is awaiting service.
Customer 43  is awaiting service.
Customer 44  is awaiting service.
Customer 45  is awaiting service.
Customer 46  is awaiting service.
Customer 47  is awaiting service.
Customer 48  is awaiting service.
Customer 49  is awaiting service.
Customer 50  is awaiting service.
Customer 51  is awaiting service.
Customer 52  is awaiting service.
Customer 53  is awaiting service.
Customer 54  is awaiting service.
Customer 55  is awaiting service.
Customer 56  is awaiting service.
Customer 57  is awaiting service.
Customer 58  is awaiting service.
Customer 59  is awaiting service.
Customer 60  is awaiting service.
Customer 61  is awaiting service.
Customer 62  is awaiting service.
Customer 63  is awaiting service.
Customer 64  is awaiting service.
Customer 65  is awaiting service.
Customer 66  is awaiting service.
Customer 67  is awaiting service.
Customer 68  is awaiting service.
Customer 69  is awaiting service.
Customer 70  is awaiting service.
Customer 71  is awaiting service.
Customer 72  is awaiting service.
Customer 73  is awaiting service.
Customer 74  is awaiting service.
Customer 75  is awaiting service.
Customer 76  is awaiting service.
Customer 77  is awaiting service.
Customer 78  is awaiting service.
Customer 79  is awaiting service.
Customer 80  is awaiting service.
Customer 81  is awaiting service.
Customer 82  is awaiting service.
Customer 83  is awaiting service.
Customer 84  is awaiting service.
Customer 85  is awaiting service.
Customer 86  is awaiting service.
Customer 87  is awaiting service.
Customer 88  is awaiting service.
Customer 89  is awaiting service.
Customer 90  is awaiting service.
Customer 91  is awaiting service.
Customer 92  is awaiting service.
Customer 93  is awaiting service.
Customer 94  is awaiting service.
Customer 95  is awaiting service.
Customer 96  is awaiting service.
Customer 97  is awaiting service.
Customer 98  is awaiting service.
Customer 99  is awaiting service.
Customer 100  is awaiting service.
R - Reschedule
C - Continue Execution
S - Show Current State
Q - Quit

R - Reschedule
C - Continue Execution
S - Show Current State
Q - Quit

q

:davis:

#5 13-Feb-2008, 12:10

...it looks like I've got the logic that displays the menu somewhat screwed up...oh well, that's what I get for such a quick hack. Shouldn't be too difficult to fix. (Perhaps due to not clearing the the buffer on each pass?)

:davis:

faisalnet5 · #6 13-Feb-2008, 13:10

Davis, man........ u really deserve more than a Normal Thanks....U r great dude....!!! Special Thanks from me. (http://faisalnet5.blogspot.com/)

#7 13-Feb-2008, 13:47

Quote:

Originally Posted by faisalnet5

Davis, man........ u really deserve more than a Normal Thanks....U r great dude....!!! Special Thanks from me. (faisalnet5.blogspot.com)

Nah...

What would be fun would be to make it multi-threaded and then randomize the amount of time that it takes for each customer to be serviced by various tellers adding a weighting factor based on "teller individual productivity" and then see the "scheduler" working "for real."

...and then, insert a signal handler so that the user could break the execution to display the menu at any "interrupt."

...then add context switching and add other random events like tellers going on break, visiting the restroom, answering the phones, going to the vault, getting supervisor approval, etc. ...and then, one of the tellers would also be a "supervisor" who would have to "shell out" from the "teller task" to perform the "supervisor task" and then return to the teller task...preemption, priority inversion, synchronization primatives...all good fun!

Oh well, probably a bit overly ambitious for a 10-minute hack!

Let me know when you're ready to add some AI so that your tellers are able to learn from their customer interactions, supervisor interactions and "competitive" teller performance! Autonomous Teller Agents! Oh Yeah! ...next is adding the OpenGL and shrinkwrapping

:davis:

faisalnet5 · #8 22-Feb-2008, 07:54

Hello Davis...related to my earlier problem I do have some other requirements, for which I actually need help. In the requirement it is mentioned that the whole scheduler simulation program has to run for 8 to 10 minutes. It can read the input from a file or it can randomly generate Processes to start the simulation. After the simulation starts it has to go through all the six main phases what the actual simulation does such as READY, RUNNING, HALTED, SUSPENDED, BLOCKED as well as TERMINATED. Finally...the requirement says there will be a output (short of like log) file where it will show each and every phases status with the following information: Total number of processes, Average wait time incurred by the process and average total time for each process.

Now can u help to get a clue about how can I run the simulation for 8 mins? Suppose there is only one input file.......each line in that file will be my single processes. Then how to come up with the ideas??? Then I need help to generate those stage and connect with the output file so that whenever any stage starts or changes, it will show in that output file with the final information.

Can u give me some hits dude? Regards

Thread Tools	Search this Thread
Show Printable Version Email this Page	Search this Thread: Advanced Search
Rate This Thread
Rate This Thread:

Simulate the scheduler component of an Operating System

Re: From Faisal

Re: From Faisal

Re: From Faisal

Re: From Faisal

Re: From Faisal

Re: From Faisal

Re: From Faisal