Question

<Operating System>

1. Which scheduling objectives from module(CPU Scheduling) would also apply to disk scheduling?

2. Which disk scheduling algorithm is the most suitable for solid-state drives? Why?

Answer 1

1)

Disk scheduling is done by operating systems to schedule I/O requests arriving for the disk. Disk scheduling is also known as I/O scheduling.

Disk scheduling is important because:

• Multiple I/O requests may arrive by different processes and only one I/O request can be served at a time by the disk controller. Thus other I/O requests need to wait in the waiting queue and need to be scheduled.
• Two or more request may be far from each other so can result in greater disk arm movement.
• Hard drives are one of the slowest parts of the computer system and thus need to be accessed in an efficient manner.

There are many Disk Scheduling Algorithms but before discussing them let’s have a quick look at some of the important terms:

• Seek Time:Seek time is the time taken to locate the disk arm to a specified track where the data is to be read or write. So the disk scheduling algorithm that gives minimum average seek time is better.
• Rotational Latency: Rotational Latency is the time taken by the desired sector of disk to rotate into a position so that it can access the read/write heads. So the disk scheduling algorithm that gives minimum rotational latency is better.
• Transfer Time: Transfer time is the time to transfer the data. It depends on the rotating speed of the disk and number of bytes to be transferred.
• Disk Response Time: Response Time is the average of time spent by a request waiting to perform its I/O operation. Average Response time is the response time of the all requests. Variance Response Time is measure of how individual request are serviced with respect to average response time. So the disk scheduling algorithm that gives minimum variance response time is better.

• Disk Scheduling Algorithms

• FCFS: FCFS is the simplest of all the Disk Scheduling Algorithms. In FCFS, the requests are addressed in the order they arrive in the disk queue.

• Advantages:

• Every request gets a fair chance
• No indefinite postponement

• Disadvantages:

• Does not try to optimize seek time
• May not provide the best possible service
• SSTF: In SSTF (Shortest Seek Time First), requests having shortest seek time are executed first. So, the seek time of every request is calculated in advance in the queue and then they are scheduled according to their calculated seek time. As a result, the request near the disk arm will get executed first. SSTF is certainly an improvement over FCFS as it decreases the average response time and increases the throughput of system.

2)

FCFS Disk Head Scheduling Algorithm

It works well under light load (few storage disk accesses) and is the primary algorithm used with Solid-State Drives.

Linux provides several I/O schedulers that allow one to tune performance for your use patterns. Traditionally disk scheduling algorithms have been designed for rotational drives where rotational latency and drive head movement latency need to be taken into consideration, hence the need for complex I/O schedulers. However a SSD does not suffer from the HDD latency issues - does this mean the default I/O scheduler choice needs to be re-thought?

I decided to benchmark a SanDisk pSSD to see the behaviour of the different I/O schedulers using the following tests:

a) untar kernel source

b) sync

c) copy kernel source tree

d) sync

e) copy tar file

f) sync

g) rm -rf kernel source tree

h) rm -rf copy of source tree

i) sync

For each of the I/O schedulers I ran the above sequence of tests 3 times and took an average of the total run time. My results are as follows:

cfq: 3m59s,

noop: 3m25s,

anticipatory: 3m51s,

deadline: 3m42s

So it appears the default cfq (Completely Fair Queuing) scheduler is least optimal and the noop scheduler behaves best. According to the noop wikipedia entry the noop scheduler is the best choice for solid state drives, so maybe my test results can be trusted after all :-)

SSDs do not require multiple I/O requests to be re-ordered since they do not suffer from traditional random-access latencies, hence the noop scheduler is optimal.