1673:
20:
1685:
1659:
177:
152:
scheduler gives a priority bonus to interactive tasks (for better throughput) while penalizing non-interactive tasks by lowering their priorities. All the calculations to determine the interactivity of tasks are complex and subject to potential miscalculations, causing non-interactive behavior from an interactive process.
89:
and moved to the expired array. Once all the tasks from the active array have exhausted their time quantum and have been moved to the expired array, an array switch takes place. Because the arrays are accessed only via pointer, switching them is as fast as swapping two pointers. This switch makes the
151:
or non-interactive. The algorithm tries to identify interactive processes by analyzing average sleep time (the amount of time the process spends waiting for input). Processes that sleep for long periods of time probably are waiting for user input, so the scheduler assumes they're interactive. The
84:
The Linux scheduler was overhauled completely with the release of kernel 2.6 in 2003. The new scheduler was called the O(1) scheduler. The algorithm used by the O(1) scheduler relies on active and expired arrays of processes to achieve constant scheduling time. Each process is given a fixed time
121:. If it is possible to establish a constant upper bound on the running time of an algorithm, it is considered to be O(1) (one might say it runs in "constant time"). That is, an O(1) algorithm is guaranteed to complete in a certain amount of time regardless of the size of the input.
134:
to efficiently handle massive numbers of tasks without increasing overhead costs as the number of tasks grows. There are two key data structures in the Linux 2.6.8.1 scheduler that allow for it to perform its duties in O(1) time, and its design revolves around them:
129:
The Linux 2.6.8.1 scheduler did not contain any algorithms that run in worse than O(1) time. That is, every part of the scheduler is guaranteed to execute within a certain constant amount of time regardless of how many tasks are on the system. This allows the
164:
was introduced, replacing the O(1) Scheduler. According to Ingo Molnar, the author of the CFS, its core design can be summed up in single sentence: "CFS basically models an 'ideal, precise multitasking CPU' on real hardware."
112:
is used to denote the growth rate of an algorithm's execution time based on the amount of input. For example, the running time of an O(n) algorithm increases linearly as the input size n grows. The running time of an
1235:
524:
1324:
1319:
1711:
449:
69:, deterministic execution is key, and an O(1) scheduler is able to provide scheduling services with a fixed upper-bound on execution times.
1677:
1056:
824:
416:
554:
1166:
494:
329:
1600:
1481:
529:
198:(BFS) – a process scheduler designed for the Linux kernel in August 2009 as an alternative to CFS and the O(1) scheduler
883:
72:
The O(1) scheduler was used in Linux releases 2.6.0 thru 2.6.22 (2003-2007), at which point it was superseded by the
1582:
1396:
514:
442:
66:
398:
1587:
1229:
565:
161:
73:
40:
1150:
1135:
1051:
839:
644:
19:
1493:
1292:
928:
816:
771:
721:
705:
682:
504:
1638:
1615:
1610:
1445:
1411:
1401:
1273:
1218:
1095:
634:
86:
43:
1689:
1592:
435:
148:
389:
266:
1622:
1224:
786:
484:
195:
408:
1418:
897:
756:
690:
308:
47:
1572:
1406:
992:
892:
829:
751:
746:
534:
241:
59:
1543:
1191:
1161:
1156:
1007:
662:
624:
24:
405:; A HW/SW co-designed POSIX-compatible OS featuring an O(1) scheduler implemented in hardware
362:
1297:
859:
580:
570:
479:
90:
active array the new empty expired array, while the expired array becomes the active array.
51:
39:(pronounced "O of 1 scheduler", "Big O of 1 scheduler", or "constant time scheduler") is a
1533:
1201:
982:
402:
190:
108:
operates over an input, and the size of that input usually determines its running time.
1563:
1468:
1379:
1256:
1246:
1241:
1024:
849:
844:
489:
118:
114:
109:
99:
55:
50:
within a constant amount of time, regardless of how many processes are running on the
1705:
1498:
1314:
1120:
1110:
869:
741:
619:
420:
147:
The main issue with this algorithm is the complex heuristics used to mark a task as
1663:
1384:
1302:
1196:
1140:
499:
458:
182:
131:
28:
1389:
1282:
864:
761:
359:
1476:
1451:
1438:
1343:
1331:
1261:
1171:
657:
560:
519:
172:
1338:
1307:
1176:
1012:
801:
672:
629:
216:
136:
105:
287:
1456:
1277:
1266:
1186:
1130:
1125:
1071:
1019:
908:
834:
1538:
1523:
1433:
1423:
1363:
1287:
1181:
1105:
1046:
960:
923:
854:
796:
791:
695:
652:
395:
1528:
1513:
1503:
1358:
1353:
1115:
1066:
1039:
1002:
972:
939:
918:
667:
614:
509:
337:
1658:
1348:
1211:
1145:
1100:
1061:
1029:
997:
955:
950:
913:
781:
776:
736:
731:
176:
18:
1428:
1206:
1034:
965:
609:
431:
427:
1508:
1486:
411:; Written by M. Tim Jones, an IBM developerWorks article
58:, which schedule processes in an amount of time that
1631:
1571:
1562:
1467:
1372:
1088:
981:
891:
882:
815:
720:
713:
704:
681:
643:
602:
595:
543:
472:
465:
363:"Linux-Kernel Archive: Re: fair clock use in CFS"
330:"Understanding the Linux 2.6.8.1 CPU Scheduler"
54:. This is an improvement over previously used
443:
390:Understanding the Linux 2.6.8.1 CPU Scheduler
16:Historical Linux 2.6 kernel process scheduler
8:
217:"Introducing the 2.6 Kernel | Linux Journal"
417:"A closer look at the Linux O(1) scheduler"
288:"An informal introduction to O(N) notation"
1568:
1464:
888:
717:
710:
599:
469:
450:
436:
428:
240:Chandandeep Singh Pabla (August 1, 2009).
125:Improvement in Linux scheduler performance
62:linearly based on the amounts of inputs.
1678:Free and open-source software portal
1236:Earliest eligible virtual deadline first
208:
309:"A Beginner's Guide to Big O Notation"
7:
23:Location of the "O(1) scheduler" (a
27:) in a simplified structure of the
419:. HP Research Labs. Archived from
14:
1684:
1683:
1671:
1657:
525:Supported computer architectures
175:
1712:Linux kernel process schedulers
555:The Linux Programming Interface
160:In 2.6.23 (October 2007), the
1:
267:"The Linux Process Scheduler"
392:; Josh Aas, 17 February 2005
242:"Completely Fair Scheduler"
85:quantum, after which it is
67:real-time operating systems
1728:
1397:High-performance computing
1219:Process and I/O schedulers
409:Inside the Linux scheduler
97:
1651:
1230:Completely Fair Scheduler
495:Tanenbaum–Torvalds debate
162:Completely Fair Scheduler
74:Completely Fair Scheduler
46:design that can schedule
1151:Kernel same-page merging
396:HybridThreads (Hthreads)
1494:OS-level virtualization
1639:List of Linux adopters
581:Linux User Group (LUG)
32:
139:and priority arrays.
22:
1225:Brain Fuck Scheduler
485:Linux Mark Institute
221:www.linuxjournal.com
196:Brain Fuck Scheduler
1419:Real-time computing
691:Linux Standard Base
361:>, Ingo Molnar.
94:About O(1) notation
1407:Compute Node Linux
993:C standard library
401:2008-05-11 at the
33:
1699:
1698:
1647:
1646:
1558:
1557:
1554:
1553:
1192:Network scheduler
1084:
1083:
1080:
1079:
878:
877:
625:Linux kernel oops
591:
590:
571:Linux conferences
423:on 16 March 2012.
415:David Mosberger.
25:process scheduler
1719:
1687:
1686:
1676:
1675:
1674:
1664:Linux portal
1662:
1661:
1569:
1465:
1274:Security Modules
889:
718:
711:
600:
480:Linux Foundation
470:
452:
445:
438:
429:
424:
377:
376:
374:
373:
355:
349:
348:
346:
345:
334:
325:
319:
318:
316:
315:
304:
298:
297:
295:
294:
283:
277:
276:
274:
273:
262:
256:
255:
253:
252:
237:
231:
230:
228:
227:
213:
185:
180:
179:
117:algorithm grows
65:In the realm of
52:operating system
1727:
1726:
1722:
1721:
1720:
1718:
1717:
1716:
1702:
1701:
1700:
1695:
1672:
1670:
1656:
1643:
1627:
1574:
1550:
1534:User-mode Linux
1463:
1368:
1076:
984:
977:
896:
874:
811:
723:
700:
677:
639:
587:
539:
530:Version history
461:
456:
414:
403:Wayback Machine
386:
381:
380:
371:
369:
357:
356:
352:
343:
341:
332:
327:
326:
322:
313:
311:
306:
305:
301:
292:
290:
285:
284:
280:
271:
269:
264:
263:
259:
250:
248:
239:
238:
234:
225:
223:
215:
214:
210:
205:
191:Time complexity
181:
174:
171:
158:
145:
127:
102:
96:
82:
56:O(n) schedulers
17:
12:
11:
5:
1725:
1723:
1715:
1714:
1704:
1703:
1697:
1696:
1694:
1693:
1681:
1667:
1652:
1649:
1648:
1645:
1644:
1642:
1641:
1635:
1633:
1629:
1628:
1626:
1625:
1620:
1619:
1618:
1613:
1605:
1604:
1603:
1595:
1590:
1585:
1579:
1577:
1566:
1560:
1559:
1556:
1555:
1552:
1551:
1549:
1548:
1547:
1546:
1541:
1536:
1531:
1526:
1518:
1517:
1516:
1511:
1506:
1501:
1491:
1490:
1489:
1484:
1473:
1471:
1469:Virtualization
1462:
1461:
1460:
1459:
1454:
1443:
1442:
1441:
1436:
1431:
1426:
1416:
1415:
1414:
1409:
1404:
1394:
1393:
1392:
1387:
1376:
1374:
1370:
1369:
1367:
1366:
1361:
1356:
1351:
1346:
1341:
1335:
1334:
1329:
1328:
1327:
1322:
1315:Device drivers
1311:
1310:
1305:
1300:
1295:
1290:
1285:
1280:
1270:
1269:
1264:
1259:
1257:SCHED_DEADLINE
1254:
1252:O(1) scheduler
1249:
1247:O(n) scheduler
1244:
1242:Noop scheduler
1239:
1233:
1227:
1222:
1215:
1214:
1209:
1204:
1199:
1194:
1189:
1184:
1179:
1174:
1169:
1164:
1159:
1154:
1148:
1143:
1138:
1133:
1128:
1123:
1118:
1113:
1108:
1103:
1098:
1096:Kernel modules
1092:
1090:
1086:
1085:
1082:
1081:
1078:
1077:
1075:
1074:
1069:
1064:
1059:
1054:
1049:
1044:
1043:
1042:
1037:
1032:
1027:
1022:
1017:
1016:
1015:
1005:
1000:
989:
987:
979:
978:
976:
975:
970:
969:
968:
958:
953:
948:
945:
942:
937:
934:
931:
926:
921:
916:
911:
906:
902:
900:
886:
880:
879:
876:
875:
873:
872:
867:
862:
857:
852:
850:Memory barrier
847:
842:
837:
832:
827:
821:
819:
813:
812:
810:
809:
808:
807:
804:
799:
794:
789:
784:
779:
769:
768:
767:
764:
759:
754:
749:
744:
739:
728:
726:
715:
708:
702:
701:
699:
698:
693:
687:
685:
679:
678:
676:
675:
670:
665:
660:
655:
649:
647:
641:
640:
638:
637:
632:
627:
622:
617:
612:
606:
604:
597:
593:
592:
589:
588:
586:
585:
584:
583:
575:
574:
573:
568:
563:
558:
547:
545:
541:
540:
538:
537:
532:
527:
522:
517:
512:
507:
502:
497:
492:
487:
482:
476:
474:
467:
463:
462:
457:
455:
454:
447:
440:
432:
426:
425:
412:
406:
393:
385:
384:External links
382:
379:
378:
350:
320:
299:
278:
257:
232:
207:
206:
204:
201:
200:
199:
193:
187:
186:
170:
167:
157:
154:
144:
141:
126:
123:
110:Big O notation
100:Big O notation
98:Main article:
95:
92:
81:
78:
37:O(1) scheduler
15:
13:
10:
9:
6:
4:
3:
2:
1724:
1713:
1710:
1709:
1707:
1692:
1691:
1682:
1680:
1679:
1668:
1666:
1665:
1660:
1654:
1653:
1650:
1640:
1637:
1636:
1634:
1630:
1624:
1621:
1617:
1614:
1612:
1609:
1608:
1606:
1602:
1599:
1598:
1597:Thin client:
1596:
1594:
1591:
1589:
1586:
1584:
1581:
1580:
1578:
1576:
1570:
1567:
1565:
1561:
1545:
1542:
1540:
1537:
1535:
1532:
1530:
1527:
1525:
1522:
1521:
1519:
1515:
1512:
1510:
1507:
1505:
1502:
1500:
1499:Linux-VServer
1497:
1496:
1495:
1492:
1488:
1485:
1483:
1480:
1479:
1478:
1475:
1474:
1472:
1470:
1466:
1458:
1455:
1453:
1450:
1449:
1447:
1444:
1440:
1437:
1435:
1432:
1430:
1427:
1425:
1422:
1421:
1420:
1417:
1413:
1410:
1408:
1405:
1403:
1400:
1399:
1398:
1395:
1391:
1388:
1386:
1383:
1382:
1381:
1378:
1377:
1375:
1371:
1365:
1362:
1360:
1357:
1355:
1352:
1350:
1347:
1345:
1342:
1340:
1337:
1336:
1333:
1330:
1326:
1323:
1321:
1318:
1317:
1316:
1313:
1312:
1309:
1306:
1304:
1301:
1299:
1296:
1294:
1291:
1289:
1286:
1284:
1281:
1279:
1275:
1272:
1271:
1268:
1265:
1263:
1260:
1258:
1255:
1253:
1250:
1248:
1245:
1243:
1240:
1237:
1234:
1231:
1228:
1226:
1223:
1220:
1217:
1216:
1213:
1210:
1208:
1205:
1203:
1200:
1198:
1195:
1193:
1190:
1188:
1185:
1183:
1180:
1178:
1175:
1173:
1170:
1168:
1165:
1163:
1160:
1158:
1155:
1152:
1149:
1147:
1144:
1142:
1139:
1137:
1134:
1132:
1129:
1127:
1124:
1122:
1121:Device mapper
1119:
1117:
1114:
1112:
1109:
1107:
1104:
1102:
1099:
1097:
1094:
1093:
1091:
1087:
1073:
1070:
1068:
1065:
1063:
1060:
1058:
1055:
1053:
1050:
1048:
1045:
1041:
1038:
1036:
1033:
1031:
1028:
1026:
1023:
1021:
1018:
1014:
1011:
1010:
1009:
1006:
1004:
1001:
999:
996:
995:
994:
991:
990:
988:
986:
980:
974:
971:
967:
964:
963:
962:
959:
957:
954:
952:
949:
946:
943:
941:
938:
935:
932:
930:
927:
925:
922:
920:
917:
915:
912:
910:
907:
904:
903:
901:
899:
894:
890:
887:
885:
881:
871:
868:
866:
863:
861:
858:
856:
853:
851:
848:
846:
843:
841:
838:
836:
833:
831:
828:
826:
823:
822:
820:
818:
814:
805:
803:
800:
798:
795:
793:
790:
788:
785:
783:
780:
778:
775:
774:
773:
770:
765:
763:
760:
758:
755:
753:
750:
748:
745:
743:
740:
738:
735:
734:
733:
730:
729:
727:
725:
719:
716:
712:
709:
707:
703:
697:
694:
692:
689:
688:
686:
684:
680:
674:
671:
669:
666:
664:
661:
659:
656:
654:
651:
650:
648:
646:
642:
636:
633:
631:
628:
626:
623:
621:
618:
616:
613:
611:
608:
607:
605:
601:
598:
594:
582:
579:
578:
576:
572:
569:
567:
564:
562:
559:
557:
556:
552:
551:
549:
548:
546:
542:
536:
533:
531:
528:
526:
523:
521:
518:
516:
513:
511:
508:
506:
503:
501:
498:
496:
493:
491:
488:
486:
483:
481:
478:
477:
475:
471:
468:
464:
460:
453:
448:
446:
441:
439:
434:
433:
430:
422:
418:
413:
410:
407:
404:
400:
397:
394:
391:
388:
387:
383:
368:
364:
360:
354:
351:
340:
339:
331:
324:
321:
310:
303:
300:
289:
282:
279:
268:
265:Robert Love.
261:
258:
247:
246:linux journal
243:
236:
233:
222:
218:
212:
209:
202:
197:
194:
192:
189:
188:
184:
178:
173:
168:
166:
163:
155:
153:
150:
142:
140:
138:
133:
124:
122:
120:
119:quadratically
116:
111:
107:
101:
93:
91:
88:
79:
77:
75:
70:
68:
63:
61:
57:
53:
49:
45:
42:
38:
30:
26:
21:
1688:
1669:
1655:
1385:Linux kernel
1303:Tomoyo Linux
1251:
898:File systems
553:
505:SCO disputes
466:Organization
459:Linux kernel
421:the original
370:. Retrieved
366:
353:
342:. Retrieved
336:
323:
312:. Retrieved
302:
291:. Retrieved
281:
270:. Retrieved
260:
249:. Retrieved
245:
235:
224:. Retrieved
220:
211:
183:Linux portal
159:
146:
132:Linux kernel
128:
103:
83:
71:
64:
36:
34:
29:Linux kernel
1390:Linux-libre
1283:Exec Shield
1162:Framebuffer
865:Video4Linux
722:System Call
550:Developers
490:Linus's law
367:lkml.iu.edu
156:Replacement
149:interactive
1477:Hypervisor
1439:PREEMPT_RT
1344:KernelCare
1332:Raw device
1262:SCHED_FIFO
1172:KMS driver
1089:Components
944:securityfs
830:Crypto API
772:Linux-only
658:System.map
561:kernel.org
520:menuconfig
515:GNU GPL v2
372:2018-08-30
344:2014-09-09
328:Josh Aas.
314:2014-09-09
307:Rob Bell.
293:2014-09-09
272:2014-09-09
251:2014-09-09
226:2019-07-19
203:References
44:scheduling
1616:LYME-LYCE
1339:initramfs
1308:Linux PAM
1177:Netfilter
1047:libcgroup
1013:libhybris
985:libraries
933:hugetlbfs
884:Userspace
817:In-kernel
802:readahead
724:Interface
673:initramfs
630:SystemTap
603:Debugging
596:Technical
535:Criticism
137:runqueues
106:algorithm
87:preempted
48:processes
1706:Category
1690:Category
1632:Adopters
1607:Server:
1588:Embedded
1564:Adoption
1457:PSXLinux
1380:Mainline
1373:Variants
1325:graphics
1278:AppArmor
1267:SCHED_RR
1187:nftables
1131:dm-crypt
1126:dm-cache
1072:liburing
1062:libevdev
1020:dietlibc
909:configfs
835:io uring
399:Archived
169:See also
80:Overview
1623:Devices
1583:Desktop
1544:coLinux
1539:MkLinux
1524:L4Linux
1452:ÎĽClinux
1434:Xenomai
1424:RTLinux
1364:Ksplice
1293:SELinux
1288:seccomp
1238:(EEVDF)
1182:Netlink
1111:Console
1106:cgroups
1057:libalsa
983:Wrapper
961:systemd
924:debugfs
893:Daemons
855:New API
797:inotify
792:dnotify
696:x32 ABI
653:vmlinux
645:Startup
544:Support
1593:Gaming
1575:of use
1529:ELinOS
1520:Other
1514:OpenVZ
1504:Lguest
1448:-less
1359:kpatch
1354:kGraft
1320:802.11
1116:bcache
1067:libusb
1052:libdrm
1040:Newlib
1025:EGLIBC
1008:Bionic
1003:uClibc
973:Kmscon
947:sockfs
940:procfs
936:pipefs
919:devpts
845:kernfs
787:splice
742:select
714:Kernel
668:initrd
663:dracut
615:ftrace
577:Users
510:Linaro
473:Kernel
338:GitHub
143:Issues
60:scales
41:kernel
1573:Range
1412:SLURM
1349:kexec
1298:Smack
1232:(CFS)
1212:zswap
1153:(KSM)
1146:evdev
1101:BlueZ
1030:klibc
998:glibc
956:tmpfs
951:sysfs
914:devfs
905:bpffs
782:epoll
777:futex
757:close
737:ioctl
732:POSIX
620:kdump
333:(PDF)
286:dws.
1611:LAMP
1601:LTSP
1429:RTAI
1207:zram
1202:SLUB
1197:perf
1141:EDAC
1035:musl
966:udev
929:FUSE
825:ALSA
762:sync
752:read
747:open
706:APIs
683:ABIs
610:CRIU
566:LKML
358:<
115:O(n)
1509:LXC
1487:Xen
1482:KVM
1446:MMU
1402:INK
1167:LVM
1157:LIO
1136:DRM
870:IIO
860:RCU
840:DRM
635:BPF
500:Tux
104:An
35:An
1708::
1276::
365:.
335:.
244:.
219:.
76:.
1221::
895:,
806:…
766:…
451:e
444:t
437:v
375:.
347:.
317:.
296:.
275:.
254:.
229:.
31:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
