Computer resources
| Author : DAOUDI Samir | Context : MSc Software Engineering – Computer Structure |
Granting access to computer’s resources can be a real challenge in multitasking environment. An important part of the Operating System called the Scheduler is responsible for selecting and granting access to the desired resources based on specific criteria.
The 1st algorithm used by the scheduler is First In First Out (FIFO) or First Come, First Served (FCFS), which seems to be the most logical one and it is based on a queue, the jobs are added at the end of the queue and selected from the head. This algorithm seems to be simple but typically long/varying waiting time due to its non-preemptive property. (F.Haziza, 2007).
Later other algorithms have been designed to optimize the response time and to reach the following goals:
- Fairness: Each process get a fair share of the CPU.
- Efficiency: Utilize the CPU at its maximum capacity and try to keep it busy 100% of the time.
- Response time: Reduce at the minimum the response time.
- Turnaround: Reduce the time users wait for output.
- Throughput: Maximize the number of jobs processed in a given timeframe. (B.Mitchell, 2005).Here is a description of some scheduling algorithms (OsDev, 2010):
| Algorithm | Description |
Advantages |
Disadvantages |
| Round Robin | A simple preemptive algorithm using one queue. Each process gets a time slice (quantum), once it uses the quantum, the algorithm Enqueu it and Dequeue the one at the head. | – Simple (FIFO) | – No priority system. |
| Priority based Round Robin | Similar to round robin except that it uses different queue for each priority. |
– Simple |
– Privileged process may monopolize the CPU time |
| Shortest Job First (SJF) | Non-preemptive algorithm, the run time is assumed known before. And select the shortest job which is available for run. |
– Optimal |
– Run times are not know all the time. |
| Shortest Remaining time next | The preemptive version of SJF, the algorithm selects the job which has the lowest remaining time |
– Optimal |
– Run time must be known at the beginning. |
The use of these algorithms may vary depending upon the environment and the type of applications being executed by the process. In fact personal computers’ CPUs running ‘simple’ standalone jobs may use different algorithms than those used by nuclear computers for scientific calculations and requiring real time and precise response time.
References :
- J.Glenn Brookshear, “Computer Science 10th Edition”. 2010.
- Frédéric Haziza ,“Scheduling Algorithms”, Department of Computer Systems Uppsala University.2007.
- Brian Mitchell, “Operating systems, Process scheduling”,Department of Computer science, college of engineering. Drexel University. 2005.
- “Wiki OS Dev”,Oct 2010 http://wiki.osdev.org/Scheduling_Algorithms
