Elevators Algorithm(LOOK)

Elevators Algorithm

LOOK

Elevators algorithm is another disk scheduling algorithm, as the name suggest its roots lay in the working of an elevator. i.e,  Once started it traverse in the same direction, being said that there are various modifications of an elevators algorithm and we will look at four of them.

In this post we will see LOOK algorithm, with complete cpp code of stimulation of LOOK algorithm. 

Look is a simple algorithm which simply does a scan and until it reaches current end of the request at one end it keeps moving the head and if there are no more request pending ahead it changes its direction. When there are no request left, we will terminate.

Modifications:

• SCAN
• LOOK

LOOK

Look is a simple algorithm which uses concept similar to SCAN algorithm. In LOOK algorithm, we scan until we reach the last request at that end (NOTE: We do not proceed further until the tape ends) and then we turn our tape head to the other direction and do the same in that direction. When we reach a point where the request halts, we will terminate our stimulation for the reasons of making our stimulation simpler.

Note: In the above diagram, we are giving minimum priority for terminating the program. i.e. IF min!= -1 would be checked first rather than IF min == -1.

Suppose, We have head pointing at position X and we choose the direction to be right then the algorithm for LOOK would be given as follows:

• Till we reach Maximum request move Right and keep updating.(IF reached max := -1)
• IF minimum exists, change state to S2. Else STOP
• When at state S2, Till we reach minimum request, move Left and keep updating.(IF reached min := -1).
• IF maximum exists, change state to S1. Else STOP.

Simple Logic:

1. Move towards max
2. update if new request
3. change direction
4. move to min
5. update if new request
6. LOOP

CPP code for LOOK:

	//
	// main.cpp
	// Elevator-LOOK stimulation
	// Created by Sarvesh Bhatnagar on 21/05/18.
	// Copyright © 2018 introtoalgo.com. All rights reserved.
	//
	/*
	This Program is a stimulation of Look algorithm, one can modify it as per required to
	make it a SCAN, CSCAN or a CLOOK stimulation.
	*/
	#include <iostream>
	using namespace std;
	int countNo = 1;
	struct Track{
	int trackNumber;
	struct Track *prev = NULL;
	struct Track *next = NULL;
	};
	struct Track *last, *temp, *head;
	void makeTrack();
	void setHeadPos(int headPos);
	void look();
	int maxOf(int a[],int num);
	int minOf(int a[],int num);
	void checkCurrentHeadAndTrack(int number,int a[],int n);
	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();
	look();
	return 0;
	}
	void makeTrack(){
	temp = new Track();
	temp->trackNumber = countNo;
	countNo ++;
	if (last == NULL) {
	last = temp;
	}else{
	last->next = temp;
	temp->prev = last;
	last = temp;
	}
	}
	void setHeadPos(int headPos){
	temp = last;
	for (int i = 0; i<headPos; i++) {
	temp = temp->prev;
	}
	head = temp;
	}
	void look(){
	int max,min;
	cout<<"Enter number of tracks to be seeked "<<endl;
	int numberOfTrackToBeSeeked;
	cin>>numberOfTrackToBeSeeked;
	cout<<"Enter all the tracks "<<endl;
	int i = 0;
	int arr[numberOfTrackToBeSeeked];
	while (i<numberOfTrackToBeSeeked) {
	cin>>arr[i];
	i++;
	}
	max = maxOf(arr,numberOfTrackToBeSeeked);
	min = minOf(arr,numberOfTrackToBeSeeked);
	cout<<"Choose a direction (L/R)(0/1)"<<endl;
	cin>>i;
	checkCurrentHeadAndTrack(head->trackNumber,arr,numberOfTrackToBeSeeked);
	if (i==0) {
	while (head->trackNumber != min) {
	cout<<"PREV "<<head->trackNumber;
	head = head->prev;
	cout<<"Current "<<head->trackNumber;
	checkCurrentHeadAndTrack(head->trackNumber,arr,numberOfTrackToBeSeeked);
	}
	min = -1;
	while (head->trackNumber != max) {
	cout<<"PREV "<<head->trackNumber;
	head = head->next;
	cout<<"Current "<<head->trackNumber;
	checkCurrentHeadAndTrack(head->trackNumber,arr,numberOfTrackToBeSeeked);
	}
	max = -1;
	}else{
	while (head->trackNumber != max) {
	cout<<"PREV "<<head->trackNumber;
	head = head->next;
	cout<<"Current "<<head->trackNumber;
	checkCurrentHeadAndTrack(head->trackNumber,arr,numberOfTrackToBeSeeked);
	}
	max = -1;
	while (head->trackNumber != min) {
	cout<<"PREV "<<head->trackNumber;
	head = head->prev;
	cout<<"Current "<<head->trackNumber;
	checkCurrentHeadAndTrack(head->trackNumber,arr,numberOfTrackToBeSeeked);
	}
	min = -1;
	}
	}
	int maxOf(int a[],int num){
	int temp = a[0];
	for (int i = 0; i<num; i++) {
	if (a[i] > temp) {
	temp = a[i];
	}
	}
	return temp;
	}
	int minOf(int a[],int num){
	int temp = a[0];
	for (int i = 0; i<num; i++) {
	if (a[i] < temp) {
	temp = a[i];
	}
	}
	return temp;
	}
	void checkCurrentHeadAndTrack(int number,int a[],int n){
	for (int i = 0; i<n; i++) {
	if (number == a[i]) {
	cout<<"PROCESSED "<<number;
	a[i] = -1;
	}
	}
	}

view raw Look.cpp hosted with ❤ by GitHub

Written By, Sarvesh Bhatnagar

 You may also like 

SCAN

Flow Shop Scheduling

Interval Scheduling