IMPLEMENT Round Robin scheduling algoritm.

CodeProject This program is general and considers the case when no programs may be running also.

/*   AUTHOR     :    VINAY CHOUDHARY

     DATE       :    20-11-2010

     TITLE      :    ROUND ROBIN SCHEDULING ALGORITHM

     COMPANY    :   

     TIME       :   

*/

#include<stdio.h>

#include<stdlib.h>

#define NUM_PRC      5    //number of process

#define TIME_QUANTUM 3    //time quantum

#define CONTEXT_SWT  1    //context switch time between process, set 0 if not to be included

int ARR[NUM_PRC];    //arrival times of processes

int BRS[NUM_PRC];    //burst times of processes

int STR[NUM_PRC];    //start times

int FIN[NUM_PRC];    //finish times

int WAT[NUM_PRC];    //waiting times

int TRN[NUM_PRC];    //turn around times

void get_times();

void RR();

void calc(int *tt, int *tw,float *at,float *aw);

void print(int *tt, int *tw,float *at,float *aw);

int main()

{

     int TT,TW;             //total wait & turnaround times

     float avg_wat,avg_trn; //average wait & turnaround times

     get_times();

     RR();

     calc(&TT,&TW,&avg_wat,&avg_trn);

     print(&TT,&TW,&avg_wat,&avg_trn);

     printf("\n\n***** END OF RR *****\n\n");

     return 0;

}

void get_times()

{

     int i;

     printf("\n***** GETTING ARRIVAL & BURST TIMES *****\n");

     for(i=0;i<NUM_PRC;i++)

     {

           STR[i] = -1;    //set this to -1 to mark it as not started

           printf("Enter arrival & burst time for process[%d] : ",i+1);

           scanf("%d%d",&ARR[i],&BRS[i]);

     }

}

void RR()

{

     int exc_time=0;        //initially execution time is 0

     int remain=NUM_PRC;    //unterminated processes

     int t_BRS[NUM_PRC];    //temporary BRS ARRAY

     int i;

     int prc_executed;

     int started=0;     //any process runs scheduling started 

     for(i=0;i<NUM_PRC;i++)

           t_BRS[i] = BRS[i];

     while(remain)

     {

           prc_executed = 0;

           for(i=0;i<NUM_PRC;i++)

           {

                //If process has arrived at this time

                //and has burst time remaining then run it.

                if(t_BRS[i] > 0 && ARR[i] <= exc_time)         

                {                                                         

                //If no process has started then no need for CONTEXT_SWT.

                //When schedular is idle started is set to 0, since it is now ruuning set stated to 1.

                //If some process was ruuninng in previous time quantum add CONTEXT_SWT.

                     if(started == 0)                               

                           started = 1;                              

                     else                                           

                           exc_time = exc_time + CONTEXT_SWT;

                    

                     //If first run

                     //then current exc_time is its start time.

                     if(STR[i] == -1)                               

                           STR[i] = exc_time;

                          

                     //Decrease TIME_QUANTUM from BRST time because process has run for this time.

                     t_BRS[i] = t_BRS[i] - TIME_QUANTUM;       

                     //Increase exc_time by TIME_QUANTUM.

                     exc_time = exc_time + TIME_QUANTUM;

                     //Mark that a process was executed, used to increment exc_time

                     //by 1 unit if no process was ready to run

                     prc_executed = 1;                              

                                                                          

                     if(t_BRS[i] <= 0)

                     {    //If process completes.

                           exc_time = exc_time + t_BRS[i];     

                           //If t_BRS[i] is -ve means it ran for less than TIME_QUANTUM and extra time must be subtracted.

                           //This extra time is in t_BRS[i],e.g, if it had to runs for 1s and TIME_QUANTUM is 3s then

                           //it should only run for 1s. so after t_BRS[i] = t_BRS[i] - TIME_QUANTUM, t_BRS[i] is -2, meanining

                           //2s must be subtracted from exc_time

                           FIN[i] = exc_time;         //current exc_time is finish time then

                           remain--;                  //decrease number of remaining process

                     }

                }

           }

          

           if(prc_executed == 0)

           {

                //If no process executed increment execution time by 1 unit, this is used in case there is no process ready to run.

                started = 0;

                //since no process was executed set schedular to idle so that there is no contect switch when a process arrives

                exc_time++;         

           }   

     }

}

void calc(int *tt, int *tw,float *at,float *aw)

{

     int i;

     *tw = *tt = 0;

     for(i=0;i<NUM_PRC;i++)

     {

           TRN[i] = FIN[i] - ARR[i];            //turnaround time = finish time - submission time

           WAT[i] = TRN[i] - BRS[i];            //wait time = finish time - submission time - burst time

                                                //or wait time = turnaround time - burst time, this is time spent in ready queue

           *tw += WAT[i];

           *tt += TRN[i];       //total wait & turn around times

     }

     *at = (float)*tt/NUM_PRC;

     *aw = (float)*tw/NUM_PRC;       //average wait & turn around times

}

void print(int *tt, int *tw,float *at,float *aw)

{

     int i;

     printf("\n\nPID ARR BRS STR FIN WAT TRN");

     printf("\n---------------------------");

     for(i=0;i<NUM_PRC;i++)

           printf("\n%3d %3d %3d %3d %3d %3d %3d",i+1,ARR[i],BRS[i],STR[i],FIN[i],WAT[i],TRN[i]);

     printf("\n---------------------------\n");

     printf("\nTOTAL TURNAROUND TIME : %d\tAVERAGE TURNAROUND TIME : %.2f",*tt,*at);

     printf("\nTOTAL WAITING    TIME : %d\tAVERAGE WAITING    TIME : %.2f",*tw,*aw);

}

IMPLEMENT First Come First Come scheduling algoritm.

CodeProject #include<stdio.h>
#include<stdlib.h>

#define MAX 5

void get_data(int *a, int *b);
void fcfs(int *a,int *b,int *t,int *w);
void calc(int *tt, int *tw,int *a,int *b,int *t,int *w);
void show(int *tt, int *tw,int *a,int *b,int *t,int *w);

int main()
{
    int arr[MAX];
    int brs[MAX];
    int trn[MAX];
    int wat[MAX];
    int total_turn=0;
    int total_wait=0;

    get_data(arr,brs);
    fcfs(arr,brs,trn,wat);
    calc(&total_turn,&total_wait,arr,brs,trn,wat);
    show(&total_turn,&total_wait,arr,brs,trn,wat);

    printf("\n\n");
    system("pause");
    return 0;
}

void get_data(int *a, int *b)
{
    int i;

    for(i=0;i<MAX;i++)
    {
        printf("\nENTER ARRIVAL TIME OF P[%d] : ",i);
        scanf("%d",a+i);
        printf("ENTER BURST TIME OF P[%d] : ",i);
        scanf("%d",b+i);
    }
}

void fcfs(int *a,int *b,int *t,int *w)
{
    int response=0;
    int i;
    int execution_time=0;

    for(i=0;i<MAX;i++)
    {
        w[i] = response - a[i];        //wait is response - arrival
        execution_time += b[i];        //add current burst to total execution, this gives finish time for this process
        response = execution_time;    //this is response time for next process
        t[i] = execution_time - a[i];    //turnaround is finish - arrival;
    }
}

void calc(int *tt, int *tw,int *a,int *b,int *t,int *w)
{
    int i;
   
    for(i=0;i<MAX;i++)
    {
        *tt += t[i];
        *tw += w[i];
    }
}

void show(int *tt, int *tw,int *a,int *b,int *t,int *w)
{
    int i;

    printf("\nPRC ARRV BRST WAIT TURN");

    for(i=0;i<MAX;i++)
    {
        printf("\n%3d %4d %4d %4d %4d",i,a[i],b[i],w[i],t[i]);
    }

    printf("\nTOTAL TURNAROUND TIME : %4d",*tt);
    printf("\nTOTAL WAITING    TIME : %4d",*tw);
}

SORT a LINKED LIST containing STRINGS

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

typedef struct STR_DATA
{
    char *name;
    struct STR_DATA *next;
}NODE;

int count=0;
void add_names(NODE **head);
void sort_names(NODE *head);
void print_names(NODE *head);
char printmenu(NODE *head);

int main()
{
    NODE *head=NULL;
    char ch='y';
    int flag=1;

    while(flag)
    {
        ch = printmenu(head);
        switch(ch)
        {
            case '0':
                    printf("\n\nEXITING...");
                    flag = 0;
                    break;
            case '1':
                    while ((ch = getchar()) != '\n' && ch != EOF);
                    add_names(&head);
                    break;
            case '2':
                    while ((ch = getchar()) != '\n' && ch != EOF);
                    sort_names(head);
                    break;
            default:
                    printf("\n\nENTER VALID CHOICE...");
                    break;   
        }
       
    }

    printf("\n\n");
    system("wait");
    printf("\n");
    return 0;
}
char printmenu(NODE *head)
{
    char ch;

    printf("\nCurrent list: ");
    print_names(head);
    printf("\nWHAT TO DO: ");
    printf("\n[1] ADD a name\n[2] SORT names");
    printf("\n\nEnter choice: ");
    scanf("%c",&ch);

    return ch;
}
void add_names(NODE **head)
{
    NODE *new_node;
    int num_char=0;
    char *str1=NULL,ch='x';

    new_node =(NODE*)malloc(1*sizeof(NODE));
    count++;
    new_node->next=*head;
    *head=new_node;

    printf("\nEnter name : ");   
    while(ch!='\n' && ch != EOF)
    {
        ch=getchar();
        if(ch=='\n')
            break;
       
        num_char++;
        str1 = (char*)realloc( str1,(num_char+1)*sizeof(char));
        if(str1 == NULL)
        {
            printf("\nERROR: reallocating memory...\n\n");
            exit(1);
        }

        str1[num_char-1]=ch;
        str1[num_char]='\0';
    }
   
    new_node->name = (char*)malloc((num_char+1)*sizeof(char));
    strcpy(new_node->name,str1);
    free(str1);
}

void sort_names(NODE *head)
{
    int i,j;
    NODE *curr,*prev;
    char *temp1,*temp2;

    for(i=0;i<count-1;i++)
    {
        prev=head;
        curr=head->next;               
        for(j=0;j<count-1-i;j++)
        {
            if(strcmp(prev->name,curr->name) > 0)
            {
                temp1 = (char*)malloc(strlen(prev->name));
                temp2 = (char*)malloc(strlen(curr->name));
                strcpy(temp1,prev->name);
                strcpy(temp2,curr->name);

                curr->name = (char*)realloc(curr->name,strlen(temp1));
                prev->name = (char*)realloc(prev->name,strlen(temp2));
                strcpy(prev->name,temp2);
                strcpy(curr->name,temp1);
                free(temp1);
                free(temp2);
            }
            prev=curr;
            curr=curr->next;
        }
    }
}

void print_names(NODE *head)
{
    if(!head)
    {
        printf("EMPTY");
        return;
    }
    while(head)
    {
        printf("%s|",head->name);
        head=head->next;
    }
}

Modify STACK EXAMPLE to create A DYNAMIC QUEUE

DYNAMIC QUEUE using DYNAMIC STACK

//TITLE         DYNAMIC QUEUE by modifying DYNAMIC STACK

//AUTHOR        VINAY CHOUDHARY

//DATE          26 OCT 2009

//This is a C program for DYNAMIC queue using stack functions

#include<stdio.h>

#include<stdlib.h>

#include<conio.h>

#define NUM 5

/*

*pos  :    we will use "pos" to point to top element in array,            used in pop, value updates in push.

*arr  :    pointer to array which is allocated memory at run-time.Can be replaced by static array. Just comment out part where we are using malloc() for array in push().

num   :    "num" tells how much data is present.

*next :    "*next" is pointer to next stack element.

*/

typedef struct blk{

     int *pos;                 

     int *arr;                 

     int num;         

     struct blk *next;   

}stack;

/*

PUSH FUCTION : we pass head as pointer and data here. Head is stored in backup for returning new value when stack is created for first time, else it contains old head value.

In loop above we check if head exists and go to last stack,which has next == null. There we check if head(stack) exists or not or if array is full for current last stack. In both cases we create a new stack as temp. temp points to NULL, since it will be last stack and has no data at present so num = 0 for temp and make pos to point to base of arr.

Now if stack doesnt exist then assign temp as head of stack since we will add data to it. Also since this is new head, store it in backup for returning purpose, else if array has filled for current last stack attach newly created temp stack to stack by storing its address in next of curent stack and make head same as temp since we add data to newly created stack(temp) using head(head=temp).

Then add data and increment index and return backup

*/

stack* push(stack *head,int data)

{         

     stack* backup,*temp;                

     for(backup = head;head && head->next != NULL;head = head->next);               

     if(head == NULL || head->num == NUM)

     {              

           temp = (stack *)malloc(1*sizeof(stack));  

           temp->arr = (int*)malloc(NUM*sizeof(int));

           temp->next = NULL;                                  

           temp->num = 0;      

           temp->pos = temp->arr;                              

           if(backup == NULL)

                backup = head = temp;

           else if(head->num == NUM)

                head = head->next = temp;

     }                                        

     head->arr[head->num++] = data

    

     return backup;

}

//POP FUNCTION: we pass head as pointer and data as pointer here.

//save backup as head;

//Read data at pos. pos is where queue starts

//since data at pos is read, now we will read next element next time so //pos++

//and take data in pointer passed, which is collected in main

//here we check if array of current last stack has become empty, if so

//second last stack, use temp to make second last stack to point to NULL. //Hence stack

//pointed by temp is now the last stack. Free memory of stack to be deleted.

//NOTE THAT stack is deleted only when no data is left

//whether updated or not return backup which is collected as head in main //program

stack* pop(stack *head,int *data)

{        

stack* backup,*temp=NULL;

     backup = head;                                 

     *data = *head->pos;       

     head->pos++;              

     --head->num;                   

if(head->num == 0)

{                    

temp = head->next;

           free(head->arr);    

           free(head);               

           backup = temp;           

}         

     return backup; 

}

void display(stack *head)

{   

     int *p,i;                                 

    

     printf("\nCURRENT STACK: ");

    

     if(!head)

           printf("DOESN'T EXIST");

    

     while(head)

{

           for(i=0,p=head->pos;i<head->num;p++,i++)

                printf("%d ",*p);

           head = head->next;

     }

}

void main()

{

     stack *head=NULL;

     int data,run=1;

     char ch;

     while(run)

{

           display(head);

           printf("\n\nWHAT TO DO ?");

           printf("\n1. PUSH\n2. POP\n3. DISPLAY\n4. EXIT\nYOUR OPTION : ");

           scanf(“%c”,&ch);

           switch(ch)

{

                case '1':

{

                     printf("Enter number to push: ");

                     scanf(“%d”,&data);

                     head = push(head,data);        

                     break;

                }

    

                case '2':

{                                         

                     if( (head) )

{                              

                           head = pop(head,&data);   

                           printf("DATA POPPED: %d",data);

                          

                     }

                     else

                           printf("CAN'T POP: NO DATA IN STACK");

                     break;

                }

    

                case '3':

{

                     display(head);

                     break;

                }

                case '4':

{

                     run = 0;

                     break;

                }

               

                default:

{

                     printf("\nENTER VALID OPTION");

                     break;

                }

           }

     }

     printf("\n\n");

}