First-Come, First-Served (FCFS) Scheduling

Overview:

First-Come, First-Served (FCFS) is one of the simplest types of CPU scheduling algorithms. It operates in a straightforward manner where the process that arrives first is served first. It is non-preemptive, meaning once a process starts its execution, it runs to completion.

Key Characteristics:

Non-preemptive scheduling.
Processes are executed in the order of their arrival.
Simple and easy to implement.
Can lead to the "convoy effect," where shorter processes wait for longer ones to complete.

Advantages:

Easy to understand and implement.
Fair in the sense that it serves requests in the order they arrive.

Disadvantages:

Not optimal for time-sharing systems.
Can cause high waiting times, especially for short processes following long ones.

Use Cases:

Batch systems where turnaround time is the main focus.
Situations where process execution order is not critical.

Example 1: Simple FCFS Scheduling

Consider three processes arriving in the order P1, P2, P3 with burst times 5, 9, and 2 respectively.


        Process   Burst Time   Completion Time
        P1        5            5
        P2        9            14
        P3        2            16

Explanation:

- P1 starts at 0 and finishes at 5.

- P2 starts after P1 finishes, at 5, and completes at 14.

- P3 starts at 14 and ends at 16.

Example 2: FCFS with Convoy Effect

Consider processes P1, P2, P3 with burst times 10, 1, and 2 arriving in that order.


        Process   Burst Time   Completion Time
        P1        10           10
        P2        1            11
        P3        2            13

Explanation:

- P1 holds the CPU for 10 units, causing P2 and P3 to wait.

- P2, despite its short burst time, waits for P1 to finish.

- This demonstrates the convoy effect, where shorter processes wait for longer ones to complete.

Example 3: Fairness in FCFS

Consider processes P1, P2, P3 arriving in the sequence and having equal burst times of 4.


        Process   Burst Time   Completion Time
        P1        4            4
        P2        4            8
        P3        4            12

Explanation:

- Each process gets an equal share of CPU time in the order they arrive.

- Demonstrates fairness as each process is treated equally with respect to its arrival order.

Example 4: FCFS in Batch Systems

In batch processing systems, FCFS can be used to manage jobs in the order they arrive.


        Job       Arrival Time   Burst Time   Completion Time
        J1        0              5            5
        J2        1              3            8
        J3        2              1            9

Explanation:

- Jobs are processed in the order they arrive, ensuring a simple and straightforward execution flow.

- Suitable for environments where job priority is not critical.

Example 5: FCFS in Non-Critical Systems

In systems where timing is not critical, FCFS can be applied to manage processes efficiently.


        Process   Arrival Time   Burst Time   Completion Time
        P1        0              6            6
        P2        2              3            9
        P3        4              2            11

Explanation:

- Processes are handled in the order they arrive, which is suitable for non-critical applications.

- Ensures a straightforward handling of tasks without complex scheduling mechanisms.