Disk Scheduling: FCFS and SSTF

Given Data

• Cylinder range: 0 to 199
• Current head position: 143
• Request queue (FIFO): 25, 17, 119, 197, 194, 15, 182, 115, 183

a) FCFS (First Come First Served)

Service order: 143 → 25 → 17 → 119 → 197 → 194 → 15 → 182 → 115 → 183

$$\text{Total} = 118+8+102+78+3+179+167+67+68 = 790$$

FCFS total head movement = 790 cylinders

b) SSTF (Shortest Seek Time First)

Always move to the nearest pending request.

At every step the head jumps to whichever pending cylinder is closest, so the distances to all remaining requests are compared before each move.

Service order: 143 → 119 → 115 → 182 → 183 → 194 → 197 → 25 → 17 → 15

$$\text{Total} = 24+4+67+1+11+3+172+8+2 = 292$$

SSTF total head movement = 292 cylinders

Note that 119 has to be taken before 115, since $|143-119| = 24$ is smaller than $|143-115| = 28$. Servicing 115 first would violate the shortest-seek rule even though the two requests sit close together.

Summary

SSTF greatly reduces head movement versus FCFS, at the risk of starvation for distant requests.

Process and 3-State Process Model

What is a Process?

A process is a program in execution. It is an active entity that requires resources such as CPU time, memory, files, and I/O devices to accomplish its task. A process is more than just program code (text section); it also includes the current activity represented by the value of the program counter, processor registers, stack, and data section.

In simple terms: Program + Execution State = Process

3-State Process Model

As a process executes, it moves through different states. In the 3-state (three-state) process model, a process can be in one of the following three states:

States

State Transition Diagram

         Dispatch
  +--------->---------+
  |                   |
  |                   v
READY              RUNNING
  ^                   |
  |      Timeout/     |
  +-------<-----------+
  (Preempt)           |
                      | Wait for
                      | I/O or Event
                      v
                  BLOCKED
                      |
                      | I/O or Event
                      | Completes
                      |
                      +--------->-----> READY

Explanation of Transitions

1. Ready → Running (Dispatch)

   • The OS scheduler selects the process from the ready queue and assigns the CPU to it.

2. Running → Ready (Timeout / Preemption)

   • The running process is preempted because its time slice (quantum) has expired, or a higher-priority process becomes ready. The process goes back to the ready queue.

3. Running → Blocked (Wait for I/O or Event)

   • The running process requests an I/O operation or waits for an event (e.g., reading from disk). Since it cannot continue, it moves to the blocked state.

4. Blocked → Ready (I/O or Event Completes)

   • When the awaited I/O or event is complete, the process moves back to the ready state and waits for CPU allocation.

Key Points

• Only one process can be in the Running state at a time on a single-processor system.
• Multiple processes can be in the Ready or Blocked state simultaneously.
• A process never goes directly from Blocked to Running; it must pass through Ready first.
• This model forms the foundation for more complex models (5-state, 7-state models).