WikiGalaxy

Personalize

Disk Scheduling Algorithms

Introduction to Disk Scheduling:

Disk scheduling algorithms are crucial for optimizing the performance of disk drives. They determine the order in which disk I/O requests are processed, thereby reducing seek time and improving throughput.

First-Come, First-Served (FCFS)

Overview:

FCFS is the simplest disk scheduling algorithm. Requests are processed in the order they arrive.

Easy to implement and understand.
Can lead to high average wait times.
Not optimal for minimizing seek time.


        // Example of FCFS Disk Scheduling
        import java.util.LinkedList;
        import java.util.Queue;

        class FCFSDiskScheduling {
            public static void main(String[] args) {
                int[] requests = {98, 183, 37, 122, 14, 124, 65, 67};
                int headStart = 53;
                fcfs(requests, headStart);
            }

            static void fcfs(int[] requests, int headStart) {
                int totalSeekTime = 0;
                int currentPosition = headStart;

                for (int request : requests) {
                    totalSeekTime += Math.abs(request - currentPosition);
                    currentPosition = request;
                }

                System.out.println("Total Seek Time: " + totalSeekTime);
            }
        }

Advantages:

Simple to implement and understand, making it a good choice for small systems.

Disadvantages:

High variance in response time; not efficient for large workloads.

Shortest Seek Time First (SSTF)

Overview:

SSTF selects the request closest to the current head position, minimizing seek time.

Reduces total seek time compared to FCFS.
Can cause starvation for some requests.


        // Example of SSTF Disk Scheduling
        import java.util.*;

        class SSTFDiskScheduling {
            public static void main(String[] args) {
                int[] requests = {98, 183, 37, 122, 14, 124, 65, 67};
                int headStart = 53;
                sstf(requests, headStart);
            }

            static void sstf(int[] requests, int headStart) {
                List requestList = new ArrayList<>();
                for (int request : requests) {
                    requestList.add(request);
                }

                int totalSeekTime = 0;
                int currentPosition = headStart;

                while (!requestList.isEmpty()) {
                    int closestRequest = findClosestRequest(requestList, currentPosition);
                    totalSeekTime += Math.abs(closestRequest - currentPosition);
                    currentPosition = closestRequest;
                    requestList.remove((Integer) closestRequest);
                }

                System.out.println("Total Seek Time: " + totalSeekTime);
            }

            static int findClosestRequest(List requests, int currentPosition) {
                int minDistance = Integer.MAX_VALUE;
                int closestRequest = -1;

                for (int request : requests) {
                    int distance = Math.abs(request - currentPosition);
                    if (distance < minDistance) {
                        minDistance = distance;
                        closestRequest = request;
                    }
                }
                return closestRequest;
            }
        }

Advantages:

Minimizes seek time effectively for most workloads.

Disadvantages:

Can lead to starvation of requests far from the current head position.

SCAN (Elevator Algorithm)

Overview:

The SCAN algorithm moves the disk arm across the disk, servicing requests in one direction before reversing.

Also known as the elevator algorithm.
Provides a more uniform wait time than SSTF.


        // Example of SCAN Disk Scheduling
        import java.util.*;

        class SCANDiskScheduling {
            public static void main(String[] args) {
                int[] requests = {98, 183, 37, 122, 14, 124, 65, 67};
                int headStart = 53;
                int diskSize = 200;
                scan(requests, headStart, diskSize);
            }

            static void scan(int[] requests, int headStart, int diskSize) {
                Arrays.sort(requests);
                int totalSeekTime = 0;
                int currentPosition = headStart;
                boolean directionUp = true;

                List requestList = new ArrayList<>();
                for (int request : requests) {
                    requestList.add(request);
                }

                while (!requestList.isEmpty()) {
                    int nextRequest = findNextRequest(requestList, currentPosition, directionUp);
                    if (nextRequest == -1) {
                        directionUp = !directionUp;
                        continue;
                    }
                    totalSeekTime += Math.abs(nextRequest - currentPosition);
                    currentPosition = nextRequest;
                    requestList.remove((Integer) nextRequest);
                }

                System.out.println("Total Seek Time: " + totalSeekTime);
            }

            static int findNextRequest(List requests, int currentPosition, boolean directionUp) {
                if (directionUp) {
                    for (int request : requests) {
                        if (request >= currentPosition) {
                            return request;
                        }
                    }
                } else {
                    for (int i = requests.size() - 1; i >= 0; i--) {
                        if (requests.get(i) <= currentPosition) {
                            return requests.get(i);
                        }
                    }
                }
                return -1;
            }
        }

Advantages:

Reduces variance in response time and avoids starvation.

Disadvantages:

May still have higher seek time compared to more advanced algorithms.

C-SCAN (Circular SCAN)

Overview:

C-SCAN treats the disk as a circular list that wraps around from the last cylinder to the first.

Provides a more uniform wait time than SCAN.
Reduces the variance in response time.


        // Example of C-SCAN Disk Scheduling
        import java.util.*;

        class CSCANDiskScheduling {
            public static void main(String[] args) {
                int[] requests = {98, 183, 37, 122, 14, 124, 65, 67};
                int headStart = 53;
                int diskSize = 200;
                cscan(requests, headStart, diskSize);
            }

            static void cscan(int[] requests, int headStart, int diskSize) {
                Arrays.sort(requests);
                int totalSeekTime = 0;
                int currentPosition = headStart;

                List requestList = new ArrayList<>();
                for (int request : requests) {
                    requestList.add(request);
                }

                while (!requestList.isEmpty()) {
                    int nextRequest = findNextRequest(requestList, currentPosition);
                    if (nextRequest == -1) {
                        totalSeekTime += (diskSize - 1 - currentPosition);
                        currentPosition = 0;
                        continue;
                    }
                    totalSeekTime += Math.abs(nextRequest - currentPosition);
                    currentPosition = nextRequest;
                    requestList.remove((Integer) nextRequest);
                }

                System.out.println("Total Seek Time: " + totalSeekTime);
            }

            static int findNextRequest(List requests, int currentPosition) {
                for (int request : requests) {
                    if (request >= currentPosition) {
                        return request;
                    }
                }
                return -1;
            }
        }

Advantages:

Provides a more uniform wait time for requests.

Disadvantages:

Can result in higher overall seek time compared to SCAN.

LOOK Algorithm

Overview:

The LOOK algorithm is similar to SCAN but does not go to the end of the disk unless there is a request.

Improves efficiency over SCAN by not going to the disk's end pointlessly.
Reduces unnecessary seek time.


        // Example of LOOK Disk Scheduling
        import java.util.*;

        class LOOKDiskScheduling {
            public static void main(String[] args) {
                int[] requests = {98, 183, 37, 122, 14, 124, 65, 67};
                int headStart = 53;
                look(requests, headStart);
            }

            static void look(int[] requests, int headStart) {
                Arrays.sort(requests);
                int totalSeekTime = 0;
                int currentPosition = headStart;
                boolean directionUp = true;

                List requestList = new ArrayList<>();
                for (int request : requests) {
                    requestList.add(request);
                }

                while (!requestList.isEmpty()) {
                    int nextRequest = findNextRequest(requestList, currentPosition, directionUp);
                    if (nextRequest == -1) {
                        directionUp = !directionUp;
                        continue;
                    }
                    totalSeekTime += Math.abs(nextRequest - currentPosition);
                    currentPosition = nextRequest;
                    requestList.remove((Integer) nextRequest);
                }

                System.out.println("Total Seek Time: " + totalSeekTime);
            }

            static int findNextRequest(List requests, int currentPosition, boolean directionUp) {
                if (directionUp) {
                    for (int request : requests) {
                        if (request >= currentPosition) {
                            return request;
                        }
                    }
                } else {
                    for (int i = requests.size() - 1; i >= 0; i--) {
                        if (requests.get(i) <= currentPosition) {
                            return requests.get(i);
                        }
                    }
                }
                return -1;
            }
        }

Advantages:

Reduces unnecessary head movement and improves efficiency.

Disadvantages:

Still can lead to starvation if not managed properly.

C-LOOK Algorithm

Overview:

C-LOOK is a variant of the LOOK algorithm that wraps around the end of the disk to the beginning.

Similar to C-SCAN but with more efficient seeking.
Reduces unnecessary seek time by wrapping only when necessary.


        // Example of C-LOOK Disk Scheduling
        import java.util.*;

        class CLOOKDiskScheduling {
            public static void main(String[] args) {
                int[] requests = {98, 183, 37, 122, 14, 124, 65, 67};
                int headStart = 53;
                clook(requests, headStart);
            }

            static void clook(int[] requests, int headStart) {
                Arrays.sort(requests);
                int totalSeekTime = 0;
                int currentPosition = headStart;

                List requestList = new ArrayList<>();
                for (int request : requests) {
                    requestList.add(request);
                }

                while (!requestList.isEmpty()) {
                    int nextRequest = findNextRequest(requestList, currentPosition);
                    if (nextRequest == -1) {
                        currentPosition = requestList.get(0);
                        continue;
                    }
                    totalSeekTime += Math.abs(nextRequest - currentPosition);
                    currentPosition = nextRequest;
                    requestList.remove((Integer) nextRequest);
                }

                System.out.println("Total Seek Time: " + totalSeekTime);
            }

            static int findNextRequest(List requests, int currentPosition) {
                for (int request : requests) {
                    if (request >= currentPosition) {
                        return request;
                    }
                }
                return -1;
            }
        }

Advantages:

Efficient for large workloads with uniformly distributed requests.

Disadvantages:

Can still lead to starvation for requests at the far ends.