İşletim Sistemlerinin Öncüleri

Komutların ve verinin aynı bellekte durduğu depolanmış program (stored-program) modelinin biçimlenmesine katkı yaptı.

Mimari, bellek, yürütme, ayrıcalıklı denetim ve program yükleme bu modele dayanır.

Güçlü bir bilgisayarı birçok kullanıcının zaman paylaşımıyla aynı anda kullanması fikrini savundu. Bu öneriyi 1959'da MIT'de yazdığı bir notla ortaya koydu.

Zaman paylaşımı; çizelgeleme (scheduling), zamanlayıcı kesmeleri, bağlam değiştirme (context switch) ve çok kullanıcılı koruma ihtiyacını doğurdu.

MIT'de CTSS ve Multics gibi etkili zaman paylaşımlı sistem projelerini yönetti. Bu çalışmalarla 1990'da Turing Ödülü'nü (Turing Award) aldı.

Multics; koruma halkalarını, hiyerarşik dosya sistemini, dinamik bağlamayı ve çok kullanıcılı kullanımı ileri taşıdı.

Semaforu (semaphore) tanıttı ve katmanlı THE sistemini tasarladı. Senkronizasyonun ve eş zamanlı programlamanın temellerini attı.

Kritik bölge (critical section), karşılıklı dışlama (mutual exclusion), kilitlenme (deadlock) ve açlık (starvation) bugün de işletim sistemlerinin temel sorunlarıdır.

Yerelliği (locality) ve sanal bellek başarımını açıklamak için çalışma kümesi (working set) modelini geliştirdi.

Bu model sayfa hatalarını (page fault), bellek baskısını ve boşa çabalamayı (thrashing) açıklar.

UNIX'i Dennis Ritchie ile birlikte geliştirdi. Basit ve birbirine eklenebilen araçlara dayanan yalın bir tasarım anlayışı kurdu.

UNIX; süreç (process), dosya tanımlayıcısı (file descriptor), boru (pipe), kabuk (shell) ve hiyerarşik dosya sistemi kavramlarını biçimlendirdi.

C dilini yarattı ve UNIX'i birlikte geliştirdi. Böylece taşınabilir sistem yazılımı mümkün oldu.

UNIX'in 1973'te büyük ölçüde C ile yeniden yazılması, bir işletim sisteminin farklı donanımlara taşınabileceğini gösterdi.

Eş zamanlı programlama ve işletim sistemi yapısı için etkili soyutlamalar geliştirdi. RC 4000 çekirdeği ve Concurrent Pascal dili bu çalışmaların ürünüdür.

Monitöre (monitor) dayalı senkronizasyon, paylaşılan veriye erişimi daha düzenli hâle getirdi.

Eş zamanlılık çalışmalarına monitörleri ve Communicating Sequential Processes (CSP, iletişen ardışık süreçler) modelini kazandırdı.

Bu çalışmalar senkronizasyon, kanallar ve ileti geçirme (message passing) için açık modeller sunar.

Alto gibi etkili kişisel bilgisayar projelerine ve dağıtık sistem çalışmalarına katkı yaptı.

Sistem çalışmaları koruma, adlandırma, ağ ve güvenilir arayüz tasarımını bir araya getirir.

UNIX uyumlu, özgür bir yazılım sistemi kurmak için GNU Projesi'ni başlattı.

GNU derleyicileri, kütüphaneleri, kabukları ve araçları UNIX benzeri sistemlerin merkezine yerleşti.

İlk Macintosh'un sistem yazılımı ve Macintosh Toolbox üzerinde çalıştı.

İlk Macintosh yazılımı, masaüstü grafik kullanıcı arayüzünden (GUI) beklentileri ve sıkı bütünleşik sistem hizmetlerini etkiledi.

MINIX'i geliştirdi ve etkili işletim sistemi ders kitapları yazdı.

MINIX; mikro çekirdek (microkernel), süreçler arası iletişim (IPC), süreç ve dosya sistemi kavramlarını bütün bir sistem üzerinde incelenebilir kılar.

DEC'te RSX-11M ve VMS gibi büyük işletim sistemi projelerini, ardından Microsoft'ta Windows NT'yi yönetti.

Windows NT; korumalı bellek, güvenlik, eş zamansız G/Ç (giriş/çıkış) ve taşınabilirlik için güçlü soyutlamalar kurdu.

Gömülü ve gerçek zamanlı sistemlerde etkili olan TRON projesini 1984'te başlattı.

ITRON belirlenimci çizelgelemeyi, kesme gecikmesini ve son tarihe göre tasarımı öne çıkarır.

Linux çekirdeğini yarattı. Bu çekirdek bugün sunucularda, bulut sistemlerinde, Android'de, gömülü aygıtlarda ve süper bilgisayarlarda çalışır.

Linux, büyük bir monolitik çekirdeğin (monolithic kernel) içinde modüler alt sistemlerin nasıl kurulabileceğini gösterir.

Tek başına çalışan toplu iş makinelerinin ötesinde, etkileşimli ve ağa bağlı bir bilgisayar kullanımını savundu.

Etkileşimli kullanım; düşük gecikmeyi, zaman paylaşımını ve uzaktan erişimi önemli hâle getirdi.

NLS projesini yönetti. Etkileşimli kullanımı, hiper metni, ortak çalışma araçlarını ve fareyi 1968'deki ünlü gösterimde tanıttı.

Bu çalışmalar olay güdümlü G/Ç'ye, ekranlara ve hızlı tepki veren grafik ortamlara olan ihtiyacı artırdı.

UNIX borularını önerdi. Borular 1973'te UNIX'e eklendi. McIlroy “yazılım araçları” anlayışını da derinden etkiledi.

Borular, bağımsız programların standart giriş ve çıkış akışları üzerinden birbirine bağlanmasını sağlar.

UNIX yazılım ortamına katkı yaptı. AWK gibi etkili araçları ve programlama kitaplarını başkalarıyla birlikte yazdı.

Bu çalışmalar komut satırında araçları birleştirmeyi, betik yazmayı ve taşınabilir sistem programlamayı biçimlendirdi.

UNIX Version 6 çekirdeğinin kaynak kodunu satır satır açıklayan etkili bir çalışma hazırladı: Lions' Commentary on UNIX 6th Edition.

Süreç tabloları, tuzaklar (trap), çizelgeleme, i-node'lar ve sistem çağrısı (system call) yolları bu çalışma sayesinde öğrencilere açıldı.

BSD UNIX'in başlıca geliştiricilerinden biridir. vi düzenleyicisini ve csh kabuğunu yazdı.

BSD; ağ, iş istasyonları ve sonraki UNIX türevleri üzerinde büyük etki bıraktı.

BSD'nin önde gelen geliştiricilerindendir. Özellikle Fast File System (FFS, hızlı dosya sistemi) ve FreeBSD çalışmalarıyla tanınır.

FFS, dosya sisteminde yerelliği, blok tahsisini ve disk başarımını iyileştirdi.

Bir mimarinin sanal makineleri hangi koşullarda verimli biçimde destekleyebileceğini belirleyen biçimsel ölçütleri 1974'te Robert P. Goldberg ile birlikte ortaya koydu.

Popek–Goldberg ölçütleri, hipervizörlerin (hypervisor) ve tuzakla öykünmeye (trap-and-emulate) dayalı sanallaştırmanın temeli oldu.

Sanal makine izleyicilerinin (virtual machine monitor, VMM) biçimsel olarak incelenmesinin temellerini attı.

Bu çalışmalar eşdeğerliği, kaynak denetimini ve verimliliği bir VMM'nin temel özellikleri olarak belirledi.

Dağıtık sistemlerde olayların sırası, saatler ve doğruluk üzerine akıl yürütmenin temel yöntemlerini geliştirdi.

Mantıksal saatler ve “önce gelir” (happens-before) ilişkisi, dağıtık eşgüdümün ve çoğaltmanın temelini oluşturur.

Programlama dillerinde soyutlamaya (abstraction) ve hataya dayanıklı dağıtık sistem tasarımına öncülük etti.

Bu çalışmalar modüler arayüzleri, atomik işlemleri ve güvenilir hizmet tasarımını güçlendirdi.

Manchester'daki bilgisayar projelerini yönetti. Bunlardan Atlas (1962), sanal bellek tarihinde bir dönüm noktasıdır.

Atlas; sayfalamanın (paging), bellek ile depolama arasında kendiliğinden veri taşımanın ve adres çevirisinin uygulamada işe yaradığını gösterdi.

EDSAC'ı (1949) geliştiren ekibi yönetti. İşlemci denetimi için mikroprogramlamayı 1951'de önerdi.

Bu çalışmalar donanım–yazılım arayüzünü ve yeniden kullanılabilir sistem yazılımı uygulamalarını biçimlendirdi.

EDSAC üzerinde yeniden kullanılabilir alt programlara ve ilk programlama yöntemlerine önemli katkılar yaptı.

Alt program çağrıları zamanla çağrı kurallarına, yığınlara (stack), kütüphanelere ve çalışma zamanı desteğine dönüştü.

Pascal, Modula-2 ve Oberon gibi etkili programlama dilleri tasarladı. Jürg Gutknecht ile birlikte küçük ve derli toplu Oberon işletim sistemini geliştirdi.

Oberon; dilin ve işletim sisteminin birlikte tasarlanabileceğini, yalınlığı ve tutarlı bir etkileşimli sistem kurmayı gösterdi.

UNIX üzerinde çalıştı. Parola güvenliği ve sistem koruması alanında etkili katkılar yaptı; Ken Thompson ile yazdığı Password Security: A Case History (1979) bunların en bilinenidir.

Bu çalışmalar kimlik doğrulamayı (authentication), tuzlu (salted) parola özetlemeyi, ayrıcalık ayrımını ve tehdit modellemeyi birbirine bağlar.

1883'te yayımlanan La cryptographie militaire makalesinde askerî şifreler için altı kural sıraladı. Bunların en bilineni, sistemin düşman eline geçse bile güvenli kalması gerektiğini söyler: güvenlik algoritmanın gizliliğine değil, yalnız anahtarın gizliliğine dayanmalıdır.

İlke, açık tasarımın ve geniş anahtar uzayının neden önemli olduğunu açıklar; işletim sistemlerinin kullandığı şifreleme ve kimlik doğrulama düzenekleri bu varsayımla tasarlanır.

IBM'de System/360 donanımının ardından 1964'te gecikmiş OS/360 projesinin yönetimini üstlendi. Deneyimlerini 1975'te yayımlanan The Mythical Man-Month kitabında anlattı; kitaptaki en ünlü gözlem, geciken bir yazılım projesine yeni insan eklemenin projeyi daha da geciktirdiğidir (Brooks yasası). 1999'da Turing Ödülü'nü aldı.

OS/360, büyük bir işletim sisteminin karmaşıklığını yöneten ilk geniş çaplı denemelerden biriydi; Brooks'un dersleri işletim sistemi tasarımında ekip, arayüz ve kavramsal bütünlük tartışmalarının hâlâ çıkış noktasıdır.

IBM Watson Araştırma Merkezi'nde çalıştı. 1966'da IBM Systems Journal'da yayımlanan çalışmasında, gelecekte en geç kullanılacak sayfayı çıkaran algoritmanın (OPT ya da MIN) en az sayfa hatasını verdiğini gösterdi. 1969'da Nelson ve Shedler ile birlikte, FIFO'da çerçeve sayısı artınca sayfa hatası sayısının da artabildiğini buldu; bu durum Bélády anomalisi diye anılır.

OPT gerçeklenemez, ama öteki yer değiştirme algoritmalarının ölçüldüğü alt sınırdır. Anomali de LRU gibi yığın algoritmalarını FIFO'dan ayıran özelliği gösterir.

IBM System/360 mimarisinin baş tasarımcılarındandır. 1967'deki AFIPS konferansında, bir programın paralelleştirilemeyen seri kısmının hızlanmaya kesin bir üst sınır koyduğunu savundu. Bu gözlem sonradan Amdahl yasası adıyla formüle edildi: seri pay s ise, çekirdek sayısı ne kadar artarsa artsın hızlanma 1/s'yi geçemez.

Yasa, çok çekirdekli işlemcilerde iş parçacığı sayısını artırmanın neden bir noktadan sonra az kazandırdığını açıklar ve kilitlerle seri kesimleri kısaltmanın önemini gösterir.

1968'de yayımlanan The Art of Computer Programming serisinin ilk cildinde dinamik bellek ayırmayı (ilk uyan, en iyi uyan, buddy (kardeş) sistemi) ayrıntılı biçimde çözümledi. %50 kuralı bu çözümlemeden çıkar: ilk uyanla çalışan bir sistemde N tahsisli blok varken ortalamada yaklaşık 0,5 N boş delik bulunur, yani belleğin yaklaşık üçte biri parçalanma yüzünden kullanılamaz hâle gelebilir.

Kural, dış parçalanmanın ne kadar büyük olabileceğini tek bir sayıyla özetler ve sayfalama gibi parçalanmayı ortadan kaldıran yöntemlere neden ihtiyaç duyulduğunu açıklar.

M. J. Elphick ve A. Shoshani ile 1971'de ACM Computing Surveys'de yayımladığı “System Deadlocks” makalesinde kilitlenmenin dört gerekli koşulunu sıraladı: karşılıklı dışlama, tut ve bekle, kesilemezlik ve döngüsel bekleme. Bu koşullar onun adıyla Coffman koşulları diye anılır. Makale, her türden birden çok örneği olan kaynaklar için bir kilitlenme tespit algoritması da verir.

Kilitlenmeyi önleme yöntemlerinin hepsi bu dört koşuldan birini bozmaya dayanır; tespit algoritması da bugün ders kitaplarında anlatılan biçimin temelidir.

“Some Deadlock Properties of Computer Systems” çalışmasını 1971'de SOSP'ta sundu, genişletilmiş biçimini 1972'de ACM Computing Surveys'de yayımladı. Süreçleri ve kaynakları iki tür düğüm, istekleri ve atamaları da kenar olarak gösteren çizge modeli bugün kaynak tahsis çizgesi adıyla bilinir.

Çizge, kilitlenmenin nasıl oluştuğunu görünür kılar ve tespit algoritmalarının üzerinde çalıştığı veri yapısıdır: her kaynaktan tek örnek varsa çizgedeki döngü kilitlenme demektir.

MIT Project MAC'ten Liu ile Jet Propulsion Laboratory'den Layland, 1973'te Journal of the ACM'de yayımladıkları makalede periyodik görevlerin katı gerçek zamanlı çizelgelenmesini incelediler. Hız monoton (RM) önceliklerin sabit öncelikli yöntemler arasında en iyisi olduğunu kanıtladılar ve n görev için n(2^1/n − 1) kullanım sınırını verdiler. Aynı makale, toplam kullanımı 1'i aşmayan her görev kümesinin en erken son tarih önce (EDF) ile çizelgelenebildiğini gösterir.

Liu–Layland testi, bir görev kümesinin son tarihlerini kaçırmadan çalışıp çalışamayacağını çizelgeyi kurmadan söyler; gerçek zamanlı işletim sistemlerindeki öncelik atamalarının kuramsal dayanağıdır.

MITRE Corporation'da 1973'te çok düzeyli güvenlik için biçimsel bir model geliştirdiler. Modelin iki temel kuralı vardır: basit güvenlik özelliğine göre bir süreç kendi düzeyinin üstündeki nesneleri okuyamaz (yukarı okuma yok); * özelliğine göre de kendi düzeyinin altındaki nesnelere yazamaz (aşağı yazma yok).

Model, bilginin yüksek gizlilik düzeyinden alçak düzeye sızmasını kurallarla engeller; zorunlu erişim denetiminin (MAC) ve askerî sınıflandırma düzenlerinin bilgisayardaki karşılığıdır.

1975'te Proceedings of the IEEE'de yayımladıkları “The Protection of Information in Computer Systems” makalesinde güvenli sistem tasarımı için sekiz ilke sıraladılar. Düzeneğin sade tutulması, varsayılanın reddetmek olması, her erişimin denetlenmesi, açık tasarım, ayrıcalık ayrımı ve en az ayrıcalık bu ilkeler arasındadır. Saltzer, Multics projesinde de çalışmıştı.

İlkeler, erişim denetimi, setuid programlar ve ayrıcalık ayrımı gibi işletim sistemi düzeneklerini değerlendirmek için bugün de kullanılan ortak bir ölçüt sunar.

1976'da IEEE Transactions on Information Theory'de yayımladıkları “New Directions in Cryptography” makalesinde açık anahtarlı şifreleme fikrini ve adlarıyla anılan anahtar değişimini ortaya koydular. İki taraf, güvensiz bir kanal üzerinden yalnız açık değerler göndererek ortak bir gizli anahtar üretebilir. 2015 Turing Ödülü'nü birlikte aldılar.

Önceden paylaşılmış bir anahtar gerektirmeyen bu değişim, TLS el sıkışmasının ve dijital imzaların temelidir; işletim sistemlerinin ağ üzerinden kimlik doğrulama ve güvenli iletişim hizmetleri buna dayanır.

MITRE Corporation'daki “Integrity Considerations for Secure Computer Systems” raporunda (1977) bütünlüğü korumak için Bell-LaPadula modelinin tersi kurallara dayanan bir model tanımladı. Bir süreç kendinden düşük bütünlük düzeyindeki nesneleri okuyamaz (aşağı okuma yok) ve kendinden yüksek düzeydeki nesnelere yazamaz (yukarı yazma yok).

Model, güvenilmeyen verinin güvenilir bileşenleri bozmasını engeller; Windows'taki bütünlük düzeyleri gibi zorunlu bütünlük denetimleri bu fikrin uygulamalarıdır.

1981'de Information Processing Letters'ta yayımlanan “Myths About the Mutual Exclusion Problem” makalesinde, iki süreç için yalnız okuma ve yazma işlemleriyle doğru çalışan kısa bir karşılıklı dışlama çözümü verdi. Algoritma, her sürecin “girmek istiyorum” bayrağını sıranın kimde olduğunu tutan tek bir değişkenle birleştirir.

Algoritma, kritik bölge probleminin üç koşulunu (karşılıklı dışlama, ilerleme, sınırlı bekleme) sağlayan çözümün klasik örneğidir; modern işlemcilerde bellek bariyeri olmadan neden bozulduğu da bellek sıralamasının önemini gösterir.

Stanford Üniversitesi'nde geliştirdikleri WSClock algoritmasını 1981'de SOSP'ta sundular. Algoritma, çalışma kümesi fikrini saat algoritmasının dairesel çerçeve listesiyle birleştirir: el çerçeveler üzerinde sırayla gezinir ve tüm tabloyu taramadan ilk uygun kurbanda durur.

WSClock, çalışma kümesi modelinin pratikte uygulanabilir bir biçimidir; sayfa yer değiştirmede yerellik bilgisini düşük maliyetle kullanır.

Xerox PARC'ta Cedar ortamı için geliştirdikleri RPC paketini 1984'te ACM Transactions on Computer Systems'te yayımlanan “Implementing Remote Procedure Calls” makalesinde anlattılar. Başka bir makinedeki bir prosedür, otomatik üretilen istemci ve sunucu koçanları sayesinde sıradan bir yerel çağrı sözdizimiyle çağrılabilir.

RPC, ileti geçirmenin ayrıntılarını programcıdan gizleyen temel dağıtık sistem soyutlamasıdır; NFS gibi dağıtık dosya sistemleri ve bugünkü gRPC benzeri çerçeveler bu modele dayanır.

Sandia Ulusal Laboratuvarları'nda 1024 işlemcili bir sistem üzerindeki çalışmalarına dayanarak 1988'de Communications of the ACM'de “Reevaluating Amdahl's Law” notunu yayımladı. Çekirdek sayısı artınca genellikle problemin de büyüdüğünü, bu durumda ölçeklenmiş hızlanmanın çekirdek sayısıyla neredeyse doğrusal arttığını gösterdi.

Amdahl “bu iş ne kadar hızlı biter?”, Gustafson ise “aynı sürede ne kadar büyük bir iş yapılabilir?” sorusunu cevaplar; ikisi birlikte paralel sistemlerin ölçeklenmesini değerlendirmenin iki yüzüdür.

UC Berkeley'de 1988'de SIGMOD'da sundukları “A Case for Redundant Arrays of Inexpensive Disks (RAID)” makalesinde, pahalı tek büyük disk yerine ucuz küçük disklerden oluşan ve fazlalıkla korunan diziler kurmayı önerdiler. Makale beş RAID düzeyi tanımlayıp maliyet ve başarımlarını karşılaştırdı. Kısaltmadaki “I” sonradan independent olarak yeniden tanımlandı.

Şeritleme, aynalama ve eşlik bilgisi bugün işletim sistemlerinin yazılım RAID katmanlarında ve depolama denetleyicilerinde kullanılan temel güvenilirlik ve başarım yöntemleridir.

Sprite işletim sistemi için geliştirdikleri günlük yapılı dosya sistemini (LFS) 1991'de SOSP'ta sundular. Tasarım, okumaların çoğunun önbellekten karşılanacağını ve diske giden trafiğin ağırlıkla yazma olacağını varsayar; bu yüzden bütün değişiklikler diske tek bir uzun sıralı günlük olarak yazılır. Günlük kesimlere bölünür ve bir temizleyici dağınık kesimlerdeki canlı veriyi sıkıştırarak boş alan açar.

LFS, yazmaları sıralı hâle getirerek küçük dosya yükünde büyük başarım kazancı sağladı ve çökme sonrası kurtarmayı hızlandırdı; fikirleri günlüklemeli ve yazınca kopyalayan dosya sistemlerinde, SSD'lerin çeviri katmanlarında yaşamaya devam eder.

1991'de ACM Transactions on Computer Systems'te yayımlanan makalelerinde, adlarının baş harfleriyle anılan MCS kuyruk kilidini önerdiler. Bekleyenler bir bağlı liste oluşturur; her bekleyen ayrı bir önbellek satırındaki kendi bayrağında döner ve kilidi bırakmak tek bir uzak yazmayla olur. Bu çalışma 2006 Dijkstra Ödülü'nü aldı.

Tek bir paylaşılan değişkende dönen kilitler çekirdek sayısı arttıkça önbellek tutarlılık trafiğinde boğulur; MCS bu sorunu çözen ölçeklenebilir senkronizasyonun temel örneğidir ve Linux'un qspinlock'u bu fikre dayanır.

MIT'de 1994'te OSDI'da sundukları piyango çizelgelemede (lottery scheduling) her sürece bilet verilir ve her dilimde rastgele çekilen biletin sahibi çalışır; daha çok bilet, işlemcide daha büyük pay demektir. Waldspurger 1995'te aynı payları rastgelelik olmadan sağlayan stride çizelgelemeyi önerdi.

Bu yöntemler orantılı pay (proportional share) fikrini basit ve anlaşılır biçimde gerçekledi; Linux'un CFS ve EEVDF çizelgeleyicilerindeki ağırlıklı adil paylaşım aynı soyağacından gelir.

Sun Microsystems'te SunOS 5.4 (Solaris) çekirdeği için tasarladığı slab ayırıcıyı 1994'te USENIX Summer konferansında yayımladı. Ayırıcı, sık kullanılan çekirdek nesnelerini önceden hazırlanmış önbelleklerde tutar; nesneler tam boyutludur ve sayfa içinde yan yana paketlenir.

Slab ayırıcı, çekirdek nesneleri için iç parçalanmayı ve ilk değer verme maliyetini azaltır; Linux'un SLAB ve SLUB ayırıcıları bu tasarımdan türemiştir.

MIT'de James O'Toole ile birlikte 1995'te SOSP'ta sundukları exokernel mimarisinde çekirdek yalnız donanım kaynaklarını korumalı biçimde dağıtır ve sahipliği izler. Sanal bellek ve dosya gibi soyutlamaları kullanıcı modunda çalışan kütüphane işletim sistemleri sağlar. Prototipte çekirdeğin adı Aegis, kütüphane işletim sisteminin adı ExOS'tur.

“Yönetimi korumadan ayırmak” sloganı, çekirdekte ne kadar işlev bulunması gerektiği tartışmasının uç noktasıdır; fikir bugün unikernel'lerde ve DPDK, SPDK gibi çekirdeği atlayan G/Ç kütüphanelerinde yaşar.

1995'te önerdikleri “Earliest Eligible Virtual Deadline First” (EEVDF) algoritması orantılı pay çizelgelemeyi iki net ölçüte dayandırır: bir görev ancak payının gerisinde kaldığında uygundur ve uygun görevler arasından sanal son tarihi en erken olan seçilir. Algoritmayı Linux çekirdeğine Peter Zijlstra uyarladı; EEVDF, 6.6 sürümünden itibaren CFS'in yerini aldı.

EEVDF, adaleti korurken gecikmeye duyarlı görevlere daha kısa dilimler verebilir; bugün Linux'ta sıradan görevlerin varsayılan çizelgeleyicisidir.

Linux çekirdeğine 2.6.0 sürümüyle gelen O(1) çizelgeleyiciyi yazdı. 2007'de 2.6.23 sürümüyle O(1)'in yerini alan tamamen adil çizelgeleyiciyi (Completely Fair Scheduler, CFS) geliştirdi. CFS ideal bir çok görevli işlemciye öykünür: her görevin sanal çalışma süresini (vruntime) tutar ve kırmızı-siyah ağaçta en geride kalan görevi çalıştırır.

CFS, Linux'ta on beş yılı aşkın süre sıradan görevlerin varsayılan çizelgeleyicisi oldu ve ağırlıklı adil paylaşımı geniş ölçekte uygulanabilir kıldı.