Academic Integrity: tutoring, explanations, and feedback — we don’t complete graded work or submit on a student’s behalf.

Write a program that implements the following disk-scheduling algorithms: a. FCF

ID: 3685981 • Letter: W

Question

Write a program that implements the following disk-scheduling algorithms: a. FCFS b. SSTF c. SCAN d. C-SCAN e. LOOK f. C-LOOK Your program will service a disk with 5,000 cylinders numbered 0 to 4,999. The program will generate a random series of 1,000 cylinder requests and service them according to each of the algorithms listed above. The program will be passed the initial position of the disk head (as a parameter on the command line) and report the total amount of head movement required by each algorithm.

Explanation / Answer

main.c

#include "methods.h"

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

   //printf("Hello ");
   char* fileName = argv[1];
   headStart = atoi(fileName);
   printGreen("The Starting Position of the Disk Head: ");
   printf("%d ", headStart);
   printGreen("Window Size: ");
   printf("%d ", 100);

   int totalfcfs = 0;
   int totalsstf = 0;
   int totalscan = 0;
   int totalcscan = 0;
   int totallook = 0;
   int totalclook = 0;
   int runs = 0;
   start = (node *)malloc(sizeof(node));

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

       initialize();
       start -> next = NULL;
       start -> prev = NULL;
       //used in order to place values in the head node
       start -> data = -1;

       totalfcfs += fcfs(start, headStart);
       start -> next = NULL;
       start -> prev = NULL;
       //used in order to place values in the head node
       start -> data = -1;

       totalsstf += sstf(start, headStart);

       start -> next = NULL;
       start -> prev = NULL;
       start -> data = -1;
       printf("hey ");

       start -> next = NULL;
       start -> prev = NULL;
       start -> data = -1;
       printf("hey ");

       start -> next = NULL;
       start -> prev = NULL;
       start -> data = -1;
       printf("hey ");

       start -> next = NULL;
       start -> prev = NULL;
       start -> data = -1;
       printf("hey ");

       //runs
       runs ++;
   }

   printGreen("Average Head Movements after ");
   printf("%d",runs);
   printGreen(" runs consisting of 1000 random cylinders ranging in value between 0 and 4999 ");
   //fcfs
   printf("FCFS:     ");
   printf("%d ", totalfcfs/runs);
   //sstf
   printf("SSTF:     ");
   printf("%d", totalsstf/runs);
   printRed(" check the head movemnet print out, stays at same value for 100 movements ");
   //scan
   printf("SCAN:     ");
   printf("%d ", totalscan/runs);
   //cscan
   printf("C-SCAN:   ");
   printf("%d ", totalcscan/runs);
   //look
   printf("LOOK:     ");
   printf("%d ", totallook/runs);
   //clook
   printf("C-LOOK:   ");
   printf("%d ", totalclook/runs);

   printGreen("Done, check README for further explanation ");
}

methods.h
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>

//#include "terminalColors.h"
#define CLEAR            ""
#define BLACK            ""
#define RED            ""
#define GREEN            ""
#define BROWN            ""
#define BLUE            ""
#define MAGENTA        ""
#define CYAN            ""
#define GRAY            ""
#define BOLD_GRAY        ""
#define BOLD_RED        ""
#define BOLD_GREEN        ""
#define YELLOW            ""
#define BOLD_BLUE        ""
#define BOLD_MAGENTA   ""
#define BOLD_CYAN        ""
#define WHITE            ""

//data structures
typedef struct Node
{
        int data;
        struct Node *next;
        struct Node *prev;
}node;

//start always points to the first node of the linked list.
//temp is used to point to the last node of the linked list.
//declare two pointers to struct Node named node_t
node *start;

//initialize methods
void initialize();
long random_at_most(long max);
void print_cylinders();
//initialize global variables
int headStart;
int cylinders[1000];

void insertAtEnd(node *pointer, int data);
void clear();
void print(node *pointer);

//fcfs methods
int fcfs(node *pointer, int headStart);

//sstf methods
int sstf(node *pointer, int headStart);
node * leastSeekFirstMove(int headStart);
node * leastSeek(node *pointer);

//scan methods
int scan(node *pointer, int headStart);
int directionCheck(node * pointer, int currentDirection);
node * scanMove(node * pointer, int currentDirection);

//cscan methods
int cscan(node *pointer, int headStart);
node * maxNode();
node * minNode();
int ismin(node * pointer);
int ismax(node * pointer);

//look methods
int look(node *pointer, int headStart);

//clook methods
int clook(node *pointer, int headStart);

//scheduling methods global varibales
int fcfsHeadMovements;
int fcfsRuns;

//color print
void printRed(char* chArr);
void printBlue(char* chArr);
void printGreen(char* chArr);
void printCyan(char* chArr);
void printBrown(char* chArr);


scan.c
#include "methods.h"

int scan(node *pointer, int headStart){
   //reset counters
    int headMovements = 0;
   int arrayTraverse = 0;
   int currentDirection;
   int swap;
    //place first 100 cylindes in linked list
   for(int i = 0 ; i < 100 ; i++){
       arrayTraverse = i;
       insertAtEnd(pointer,cylinders[arrayTraverse]);
   }
   node * fm = leastSeekFirstMove(headStart);
   if(fm->data - headStart <= 0){
   currentDirection = 0;
   }
   if(fm->data - headStart > 0){
   currentDirection = 1;
   }
   headMovements += abs(headStart - fm->data);
    pointer = fm;
node * scan;
    while(1){
        swap = currentDirection;
        currentDirection = directionCheck(pointer, currentDirection);
        if(swap != currentDirection){
           if(swap == 0){
               headMovements += 2*(abs(pointer->data-0));
           }
           if(swap == 1){
               headMovements += 2*(abs(pointer->data-4999));
           }
        }
        scan = scanMove(pointer, currentDirection);
        if(scan->data == -10000){
           return(headMovements);
       }

        headMovements += abs(pointer->data - scan->data);
        if(arrayTraverse > 999){
             pointer->data = -10000;
        }
        if(arrayTraverse <= 999){
             pointer->data = cylinders[arrayTraverse];
        }
        arrayTraverse++;
        pointer = scan;
   }
}

int directionCheck(node * pointer, int currentDirection){
    node * traverseNode = start;
   if(currentDirection == 1){
       while(traverseNode->next != NULL){
            if(abs(traverseNode->data - 4999) < abs(pointer->data - 4999)){
               return(1);
            }
           traverseNode = traverseNode->next;
       }
       return(0);
   }
   if(currentDirection == 0){
       while(traverseNode->next != NULL){
            if(abs(traverseNode->data - 0) < abs(pointer->data - 0)){
               return(0);
            }
            traverseNode = traverseNode->next;
       }
       return(1);
   }
}
node * scanMove(node * pointer, int currentDirection){
   int difference = 999999999;
    node * scanNode;
    //moves through the linked list
    node * traverseNode = start;
    //catch all but last, need to fix                           however traverseNode != NULL gives me segmentation fault (actually both cause seg fualt)
    while(traverseNode != NULL){
       //going left
       if(currentDirection == 0){
           //new cylinder is smaller than current node
           if(abs(pointer->data - traverseNode->data) < difference && pointer->data > traverseNode->data ){
               //make sure trverse node not in the same possition as the current pointer
               if(traverseNode != pointer){
                   difference = abs(pointer->data - traverseNode->data);
                   scanNode = traverseNode;
               }
              }
          }
       //going right
       if(currentDirection == 1){
           //new cylinder is larger than current cyliner
           if(abs(pointer->data - traverseNode->data) < difference && pointer->data < traverseNode->data ){
               //make sure trverse node not in the same possition as the current pointer
               if(traverseNode != pointer){
                   difference = abs(pointer->data - traverseNode->data);
                   scanNode = traverseNode;
               }
              }
       }
       //this will cause a null pointer i think
       traverseNode = traverseNode->next;
    }
    return(scanNode);
}

fcfs.c
#include "methods.h"

int fcfs(node *pointer, int headStart){
   int fcfsHeadMovements = 0;
   int arrayTraverse = 0;

   //place first 100 cylindes in linked list
   for(int i = 0 ; i < 100 ; i++){
       arrayTraverse = i;
       insertAtEnd(pointer,cylinders[arrayTraverse]);
   }
   //first move
   int firstHeadMovement = abs(headStart - pointer->data);
   //printf("%d ", firstHeadMovement);
   fcfsHeadMovements = firstHeadMovement ;
while (pointer->next != NULL && pointer->data != -10000){
   //are we at the end of the linked list
   if(pointer->next != NULL){
       //add head movement
       fcfsHeadMovements += abs(pointer->data - pointer->next->data);
       //add new cylinder
       //place new cylinder in the position of the old cylinder in the linkedlist
       if(arrayTraverse > 999){
           pointer->data = -10000;
       }
       //still have more to add from array
       if(arrayTraverse <= 999){
           pointer->data = cylinders[arrayTraverse];
       }
       //increment traverse
       arrayTraverse++;
       //move pointer
       pointer = pointer->next;
   }

   //yes we are at the end of the linkedList
   if(pointer->next == NULL){
       //add head movement
       fcfsHeadMovements += abs(pointer->data - start->data);
       if(arrayTraverse > 999){
           pointer->data = -10000;
       }
       //still have more to add from array
       if(arrayTraverse <= 999){
           pointer->data = cylinders[arrayTraverse];
       }
       //increment traverse
       arrayTraverse++;
       //move pointer
       pointer = start;
   }
}

return(fcfsHeadMovements);
}

cscan.c
#include "methods.h"
int cscan(node *pointer, int headStart){
    int headMovements = 0;
   int arrayTraverse = 0;
   int currentDirection;
   int swap;

   for(int i = 0 ; i < 100 ; i++){
       arrayTraverse = i;
       insertAtEnd(pointer,cylinders[arrayTraverse]);
   }
   node * fm = leastSeekFirstMove(headStart);
   if(fm->data - headStart <= 0){
       currentDirection = 0;
   }
   if(fm->data - headStart > 0){
       currentDirection = 1;
   }
   headMovements += abs(headStart - fm->data);
    pointer = fm;
    node * scan;
    node * temp;
    while(1){
       if(ismin(pointer) == 1 || ismax(pointer)==1){
           printBlue("end");
           //printf("%d ",minnum);
            if(ismin(pointer) == 1){
               //get from the bottom go back to the top adding needed head movments and repositioning pointer maintain direction of 0
               headMovements += abs(pointer->data - 0);
               headMovements += 5000;
               if(arrayTraverse > 999){
                      pointer->data = -10000;
               }
               if(arrayTraverse <= 999){
                      pointer->data = cylinders[arrayTraverse];
                  }
               arrayTraverse++;
               // //causing the segmentation fault
               temp = maxNode();
               headMovements += 2*(abs(temp->data-4999));
            }
            if(ismax(pointer)==1){
               //get from the top go back to the bottom adding needed head movments and repositioning pointer maintaining direction of 1
                headMovements += 2*(abs(pointer->data-4999));
               headMovements += 5000;
               if(arrayTraverse > 999){
                      pointer->data = -10000;
                  }
                  if(arrayTraverse <= 999){
                      pointer->data = cylinders[arrayTraverse];
               }
               arrayTraverse++;
               temp = minNode();
               headMovements += (abs(pointer->data-0));
               currentDirection = 1;
            }
            pointer = temp;
       }
        scan = scanMove(pointer, currentDirection);

        if(scan->data == -10000){
           return(headMovements);
       }
        headMovements += abs(pointer->data - scan->data);

        if(arrayTraverse > 999){
             pointer->data = -10000;
        }
        if(arrayTraverse <= 999){
             pointer->data = cylinders[arrayTraverse];
        }

        arrayTraverse++;
        pointer = scan;
   }
}

int ismax(node * pointer){
    node * traverseNode = start;
    while(traverseNode != NULL){
       if(traverseNode->data > pointer->data && traverseNode->data < 5000){
              //not max
              return(0);
        }
        traverseNode = traverseNode->next;
    }
    //is max
    return(1);
}

int ismin(node * pointer){
   node * traverseNode = start;
    while(traverseNode != NULL){
       if(traverseNode->data < pointer->data && traverseNode->data > -1){
              //not min
              return(0);
        }
        traverseNode = traverseNode->next;
    }
    //is min
    return(1);
}

node * maxNode(){
    node * maxNode;
    maxNode->data = -1;
    node * traverseNode = start;

    while(traverseNode != NULL){
       if(traverseNode->data > maxNode->data && traverseNode->data < 5000){
              maxNode = traverseNode;
        }
        traverseNode = traverseNode->next;
    }
    return(maxNode);
}

node * minNode(){
    node * minNode;
    node * traverseNode = start;
    while(traverseNode != NULL){
       if(traverseNode->data < minNode->data && traverseNode->data > -1){
                  minNode = traverseNode;
          }
       traverseNode = traverseNode->next;
    }
    return(minNode);
}

clook.c
#include "methods.h"
int clook(node *pointer, int headStart){
    int headMovements = 0;
   int arrayTraverse = 0;
   int currentDirection;
   int swap;
   for(int i = 0 ; i < 100 ; i++){
       arrayTraverse = i;
       insertAtEnd(pointer,cylinders[arrayTraverse]);
   }
   node * fm = leastSeekFirstMove(headStart);
   if(fm->data - headStart <= 0){
       currentDirection = 0;
   }
   if(fm->data - headStart > 0){
       currentDirection = 1;
   }
   headMovements += abs(headStart - fm->data);
    pointer = fm;
    node * scan;
    node * max;
    node * min;
    while(1){

        swap = currentDirection;
        currentDirection = directionCheck(pointer, currentDirection);

        if(swap != currentDirection){
           if(swap == 0){
               //get to the min node go back to the max node adding needed head movments and repositioning pointer maintain direction of 0
               max = maxNode();
               headMovements += abs(pointer->data - max->data);
               if(arrayTraverse > 999){
                    pointer->data = -10000;
               }
               if(arrayTraverse <= 999){
                    pointer->data = cylinders[arrayTraverse];
               }
               arrayTraverse++;
               pointer = max;
               //headMovements += 2*(abs(pointer->data-4999));
               currentDirection = 0;
           }
           if(swap == 1){
               //get to the max node go back to the min adding needed head movments and repositioning pointer maintaining direction of 1
                headMovements += 2*(abs(pointer->data-4999));
               min = minNode();
               headMovements += abs(pointer->data - max->data);
               if(arrayTraverse > 999){
                    pointer->data = -10000;
               }
               if(arrayTraverse <= 999){
                    pointer->data = cylinders[arrayTraverse];
               }
               arrayTraverse++;
               pointer = min;
               //headMovements += (abs(pointer->data-0));
               currentDirection = 1;
           }
        }

        scan = scanMove(pointer, currentDirection);
        if(scan->data == -10000){
           return(headMovements);
       }
        headMovements += abs(pointer->data - scan->data);
        if(arrayTraverse > 999){
             pointer->data = -10000;
        }
        if(arrayTraverse <= 999){
             pointer->data = cylinders[arrayTraverse];
        }
        arrayTraverse++;
        pointer = scan;
   }
}
doublyLinkedList.c
//doublyLinkedList
#include "methods.h"

void insertAtEnd(node *pointer, int data)
{
        if(pointer->data == -1){
            pointer->data = data;
            //printf("test ");
            return;
        }
        /* Iterate through the list till we encounter the last node.*/
        while(pointer->next!=NULL)
        {
                //printf("test ");
                pointer = pointer -> next;
        }
        /* Allocate memory for the new node and put data in it.*/
        pointer->next = (node *)malloc(sizeof(node));
        (pointer->next)->prev = pointer;
        pointer = pointer->next;
        pointer->data = data;
        pointer->next = NULL;
}
void clear(){
    start->next = NULL;
    start->prev = NULL;
    start->data = -1;
}
void print(node *pointer)
{
        if(pointer==NULL)
        {
                return;
        }
        printf("%d ",pointer->data);
        print(pointer->next);
}

initialize.c
//initialize
#include "methods.h"

//random Integers from 0 to 4999
void initialize(){
   for(int i = 0 ; i<1000; i++){
       cylinders[i] = random_at_most(4999);
   }
}
//print out the cylinder array
void print_cylinders(){
for (int i = 0; i<1000;i++){
    printf("%d    ",i);
    printf("%d ",cylinders[i]);
}
}
// Assumes 0 <= max <= RAND_MAX
// Returns in the half-open interval [0, max]
long random_at_most(long max) {
srand(time(NULL));
unsigned long
    // max <= RAND_MAX < ULONG_MAX, so this is okay.
    num_bins = (unsigned long) max + 1,
    num_rand = (unsigned long) RAND_MAX + 1,
    bin_size = num_rand / num_bins,
    defect   = num_rand % num_bins;
long x;
do {
   x = random();
}
// This is carefully written not to overflow
while (num_rand - defect <= (unsigned long)x);

// Truncated division is intentional
return x/bin_size;
}

look.c
#include "methods.h"
int look(node *pointer, int headStart){
    int headMovements = 0;
   int arrayTraverse = 0;
   int currentDirection;
   int swap;
   for(int i = 0 ; i < 100 ; i++){
       arrayTraverse = i;
       insertAtEnd(pointer,cylinders[arrayTraverse]);
   }
   node * fm = leastSeekFirstMove(headStart);
   if(fm->data - headStart <= 0){
       currentDirection = 0;
   }
   if(fm->data - headStart > 0){
       currentDirection = 1;
   }
   headMovements += abs(headStart - fm->data);
    pointer = fm;
    node * scan;
    while(1){
        swap = currentDirection;
        currentDirection = directionCheck(pointer, currentDirection);
        scan = scanMove(pointer, currentDirection);
        if(scan->data == -10000){
           return(headMovements);
       }
        headMovements += abs(pointer->data - scan->data);
        if(arrayTraverse > 999){
             pointer->data = -10000;
        }
        if(arrayTraverse <= 999){
             pointer->data = cylinders[arrayTraverse];
        }
        arrayTraverse++;
        pointer = scan;
   }
}

sstf.c
#include "methods.h"

int sstf(node *pointer, int headStart){
    int headMovements = 0;
   int arrayTraverse = 0;
   for(int i = 0 ; i < 100 ; i++){
       arrayTraverse = i;
       insertAtEnd(pointer,cylinders[arrayTraverse]);
       //printf("%d   " , arrayTraverse);
       //printf("%d ", cylinders[arrayTraverse]);
   }
   //first move
   //smallest absolute value to the current head
    node * ls = leastSeekFirstMove(headStart);
   int firstHeadMovement = abs(headStart - ls->data);
   //printf("%d ", firstHeadMovement);
   headMovements = firstHeadMovement ;
    pointer = ls;
    while (1){
    ls = leastSeek(pointer);

    if(ls->data == -10000){
            return(headMovements);
    }

     //are we at the end of the linked list
     //if(pointer->next != NULL){
         //add head movement
         headMovements += abs(pointer->data - ls->data);
         //add new cylinder
         //place new cylinder in the position of the old cylinder in the linkedlist
         if(arrayTraverse > 999){
             pointer->data = -10000;
         }
         //still have more to add from array
         if(arrayTraverse <= 999){
             pointer->data = cylinders[arrayTraverse];
         }
         //increment traverse
         arrayTraverse++;
         //move pointer
         pointer = ls;
    }//return(headMovements);
}
node * leastSeekFirstMove(int headStart){
    int difference = 999999999;
    //node * originalNode = pointer;
    node * leastSeekNode;
    //moves through the linked list
    node * traverseNode = start;
    //catch all but last
    while(traverseNode->next != NULL){
        if(abs(headStart - traverseNode->data) < difference){
                difference = abs(headStart - traverseNode->data);
                leastSeekNode = traverseNode;
        }traverseNode = traverseNode->next;
    }return(leastSeekNode);
}

//find the value leastSeek Value to the imput value
node * leastSeek(node *pointer){
    int difference = 999999999;
    //node * originalNode = pointer;
    node * leastSeekNode;
    //moves through the linked list
    node * traverseNode = start;
    //catch all but last
    while(traverseNode->next != NULL){
        if(abs(pointer->data - traverseNode->data) < difference){
            //make sure trverse node not in the same possition as the current pointer
            if(traverseNode != pointer){
                difference = abs(pointer->data - traverseNode->data);
                leastSeekNode = traverseNode;
            }
        }traverseNode = traverseNode->next;
    }return(leastSeekNode);
}

terminalColors.c
#include "methods.h"

#define CLEAR            ""

#define BLACK            ""
#define RED            ""
#define GREEN            ""
#define BROWN            ""
#define BLUE            ""
#define MAGENTA        ""
#define CYAN            ""
#define GRAY            ""
#define BOLD_GRAY        ""
#define BOLD_RED        ""
#define BOLD_GREEN        ""
#define YELLOW            ""
#define BOLD_BLUE        ""
#define BOLD_MAGENTA   ""
#define BOLD_CYAN        ""
#define WHITE            ""


void printRed(char* chArr){
   printf("%s%s%s",RED,chArr, CLEAR);
}
void printBlue(char* chArr){
   printf("%s%s%s",BLUE,chArr, CLEAR);
}
void printGreen(char* chArr){
   printf("%s%s%s",GREEN,chArr, CLEAR);
}
void printCyan(char* chArr){
   printf("%s%s%s",CYAN,chArr, CLEAR);
}
void printBrown(char* chArr){
   printf("%s%s%s",BROWN,chArr, CLEAR);
}

Related Questions

Write a program that has an array of at least 10 string objects that hold people
Question #3539280
Write a program that has an array of at least 10 string objects that hold people
Question #3620701
Write a program that has an array of at least 10 string objectsthat hold people’
Question #3618053
Write a program that has an array of at least 20 integers. It should call a func
Question #3908440
Write a program that has five functions as follows: main – the main function wil
Question #3627441
Write a program that has four functions that do the following: A main() function
Question #3761152
Write a program that has the following menu of options as listed below. When a u
Question #3538396
Write a program that has the user input two points in the xy-plane, and then dis
Question #3799422
Hire Me For All Your Tutoring Needs
Integrity-first tutoring: clear explanations, guidance, and feedback.
Drop an Email at
drjack9650@gmail.com
Chat Now And Get Quote

Navigate

Previous
Write a program that implements the following disk-scheduling algorithms from ch
Next
Write a program that implements the following functions The function partial sum

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.