Created
September 15, 2020 14:58
-
-
Save omar-faruk/ee29fcab474bfdf9122476a720e724f2 to your computer and use it in GitHub Desktop.
SCAN disk scheduling algorithm
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <bits/stdc++.h> | |
| #include <pthread.h> | |
| #include <unistd.h> | |
| #define DISK_SIZE 512 | |
| using namespace std; | |
| //SCAN ALGORITHM IS LIKE SSTF (Shortest Seek Time First) | |
| //WE need 2 min heap to pop items in sorted order | |
| priority_queue <int, vector<int>, greater<int> > to_higher; | |
| priority_queue <int, vector<int>, less<int> > to_lower; | |
| //queue<int>to_higher,to_lower; | |
| /********************************/ | |
| //SHARED RESOURCE BETWEEN THREADS | |
| //REQUIRE THREAD SAFE ACCESS | |
| int curr_elem,last_elem; | |
| string current_direction; | |
| /*********************************/ | |
| mutex m; | |
| void * AddRequest(void *) | |
| { | |
| int loc,total=0; | |
| int sequence[20]; | |
| //cout<<"AddRequest Handler"<<endl; | |
| for(;;) | |
| { | |
| total = 0; | |
| while(scanf("%d",&loc)) | |
| { | |
| if(loc == -1){ | |
| break; | |
| } | |
| sequence[total++]=loc; | |
| } | |
| m.lock(); | |
| for(int i=0;i<total;i++){ | |
| if(sequence[i] < curr_elem){ | |
| to_lower.push(sequence[i]); | |
| } | |
| } | |
| for(int i=0;i<total;i++){ | |
| if(sequence[i] > curr_elem){ | |
| to_higher.push(sequence[i]); | |
| } | |
| } | |
| m.unlock(); | |
| } | |
| } | |
| void * ProcessRequest(void * init_pos) | |
| { | |
| cout<<"Request Handler"<<endl; | |
| last_elem = *((int *)init_pos); | |
| cout<<"Starting Position: "<<last_elem<<endl; | |
| int sum=0; | |
| for(;;) | |
| { | |
| if(current_direction=="to_higher" && !to_higher.empty()){ | |
| cout<<endl; | |
| cout<<"<----------PROCESSING ELEMENTS TO HIGHER DIRECTION--------->"<<endl; | |
| while(!to_higher.empty()){ | |
| m.lock(); | |
| curr_elem = to_higher.top(); | |
| to_higher.pop(); | |
| cout<<"Location: "<<curr_elem; | |
| if(curr_elem == DISK_SIZE){ | |
| cout<<"<----End of DISK Size, Reversing Rotation ---->"<<endl; | |
| } | |
| sum += curr_elem - last_elem; | |
| last_elem = curr_elem; | |
| if(to_higher.empty() && curr_elem != DISK_SIZE){ | |
| //add last node of disk to travarse while traversing upwards | |
| to_higher.push(DISK_SIZE); | |
| } | |
| m.unlock(); | |
| cout<<" Total Seek: "<<sum<<endl<<endl; | |
| sleep(3); | |
| } | |
| m.lock(); | |
| current_direction = "to_lower"; | |
| m.unlock(); | |
| } | |
| if(current_direction=="to_lower" && !to_lower.empty()){ | |
| cout<<endl; | |
| cout<<"<----------PROCESSING ELEMENTS TO LOWER DIRECTION--------->"<<endl; | |
| while(!to_lower.empty()){ | |
| m.lock(); | |
| curr_elem = to_lower.top(); | |
| to_lower.pop(); | |
| cout<<"Location: "<<curr_elem; | |
| if(curr_elem == 0){ | |
| cout<<"<----End of DISK, Reversing Rotation---->"<<endl; | |
| } | |
| sum += last_elem - curr_elem; | |
| last_elem = curr_elem; | |
| if(curr_elem !=0 && to_lower.empty()){ | |
| //add first node of disk to travarse while traversing downwards | |
| to_lower.push(0); | |
| } | |
| m.unlock(); | |
| cout<<" Total Seek: "<<sum<<endl<<endl; | |
| sleep(3); | |
| } | |
| m.lock(); | |
| current_direction = "to_higher"; | |
| m.unlock(); | |
| } | |
| } | |
| } | |
| int main() | |
| { | |
| pthread_t pid1,pid2; | |
| int initial_sequence[10] = {50,176,79,34,60,92,11,41,114,118}; | |
| int min=9999,max=-1; | |
| current_direction = "to_lower"; | |
| cout<<"To Lower"<<endl; | |
| for(int i=1;i<10;i++){ | |
| if(initial_sequence[i]<initial_sequence[0]){ | |
| to_lower.push(initial_sequence[i]); | |
| cout<<initial_sequence[i]<<" "; | |
| } | |
| } | |
| to_lower.push(0); | |
| cout<<endl; | |
| cout<<"To Higher"<<endl; | |
| for(int i=1;i<10;i++) | |
| { | |
| if(initial_sequence[i]>initial_sequence[0]){ | |
| to_higher.push(initial_sequence[i]); | |
| cout<<initial_sequence[i]<<" "; | |
| } | |
| } | |
| to_higher.push(DISK_SIZE); | |
| cout<<endl<<endl; | |
| pthread_create(&pid1,NULL,&ProcessRequest,(void *)&initial_sequence[0]); | |
| pthread_create(&pid2,NULL,&AddRequest,NULL); | |
| while(1){ | |
| } | |
| return 0; | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment