1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 |
#include <iostream> #include <vector> #include <algorithm> #include <cmath> class DiskScheduler { public: // FCFS Algorithm int FCFS(const std::vector<int>& requests, int head) { int seek_operations = 0; int current_position = head; for (int request : requests) { seek_operations += std::abs(current_position - request); current_position = request; } return seek_operations; } // SSTF Algorithm int SSTF(std::vector<int> requests, int head) { int seek_operations = 0; int current_position = head; while (!requests.empty()) { auto closest = std::min_element(requests.begin(), requests.end(), [¤t_position](int a, int b) { return std::abs(a - current_position) < std::abs(b - current_position); }); seek_operations += std::abs(current_position - *closest); current_position = *closest; requests.erase(closest); } return seek_operations; } // SCAN (Elevator) Algorithm int SCAN(std::vector<int> requests, int head, int disk_size) { int seek_operations = 0; int current_position = head; std::sort(requests.begin(), requests.end()); // Split requests into those less than and greater than the current head position std::vector<int> left, right; for (int request : requests) { if (request < current_position) left.push_back(request); else right.push_back(request); } // Scan to the right (towards the end of the disk) for (int request : right) { seek_operations += std::abs(current_position - request); current_position = request; } // Then scan to the left (towards the beginning of the disk) if (!left.empty()) { seek_operations += std::abs(current_position - disk_size); current_position = disk_size; for (auto it = left.rbegin(); it != left.rend(); ++it) { seek_operations += std::abs(current_position - *it); current_position = *it; } } return seek_operations; } }; int main() { DiskScheduler scheduler; int head, disk_size, num_requests; std::cout << "Enter initial head position: "; std::cin >> head; std::cout << "Enter disk size: "; std::cin >> disk_size; std::cout << "Enter number of requests: "; std::cin >> num_requests; std::vector<int> requests(num_requests); std::cout << "Enter the requests: "; for (int i = 0; i < num_requests; ++i) { std::cin >> requests[i]; } int fcfs_seek = scheduler.FCFS(requests, head); int sstf_seek = scheduler.SSTF(requests, head); int scan_seek = scheduler.SCAN(requests, head, disk_size); std::cout << "Total seek operations (FCFS): " << fcfs_seek << "\n"; std::cout << "Total seek operations (SSTF): " << sstf_seek << "\n"; std::cout << "Total seek operations (SCAN): " << scan_seek << "\n"; return 0; } |
Explanation
- DiskScheduler Class:
- This class contains implementations for the FCFS, SSTF, and SCAN (Elevator) disk scheduling algorithms.
- Each algorithm is implemented as a member function returning the total number of seek operations required.
- FCFS Algorithm:
- The
FCFS
function implements the First-Come, First-Served algorithm. It processes each request in the order received and calculates the total seek time. - This algorithm is straightforward but can lead to high seek times if requests are far apart.
- The
- SSTF Algorithm:
- The
SSTF
function implements the Shortest Seek Time First algorithm. It selects the request that is closest to the current head position, minimizing seek time at each step. - This algorithm reduces seek time but can cause starvation for requests that are far from the current head position.
- The
- SCAN Algorithm:
- The
SCAN
function simulates the Elevator algorithm, where the disk arm moves in one direction, fulfilling requests until it reaches the end, then reverses direction. - This algorithm reduces the variance in seek time and is more efficient than FCFS in most cases.
- The
- Main Function:
- The main function prompts the user for the initial head position, disk size, and a list of disk requests.
- It then calculates the total seek operations for each algorithm and displays the results.
Usage
- Initial Head Position: The starting position of the disk head.
- Disk Size: The total size of the disk, which defines the maximum possible request position.
- Requests: A series of disk I/O requests, each representing a position on the disk where data needs to be read or written.