Linux Resources

Process Scheduling

By Roberto Espinoza at www.cpccci.com

CPC Computer Consultants, Inc.

This project has been developed using the C programming language and run in a Linux, Fedora Core 2 platform.

SCHEDULING POLICIES

Linux offers 3 different ways to deal with scheduling, 2 of them for real-time applications and 1 for normal processes. A static priority value, sched_priority, ranging from 0 to 99, is assigned to each process. This static priority value can be changed only via system calls. The scheduler keeps a list of runnable processes with these priority values. The way Linux determines which process will be running next is by looking at such list for the highest priority number, and then takes the process at the head of the list. The scheduling policy determines where a process will be inserted in the event that it has an equal priority value with another process. Likewise, it will determine how it will move once inside the list.

Most processes use SCHED_OTHER which is the default universal time-sharing scheduler policy. Other most time-critical applications that require precise control use SCHED_FIFO and SCHED_RR. When using SCHED_OTHER, processes must be assigned an static priority value of 0. Otherwise, if using the two other algorithms, the priority value shall range from 1 to 99. Only such processes with superuser privileges can have a priority value greater than 0, therefore they may use SCHED_FIFO and SCHED_RR.
All scheduling is preemptive, meaning that if a process with a higher priority is ready to run, the currently running process is preempted and taken to the wait list. It is the task of the scheduling policy to determine the ordering within the list of runnable processes with equal static priority value.

SCHED_FIFO: First In - First Out Scheduling

SCHED_FIFO is used only with priority values ranging from 1 to 99, that is, a SCHED_FIFO process ready to be run will always preempt a normal, SCHED_OTHER, process currently running. SCHED_FIFO does not deal with time slicing. If a SCHED_FIFO process has been preempted by a higher priority process, it will go to the top of the wait list and will resume running as soon as all processes with higher priority values have been blocked.

SCHED_RR: Round Robin Scheduling

SCHED_RR works just like SCHED_FIFO, but with one difference: each SCHED_RR process is allowed to run for a specified time quantum. As soon as a running process reaches its alloted time quantum it will be put back at the end of the same-priority-value list. If a SCHED_RR process has been preempted by a higher value priority process, it will complete the unexpired portion of its alloted time quantum when it resumes execution.

SCHED_OTHER: Default Linux Time-Sharing Scheduling

This is the usual time-sharing scheduling algorithm used for all normal processes, or processes that do not require special static priority real-time mechanisms. The process that runs is determined by a dynamic priority inside the list of the same static priority values processes, namely 0. The dynamic priority is based on the nice level and increased for each time quantum the process is ready to run, but denied to run by the scheduler. This way ensures fairness among all static priority 0 processes.
Nice Level - the 'nice' command changes the priority level value of a process. The priority that may be adjusted by 'nice' runs from -20, the highest, to 19 the lowest.

IMPLEMENTATION

Each of the three programs in both, the Kernel and User Levels, was run 25 times, which produced varying time results depending on the random numbers genereated by them. An average was computed of these 25 results to come up with a final result for each algorithm.
The time was accurately measured using the following commands:
start_time = clock();
end_time = clock();
cpu_time_used = ((double) (end_time - start_time)) / CLOCKS_<stockticker>PER_<stockticker>SEC;
system("date");

IMPLEMENTATION OF SCHEDULING AT KERNEL LEVEL

SCHED_FIFO: First In - First Out Scheduling

Three different programs were written in C to implement and test the FIFO algorithm. Each program creates 10 threads, and each thread, in turn, generates between 300,000 and 3,000,000 random numbers so they utilize CPU resources in varying time slots.
A completely different program from the ones indicated in the paragraph above runs the 3 main programs.

SCHED_RR: Round Robin Scheduling

Three different programs were written in C to implement and test the Round Robin algorithm. Each program creates 10 threads, and each thread, in turn, generates between 300,000 and 3,000,000 random numbers so they utilize CPU resources in varying time slots.
A completely different program from the ones indicated in the paragraph above runs the 3 main programs.

SCHED_OTHER: Default Linux Time-Sharing Scheduling

Three different programs were written in C to implement and test the Other algorithm. Each program creates 10 threads, and each thread, in turn, generates between 300,000 and 3,000,000 random numbers so they utilize CPU resources in varying time slots.
A completely different program from the ones indicated in the paragraph above runs the 3 main programs.

IMPLEMENTATION OF SCHEDULING AT USER LEVEL

SCHED_FIFO: First In - First Out Scheduling
Three different programs were written in C to implement and test the FIFO algorithm. Each program creates 10 threads, and each thread, in turn, increases or decreases the number of random numbers by a random number so each utilizes CPU resources in varying time slots.
A completely different program from the ones indicated in the paragraph above runs the 3 main programs.
Shortest Job Fist Scheduling
Three different programs were written in C to implement and test the Shortest Job First algorithm. Each program creates 10 threads, and each thread, in turn, increases the number of random numbers so they utilize CPU resources in varying time slots.
A completely different program from the ones indicated in the paragraph above runs the 3 main programs.
Longest Job Fist Scheduling
Three different programs were written in C to implement and test the Shortest Job First algorithm. Each program creates 10 threads, and each thread, in turn, decreases the number of random numbers so they utilize CPU resources in varying time slots.
A completely different program from the ones indicated in the paragraph above runs the 3 main programs.

CONCLUSIONS

The results at the Kernel Level were much better for the Round Robin algorithm and much worse for the Other algorithm.
The results at the User Level was best for LJF and worst for SJF.

BIBLIOGRAPHY

COP 5994 - Operating Systems Class Website
Operating Systems, Harvey M. Deitel, Paul J. Deitel, David R. Choffnes, Third Edition
Understanding the Linux Kernel, O'Reilly Online Catalog
Linux Process Scheduling
Linux Process Management
Linux Process Scheduling - Summary
Man Pages, Fedora Core 2
Info Pages, Fedora Core 2