Operating System #21 Scheduling in Linux: O(n), O(1) Scheduler

Operating System #21 Scheduling in Linux: O(n), O(1) Scheduler
Complete Operating Systems Lecture/ Tutorials from IIT @ https://goo.gl/GMr3if
MATLAB Tutorials @ https://goo.gl/EiPgCF

00:37 Process Types
• Real time
– Deadlines that have to be met
– Should never be blocked by a low priority task
• Normal Processes
– Either interactive (IO based) or batch (CPU bound)
• Linux scheduling is modular
– Different types of processes can use different scheduling algorithms

03:24 History (Schedulers for Normal Processors)
• O(n) scheduler
– Linux 2.4 to 2.6
• O(1) scheduler
– Linux 2.6 to 2.6.22
• CFS scheduler
– Linux 2.6.23 onwards

03:54 O(n) Scheduler
• At every context switch
– Scan the list of runnable processes
– Compute priorities
– Select the best process to run
• O(n), when n is the number of runnable processes … not scalable!!
– Scalability issues observed when Java was introduced (JVM spawns many tasks)
• Used a global runqueue in SMP systems
– Again, not scalable!!

05:47 O(1) scheduler:
• Constant time required to pick the next process to execute
– easily scales to large number of processes
• Processes divided into 2 types
– Real time
• Priorities from 0 to 99
– Normal processes
• IO bound (interactive)
• CPU bound
• Priorities from 100 to 139 (100 highest, 139 lowest priority)

Видео Operating System #21 Scheduling in Linux: O(n), O(1) Scheduler канала Xoviabcs