Disk Scheduling- FCFS, SCAN,C-SCAN



Disk scheduling algorithms are used by the operating system to manage requests for accessing disk blocks efficiently. When multiple requests are made to read or write data on a disk, the operating system must decide in what order to service these requests. Disk scheduling algorithms help in optimizing this process by minimizing seek time (the time taken to position the disk's read/write head over the desired track) and rotational latency (the time taken for the desired sector to rotate under the disk's read/write head).

Here are some common disk scheduling algorithms:

First-Come, First-Served (FCFS):Requests are served in the order they arrive. Simple and fair, but can result in poor performance due to high seek times, especially if there's a mix of near and far tracks.
  • The simplest algorithm where requests are addressed in the order they arrive in the disk queue.
  • Requests are served sequentially without considering their location on the disk.
  • Example: Suppose we have requests (82, 170, 43, 140, 24, 16, 190) with the current head position at 50. The total overhead movement is 692
Shortest Seek Time First (SSTF):The request with the shortest seek time from the current head position is serviced next. This reduces the overall seek time, but can lead to starvation of requests that are far from the current head position.
  • Chooses the request closest to the current head position.
  • Minimizes seek time by selecting the shortest seek distance.
  • Example: If we apply SSTF to the same requests, the total overhead movement would be different.
SCAN (Elevator):The disk arm moves in one direction, serving requests along the way until it reaches the end of the disk, then it reverses direction. This mimics the movement of an elevator, hence the name. It prevents starvation and reduces average seek time.
  • Moves the head in one direction (e.g., from outer track to inner track) and services requests along the way.
  • When it reaches the end, it reverses direction.
  • Example: SCAN would handle the requests differently, scanning back and forth.
C-SCAN(Circular):Similar to SCAN, but the arm only moves in one direction, servicing requests until it reaches the end of the disk and then "wraps around" to the beginning of the disk. This can lead to a more uniform wait time for requests.
  • Treats the disk track as a circular buffer.
  • Moves the head in one direction, but when it reaches the end, it jumps to the other end.
  • Example: C-SCAN would exhibit circular behavior.
Different algorithms have their own strengths and weaknesses, and the choice of which to use depends on factors such as workload characteristics, system requirements, and hardware constraints.

Here's a simple example of the First-Come, First-Served (FCFS) disk scheduling algorithm implemented in C. In this example, we'll simulate disk requests as track numbers and assume that the disk arm starts at track 0. We'll calculate the total seek time needed to service all requests.

//*************************************************
// C program Implementation-FCFS
//*************************************************
#include <stdio.h>
#include <stdlib.h>

#define MAX_REQUESTS 100

// Function to calculate total seek time using FCFS algorithm
int calculateTotalSeekTime(int *requests, int numRequests) {
    int totalSeekTime = 0;
    int currentTrack = 0; // Start at track 0

    // Iterate through each request
    for (int i = 0; i < numRequests; i++) {
        // Calculate seek time for current request
        int seekTime = abs(currentTrack - requests[i]);
        
        // Update current track to the requested track
        currentTrack = requests[i];

        // Add seek time for this request to total seek time
        totalSeekTime += seekTime;
    }

    return totalSeekTime;
}

int main() {
    int requests[MAX_REQUESTS];
    int numRequests;

    // Input number of disk requests
    printf("Enter the number of disk requests: ");
    scanf("%d", &numRequests);

    if (numRequests <= 0 || numRequests > MAX_REQUESTS) {
        printf("Invalid number of requests.\n");
        return 1;
    }

    // Input disk requests
    printf("Enter the disk requests (track numbers):\n");
    for (int i = 0; i < numRequests; i++) {
        scanf("%d", &requests[i]);
    }

    // Calculate and print total seek time
    int totalSeekTime = calculateTotalSeekTime(requests, numRequests);
    printf("Total seek time using FCFS: %d\n", totalSeekTime);

    return 0;
}

Enter the number of disk requests: 7
Enter the disk requests (track numbers):
82
170
43
140
24
16
190
Total seek time using FCFS: 692

Below is a simple implementation of the SCAN disk scheduling algorithm in C. In this implementation, we assume that the disk arm starts at track 0 and moves towards the maximum track number, serving requests along the way. When it reaches the end, it changes direction and starts moving towards track 0 again, serving any pending requests.

//*************************************************
// C Program Implementation-SCAN
//*************************************************
#include <stdio.h>
#include <stdlib.h>

#define MAX_REQUESTS 100

// Function to calculate total seek time using SCAN algorithm
int calculateTotalSeekTime(int *requests, int numRequests) {
    int totalSeekTime = 0;
    int currentTrack = 0; // Start at track 0
    int direction = 1; // Initial direction: 1 (towards higher tracks)

    // Iterate through each request
    for (int i = 0; i < numRequests; i++) {
        // Scan in the current direction until the end of the disk
        while (currentTrack >= 0 && currentTrack <= 199) {
            // Check if the current request lies on the current track
            if (requests[i] == currentTrack) {
                totalSeekTime += abs(currentTrack - requests[i]); // Add seek time
                requests[i] = -1; // Mark request as serviced
                break; // Move to next request
            }
            // Move the disk arm in the current direction
            currentTrack += direction;
            totalSeekTime++; // Increment total seek time
        }

        // Change direction if necessary
        if (currentTrack == 200) {
            direction = -1; // Change direction to towards lower tracks
            currentTrack = 199; // Move to the highest track
        } else if (currentTrack == -1) {
            direction = 1; // Change direction to towards higher tracks
            currentTrack = 0; // Move to the lowest track
        }
    }

    return totalSeekTime;
}

int main() {
    int requests[MAX_REQUESTS];
    int numRequests;

    // Input number of disk requests
    printf("Enter the number of disk requests: ");
    scanf("%d", &numRequests);

    if (numRequests <= 0 || numRequests > MAX_REQUESTS) {
        printf("Invalid number of requests.\n");
        return 1;
    }

    // Input disk requests
    printf("Enter the disk requests (track numbers):\n");
    for (int i = 0; i < numRequests; i++) {
        scanf("%d", &requests[i]);
    }

    // Calculate and print total seek time
    int totalSeekTime = calculateTotalSeekTime(requests, numRequests);
    printf("Total seek time using SCAN: %d\n", totalSeekTime);

    return 0;
}
Enter the number of disk requests: 7
Enter the disk requests (track numbers):
82
170
43
140
24
16
190
Total seek time using SCAN: 400

Below is a simple implementation of the C-SCAN (Circular SCAN) disk scheduling algorithm in C. C-SCAN is a variant of SCAN where the disk arm only scans in one direction, serving requests until it reaches the end of the disk and then "wraps around" to the beginning of the disk.

//*************************************************
// C Program Implementation-C-SCAN
//************************************************

#include <stdio.h>
#include <stdlib.h>

#define MAX_REQUESTS 100

// Function to calculate total seek time using C-SCAN algorithm
int calculateTotalSeekTime(int *requests, int numRequests) {
    int totalSeekTime = 0;
    int currentTrack = 0; // Start at track 0
    int direction = 1; // Initial direction: towards higher tracks

    // Sort requests in ascending order
    for (int i = 0; i < numRequests - 1; i++) {
        for (int j = 0; j < numRequests - i - 1; j++) {
            if (requests[j] > requests[j + 1]) {
                int temp = requests[j];
                requests[j] = requests[j + 1];
                requests[j + 1] = temp;
            }
        }
    }

    // Iterate through each request
    for (int i = 0; i < numRequests; i++) {
        // Scan in the current direction until the end of the disk
        while (currentTrack >= 0 && currentTrack <= 199) {
            // Check if the current request lies on the current track
            if (requests[i] == currentTrack) {
                totalSeekTime += abs(currentTrack - requests[i]); // Add seek time
                requests[i] = -1; // Mark request as serviced
                break; // Move to next request
            }
            // Move the disk arm in the current direction
            currentTrack += direction;
            totalSeekTime++; // Increment total seek time
        }

        // If reached the end of the disk, wrap around to the beginning
        if (currentTrack == 200) {
            currentTrack = 0;
            direction = 1; // Move towards higher tracks
        }
    }

    return totalSeekTime;
}

int main() {
    int requests[MAX_REQUESTS];
    int numRequests;

    // Input number of disk requests
    printf("Enter the number of disk requests: ");
    scanf("%d", &numRequests);

    if (numRequests <= 0 || numRequests > MAX_REQUESTS) {
        printf("Invalid number of requests.\n");
        return 1;
    }

    // Input disk requests
    printf("Enter the disk requests (track numbers):\n");
    for (int i = 0; i < numRequests; i++) {
        scanf("%d", &requests[i]);
    }

    // Calculate and print total seek time
    int totalSeekTime = calculateTotalSeekTime(requests, numRequests);
    printf("Total seek time using C-SCAN: %d\n", totalSeekTime);

    return 0;
}
Enter the number of disk requests: 7
Enter the disk requests (track numbers):
82
170
43
140
24 
16
190
Total seek time using C-SCAN: 190

Comments

Post a Comment

Popular posts from this blog

CSL 204 OPERATING SYSTEM LAB KTU IV SEM CSE

About Me Syllabus Scheme Program List Linux Basics 1. Linux History and GNU 2. Linux Basic Features and Architecture 3. How to Install Linux 4. Install Linux Inside Windows using WSL 5. Free software 6. Linux Chronology 7 .Package Management 8 .Compile and install from source 9 .Important Directories 10. File Permissions 11. Special Permissions 12 .Shell 13. Bash shell in windows 10 14 .Basic Linux command for beginners 15. Input Output Redirection  16. Directory Commands 17. File Commands 18 .Communication Commands 19. Information Commands  20 .IO Commands   21 .Process Management Commands 22. Account Administration Commands 23. Pipes and Filters  24. Top 100 commands to learn. Shell Programming 1. Shell Script 2. Arithmetic Expressions 3. Special Shell Variables 4. Shell Script for getting important info 5. if and case statement 6. looping statements while,until,for 7. Menu driven Programs 8. GUI Menus 9. Functions in scripts 10. String Handling 11. Command line arguments in scripts
Read more

FCFS and SJF

Image
CPU Scheduling in Operating Systems: In the context of operating systems, CPU scheduling involves determining which process (or task) should be executed next by the central processing unit (CPU). The goal is to maximize CPU utilization, minimize waiting time, and ensure fair allocation of resources. Various scheduling algorithms are used to achieve these objectives. First-Come-First-Serve (FCFS) Scheduling: Definition: FCFS is the simplest CPU scheduling algorithm. It is non-preemptive, meaning once a process starts executing, it cannot be interrupted until completion. Processes are placed in a queue based on their arrival time. The process that arrives first gets executed first. Execution Order : Processes are executed in the order they arrive. The process at the front of the queue is selected for execution. Advantages: Easy to implement. Minimal overhead. Disadvantages: Often results in long waiting times. Leads to the convoy effect (where a long process holds up other processes). Sh
Read more

Shared Memory Inter-Process Communication ( IPC)

Shared memory Inter-Process Communication (IPC) in Linux allows processes to communicate by sharing a region of memory. This method is efficient because it avoids the overhead of copying data between processes. Here's how shared memory IPC is typically done in Linux: Create a Shared Memory Segment: To use shared memory IPC, you need to create a shared memory segment. This is done using the shmget() system call, which allocates a new shared memory segment or obtains the identifier of an existing one. You specify the size of the shared memory segment and some permissions. Attach the Shared Memory Segment: Once you have obtained the identifier for the shared memory segment, you need to attach it to the address space of your process. This is done using the shmat() system call. This call returns the address of the shared memory segment in your process's address space. Accessing the Shared Memory: After attaching the shared memory segment to your process's address space, you c
Read more