News Contents

Toplam 3 İlan Bulundu

Disk Scheduling Algorithms

This tutorial is prepared for those that need assistance in Disk Scheduling Algorithms.


In operating systems, seek time is very important. Since all device requests are linked in queues, the seek time is increased causing the system to slow down. Disk Scheduling Algorithms are used to reduce the total seek time of any request.


The purpose of this material is to provide one with help on disk scheduling algorithms. Hopefully with this, one will be able to get a stronger grasp of what disk scheduling algorithms do.


Although there are other algorithms that reduce the seek time of all requests, I will only concentrate on the following disk scheduling algorithms:
First Come-First Serve (FCFS)
Shortest Seek Time First (SSTF)
Elevator (SCAN) 
Circular SCAN (C-SCAN)
These algorithms are not hard to understand, but they can confuse someone because they are so similar. What we are striving for by using these algorithms is keeping Head Movements (# tracks) to the least amount as possible. The less the head has to move the faster the seek time will be. I will show you and explain to you why C-LOOK is the best algorithm to use in trying to establish less seek time.

Given the following queue -- 95, 180, 34, 119, 11, 123, 62, 64 with the Read-write head initially at the track 50 and the tail track being at 199 let us now discuss the different algorithms.

1. First Come -First Serve (FCFS) [DIAGRAM] All incoming requests are placed at the end of the queue. Whatever number that is next in the queue will be the next number served. Using this algorithm doesn’t provide the best results. To determine the number of head movements you would simply find the number of tracks it took to move from one request to the next. For this case it went from 50 to 95 to 180 and so on. From 50 to 95 it moved 45 tracks. If you tally up the total number of tracks you will find how many tracks it had to go through before finishing the entire request. In this example, it had a total head movement of 640 tracks. The disadvantage of this algorithm is noted by the oscillation from track 50 to track 180 and then back to track 11 to 123 then to 64. As you will soon see, this is the worse algorithm that one can use.

2. Shortest Seek Time First (SSTF) [DIAGRAM] 
In this case request is serviced according to next shortest distance. Starting at 50, the next shortest distance would be 62 instead of 34 since it is only 12 tracks away from 62 and 16 tracks away from 34. The process would continue until all the process are taken care of. For example the next case would be to move from 62 to 64 instead of 34 since there are only 2 tracks between them and not 18 if it were to go the other way. Although this seems to be a better service being that it moved a total of 236 tracks, this is not an optimal one. There is a great chance that starvation would take place. The reason for this is if there were a lot of requests close to eachother the other requests will never be handled since the distance will always be greater.

3. Elevator (SCAN) [DIAGRAM] 
This approach works like an elevator does. It scans down towards the nearest end and then when it hits the bottom it scans up servicing the requests that it didn’t get going down. If a request comes in after it has been scanned it will not be serviced until the process comes back down or moves back up. This process moved a total of 230 tracks. Once again this is more optimal than the previous algorithm, but it is not the best.

4. Circular Scan (C-SCAN) [DIAGRAM] 
Circular scanning works just like the elevator to some extent. It begins its scan toward the nearest end and works it way all the way to the end of the system. Once it hits the bottom or top it jumps to the other end and moves in the same direction. Keep in mind that the huge jump doesn’t count as a head movement. The total head movement for this algorithm is only 187 track, but still this isn’t the mose sufficient.



Show More Devamı
Tüm Yorumlar - All Comments

Bu yazıda anlatılan içerik değiştirme (context switching) konusunu anlamadan önce bilgisayarlarda bulunan işlemcinin (CPU) anlık olarak tek bir iş ile uğraşabileceğini söylememiz gerekiyor. İşletim sistemi tasarımında (operating system design) bulunan bir özellik sayesinde, anlık olarak işlemcide tek iş çalıştırılması ve yinede birden fazla işin bilgisayarda aynı anda çalışıyormuş gibi hissettirilmesi mümkündür.

Aslında tek işlem çalıştırıp birden fazla iş yapıyormuş gibi gösteren işletim sistemi özelliği kısaca çok işlemlilik (multiprocess) olarak geçer ve bu özellik işlemcinin (CPU), işlemleri (process) sırayla çalıştırması sayesinde elde edilir. Yani bilgisayarda iki program çalışıyorsa (birinci programa A ikincisine B diyelim). Bilgisayar sırayla bir A programını bir de B programını çalıştırır. Bu sayede programlardan hiçbirisi aslında bekletilmeden işlemciye belirli aralıklarla erişme imkanı bulur ve biraz A programı biraz B programı çalıştırılarak aynı anda çalışıyor izlenim olur.

Bu programlar arasında işlemcinin geçiş yapmasına da içerik değiştirme (context switching) ismi verilir. Aslında her içerik değiştirmenin bilgisayar açısından bir maliyeti vardır. Dolayısıyla içerik değiştirmek aslında iyi bir özellik olmasına karşılık bir de maliyeti vardır ve oranı yükseldikçe dezavantaj haline gelir.

Show More Devamı
Tüm Yorumlar - All Comments

A typical processor executes instructions one by one. But there may be occasions where the processor has to stop current instruction and execute some other program or code segment (residing in some other place). After doing this the processor returns to normal execution and continues from where it left off. A system call and a function call are such occasions. A system call is a call to a subroutine built in to the system. A function call is a call to a subroutine within the program itself.

What is a System Call?

System calls provide programs running on the computer an interface to talk with the operating system. When a program needs to ask for a service (for which it does not have permission to do that by itself) from the kernel of the operating system, it uses a system call. User level processes do not have the same permissions as the processes directly interacting with the operating system. For example, to communicate with and external I/O device or to interact with any other processes, a program uses system calls.

What is a Function Call?

A function call is also called a subroutine call. A subroutine (also known as a procedure, function, method or routine) is part of a larger program that is responsible for carrying out a specific task. The larger program may execute a heavy workload, and the subroutine may be performing just a simple task, which is also independent of the remaining program coding. A function is coded in such a way that it may be called multiple times and from different places (even from within other functions). When a function is called, the processor may go to where the code for the function is residing and execute the instructions of the function one by one. After completing the functions, the processor will return to exactly where it left off and continue the execution starting from the next instruction. Functions are a great tool for code reuse. Many modern programming languages support functions. A collection of functions is called a library. Libraries are often used as means of sharing and trading software. In some cases, the whole program could be a sequence of subroutines (e.g. threaded code compilation).

Show More Devamı
Tüm Yorumlar - All Comments