Traditional UNIX scheduling, as used in SVR3 and 4.3 BSD UNIX , is primarily designed for a time-sharing interactive environment . The goal of the scheduling algorithm is to provide good response time for interactive users while ensuring that low-priority background jobs do not starve. Although modern UNIX systems have replaced this algorithm, understanding its structure offers valuable insights into time-sharing scheduling .
Multilevel Feedback with Round Robin:-
The traditional UNIX scheduler employs a multilevel feedback queue combined with a round-robin scheduling approach within each priority queue. This means processes are assigned to different queues based on their priority, and within each queue, processes take turns executing.
One-Second Preemption:-
The system uses one-second preemption , meaning that if a running process does not block or complete within one second, it is preempted. This ensures that no single process can monopolize the CPU for too long, maintaining fairness across processes.
Priority Calculation:-
Process priority is determined based on the process type and execution history . The following formulas are used to calculate CPU utilization and process priority:
Priority Recalculation:-
The priority of each process is recomputed once per second , at which point a new scheduling decision is made. The base priority ensures processes remain within fixed priority bands. These bands group processes into different priority levels, such as Swapper , Block I/O device control , File manipulation , Character I/O device control , and User processes .
The bands are used to:
- Optimize access to block devices (like disk drives).
- Respond quickly to system calls .
I/O-Bound vs. CPU-Bound Processes:-
Within the user process band , the scheduler penalizes processor-bound processes (those using significant CPU time) and favors I/O-bound processes (those waiting for input/output operations). This helps improve system efficiency by ensuring that processes waiting for I/O can proceed quickly, while processes that are consuming large amounts of CPU time are deprioritized.
Scheduling Example:-
An example of process scheduling might involve three processes (A, B, and C), all starting at the same time with a base priority of 60. Ignoring the nice value , the clock interrupts the system 60 times per second, incrementing a counter for the running process. Assuming none of the processes block themselves and no other processes are ready to run, they are scheduled based on their priorities, and preempted as necessary.
Conclusion:-
The traditional UNIX scheduling algorithm is well-suited to general-purpose time-sharing environments. By using multilevel feedback, round-robin preemption, and execution history, it balances the needs of interactive users and background tasks while ensuring efficient use of system resources, especially I/O devices.
