Disk Scheduling Alorithms For Linux Computer Science Essay

Published:

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

The Performance of a computer system is increasing with a great amount. Some components are developing with a very great speed like the processor. But some components like disk drive are not developing like other. "Over the last 40 years, the increase in the speed of processors and main memory has far outstripped that for disk access, with processor and main memory speeds increasing by about two orders of magnitude compared to one order of magnitude for disk. The result is that disks are currently at least four orders of magnitude slower than main memory" [1]. This creates a gap between performance of processor and a disk drive. This gap is increasing day by day as more and more development is being done in field of computer science.

Abstract

In this paper I will discuss performance of scheduling algorithm used in Linux 2.4 through Linux 2.6. Many of the disk scheduling algorithms has been proposed for Linux. But there is no single algorithm that can meet all requirements i.e. none of the algorithm can match the speed of processor. It does not matter how fast processor a computer is using until disk matches speed of processor. Disk accessing is acting as bottleneck for the speed of computer.

Linux uses many disk scheduling algorithms Linux 2.4 uses Linus Elevator. In Linux 2.6 elevator algorithm was enhanced with deadline IO scheduler and anticipatory IO scheduler. Current Linux 2.6 is using CFQ. In this paper I will discuss all of these algorithms and then I will compare these algorithms on the basis of data available.

Average access time of disk depends upon three factors: seek time, rotational delay, transfer time. Seek time is time required to move head from current position to the desired track, rotational delay is time required to move head form current sector to desired sector on a particular track, transfer time is time required to fetch data form desired sector on disk. From all of these three factors seek time is one of the greatest factor upon which average disk access time depends. Most of the disk scheduling algorithms so far used in Linux are designed to reduce the seek time.

Linus Elevator

Linux 2.4 uses algorithm Linus elevator. This was named elevator because it works like elevator. Elevator moves in particular direction processing all requests. Similarly head moves in particular direction processing each block number in between. Elevator Scheduler is a variant of LOOK algorithm. This algorithm uses a queue to process all read and write requests. Requests are shorted by block number for that request. When a new request is added to queue, four operations are considered in order [1]:

If a request is on same sector or adjacent to pending request then two requests are merged.

If request in queue is old then new request is inserted at tail of queue.

If there is a suitable location then new request is inserted in sorted order.

If there is no suitable location then request is added at tail.

Consider an example where requests for block numbers 15, 30, 45, 52, 61, 67, 69, 81, 89, 101, 110 are in queue. At some time request for the block 30 is under processing and new request for block 10, 46, 62, 85,115 comes now request for block no 10 will be added to at the end of queue. Request for block no 46 will be merged with 45. Request 62 will be merged with 61. Request 85 will be added in queue after 81. Request for 115 will be added after 110.

Limitations of Elevator Scheduler:

With elevator scheduler there is a problem of long waiting for a request. Suppose head is currently processing request at 85 and new request for 11 comes into queue and added at the tail of queue. Meanwhile suppose request from 86 to 110 keeps coming and merging in between queue. In this cases request for 11 may have to wait for really long time. This will create a problem similar to starvation.

There is one more problem associated with elevator scheduler. Suppose all the request are processed till the last block 115 now head has to move back to process request that were added at the end of queue i.e. head has to move back to starting without processing requests in between. This will waste lot of time.

There is one major problem with elevator is read write problem. For a running process there are two type of disk access Read and Write. Read operations are important than a write operation. When a process issues a write operation it just writes data in the kernel buffer and proceeds forward it doesn't have to wait for write operation to complete. But a read operation s different. When a process issues a read operation it waits for that read operation to complete. So read operations should be giving higher priority. Because if a process that issued read request stuck behind a write request will have to wait for long time.

Deadline scheduler

To overcome problem of elevator scheduler in Linux 2.4 a new scheduler deadline scheduler is used in Linux 2.6. This algorithm was introduced by keeping in mind the problems of starvation and no distinction between read and write requests in elevator scheduler. This Scheduling algorithm named deadline because it imposes an expiration time on all requests, with default value of 0.5 seconds for read operations and 5 seconds for write operations [1]. There are three queues in deadline scheduler sorted queue, read queue, write queue. Read and Write queues are FIFO queues. In normal manner requests are processed form sorted queue. When a request is completed it is removed from sorted queue and associated FIFO queue. In both FIFO queue if timeline of a request expire head moves to the FIFO queue and that request is processed and removed from both FIFO and Sorted Queue.

Limitations of Deadline scheduler:

Deadline Scheduler increases the overhead of keeping the two copies of single request one in Sorted Queue and another one in FIFO Queues.

There is one more problem associated with deadline scheduler suppose there are requests for block no 10, 11, 20, 31, 42, 44, 54, 58, 70, 99, 100 in the sorted queue. Current request that is being processed is 20 and time for request no 70 in read FIFO queue expire. Instead of processing request 31 head will move to 70 skipping all the requests between 31 and 70. This will affect the seek time greatly.

Figure1. The Deadline Scheduler [1]

In deadline scheduler priority is given to read request. This also creates a problem. Suppose if for write request data is placed in kernel buffer and is waiting to be written on disk. Meanwhile a read request is made for that particular data but the data is still in buffer. In that case either process will take data that is not updated or that process has to wait for that write request to complete.

Anticipatory Algorithm

Elevator scheduler and deadline schedulers are designed in such way that as soon a request is processed next request is dispatched. "Unfortunately many application issues synchronous, almost continuous streams of read requests. This forces the scheduler into making decision too early, falsely assuming that process has become momentarily idle. This phenomenon if deceptive idleness causes degradation in performance of system. Overall performance of system can be enhanced if scheduler waits for short time for next request to come" [2]. When a read request is processed anticipator algorithm will cause scheduling system to delay for some time. Because there may be possibility that process that issued read will issued another request on the same track.

"[LOVE04] reports on two tests of the Linux scheduling algorithms. The first test involved the reading of a 200-MB file while doing a long streaming write in the background. The second test involved doing a read of a large file in the background while reading every file in the kernel source tree. The results are listed in the following table"[1].

I/O Scheduler and Kernel

Test 1

Test 2

Linus elevator on 2.4

45 seconds

30 minutes, 28 seconds

Deadline I/O scheduler on 2.6

40 seconds 3 minutes,

30 seconds

Anticipatory I/O scheduler on 2.6

4.6 seconds

15 seconds

Table 1[1]

According to two tests given in Table 1 it clear that Anticipatory I/O scheduler best in performance as compared to previous algorithms of Linux. That is why this algorithm was used as default scheduling algorithm of Linux. But in Linux 2.6.33 this was replaced by CFQ.

Limitations of Anticipatory Algorithm:

If disk sits idle and wait for a process to issue more request and requests are not synchronous. This delay time will be added to seek time and affect overall performance of disk.

If a large process is making successive read request. Then some other processes have to wait for a long time. This will cause a problem of starvation.

In anticipatory algorithm priority is given to a single process. But what if multiple processes are working cooperatively.

Completely Fair Queuing

"Anticipatory Scheduler has been removed from default disk scheduler of Linux 2.6.33"[3]. Current versions of Linux are using CFQ (Completely Fair Queuing) as their default disk access algorithm. This algorithm was introduced to provide fair queuing to all processes. "CFQ is based on the working of Stochastic Fair Queuing (SFQ). A SFQ-based scheduler design was initially proposed (and ultimately being implemented) for some network scheduling related subsystems" [6]. The goal of both CFQ and SFQ is to divide the I/O bandwidth equally. In CFQ there are time slices for processes. A process can dispatch its requests for disk access during this time slice. During a time slice scheduler will allow disk to go ideal so that a process can request as many as requests. If process requests increases seek time then that process will lose its right to keep the disk idle. CFQ gives fairness to all process trying to access disk. By using CFQ problem of starvation can be removed because each process can issues disk access requests on for a single time slice. If time slice expires control is passed to next process. Robin Round algorithm is use to transfer control of disk from one process to another.

Jens Axboe performs some tests and compares CFQ with anticipator algorithm used in Linux. Tests were performed on IDE drive using ext2. Table 2 through table 9 gives results of tests performed by Jens Axboe. These tests were performed on different types of read and write requests. When more and more clients i.e. processes are added bandwidth is divided among processes and this will cause increase in latency. This increase in latency is very large in anticipatory scheduler as compare to that of CFQ.

Case 1: Read File, Sequential

Scheduler: AS

Clients

Max bandwidth

Min bandwidth

Agg bandwidth

Max latency

1

19480

19480

19480

30msec

2

9250

9189

18434

261msec

4

4513

4469

17970

488msec

8

2238

2157

17581

934msec

Table 2 [4]

Scheduler: CFQ

Clients

Max bandwidth

Min bandwidth

Agg bandwidth

Max latency

1

19433

19433

19433

9msec

2

8686

8628

17312

90msec

4

4507

4471

17963

254msec

8

2181

2104

17134

578msec

Table 3 [4]

Case 2: Read File, Random

Scheduler: AS

Clients

Max bandwidth

Min bandwidth

Agg bandwidth

Max latency

1

7041

7041

7041

18msec

2

4616

2298

6912

270msec

4

3190

928

6901

360msec

8

1524

645

6765

636msec

Table 4 [4]

Schedule: CFQ

Clients

Max bandwidth

Min bandwidth

Agg bandwidth

Max latency

1

7027

7027

7027

19msec

2

3429

3413

6841

107msec

4

1718

1700

6844

282msec

8

875

827

6795

627msec

Table 5 [4]

Case 3: Write File, Sequential

Schedule: AS

Clients

Max bandwidth

Min bandwidth

Agg bandwidth

Max latency

1

13330

13330

13330

21msec

2

2694

2694

5388

77msec

4

1754

17

4988

762msec

8

638

342

3866

848msec

Table 6 [4]

Schedule: CFQ

Clients

Max bandwidth

Min bandwidth

Agg bandwidth

Max latency

1

13267

13267

13267

30msec

2

6352

6150

12459

239msec

4

3230

2945

12524

289msec

8

1640

1640

12564

599msec

Table 7 [4]

Case 4: Write Files, random

Schedule: AS

Clients

Max bandwidth

Min bandwidth

Agg bandwidth

Max latency

1

4110

4110

4110

114msec

2

815

809

1623

631msec

4

482

349

1760

606msec

8

476

111

2863

752msec

Table 8 [4]

Schedule: CFQ

Clients

Max bandwidth

Min bandwidth

Agg bandwidth

Max latency

1

4493

4493

4493

129msec

2

1710

1513

3216

321msec

4

521

482

2002

476msec

8

938

877

7210

927msec

Table 8 [4]

Limitation of CFQ:

Although CFQ eliminates the one of the major problem of anticipatory algorithm and a process cannot hold disk no longer than a single time slice. But one question still arise what if multiple processes are working cooperatively.

One more major issue of CFQ is its complexity

Conclusion

We have discussed algorithms used in Linux. All of the algorithms have their pro and con. We can say that CFQ scheduler is the one that can improve the performance of disk drive. Although using CFQ also have some disadvantages like complexity. But can also see that data provided by Jens Axboe clearly explain that performance of CFQ is much better than that of other disk schedulers. This is the only reason now CFQ is used as default disk scheduler in Linux.

Writing Services

Essay Writing
Service

Find out how the very best essay writing service can help you accomplish more and achieve higher marks today.

Assignment Writing Service

From complicated assignments to tricky tasks, our experts can tackle virtually any question thrown at them.

Dissertation Writing Service

A dissertation (also known as a thesis or research project) is probably the most important piece of work for any student! From full dissertations to individual chapters, we’re on hand to support you.

Coursework Writing Service

Our expert qualified writers can help you get your coursework right first time, every time.

Dissertation Proposal Service

The first step to completing a dissertation is to create a proposal that talks about what you wish to do. Our experts can design suitable methodologies - perfect to help you get started with a dissertation.

Report Writing
Service

Reports for any audience. Perfectly structured, professionally written, and tailored to suit your exact requirements.

Essay Skeleton Answer Service

If you’re just looking for some help to get started on an essay, our outline service provides you with a perfect essay plan.

Marking & Proofreading Service

Not sure if your work is hitting the mark? Struggling to get feedback from your lecturer? Our premium marking service was created just for you - get the feedback you deserve now.

Exam Revision
Service

Exams can be one of the most stressful experiences you’ll ever have! Revision is key, and we’re here to help. With custom created revision notes and exam answers, you’ll never feel underprepared again.