LIFO (Last In, First Out) is a simple disk scheduling algorithm where the most recently received disk request is serviced first, regardless of its location on the disk. It operates like a stack data structure, where requests are processed in the reverse order of their arrival.
How LIFO Works
The LIFO disk scheduling algorithm is conceptually simple but rarely used in practice due to its potential inefficiency. It prioritizes recent requests over older ones without considering the disk head's current position.
The algorithm follows these steps:
- New disk requests are added to a stack data structure
- The request at the top of the stack (the most recently arrived request) is serviced first
- After servicing a request, the next request at the top of the stack is processed
- This continues until all requests are handled or a new request arrives
Example Calculation
Let's say we have a disk with 200 cylinders (0-199), and the head is currently at position 50. The request queue is:
| Request Arrival Order | 1st | 2nd | 3rd | 4th | 5th | 6th | 7th |
|---|---|---|---|---|---|---|---|
| Cylinder Number | 95 | 180 | 34 | 119 | 11 | 123 | 62 |
The LIFO algorithm will process these requests in reverse order of arrival:
| Requests Processed by LIFO Algorithm (Initial Position: 50) | ||||||
|---|---|---|---|---|---|---|
| 62 | 123 | 11 | 119 | 34 | 180 | 95 |
The head movements will be:
| Head Movement | |50-62| | |62-123| | |123-11| | |11-119| | |119-34| | |34-180| | |180-95| |
|---|---|---|---|---|---|---|---|
| Distance | 12 | 61 | 112 | 108 | 85 | 146 | 85 |
Total head movement = 12 + 61 + 112 + 108 + 85 + 146 + 85 = 609 cylinders
Advantages
- Very simple to implement and understand
- Low computational overhead for determining the next request to service
- Can prioritize recent requests, which might be beneficial in some specific workloads
- No starvation for new requests (they get serviced immediately)
Disadvantages
- Typically results in higher total seek distance compared to other algorithms
- Can cause starvation for older requests that remain at the bottom of the stack
- Ignores the current position of the disk head, leading to inefficient movements
- No consideration for spatial locality of requests, which can increase seek time
- Poor performance for most real-world disk workloads
Comparison with Other Algorithms
- FCFS (First Come, First Served): Unlike LIFO, FCFS processes requests in the order they arrive, which is more fair but still does not optimize seek time
- SSTF (Shortest Seek Time First): Prioritizes the request closest to the current head position, which is typically more efficient than LIFO
- SCAN and C-SCAN: These algorithms move the head in a systematic manner to reduce overall seek time, unlike the random movements that can occur with LIFO
- LOOK and C-LOOK: Variants of SCAN and C-SCAN that are typically more efficient than LIFO
Use Cases
LIFO is rarely used in production disk scheduling systems due to its inefficiency and potential for starvation. However, it might be used in:
- Educational contexts to demonstrate suboptimal scheduling algorithms
- Systems where the most recent requests are consistently more important than older ones
- Simple embedded systems with minimal disk access patterns