Elevators Algorithm (SCAN)

Elevators Algorithm

SCAN

Elevators Algorithm is another disk scheduling algorithm, as the name suggest its roots lay on working of an elevator. i.e., Once started then it goes in the same direction, being said that there are various modifications to it and we will look upon two well known methods to implement elevators algorithm.

In this post we will see SCAN algorithm in detail , with a complete cpp code to stimulate it. We will use busy scanning for coding purpose. i.e, The pointing head will keep scanning even if there is nothing to be scheduled, but some disk are yet expected to scheduled.

• SCAN
• LOOK

SCAN

Suppose we have a tape, which is indexed from 0 to Nth location. Assume we start from a location x <= N  and we choose one direction Left or Right, Assuming we take Right we will start processing all the requests coming till we move to the end of the tape without changing direction and after reaching the end of the tape , we will change the direction and continue till another end. This method is known as SCAN and it can be better understood by the theoretical model given above.

CPP Program for SCAN

	//
	// main.cpp
	// Elevator-SCAN stimulation
	// Created by Sarvesh Bhatnagar on 22/04/18.
	// Copyright © 2018 introtoalgo.com. All rights reserved.
	//
	/*
	This Program is a stimulation of SCAN algorithm, one can modify it as per required to
	make it a CSCAN, LOOK or a CLOOK stimulation.
	*/
	#include <iostream>
	using namespace std;
	int countNo = 1;
	//Preparing for stimulating the disk
	struct Track{
	int trackNumber;
	struct Track *prev = NULL;
	struct Track *next = NULL;
	};
	struct Track *last, *temp, *head;
	void makeTrack();
	void setHeadPos(int headPos);
	void scan();
	int main() {
	last = temp = NULL;
	cout<<"Enter The assumed number of track"<<endl;
	int num;
	cin>>num;
	for (int i = 0; i<num; i++) {
	makeTrack();
	}
	int headPos;
	cout<<"Enter assumed head position "<<endl;
	do {
	cin>>headPos;
	if (headPos>num) {
	cout<<"Please enter head position within range"<<endl;
	}
	} while (headPos > num);
	int effectiveHeadPost = num - headPos;
	setHeadPos(effectiveHeadPost);
	scan();
	return 0;
	}
	//We are trying to use just one pointer for reference of the tracks. i.e. last
	void makeTrack(){
	temp = new Track();
	temp->trackNumber = countNo;
	countNo ++;
	if (last == NULL) {
	last = temp;
	}else{
	last->next = temp;
	temp->prev = last;
	last = temp;
	}
	//BELOW CODE IS JUST FOR TESTING THAT IS EVERYTHING WORKING FINE
	// cout<<"MADE "<<last->trackNumber<<endl;
	// if (last->prev != NULL) {
	// temp = last->prev;
	// cout<<"PREV "<<temp->trackNumber<<endl;
	// }
	}
	void setHeadPos(int headPos){
	temp = last;
	for (int i = 0; i<headPos; i++) {
	temp = temp->prev;
	}
	head = temp;
	//The below code is just to check if the above code is working properly
	// cout<<"CURRENT "<<temp->trackNumber<<endl;
	}
	void scan(){
	int cnt;
	temp = head;
	cout<<"Enter the number of tracks you may seek ?"<<endl;
	int n;
	cin>>n;
	cnt = n;
	cout<<"Enter tracks initially in the queue"<<endl;
	int nt;
	cin>>nt;
	int plist[nt];
	for (int i = 0; i<nt; i++) {
	cout<<"Enter track at pos "<<i<<" in the queue "<<endl;
	cin>>plist[i];
	}
	int ntCount = n-nt;
	int maybe[nt];
	for (int i = 0; i<nt; i++) {
	maybe[i] = -1;
	}
	cout<<"Enter direction 0/1 (L/R) "<<endl;
	int dir = 0;
	cin>>dir;
	while (true) {
	if (cnt == 0) {
	break;
	}
	if (dir == 0) {
	for (int i = 0; i<nt; i++) {
	if (plist[i] == temp->trackNumber) {
	plist[i] = -1;
	cnt--;
	}
	}
	for (int i = 0; i<nt; i++) {
	if(maybe[i] == temp->trackNumber){
	maybe[i] = -1;
	cnt--;
	}
	}
	if (temp->prev != NULL) {
	temp = temp->prev;
	}else{
	dir = 1;
	temp = temp->next;
	}
	if (ntCount > 0) {
	cout<<"Do you want to seek a track? [1/0] y/n "<<endl;
	int temptrack;
	cin>>temptrack;
	if (temptrack == 1) {
	for (int i = 0; i<nt; i++) {
	if (maybe[i] == -1) {
	cout<<"Enter track "<<endl;
	cin>>maybe[i];
	ntCount--;
	break;
	}
	}
	}
	}
	cout<<"CURRENT "<<temp->trackNumber<<endl;
	}else{
	for (int i = 0; i<nt; i++) {
	if (plist[i] == temp->trackNumber) {
	plist[i] = -1;
	cnt --;
	}
	}
	for (int i = 0; i<nt; i++) {
	if(maybe[i] == temp->trackNumber){
	maybe[i] = -1;
	cnt--;
	}
	}
	if (temp->next != NULL) {
	temp = temp->next;
	}else{
	dir = 0;
	temp = temp->prev;
	}
	if (ntCount > 0) {
	cout<<"Do you want to seek a track? [1/0] y/n "<<endl;
	int temptrack;
	cin>>temptrack;
	if (temptrack == 1) {
	for (int i = 0; i<nt; i++) {
	if (maybe[i] == -1) {
	cout<<"Enter track "<<endl;
	cin>>maybe[i];
	ntCount--;
	break;
	}
	}
	}
	}
	cout<<"Current "<<temp->trackNumber<<endl;
	}
	}
	}

view raw scan.cpp hosted with ❤ by GitHub

Written by , Sarvesh Bhatnagar