SCAN (Elevator’s Algorithm):
// C++ program to demonstrate
// SCAN Disk Scheduling algorithm
#include <bits/stdc++.h>
using namespace std;
int size = 8;
int disk_size = 200;
void SCAN(int arr[], int head, string direction)
{
int seek_count = 0;
int distance, cur_track;
vector<int> left, right;
vector<int> seek_sequence;
// appending end values
// which has to be visited
// before reversing the direction
if (direction == "left")
left.push_back(0);
else if (direction == "right")
right.push_back(disk_size - 1);
for (int i = 0; i < size; i++) {
if (arr[i] < head)
left.push_back(arr[i]);
if (arr[i] > head)
right.push_back(arr[i]);
}
// sorting left and right vectors
std::sort(left.begin(), left.end());
std::sort(right.begin(), right.end());
// run the while loop two times.
// one by one scanning right
// and left of the head
int run = 2;
while (run--) {
if (direction == "left") {
for (int i = left.size() - 1; i >= 0; i--) {
cur_track = left[i];
// appending current track to seek sequence
seek_sequence.push_back(cur_track);
// calculate absolute distance
distance = abs(cur_track - head);
// increase the total count
seek_count += distance;
// accessed track is now the new head
head = cur_track;
}
direction = "right";
}
else if (direction == "right") {
for (int i = 0; i < right.size(); i++) {
cur_track = right[i];
// appending current track to seek sequence
seek_sequence.push_back(cur_track);
// calculate absolute distance
distance = abs(cur_track - head);
// increase the total count
seek_count += distance;
// accessed track is now new head
head = cur_track;
}
direction = "left";
}
}
cout << "Total number of seek operations = "
<< seek_count << endl;
cout << "Seek Sequence is" << endl;
for (int i = 0; i < seek_sequence.size(); i++) {
cout << seek_sequence[i] << endl;
}
}
// Driver code
int main()
{
// request array
int arr[size] = { 176, 79, 34, 60,
92, 11, 41, 114 };
int head = 50;
string direction = "left";
SCAN(arr, head, direction);
return 0;
}
Output
Total number of Seek Operations = 226
Seek Sequence: 41, 34, 11, 0, 60, 79, 92, 114, 176
Time Complexity: O(N * logN)
Auxiliary Space: O(N)
…………………______________________________
Optimal page replacement
#include <bits/stdc++.h>
using namespace std;
/*
predict() that takes a frame vector, index, and page array. It returns the predicted page.
*/
int predictPage(int page[], vector<int> &frames, int pageNumber, int pageIndex)
{
int result = -1, farthestPage = pageIndex;
for (int i = 0; i < frames.size(); i++)
{
int j;
for (j = pageIndex; j < pageNumber; j++)
{
if (frames[i] == page[j])
{
if (j > farthestPage)
{
farthestPage = j;
result = i;
}
break;
}
}
if (j == pageNumber)
return i;
}
if (result == -1)
return 0;
else
return result;
}
/*
boolSearch() that takes a frame vector, and a key that has to be searched in the frame. It return
true if the key is found else it returns false
*/
bool searchPage(int key, vector<int> &frames)
{
for (int i = 0; i < frames.size(); i++)
{
// if the frame is found, return true
if (frames[i] == key)
return true;
}
return false;
}
/*
find() that takes a page array, frame number, and page number. It finds and prints the page hits
and page misses.
*/
void find(int page[], int pageNumber, int frameNumber)
{
vector<int> frames;
int hit = 0;
for (int i = 0; i < pageNumber; i++)
{
if (searchPage(page[i], frames))
{
// if found, increment the hit counter
hit++;
continue;
}
if (frames.size() < frameNumber)
frames.push_back(page[i]);
else
{
int j = predictPage(page, frames, pageNumber, i + 1);
frames[j] = page[i];
}
}
// printing the hits and misses.
cout << "Page hits: " << hit << endl;
cout << "Page misses: " << pageNumber - hit << endl;
}
int main()
{
int page[] = {1, 7, 8, 3, 0, 2, 0, 3, 5, 4, 0, 6, 1};
int pageNumber = sizeof(page) / sizeof(page[0]);
int frameNumber = 3;
find(page, pageNumber, frameNumber);
return 0;
}
Output :
Page hits: 3
Page misses: 10
