Bölüm 12: Çok İşlemcili Sistemler

12.1Neden çok işlemci?

Bir bilgisayarı hızlandırmanın en eski yolu saat hızını artırmaktı. 1980'lerden 2000'lerin başına kadar işlemcilerin saat hızı her birkaç yılda bir ikiye katlandı. Bu yol 2005 dolaylarında tıkandı. Bugün de masaüstü işlemcilerin saat hızı 3 ile 5 GHz arasındadır. Yarı iletken üreticileri her yıl daha çok transistörü bir yongaya sığdırmayı sürdürüyor. Ama bu transistörler artık daha hızlı tek bir çekirdeğe değil, daha çok çekirdeğe harcanıyor. Bu kesim, paralel sistemlerin üç temel düzenini ve paralelliğin getirdiği kazancın sınırını anlatır.

12.1.1Üç paralel düzen

Birden çok işlemciyi bir arada çalıştırmanın üç ana yolu vardır (Şekil 12.1). Birincisinde bütün işlemciler tek bir ortak belleğe bağlıdır. Her işlemci her bellek sözcüğünü sıradan LOAD ve STORE komutlarıyla okuyup yazabilir. Buna paylaşımlı bellekli çok işlemci (shared-memory multiprocessor) denir. İkincisinde her işlemcinin kendi belleği vardır ve işlemciler hızlı bir ara bağlantıyla birbirine bağlanır. Bir işlemci başkasının belleğini doğrudan okuyamaz; veri ancak iletiyle gönderilir. Bu düzene çoklu bilgisayar (multicomputer) ya da küme denir. Üçüncüsünde tam bilgisayarlar, yani kendi diski, çevre birimleri ve işletim sistemi olan makineler, İnternet gibi geniş alanlı bir ağla bağlanır. Bu da dağıtık sistemdir.

Üç düzen arasındaki fark bağlantının sıkılığıdır. Çok işlemcide iletişim nanosaniyeler düzeyinde bir bellek erişimidir. Çoklu bilgisayarda bir ileti birkaç mikrosaniye sürer. Dağıtık sistemde iletiler milisaniyeler alır. Bağlantı gevşedikçe sistem büyütülebilir, ama programlamak ve yönetmek zorlaşır.

Paylaşımlı bellekli çok işlemciler kendi içinde de ikiye ayrılır. Simetrik çok işlemcide (symmetric multiprocessor, SMP) bütün işlemciler belleğe ve giriş/çıkış (G/Ç) aygıtlarına eşit hakla erişir. Çekirdek kodu her işlemcide çalışabilir. Asimetrik çok işlemcide (AMP) işlemciler eşit değildir. Ya işletim sistemini yalnız biri yürütür ya da her işlemci ayrı bir yazılım çalıştırır. Bugünkü masaüstü ve sunucu işletim sistemlerinin hepsi SMP'dir. Asimetrik düzen daha çok gömülü yongalarda karşımıza çıkar.

Çok işlemci işletim sistemine yeni işler yükler. Hangi iş parçacığı hangi işlemcide çalışacak? Aynı çekirdek tablosuna iki işlemci aynı anda dokunursa ne olur? İşlemciler arasında veri nasıl taşınır? Paylaşılan verinin kopyaları nasıl tutarlı tutulur? Bu bölümün geri kalanı bu soruların yanıtlarıdır.

12.1.2Saat hızının sınırı ve Amdahl yasası

Saat hızının neden durduğunu anlamak için güç tüketimine bakmak gerekir. Uzun yıllar boyunca transistörler küçüldükçe çalışma gerilimi de düştü. Böylece birim alandaki güç sabit kaldı. Bu gözleme Dennard ölçeklemesi denir. 2000'lerin ortasında gerilim daha fazla düşürülemez hâle geldi. Saat hızını artırmak artık yonganın aşırı ısınması demekti. Üreticiler de transistör bütçesini daha çok çekirdeğe harcamaya başladı.

Çekirdek sayısını artırmak her programı aynı oranda hızlandırmaz. Programın bir kısmı ancak sırayla yürütülebilir: girdiyi okumak, sonuçları birleştirmek, ortak bir yapıyı kilitle korumak gibi. Bu sıralı kısım, çekirdek sayısı ne olursa olsun aynı sürede biter.

Formülün nereden geldiği kolayca görülür. Tek işlemcide süre 1 birim olsun. Sıralı kısım n işlemcide de 1 − p sürer. Paralel kısım n işlemciye eşit bölünürse p / n sürer. Yeni süre bu ikisinin toplamıdır; hızlanma da eski sürenin yeni süreye oranıdır.

Amdahl yasası sabit bir problem boyutu varsayar. Gerçekte işlemci sayısı arttıkça çözülmek istenen problem de büyür: daha büyük bir benzetim, daha çok veri. Bu durumda sıralı kısmın payı küçülür ve kazanç Amdahl'ın öngördüğünden fazla olur. Bu bakışa Gustafson yasası denir. Yine de Amdahl'ın dersi geçerlidir: çekirdek sayısı arttıkça yazılımın sıralı kısmını küçültmek, çekirdek eklemekten daha önemli hâle gelir. İşletim sisteminin kendi kilitleri de bu sıralı kısmın bir parçasıdır. Tek bir çekirdek kilidi bütün işlemcileri sıraya sokar ve sistemin ölçeklenmesini sınırlar.

12.2Çok işlemcili donanım

İşletim sisteminin çok işlemcide nasıl davranması gerektiğini anlamak için önce donanımın nasıl kurulduğunu bilmek gerekir. Bu kesim işlemcileri belleğe bağlamanın yollarını, bellek erişim süresinin neden her yerde aynı olmadığını ve önbelleklerin nasıl tutarlı tutulduğunu anlatır.

12.2.1UMA: veri yolu tabanlı mimari

UMA programcı için en rahat düzendir. Verinin nereye yerleştiği performansı değiştirmez; bir program tek işlemcide nasıl yazılıyorsa çok işlemcide de öyle yazılabilir. En basit UMA makinesi bütün işlemcileri ve belleği tek bir veri yoluna bağlar (Şekil 12.2 (a)). Bir CPU bellekten okumak istediğinde önce yolun boş olup olmadığına bakar. Yol boşsa adresi yola koyar, birkaç denetim sinyali verir ve bellek yanıtı yola koyana kadar bekler. Yol meşgulse boşalmasını bekler.

Bu düzen iki ya da üç işlemcide iyi çalışır. İşlemci sayısı arttıkça yol doyar. Otuz iki ya da altmış dört işlemcide CPU'lar zamanlarının çoğunu yolu beklemekle geçirir; yeni işlemci eklemek sistemi hızlandırmaz. (b) düzeninde her CPU'ya bir önbellek eklenir. Okumaların çoğu yerel önbellekte karşılanır ve yola çıkmaz; trafik büyük ölçüde azalır. Bunun bedeli yeni bir sorundur: aynı bellek satırının birden çok önbellekte kopyası bulunabilir. Bir CPU kendi kopyasını değiştirirse diğer kopyalar eskir. Bu kopyaları tutarlı tutmak donanımın görevidir ve ilerideki kesimlerde ayrıntılı anlatılır.

(c) düzeninde her CPU'nun bir de özel belleği vardır. Derleyici programın kodunu, sabitleri, yığını ve yerel değişkenleri bu özel belleğe koyar. Paylaşımlı bellek yalnız gerçekten paylaşılan değişkenler için kullanılır. Böylece yol trafiği daha da azalır. Ama derleyicinin hangi verinin paylaşıldığını bilmesi gerekir; bu da programlamayı zorlaştırır.

Bugünkü yongalarda tek bir paylaşılan veri yolu kalmadı. Çekirdekler, önbellek dilimleri ve bellek denetleyicileri yonga içinde bir halka ya da ızgara ağıyla bağlanır. Intel'in “mesh” ağı ve AMD'nin Infinity Fabric'i bunun örnekleridir. Düşünce yine aynıdır: ortak bir iletişim ortamı, ve o ortamın sınırlı bant genişliğini korumak için büyük önbellekler.

12.2.2Çapraz çubuk anahtar

Tek veri yolunun darboğazından kurtulmanın en doğrudan yolu her CPU'yu her bellek modülüne ayrı bir yolla bağlamaktır. Çapraz çubuk anahtar (crossbar switch) bunu bir ızgarayla yapar (Şekil 12.3). Yatay çizgiler CPU'ları, dikey çizgiler bellek modüllerini temsil eder. Her kesişim noktasında küçük bir elektronik anahtar vardır. Anahtar kapanınca o CPU ile o bellek modülü arasında doğrudan bir yol kurulur.

Şekilde önce CPU 2, M5'e erişmek ister: (2, 5) kesişim noktası kapanır ve yol kurulur. Ardından CPU 0 → M1 ve CPU 6 → M3 bağlantıları da aynı anda kurulur. Farklı bellek modüllerine giden istekler birbirini hiç beklemez. Bu nedenle çapraz çubuk engellemesiz (non-blocking) bir ağdır. CPU 4 de M5'i isterse ağda yol vardır, ama modülün kendisi meşguldür. Tek çekişme noktası bellek modülüdür, ağın kendisi değil.

Çapraz çubuğun bedeli boyutudur. n CPU ve n bellek modülü için n² kesişim noktası gerekir. 8 × 8 bir anahtarda 64 kesişim vardır; 64 × 64'te 4096, 1024 × 1024'te 1.048.576. Bu yüzden büyük çapraz çubuklar pahalıdır. Eski Sun Fire E25K sunucusu 18 × 18 bir çapraz çubuk kullanıyordu. Bugün çapraz çubuklar daha çok yonga içinde, çekirdekler ile L3 önbellek dilimleri arasında küçük ölçekte kullanılır.

12.2.3Omega ağı

n² maliyetten kaçmak için ağ küçük anahtarlardan aşamalı olarak kurulabilir. Yapı taşı 2 × 2 anahtardır: iki girişi, iki çıkışı vardır. Bir girişten gelen ileti iki çıkıştan birine yönlendirilir. İleti dört alan taşır: hedef bellek modülü (Modül), modül içindeki adres, işlem kodu (okuma ya da yazma) ve yazılacak değer. Anahtar yalnız Modül alanına bakar (Şekil 12.4).

Omega ağı bu anahtarları log₂n aşamaya dizer. 8 CPU ve 8 bellek için 3 aşama gerekir; her aşamada dört anahtar vardır (1A–1D, 2A–2D, 3A–3D). Aşamalar arasındaki kablolama mükemmel karıştırmadır (perfect shuffle). Bir çıkışın numarası bir sola döndürülerek sonraki aşamadaki girişin numarası bulunur. Örneğin 011 numaralı hat 110 numaralı girişe bağlanır.

Yönlendirme kuralı çok basittir. k. aşamadaki anahtar, hedef adresin soldan k. bitine bakar. Bit 0 ise iletiyi üst çıkışa, 1 ise alt çıkışa gönderir. Kaynak adres yönlendirmeye hiç karışmaz.

Yanıt aynı ağdan geri döner. Bunun için her anahtar, iletiyi geçirirken hangi girişten aldığını, yani kaynak adresin bir bitini Modül alanına yazar. İleti belleğe vardığında Modül alanında kaynak adres, 011, birikmiş olur. Bellek yanıtı bu etiketle geri gönderir ve yanıt aynı kuralla CPU 011'e ulaşır.

Omega ağı birçok aktarımı aynı anda taşıyabilir, ama her zaman değil. Aynı anda CPU 001'in bellek 111'e gitmek istediğini düşünelim. Bu istek 1B'den alt çıkışla çıkar ve karıştırmadan sonra 2D'ye girer. Hedefin 2. biti 1 olduğu için o da 2D'nin alt çıkışını ister. İki istek aynı çıkışa düşer ve biri beklemek zorunda kalır (Şekil 12.6). Bu yüzden omega ağı engellemeli (blocking) bir ağdır.

Omega ağı n / 2 × log₂n anahtar kullanır. 8 girişte 4 × 3 = 12 anahtar, 64 girişte 32 × 6 = 192, 1024 girişte 512 × 10 = 5120 anahtar gerekir. 1024 × 1024 bir çapraz çubuğun bir milyonu aşan kesişim noktasıyla karşılaştırıldığında bu çok küçük bir donanımdır. Bedeli ikidir: istekler çakışınca bekler ve her istek log₂n aşamadan geçtiği için gecikme artar.

12.2.4NUMA çok işlemcileri

Veri yolu ya da anahtar ağıyla kurulan UMA makineleri birkaç düzine işlemcinin ötesine büyütülemez. Yüzlerce işlemcili makineler için bir ödün vermek gerekir: her bellek sözcüğüne aynı sürede erişme isteğinden vazgeçilir. Bu makinelere NUMA çok işlemcileri denir (Tanım 12.1).

Bir NUMA makinesinde bellek düğümlere bölünür. Her düğümde birkaç CPU ve onlara yakın bir bellek bulunur. Bugünkü iki soketli bir sunucuda her soket bir düğümdür (Şekil 12.7). Soketin çekirdekleri kendi bellek denetleyicisine bağlı DRAM'den yaklaşık 80 ns'de okur. Diğer soketin belleğine ise soketler arası bağlantı (Intel'de UPI, AMD'de Infinity Fabric) üzerinden, örneğin 140 ns'de ulaşır. Bu gecikmeler örnek değerlerdir; gerçek değerler makineden makineye değişir.

NUMA makinelerinin üç ortak özelliği vardır. Birincisi, bütün CPU'lar tek bir fiziksel adres alanı görür. İkincisi, uzak belleğe de sıradan LOAD ve STORE komutlarıyla erişilir; program iletiler göndermez. Üçüncüsü, uzak erişim yerel erişimden yavaştır. NUMA makineleri önbellek tutarlılığı olup olmamasına göre ikiye ayrılır. Önbellek tutarlılığı olmayanlara NC-NUMA, olanlara CC-NUMA (cache-coherent NUMA) denir. Bugünkü sunucuların hepsi CC-NUMA'dır ve tutarlılığı çoğunlukla bir dizinle sağlar.

NUMA işletim sistemi için yeni bir sorumluluk demektir: veriyi onu kullanan işlemcinin yanında tutmak. Ortalama erişim süresi, erişimlerin ne kadarının yerel olduğuna bağlıdır.

ortalama erişim = y · t_yerel + (1 − y) · t_uzak

Burada y, erişimlerin yerel kesridir.

Bu kaybı önlemek için işletim sistemi üç şey yapar. İlki ilk dokunma (first touch) ilkesidir: bir sayfayı ilk kez hangi düğümdeki CPU kullanırsa sayfa o düğümün belleğinden ayrılır. İkincisi, çizelgeleyici bir iş parçacığını mümkün olduğunca verisinin bulunduğu düğümde çalıştırır. Yük dengelemesi önce düğüm içinde yapılır, düğümler arasına ancak gerekirse geçilir. Üçüncüsü, Linux'un otomatik NUMA dengelemesi bir sürecin hangi sayfalara hangi düğümden eriştiğini örnekleyerek izler. Sayfaları süreçlerin yanına ya da süreçleri sayfaların yanına taşır. Uygulama tarafında da numactl aracıyla bir süreç ve belleği belirli bir düğüme bağlanabilir.

NUMA yalnız çok soketli sunuculara özgü değildir. Tek soketli büyük yongalar da içeride NUMA olabilir. Örneğin AMD EPYC'de NPS (nodes per socket) ayarı, Intel'de SNC (sub-NUMA clustering) bir soketi birkaç NUMA düğümüne böler.

12.2.5Dizin tabanlı CC-NUMA

Az sayıda işlemcide önbellekler ortak yolu dinleyerek tutarlı tutulabilir. Yüzlerce düğümde ise her isteği bütün düğümlere yaymak ağı boğar. Çözüm, her bellek satırının hangi önbelleklerde bulunduğunu bir kayıtta tutmaktır. Bu kayda dizin (directory) denir. Bir satır için ileti yalnız o satırın kopyasını tutan düğümlere gönderilir.

Tanenbaum'un örneği düşünceyi somutlaştırır. Sistemde 256 düğüm vardır. Her düğümde bir CPU ve 16 MiB bellek bulunur; toplam bellek 256 × 16 MiB = 2³² bayttır. Önbellek satırları 64 bayttır. 32 bitlik bir fiziksel adres üç alana bölünür (Şekil 12.8):

• en soldaki 8 bit düğüm numarasıdır (256 düğüm);
• sonraki 18 bit, o düğümün belleğindeki blok (satır) numarasıdır: 16 MiB / 64 B = 2¹⁸ satır;
• son 6 bit satır içindeki ofsettir (64 bayt).

Her düğüm, kendi belleğindeki 2¹⁸ satırın her biri için bir dizin girdisi tutar. Bu basit tasarımda bir girdi, satır şu anda bir önbellekteyse o önbelleğin düğüm numarasını saklar. Bir satır aynı anda yalnız bir düğümde önbelleklenebilir.

Bütün bu iletişim noktadan noktaya iletilerle yapılır. Bir veri yolunu bütün önbelleklerin dinlemesi gerekmez. Dizinin bedeli bellektir. Her girdi 8 bitlik bir düğüm numarası ve bir geçerli biti tutarsa 9 bit eder. Bir düğümün dizini 2¹⁸ × 9 bit = 294.912 bayt olur. Bu, 64 baytlık her satır için 9 bit, yani belleğin yaklaşık %1,76'sı kadar bir ek yüktür.

Bir satırın tek bir düğümde önbelleklenebilmesi gerçekçi değildir; sık okunan bir satırın birçok kopyası olmalıdır. Gerçek sistemler kopya kümesini her düğüm için bir bit içeren bir bit vektörüyle ya da sınırlı sayıda işaretçiden oluşan bir listeyle tutar. Çok çekirdekli yongaların içinde aynı işi “snoop filter” adı verilen yapılar görür: hangi satırın hangi çekirdeğin özel önbelleklerinde olduğunu izler.

12.2.6Önbellek tutarlılığı sorunu

Her çekirdeğin kendi özel önbelleği vardır ve bu önbellekler aynı belleğin kopyalarını tutar. Şekil 12.10 sorunu gösterir. Bellekte x = 5'tir. İki çekirdek de x'i okuyup önbelleğine almıştır. Çekirdek 1, x'e 7 yazar. Yazma yalnız kendi önbelleğindeki kopyayı değiştirir. Çekirdek 0 şimdi x'i okursa kendi önbelleğindeki eski 5 değerini görür. Program açısından bu yanlıştır: x'e en son 7 yazılmıştı.

Donanım tutarlılığı iki yoldan sağlar. Dinleme (snooping) yönteminde bütün önbellek denetleyicileri ortak yolu sürekli dinler. Bir önbellek, kendinde kopyası olan bir satıra başka biri yazacaksa bunu yoldan görür ve kopyasını günceller ya da geçersiz kılar. Bu yöntem az sayıda çekirdekte uygundur. Dizin yönteminde ise kopyaların listesi tutulur ve iletiler yalnız ilgili düğümlere gider. Bu yöntem çok çekirdekli yongalara ve NUMA makinelerine ölçeklenir.

Yazmalarla ilgili iki temel politika vardır. Yazınca geçersiz kıl (write-invalidate) politikasında bir çekirdek yazmadan önce diğer kopyaları geçersiz kılar; onlar bir sonraki okumada satırı yeniden ister. Yazınca güncelle (write-update) politikasında yeni değer bütün kopyalara gönderilir. Aynı satıra art arda yapılan yazmalarda güncelleme her seferinde trafik üretir, geçersiz kılma ise yalnız ilk yazmada. Bu yüzden bugünkü işlemcilerin hemen hepsi geçersiz kılma kullanır.

Tutarlılık tek bir adresle ilgilidir. Farklı adreslere yapılan yazmaların başka çekirdeklerce hangi sırada görüleceği ayrı bir konudur. Bu konuya bellek tutarlılık modeli (memory consistency model) denir. x86'nın modeli (x86-TSO) oldukça güçlüdür; ARM ve RISC-V daha zayıf modeller kullanır. Kilit gerçeklemeleri bu yüzden bellek bariyerleri içerir: kritik bölgedeki yazmaların, kilit bırakılmadan önce herkese görünmesini zorlar.

12.2.7MESI protokolü

Yazınca geçersiz kılan protokollerin en yaygını MESI'dir. Adını bir önbellek satırının alabileceği dört durumun baş harflerinden alır (Tablo 12.2).

Bir satırın durumu iki tür olayla değişir: kendi çekirdeğinin okuma ve yazmaları ile başka bir çekirdeğin yolda görülen istekleri. Şekil 12.11 bütün geçişleri bir arada gösterir. Veri yolunda üç tür istek dolaşır. BusRd bir satırı okumak için ister. BusRdX bir satırı yazmak amacıyla, özel olarak ister; diğer kopyalar geçersiz kılınır. BusUpgr ise S durumundaki bir satırı yazmak için yalnız geçersiz kılma ister; veri zaten elde olduğu için satır taşınmaz.

Tablonun okunuşu şöyledir. I durumundaki bir satır yerel olarak okunursa BusRd gönderilir. Başka bir önbellek “bende var” derse satır S, kimse demezse E olur. I durumundaki bir satıra yazılacaksa BusRdX gönderilir ve satır M olur. E durumundaki satıra yazmak sessizdir: başka kopya olmadığı bilindiği için yola hiçbir şey çıkmaz. S durumundaki satıra yazmak BusUpgr ister. M durumundaki bir satırı başka bir çekirdek okumak isterse sahibi veriyi yola koyar (Flush), belleğe de geri yazar ve satırı S yapar. Başka bir çekirdek yazmak isterse yine veriyi verir ve satırı I yapar.

E durumunun varlık nedeni sık görülen bir durumu ucuzlatmaktır: bir iş parçacığı özel verisini önce okur, sonra yazar. E olmasaydı okuma satırı S yapar, ardından gelen yazma gereksiz bir BusUpgr üretirdi. Bu protokolün ticari türevleri de vardır. Intel'in MESIF'inde F (Forward) durumu, paylaşılan kopyalardan hangisinin istekleri yanıtlayacağını belirler. AMD'nin MOESI'sinde O (Owned) durumu kirli ama paylaşılan bir satırı gösterir; satır belleğe geri yazılmadan başka önbelleklere verilebilir.

12.2.8MESI adım adım

Protokolün nasıl işlediği bir işlem dizisi üzerinde en iyi görülür. İki çekirdekli bir sistemde x başlangıçta yalnız bellektedir ve değeri 0'dır. İki önbellekte de x'in satırı I durumundadır.

Son adım önemli bir sonucu gösterir. Bir çekirdeğin yalnız kendisinin kullandığı veriye art arda yazması ucuzdur: satır M durumunda kaldıkça hiçbir ileti üretmez. Pahalı olan, aynı satıra farklı çekirdeklerin sırayla yazmasıdır. Her yazma satırı bir önbellekten ötekine taşır. Bir sonraki kesimdeki yanlış paylaşım bu gözleme dayanır.

12.2.9Yanlış paylaşım

Tutarlılık protokolleri değişkenleri değil önbellek satırlarını izler. Bugünkü işlemcilerde bir satır 64 bayttır. Birbirinden tamamen bağımsız iki değişken aynı satıra düşerse donanım onları paylaşılan veri gibi ele alır.

Aşağıdaki kodda iki iş parçacığı iki ayrı sayacı artırır. Mantıkta hiçbir paylaşım yoktur ve kilit de gerekmez.

struct sayaclar {      /* kötü */
  long a;   /* ofset 0 */
  long b;   /* ofset 8 */
};

struct dolgulu {       /* iyi */
  _Alignas(64) long a;
  _Alignas(64) long b;
};

/* iş parçacığı 0: for(..) s.a++;
   iş parçacığı 1: for(..) s.b++; */

struct sayaclar'da a 0, b 8 numaralı bayttadır; ikisi de aynı 64 baytlık satıra düşer. İş parçacığı 0, Ç0'da s.a++'yı döngüde yürütür, iş parçacığı 1, Ç1'de s.b++'yı. Olaylar şöyle gelişir (Şekil 12.13):

1. Ç0 a++ yapar. Satırı M durumunda alır; Ç1'in kopyası geçersiz olur.
2. Ç1 b++ yapar. Satır Ç1'e taşınır ve orada M olur; Ç0'daki kopya geçersiz olur.
3. Ç0 yeniden a++ yapar ve satırı geri çeker.

Her artırmada satır bir çekirdekten ötekine gider. Buna “ping-pong” denir. Bir satırın taşınması onlarca ile yüz elli nanosaniye arasında sürer; artırmanın kendisi ise birkaç döngüdür. Sonuçta iki iş parçacıklı program, aynı işi yapan tek iş parçacıklı sürümden bile yavaş çalışabilir.

Çözüm her sayacı ayrı bir satıra koymaktır. struct dolgulu'da C11'in _Alignas(64) belirteci her alanı 64 baytlık sınıra hizalar. Yapının boyu 128 bayta çıkar ve sayaç başına 56 bayt boşa gider. Karşılığında ping-pong tamamen kalkar; kazanç çoğu zaman kat kat hızdır. Java'da aynı iş @Contended notuyla, Linux çekirdeğinde ____cacheline_aligned makrosuyla yapılır. Çekirdeğin CPU başına sayaçları da bu nedenle her CPU için ayrı satırlarda tutulur.

Aynı sorun daha büyük ölçekte de karşımıza çıkar. Dağıtık paylaşımlı bellekte tutarlılık birimi satır değil sayfadır. Bağımsız iki değişken aynı 4 KiB'lık sayfadaysa sayfa makineler arasında ağ üzerinden gidip gelir.

12.2.10Çok çekirdekli ve heterojen yongalar

Bugünkü işlemcilerin çoğu tek bir yongada birden çok bağımsız çekirdek barındırır. Bu yongalara çok çekirdekli (multicore) ya da yonga üzerinde çok işlemci (chip multiprocessor, CMP) denir (Şekil 12.14). Tipik bir düzende her çekirdeğin özel L1 ve L2 önbellekleri vardır. L3 önbellek paylaşılır ve dilimler hâlinde yonga içi ağa dağıtılır. Sunucu soketlerinde çekirdek sayısı yüzleri bulur: AMD EPYC 9005 serisinde 192 çekirdek, Intel Xeon 6900E serisinde 288 verimlilik çekirdeği vardır.

Çok çekirdekli yongaların işletim sistemini ilgilendiren dört özelliği vardır:

• Yongacıklar (chiplets): Büyük işlemciler artık tek parça değildir. Çekirdek grupları ayrı kalıplara konur ve bir paket içinde birleştirilir. Tek bir sokette bile bir çekirdeğin L3'e ve belleğe uzaklığı her yerde aynı değildir. Çizelgeleyici birlikte çalışan iş parçacıklarını aynı yongacıkta tutmaya çalışır.
• Büyük–küçük çekirdekler: ARM'ın big.LITTLE düzeni, Apple yongaları ve Intel'in P/E çekirdekleri hızlı ama çok güç harcayan çekirdekleri yavaş ama verimli olanlarla birleştirir. İşletim sistemi işi enerjiye göre yerleştirir. Linux'ta bu işi enerjiye duyarlı çizelgeleme (EAS) yapar. Intel'in Thread Director donanımı da Windows'a hangi iş parçacığının hangi çekirdeğe uygun olduğu konusunda ipuçları verir.
• Hızlandırıcılar: GPU ve yapay zekâ işlemleri için NPU aynı yongada bulunur ve aynı belleği paylaşır. Bunlar doğrudan çizelgelenmez; işletim sistemi onlara sürücü üzerinden iş gönderir.
• Paylaşılan kaynaklar: L3 önbellek ve bellek bant genişliği ortaktır. Bir çekirdekteki bellek yoğun bir iş, başka bir çekirdekteki işi yavaşlatabilir.

12.2.11Eş zamanlı çoklu iş parçacığı

Süperskalar bir çekirdek her döngüde birkaç komut yürütebilir. Ama tek bir iş parçacığı bu yuvaları nadiren doldurur. Bir önbellek ıskası ya da komutlar arasındaki bir bağımlılık çekirdeği bekletir ve yürütme birimleri boş kalır (Şekil 12.15 (a)).

Intel buna Hyper-Threading der; AMD de SMT adını kullanır. Mantıksal CPU'ların yazmaç kümeleri ayrıdır. Yürütme birimleri, L1 ve L2 önbellekleri ise ortaktır. Kazanç tipik olarak %10 ile %30 arasındadır. İki iş parçacığı aynı birimi, örneğin kayan nokta birimini isterse kazanç hiç olmayabilir. Bu nedenle çizelgeleyici işleri önce boş fiziksel çekirdeklere yerleştirir. Bir fiziksel çekirdeğin iki mantıksal CPU'sunu ancak bütün fiziksel çekirdekler doluyken birlikte kullanır.

SMT'nin bir de güvenlik yanı vardır. Aynı çekirdeği paylaşan iki iş parçacığı ortak önbellekler üzerinden birbirinin verisini sezebilir. L1TF ve MDS gibi yan kanal saldırıları bunu kullanır. Linux'un çekirdek çizelgelemesi (core scheduling) yalnız birbirine güvenen iş parçacıklarını aynı fiziksel çekirdeğe koyar. Bazı üreticiler SMT'den tamamen vazgeçmeye başladı; Intel'in Lunar Lake (2024) yongasının P çekirdeklerinde SMT yoktur.

12.2.12GPU ve heterojen hesaplama

CPU ve GPU farklı amaçlar için tasarlanmıştır (Şekil 12.16). CPU az sayıda büyük ve karmaşık çekirdekten oluşur; büyük önbellekler ve dal tahmini gibi düzeneklerle tek bir iş parçacığının gecikmesini en aza indirmeye çalışır. GPU ise binlerce basit şerit içerir ve toplam verimi en çoklar. Şeritler 32'lik gruplar hâlinde aynı komutu yürütür. NVIDIA bu gruplara warp, AMD wavefront der. Bu düzen her veri öğesine aynı işlemin uygulandığı veri paralel işlere uygundur: grafik, yapay zekâ ve bilimsel hesap.

GPU programları CUDA, ROCm/HIP, OpenCL ya da SYCL ile yazılır. CPU, GPU üzerinde çalışacak işlevi (buna da çekirdek, kernel, denir; işletim sistemi çekirdeğiyle karıştırılmamalıdır) başlatır, veriyi GPU belleğine taşır ve sonucu bekler. İşletim sistemi ve sürücü bu sırada GPU belleğini yönetir ve farklı süreçlerin GPU bağlamlarını zaman paylaşımıyla çalıştırır. Bugünkü sistemler CPU ile GPU arasında birleşik ya da paylaşılan bir sanal bellek de sunar. GPU bir sayfaya eriştiğinde, IOMMU üzerinden sayfa hatası oluşabilir ve sayfa GPU'ya taşınır. Büyük yapay zekâ kümelerinde her düğümde 4–8 GPU bulunur. GPU'lar birbirine NVLink ile, düğümler birbirine InfiniBand ya da RoCE ile bağlanır ve veriyi RDMA ile doğrudan taşır.

12.3Çok işlemcili işletim sistemi türleri

Donanım birden çok işlemciyi aynı belleğe bağladıktan sonra işletim sisteminin bu işlemcileri nasıl kullanacağına karar vermek gerekir. Tarihte üç model ortaya çıktı. Bu kesim üçünü sırayla anlatır ve karşılaştırır.

12.3.1Her CPU'nun kendi işletim sistemi

En basit yol, belleği CPU sayısı kadar bölüme ayırmak ve her CPU'ya kendi bölümünde bağımsız bir işletim sistemi kopyası çalıştırmaktır (Şekil 12.17). İşletim sisteminin kodu salt okunur olduğu için paylaşılabilir; verisi ise her kopyada ayrıdır. Bir süreç sistem çağrısı yaptığında çağrı kendi CPU'sunda yakalanır ve o CPU'nun işletim sistemi onu işler.

Bu modelin çekiciliği basitliğindedir. Tek işlemcili bir işletim sistemi neredeyse hiç değiştirilmeden kullanılabilir. Bölümler birbirinden bağımsız olduğu için aralarında kilit de gerekmez. Ama paylaşımın olmaması dört sorun doğurur:

• Süreçler paylaşılmaz. Her işletim sisteminin kendi süreç tablosu vardır. Bir CPU aşırı yüklüyken diğeri boşta kalabilir; iş birinden ötekine kolayca aktarılamaz.
• Sayfalar paylaşılmaz. Bir bölümde bellek tükenirken başka bir bölümde boş sayfa kalabilir.
• Her işletim sistemi kendi tampon önbelleğini tutar. Aynı disk bloğu iki önbellekte farklı hâllerde bulunabilir. İki kopya da değiştirilirse disk bloğu tutarsız olur. Bu sorundan kaçmanın tek yolu tampon önbelleklerini kaldırmaktır; bu da performansı düşürür.
• Bir CPU'nun işletim sistemi, diğerlerinin ne yaptığını bilmez; ortak bir çizelgeleme yapılamaz.

Bu model bugün başka adlarla yaşıyor. Büyük sunucuların donanım düzeyinde bölümlenmesi ve bir hipervizör üzerinde çalışan ayrı sanal makineler aynı düşünceye dayanır. Araştırmada ise Barrelfish işletim sistemi bunu bilinçli bir tasarım olarak kullanır. Bu “çoklu çekirdek” (multikernel) tasarımında her çekirdek, iletiyle haberleşen ayrı bir düğüm gibi ele alınır.

12.3.2Usta-köle modeli

İkinci modelde işletim sisteminin tek bir kopyası ve bütün tabloları yalnız bir CPU'dadır; bu CPU'ya usta denir (Şekil 12.18). Diğer CPU'lar, yani köleler, yalnız kullanıcı süreçlerini çalıştırır. Bir köle CPU'daki süreç sistem çağrısı yaptığında çağrı ustaya yönlendirilir ve orada işlenir.

Usta-köle modeli ayrı işletim sistemlerinin sorunlarının çoğunu çözer. Tek bir hazır listesi vardır. Bir köle boşalınca ustadan yeni bir süreç ister; böylece yük kendiliğinden dengelenir. Bellek sayfaları tek bir havuzdan dağıtılır ve tek bir tampon önbelleği olduğu için tutarsızlık oluşmaz. Çekirdek verisine yalnız usta dokunduğu için kilit de gerekmez.

Modelin zayıf yanı ölçeklenememesidir. Bütün sistem çağrıları tek bir CPU'da işlenir. Sistem çağrısı yoğun bir iş yükünde usta darboğaz olur. Köle sayısı arttıkça çağrılar ustanın önünde sıraya girer ve yeni CPU eklemek az kazandırır. Usta çökerse de bütün sistem durur. Bu yüzden usta-köle modeli az sayıda CPU'su olan sistemlerde işe yarar.

Asimetrik çok işlemciliğin (AMP) klasik biçimi budur. Bugün asimetrik düzen daha çok gömülü yongalarda karşımıza çıkar. Örneğin Linux çalıştıran Cortex-A çekirdeklerinin yanında gerçek zamanlı bir işletim sistemi çalıştıran bir Cortex-M çekirdeği bulunur. Linux bu çekirdeği remoteproc altyapısıyla başlatır ve onunla OpenAMP üzerinden haberleşir.

12.3.3Simetrik çok işlemciler

Üçüncü model ustanın darboğazını kaldırır. Bellekte işletim sisteminin tek bir kopyası vardır, ama her CPU onu çalıştırabilir (Şekil 12.19). Bir sistem çağrısı, çağrıyı yapan CPU'da işlenir. Yük ve bellek usta-kölede olduğu gibi dinamik olarak dengelenir. Bu modele simetrik çok işlemci (SMP) denir.

SMP'nin bedeli eş zamanlılıktır. İki CPU aynı anda aynı çekirdek tablosuna dokunabilir: biri hazır listesine bir süreç eklerken öteki aynı listeden süreç çıkarır. Bu yarışları önlemek için çekirdeğin paylaşılan yapıları kilitlerle korunmalıdır. En kolay ilk adım bütün çekirdeği tek bir kilitle korumaktır. Bir CPU çekirdeğe girerken bu kilidi alır, çıkarken bırakır. Linux 2.0 tam olarak böyle başladı; bu kilide “büyük çekirdek kilidi” (Big Kernel Lock, BKL) denir. Tek kilitli bir çekirdek, aslında usta-köle modelinin biraz daha esnek bir hâlidir: aynı anda çekirdekte yalnız bir CPU bulunabilir.

Ölçeklenebilmek için çekirdek, birbirinden bağımsız kritik bölgelere bölünür ve her bölge kendi kilidiyle korunur. Linux BKL'yi on yıldan uzun bir sürede adım adım küçülttü ve 2.6.39 sürümünde (2011) tamamen kaldırdı. Bugün çekirdekte binlerce ince taneli kilit vardır. Bunların yanında okuyucuların hiç kilit almadığı RCU (read-copy-update) düzeneği ve her CPU'nun yalnız kendi kopyasına dokunduğu CPU başına veri yapıları kullanılır.

İnce taneli kilitlerin kendi tehlikesi vardır. Bir kod yolu A ve B kilitlerini bu sırayla, başka bir yol ters sırayla alırsa iki CPU birbirini sonsuza dek bekleyebilir. Çekirdek geliştiricileri bunu önlemek için kilitlere sıra verir ve her kod yolunun kilitleri aynı sırayla almasını şart koşar. Linux'un lockdep aracı bu kuralın ihlallerini çalışma sırasında yakalar.

12.3.4Üç modelin karşılaştırması

Tablo 12.3 üç modeli yan yana koyar.

Bu üç model paylaşımlı bellekli çok işlemciler içindir. Çoklu bilgisayar işletim sistemlerinden farkını akılda tutmak gerekir. Çok işlemcide bütün CPU'lar aynı fiziksel belleği görür. Çoklu bilgisayarda ise her düğümün kendi belleği ve kendi işletim sistemi kopyası vardır; düğümler yalnız iletiyle haberleşir.

12.4Senkronizasyon

SMP çekirdeği paylaşılan yapılarını kilitlerle korur. Tek işlemcide bir kilit, kesmeleri kapatarak ya da bölünmez bir komutla kolayca gerçeklenebilir. Çok işlemcide ise her iki yol da yeni sorunlar çıkarır. Bu kesim kilidin donanımdaki temelini, daha ölçeklenebilir kilit türlerini ve beklerken dönmek ile uyumak arasındaki seçimi anlatır.

12.4.1TSL ve veri yolu kilidi

TSL (test and set lock) komutu bir bellek sözcüğünü okur, eski değerini bir yazmaca koyar ve sözcüğe 1 yazar. Tek işlemcide bu komut bölünmezdir: komutun ortasında kesme gelmez. Kilit sözcüğü 0 ise serbest, 1 ise tutuluyor demektir. TSL eski değer olarak 0 döndürürse kilit alınmıştır.

Çok işlemcide komutun bölünmezliği tek başına yetmez. TSL'nin okuması ve yazması iki ayrı veri yolu döngüsüdür. Başka bir CPU bu iki döngünün arasına girebilir (Şekil 12.21):

1. CPU 1 kilit sözcüğünü okur: 0, yani serbest.
2. CPU 1 yazmadan önce CPU 2 de okur: yine 0.
3. CPU 1 sözcüğe 1 yazar; CPU 2 de 1 yazar.
4. İkisi de “kilit benim” sanır ve karşılıklı dışlama bozulur.

Kesmeleri kapatmak da işe yaramaz. Kesmeyi kapatmak yalnız komutu yürüten CPU'yu korur; diğer CPU'lar belleğe erişmeyi sürdürür. Çözüm donanımdadır: TSL, okuma ve yazma süresince veri yolunu kilitler. Bu sırada başka hiçbir CPU belleğe erişemez. Bugünkü x86 işlemcilerinde LOCK öneki çoğunlukla bütün yolu değil, yalnız ilgili önbellek satırını kilitler. Satır işlem süresince M durumunda tutulur ve diğer çekirdeklerin istekleri bekletilir. ARM ise aynı işi iki yoldan yapar: LDXR/STXR komut çifti (aradaki sürede başka biri yazdıysa yazma başarısız olur ve döngü tekrarlanır) ya da LSE uzantısındaki CAS gibi tek komutlu atomik işlemler.

12.4.2Bilet kilidi

Doğru çalışan bir TSL kilidinin iki eksiği kalır. Birincisi adil değildir: kilit serbest kalınca bekleyenlerden hangisinin alacağı rastlantıdır ve biri sürekli kaybedip aç kalabilir. İkincisi her denemede bir yazma yapar ve önbellek trafiği üretir. Bilet kilidi (ticket lock) birinci sorunu tamamen, ikincisini büyük ölçüde çözer.

Düşünce bir bankadaki sıra numarası makinesidir. İki sayaç vardır: next sıradaki bileti dağıtır, serving sırası geleni gösterir. Kilidi isteyen iş parçacığı next'i atomik olarak artırır ve eski değeri kendi bileti olarak alır. Ardından serving kendi biletine eşit olana kadar bekler. Kilidi bırakan serving'i bir artırır. Sunumdaki Java programı iki iş parçacığının ortak bir sayacı bu kilitle korumasını gösterir:

import java.util.concurrent.atomic.*;
public class Bilet {
  static AtomicInteger next = new AtomicInteger();
  static volatile int serving = 0;
  static int sayac = 0;
  static void lock() {
    int my = next.getAndIncrement();
    while (serving != my) Thread.onSpinWait();
  }
  static void unlock() { serving++; }
  public static void main(String[] a)
      throws Exception {
    Runnable is = () -> {
      for (int i = 0; i < 100_000; i++) {
        lock(); sayac++; unlock(); } };
    Thread t0 = new Thread(is);
    Thread t1 = new Thread(is);
    t0.start(); t1.start(); t0.join(); t1.join();
    System.out.println("sayac = " + sayac);
  }
}

Kodun önemli satırları şunlardır. next bir AtomicInteger'dır; getAndIncrement() sayacı bölünmez biçimde artırır ve eski değeri döndürür. x86'da bu tek bir LOCK XADD komutudur. İki iş parçacığı aynı anda çağırsa bile farklı biletler alır. serving volatile'dır. Her okuma gerçek değeri görür. unlock()'taki yazma da kritik bölgedeki yazmaların herkese görünmesini sağlar. Thread.onSpinWait() işlemciye “dönüyorum” ipucu verir; x86'da PAUSE komutuna dönüşür ve güç tüketimini azaltır. unlock()'taki serving++ atomik olmak zorunda değildir, çünkü serving'e yalnız kilidin sahibi yazar.

Bilet kilidi adildir: iş parçacıkları kilide bilet sırasıyla, yani varış sırasıyla girer (FIFO). Hiçbir iş parçacığı aç kalmaz. Bekleyenler yalnız okuma yapar: serving'i kendi önbelleklerindeki S kopyadan okurlar ve veri yolunu meşgul etmezler. Kilit bırakılınca tek bir tutarlılık iletisiyle bütün kopyalar geçersiz olur. Yine de bir zayıflığı kalır. Bırakmadan sonra bütün bekleyenler satırı yeniden okur, ama yalnız biri girebilir. Çok sayıda bekleyen varsa bu okuma dalgası pahalıdır.

12.4.3Spinlock'lar ve önbellek trafiği

Kilidi beklerken döngüde dönen kilitlere spinlock denir. Çok işlemcide bir spinlock'un maliyeti, beklerken ürettiği önbellek trafiğidir. Şekil 12.23 üç tasarımı karşılaştırır.

(a) Saf TSL döngüsü. Bekleyen CPU durmadan TSL yürütür. Her TSL bir yazmadır: satırı M durumunda çeker ve diğer kopyaları geçersiz kılar. Kilit satırı bekleyenler arasında sürekli taşınır. Kilidin sahibi de bu satıra erişmek istediğinde sıraya girer. Sonuçta bekleyenler kilidin sahibini yavaşlatır ve kilidin bırakılması da gecikir.

(b) Önce oku, sonra TSL. Bu yönteme TTAS (test-and-test-and-set) denir. Bekleyen CPU önce kilidi sıradan bir okumayla dener. Kilit tutuluyorsa okuma kendi önbelleğindeki kopyadan karşılanır ve yola hiçbir şey çıkmaz. Kilit serbest görününce TSL'yi dener. Ek olarak üstel geri çekilme (exponential backoff) kullanılabilir: başarısız bir TSL'den sonra CPU bir süre bekler ve bu süreyi her başarısızlıkta ikiye katlar. Böylece bekleyenlerin aynı anda saldırması azalır.

(c) MCS kilidi. Mellor-Crummey ve Scott'ın 1991'de önerdiği kilitte bekleyenler bir bağlı liste oluşturur. Her bekleyen kendi düğümündeki bayrakta döner ve her düğüm ayrı bir önbellek satırındadır. Kilit, listenin sonunu gösteren tek bir tail işaretçisiyle yönetilir. Kilidi bırakan, listedeki bir sonrakinin bayrağına yazar. Bu tek bir uzak yazmadır ve yalnız sıradaki CPU'yu uyandırır. MCS hem adildir hem de bekleyen sayısından bağımsız olarak sabit trafik üretir. Linux'un bugünkü qspinlock'u bu düşünceye dayanır.

Bu tasarımların hiçbiri veri tutarsızlığını önlemek için yapılmaz; saf TSL de doğru çalışır. Amaç tutarlılık trafiğini, yani satırların önbellekler arasında gereksiz yere taşınmasını azaltmaktır.

12.4.4Kod izleme: TTAS kilidi

TTAS kilidinin C koduyla gerçeklemesi kısadır. tsl(k) çağrısı, *k'ya bölünmez biçimde 1 yazan ve eski değeri döndüren donanım komutunu temsil eder.

void kilitle(int *k) {
  for (;;) {
    while (*k == 1)   /* yerelde dön */
      ;
    if (tsl(k) == 0)  /* serbest göründü */
      return;         /* kilit alındı */
  }
}
void ac(int *k) {
  *k = 0;
}

kilitle() sonsuz bir döngüdür. İçteki while kilit 1 oldukça döner; bu bir okumadır ve kopya önbellekteyse yola çıkmaz. Kilit 0 görününce tsl() denenir. Eski değer 0 ise kilit alınmıştır ve işlev döner. Başka bir CPU araya girip kilidi önce aldıysa eski değer 1'dir; döngü yeniden yerel okumaya döner. ac() kilit sözcüğüne 0 yazar.

8. adımda ilginç bir ayrıntı vardır. CPU 2'nin başarısız TSL'si de bir yazmadır. Kilit değişmez (1 üzerine 1 yazılır), ama satır CPU 1'den CPU 2'ye taşınır. CPU 1 kritik bölgeden çıkıp ac() çağırdığında satırı yeniden çekmek zorunda kalır. Yarışın bedeli bu fazladan işlemlerdir. Bekleyen sayısı arttıkça her bırakmada bütün bekleyenler okur ve TSL dener; MCS kilidi bu yüzden daha iyi ölçeklenir.

12.4.5Dönmek mi, geçiş yapmak mı?

Bir iş parçacığı kilidi alamayınca iki şey yapabilir. Dönebilir (spin): CPU'yu bırakmadan kilidi yoklamayı sürdürür. CPU bu sürede boşa harcanır, ama kilit serbest kalır kalmaz iş parçacığı devam eder. Ya da geçiş yapabilir (switch, block): uyur ve CPU başka bir iş parçacığına verilir. Bunun bedeli iki bağlam değiştirmedir: biri uyurken, biri uyanırken. Uyanan iş parçacığı soğuk bir önbellekle de karşılaşır.

Şekil 12.25 iki seçeneği bir zaman çizelgesinde karşılaştırır. Kilit t = 3 µs'de serbest kalıyor, bir bağlam değiştirme C = 5 µs sürüyor. Dönen iş parçacığı 3 µs bekleyip kritik bölgeye girer. Geçiş yapan iş parçacığı 5 µs'de çıkar ve CPU başka bir işe geçer. İş parçacığı 5 µs'de geri döner ve kritik bölgeye ancak 15. mikrosaniyede girer.

Karar kuralı buradan çıkar. Beklenen bekleme süresi geçişin bedelinden, yani 2C'den kısaysa dönmek; değilse uyumak ucuzdur. Kısa kritik bölgeler için dönmek, disk G/Ç'si içeren ya da uzun süren bölgeler için uyumak doğrudur.

Sorun, bekleme süresinin önceden bilinmemesidir. Bunun için iyi bilinen bir ödünleşim vardır: önce geçişin bedeli kadar, yani 2C süre dönmek, kilit hâlâ alınamadıysa uyumak. Bu stratejinin maliyeti en kötü durumda, bekleme süresini önceden bilen ideal bir algoritmanın maliyetinin iki katını geçmez. Böyle bir garantisi olan çevrimiçi stratejiye rekabetçi (competitive) strateji denir.

Gerçek sistemler bu düşünceyi uyarlamalı kilitlerle uygular. Linux'un futex tabanlı mutex'i, kilidin sahibi başka bir CPU'da çalışıyorsa kısa süre döner, sahip uyuyorsa hemen uyur. Windows'ta CRITICAL_SECTION için bir dönme sayısı ayarlanabilir. Java sanal makinesi de çekişmesiz kilitleri ucuz bir biçimde tutar ve çekişme arttığında onları işletim sistemi kilidine dönüştürür; buna kilit şişirme denir.

Çekirdeğin içinde bir kural daha geçerlidir: kesmelerin kapalı olduğu bir bölgede uyunamaz, çünkü uyuyan kodu uyandıracak kesme gelemez. Bu tür bölgelerde yalnız spinlock kullanılabilir.

12.5Çok işlemcili çizelgeleme

Tek işlemcide çizelgeleyici yalnız bir soruyu yanıtlar: sıradaki iş parçacığı hangisi? Çok işlemcide ikinci bir soru eklenir: bu iş parçacığı hangi CPU'da çalışacak? İş parçacıkları birbirinden bağımsızsa ikinci soru kolaydır. Aynı uygulamanın iş parçacıkları birbiriyle haberleşiyorsa iki soru birlikte yanıtlanmalıdır. Bu kesim üç yaklaşımı anlatır: zaman paylaşımı, alan paylaşımı ve çete çizelgeleme.

12.5.1Zaman paylaşımı: ortak hazır kuyruğu

Birbirinden bağımsız süreçler için en basit yaklaşım, bütün CPU'ların tek bir ortak hazır kuyruğundan iş almasıdır (Şekil 12.26). Kuyruk, tek işlemcili sistemlerdeki gibi öncelik düzeylerine göre düzenlenir. Bir CPU boşaldığında kuyruğu kilitler, en yüksek öncelikli iş parçacığını çıkarır, kilidi bırakır ve o iş parçacığını çalıştırır. Şekilde 16 CPU'dan 14'ü çalışıyor; CPU 3 ve CPU 7 boşta. Boşalan ilk CPU, öncelik 7 kuyruğunun başındaki A'yı alacaktır.

Bu yaklaşımın en büyük artısı yükün kendiliğinden dengelenmesidir. Bir CPU iş beklerken başka bir CPU'da iş yığılmaz. Üç eksiği vardır:

• Tek kilit darboğazdır. CPU sayısı arttıkça kuyruğun kilidi için çekişme de artar. Yüzlerce CPU'lu bir sistemde CPU'lar sıradaki işi almak için birbirini bekler.
• Önbellek soğuk kalır. Bir iş parçacığı bir süre CPU 4'te çalıştıysa önbelleği ve TLB'si onun verisiyle doludur. Kuyruktan yeniden çıktığında boşta olan herhangi bir CPU'ya, örneğin CPU 12'ye düşebilir. Orada önbellek boştur ve iş parçacığı ilk milisaniyelerini ıskalarla geçirir. Bunu önlemek için çizelgeleyici iş parçacığını mümkünse son çalıştığı CPU'da çalıştırmaya çalışır. Bu eğilime işlemci afinitesi (processor affinity) denir.
• Kilit tutarken kesilme. Bir iş parçacığı bir spinlock tutarken zaman dilimi biterse kesilir. Kilidi isteyen diğer CPU'lar, sahip yeniden çalışana kadar boşuna döner.

Son sorun için Tanenbaum'un anlattığı akıllı çizelgeleme (smart scheduling) düşüncesi kullanılabilir. Spinlock alan iş parçacığı süreç genelinde görülebilen bir bayrak koyar ve kilidi bırakınca bayrağı kaldırır. Çizelgeleyici bayraklı bir iş parçacığını kesmez. Ona kritik bölgesini bitirmesi için biraz ek süre verir. Benzer bir düzenek bugün sanal makinelerde de kullanılır: kilit tutan bir sanal CPU'nun kesilip diğer sanal CPU'ların boşuna dönmesi sorununa “lock holder preemption” denir.

Bugünkü işletim sistemleri tek ortak kuyruk kullanmaz. Linux ve Windows her CPU için ayrı bir hazır kuyruğu tutar. Kilit çekişmesi kalkar ve iş parçacığı kendiliğinden aynı CPU'da kalır. Kuyruklar arasındaki dengesizlik ise ayrı bir yük dengeleme düzeneğiyle düzeltilir. Yükü az olan CPU başka bir CPU'nun kuyruğundan iş çeker (pull), ya da yük dengeleyici ara sıra işleri yüklü CPU'lardan boş olanlara iter (push). Linux bu dengelemeyi “çizelgeleme alanları” (scheduling domains) adı verilen bir hiyerarşiyle yapar. Önce aynı fiziksel çekirdeğin SMT kardeşleri arasında dengeler, sonra aynı L3'ü paylaşan çekirdekler arasında, en son da NUMA düğümleri arasında. Bağlantıdaki çok çekirdekli çizelgeleme simülatörü bu davranışları denemeye olanak verir.

12.5.2Alan paylaşımı

Birbiriyle sıkı haberleşen iş parçacıkları için başka bir yaklaşım daha uygundur: aynı uygulamanın bütün iş parçacıklarını aynı anda, ayrı CPU'larda çalıştırmak. Buna alan paylaşımı (space sharing) denir. Bir iş başladığında istediği sayıda CPU ona ayrılır. İş bitene kadar bu CPU'ları tutar. CPU başına çok programlama yoktur, dolayısıyla bağlam değiştirme de yoktur. Yetecek kadar boş CPU yoksa iş, yeterli CPU boşalana kadar bekler. En basit sıralama ilk gelen ilk hizmet alır (FCFS) biçimindedir.

Şekil 12.27 örneğinde 32 CPU dört işe dağıtılmıştır: 4 + 6 + 8 + 12 = 30 CPU kullanılıyor, 2'si boşta. Kuyruktaki bir sonraki iş 3 CPU isterse, bu işlerden biri bitene kadar bekler. Bu sırada iki CPU boşta kalır. Alan paylaşımının asıl sakıncası budur. Bir iş parçacığı G/Ç için bloke olduğunda onun CPU'su başka bir işe verilmez ve boşa durur. Bugün HPC kümelerindeki iş çizelgeleyicileri (Slurm, PBS) düğümleri tam olarak böyle bölümler: bir iş istediği düğümleri alır ve bitene kadar tutar.

12.5.3Çete çizelgeleme

Zaman paylaşımında haberleşen iş parçacıklarının neden yavaşladığını bir örnek gösterir (Şekil 12.28). İki CPU var, zaman dilimi 100 ms ve iki iş zaman paylaşımıyla çalışıyor. A işinin iki iş parçacığı A0 ve A1 birbirine iletiler gönderiyor. CPU 0'da sıra A0, B0, A0, B0…; CPU 1'de B1, A1, B1, A1… biçimindedir. A0, t = 0'da A1'e bir istek gönderir. A1 o sırada çalışmıyordur ve isteği ancak t = 100'de görür. Yanıtı hemen gönderir, ama bu kez A0 çalışmıyordur. A0 yanıtı t = 200'de alır. Tek bir istek-yanıt 200 ms sürmüştür.

Çete çizelgeleme zaman paylaşımı ile alan paylaşımını birleştirir. Üç parçası vardır. Birbirine bağlı iş parçacıkları bir çete olarak gruplanır. Bir çetenin bütün üyeleri aynı anda, farklı CPU'larda çalışır. Bütün çete üyeleri dilimlerine birlikte başlar ve birlikte bitirir. Böylece bir üyenin gönderdiği iletiyi alıcısı hemen görür ve yanıt da aynı dilimde döner.

Çete çizelgelemenin iki koşulu kısaca şöyle özetlenir: çete üyeleri aynı anda başlar ve hepsi farklı CPU'lardadır. Bu düşünce bugün sanal makinelerde de karşımıza çıkar. Çok sanal CPU'lu bir sanal makinenin vCPU'ları birbirini kilitlerle bekler. Hipervizör bunları birlikte çizelgelerse (co-scheduling) bir vCPU'nun, kesilmiş bir kardeşini beklerken boşuna dönmesi önlenir.

12.6Çoklu bilgisayarlar

Paylaşımlı bellekli çok işlemciler birkaç yüz CPU'nun ötesine büyütülemez; büyütmek de pahalıdır. Daha büyük sistemler belleği paylaşmayan bilgisayarlardan kurulur. Bu kesim çoklu bilgisayarların donanımını, iletilerin ağda nasıl taşındığını ve bu sistemlerde kullanılan programlama ve yük dağıtma yöntemlerini anlatır.

12.6.1Düğümler ve ağ arayüzleri

Çoklu bilgisayarlara küme de denir. Bir düğüm çoğu zaman sıradan bir sunucudur; onu özel yapan ağ arayüzü ve ara bağlantıdır. Büyük ölçekli benzetimler, yüksek başarımlı hesaplama ve yapay zekâ eğitimi bu sistemlerde çalışır. Dünyanın en hızlı bilgisayarlarını sıralayan TOP500 listesindeki sistemler on binlerce düğümlü çoklu bilgisayarlardır.

Çoklu bilgisayarda performansın önündeki en büyük engel iletilerin kopyalanmasıdır (Şekil 12.30). Bir ileti en kötü durumda beş kez kopyalanır:

1. gönderen sürecin kullanıcı tamponundan çekirdek tamponuna,
2. çekirdek tamponundan ağ arayüz kartının (NIC) belleğine,
3. NIC'ten kablo üzerinden karşı NIC'e,
4. karşı NIC'in belleğinden alıcının çekirdek tamponuna,
5. çekirdek tamponundan alıcı sürecin kullanıcı tamponuna.

Her kopya mikrosaniyeler alır ve ağın kendisi bundan daha hızlı olabilir. Kopyaları azaltmanın yolları şunlardır. NIC belleği doğrudan kullanıcı alanına eşlenebilir; süreç iletiyi oraya kendisi yazar. NIC, DMA ile ana belleği doğrudan okuyup yazabilir. En ileri çözüm RDMA'dır (remote direct memory access). InfiniBand ve RoCE ağlarında NIC, karşı makinedeki bir sürecin belleğine çekirdek hiç devreye girmeden yazar. Bir ileti böylece birkaç mikrosaniye yerine bir mikrosaniyenin altında karşıya ulaşır.

12.6.2Ara bağlantı topolojileri

Düğümlerin birbirine nasıl bağlandığına topoloji denir. Bir topolojiyi değerlendiren iki temel ölçü vardır. Çap, en uzak iki düğüm arasındaki en kısa yolun atlama sayısıdır; en kötü durumdaki gecikmeyi belirler. Bağlantı sayısı ise maliyeti belirler. Şekil 12.31 altı yaygın topolojiyi gösterir.

• Tek anahtar (yıldız): her düğüm merkezdeki anahtara bağlıdır. Çap 2'dir, ama anahtar tek hata noktasıdır ve büyütülemez.
• Halka: her düğümün iki komşusu vardır. n düğümlü çift yönlü halkada çap n / 2'dir.
• Izgara: düğümler bir kare düzende yerleşir. k × k ızgarada en uzak iki köşe arasında 2(k − 1) atlama vardır.
• Simit (torus): ızgaranın kenarları karşı kenara sarılır. k × k simitte çap 2 · ⌊k / 2⌋ olur.
• Hiperküp: d boyutlu hiperküpte 2^d düğüm vardır ve her düğüm d komşuya bağlıdır. Çap d = log₂n'dir.

Tablo bir ödünleşimi gösterir. Hiperküpün çapı en küçüktür, ama bağlantı sayısı da en büyüktür. Üstelik hiperküpte düğüm başına bağlantı sayısı boyutla birlikte artar; düğüm sayısı iki katına çıkınca her düğüme bir bağlantı daha eklenmelidir. Bugünkü süper bilgisayarlar çoğunlukla fat-tree ve dragonfly topolojilerini kullanır. Japonya'nın Fugaku süper bilgisayarı ise altı boyutlu bir simit ağı (Tofu) kullanır.

12.6.3Hiperküpte yönlendirme

Hiperküpte düğümler d bitlik numaralar taşır ve iki düğüm yalnız tek bir bitte farklıysa komşudur. 4 boyutlu hiperküpte 16 düğüm vardır; her düğümün 4 komşusu bulunur. Örneğin 0000'ın komşuları 1000, 0100, 0010 ve 0001'dir. Bu yapı yönlendirmeyi çok kolaylaştırır. İki düğüm arasındaki en kısa yolun uzunluğu, numaralarının kaç bitte farklı olduğuna, yani Hamming uzaklığına eşittir. İleti her adımda farklı bitlerden birini düzelterek ilerler.

E-küp yönlendirmesi (e-cube routing) bu bitleri her zaman aynı sırada, soldan sağa düzeltir. 0000'dan 1011'e giden bir ileti için kaynak ⊕ hedef = 1011'dir; üç bit farklıdır. Soldaki ilk farklı bit düzeltilir: 1000. Bu adım iletiyi alt 3 boyutlu küpten üst küpe geçirir. Sonra 1010'a, en son 1011'e gelinir (Şekil 12.32). Atlama sayısı 3'tür; 4 boyutlu hiperküpte en kötü durum log₂16 = 4 atlamadır.

Kuralın önemli bir özelliği yerel olmasıdır. Her düğüm yalnız kendi numarasına ve hedefin numarasına bakarak iletiyi hangi komşusuna göndereceğine karar verir. Yönlendirme tablosu gerekmez. Bitler hep aynı sırada düzeltildiği için yol döngüye de girmez.

12.6.4Kod izleme: e-küp yönlendirme

E-küp yönlendirmesi C'de birkaç satırdır. src kaynak, dst hedef düğüm, d hiperküpün boyutudur; işlev geçilen her düğümü yazdırır.

void yonlendir(int src, int dst, int d) {
  int u = src;
  for (int b = d - 1; b >= 0; b--) {
    int m = 1 << b;
    if ((u ^ dst) & m) {  /* bit farklı */
      u ^= m;             /* komşuya geç */
      printf("%d ", u);
    }
  }
}

u iletinin o anda bulunduğu düğümdür. Döngü en soldaki bitten (b = d − 1) başlayıp sağa doğru ilerler. m = 1 << b, yalnız b. biti 1 olan maskedir. (u ^ dst) & m sıfırdan farklıysa u ile hedef bu bitte farklıdır. u ^= m o biti çevirir; bu, iletinin o boyuttaki komşuya geçmesi demektir. Döngü d kez döner; atlama sayısı farklı bit sayısı kadardır.

12.6.5Sakla ve ilet ya da kesip geç

Bir paket kaynaktan hedefe birkaç anahtardan geçerek gider. Anahtarların paketi nasıl ilettiği, toplam gecikmeyi büyük ölçüde değiştirir. Örnek olarak 4 KiB'lık bir paket ve 10 Gb/s hızında bağlantılar düşünelim. Paketin bir bağlantıdan geçmesi 4096 × 8 bit / 10¹⁰ bit/s ≈ 3,28 µs sürer.

Sakla ve ilet (store-and-forward) yönteminde her anahtar paketin tamamını tamponuna alır, denetler ve ancak ondan sonra bir sonraki bağlantıya gönderir. A'dan iki anahtar üzerinden B'ye giden paket üç bağlantı geçer. Her bağlantıda paketin tamamı beklenir: 3 × 3,28 = 9,83 µs. Gecikme atlama sayısıyla doğrusal büyür.

Kesip geç (cut-through) yönteminde anahtar paketin başlığını okur okumaz yolu kurar ve paketin geri kalanını beklemeden iletmeye başlar. Paket boru gibi akar; ön kısmı hedefe varırken arka kısmı hâlâ kaynaktan çıkar. Solucan deliği (wormhole) yönlendirmesi bu düşüncenin küçük parçalara (flit) bölünmüş paketlerle kullanılan biçimidir. Toplam gecikme yaklaşık bir paket süresi artı anahtarların küçük başlık gecikmeleridir. Her anahtar başlığı 0,05 µs'de işlerse 3,28 + 2 × 0,05 ≈ 3,38 µs olur (Şekil 12.34).

Atlama sayısı arttıkça fark büyür. Sakla ve iletin gecikmesi atlama sayısıyla orantılıdır; kesip geçte ise her atlama yalnız küçük bir başlık gecikmesi ekler. Yüksek başarımlı hesaplama ağları ve veri merkezi anahtarları bu yüzden kesip geç ya da solucan deliği yöntemini kullanır.

12.6.6Bloke eden ve etmeyen gönderim

Çoklu bilgisayarda süreçler send ve receive çağrılarıyla haberleşir. Bu çağrıların en önemli tasarım sorusu, gönderenin iletinin gitmesini bekleyip beklemediğidir.

Bloke eden (blocking) ya da senkron gönderimde send çağrısı ileti iletilene kadar dönmez (Şekil 12.35 (a)). Süreç tuzakla çekirdeğe girer, ileti kopyalanır ve gönderilir; ancak ondan sonra süreç devam eder. Bu yöntem basit ve güvenlidir: send döndüğünde tampon yeniden kullanılabilir. Bedeli, CPU'nun iletim boyunca boşta beklemesidir.

Bloke etmeyen (nonblocking) ya da eş zamansız gönderimde send hemen döner ve süreç çalışmayı sürdürür (b). Hesaplama ile iletişim paralel yürür. Ama yeni bir sorun doğar: gönderen, iletim bitmeden tampondaki m'yi değiştirirse karşıya hangi veri gider? Tanenbaum bu soruna dört yanıt sıralar (Tablo 12.5).

İkinci seçenekte çekirdek iletiyi kendi tamponuna kopyalar ve süreç hemen devam eder; tampon artık serbesttir. Üçüncüsünde iletim bitince gönderene bir kesme ya da sinyal gelir; süreç o ana kadar tampona dokunmamalıdır. Dördüncüsünde tamponun sayfası salt okunur işaretlenir; süreç ancak tampona yazmaya kalkarsa sayfanın kopyası çıkarılır.

Alıcı tarafta da benzer seçenekler vardır. Bloke eden receive ileti gelene kadar bekler. Yoklama (polling) ile süreç ara sıra ileti gelip gelmediğine bakar. Üçüncü yol, ileti gelince yeni bir iş parçacığı açmak ya da iletinin içindeki kodu doğrudan çalıştırmaktır (active message). Bu kavramların bugünkü karşılıkları da tanıdıktır. MPI kütüphanesinde MPI_Send/MPI_Recv bloke eden, MPI_Isend/MPI_Irecv ile MPI_Wait bloke etmeyen çağrılardır. Linux'ta io_uring ve sıfır kopyalı MSG_ZEROCOPY aynı soruna verilmiş modern yanıtlardır.

12.6.7Uzak prosedür çağrısı

send ve receive bir G/Ç modelidir; programcıyı iletileri kendisi oluşturmaya zorlar. Birrell ve Nelson 1984'te daha tanıdık bir model önerdi: başka bir makinedeki bir prosedürü yerel bir prosedür gibi çağırmak.

Gizlemeyi koçan (stub) adı verilen küçük prosedürler yapar. İstemci sonuc = topla(3, 4) yazdığında aslında istemci koçanını çağırır. Bir çağrı şu adımlardan geçer (Şekil 12.36):

1. İstemci, istemci koçanını yerel bir prosedür gibi çağırır. Parametreler her zamanki gibi yığına konur.
2. Koçan parametreleri bir iletiye paketler ve çekirdeğe sistem çağrısı yapar. Paketlemeye sıralama (marshalling) denir.
3. Çekirdek iletiyi ağ üzerinden sunucu makinesine gönderir.
4. Sunucunun çekirdeği iletiyi sunucu koçanına verir.
5. Sunucu koçanı parametreleri açar ve sunucu prosedürünü yerel olarak çağırır.

Yanıt aynı yolu ters yönde izler: sunucu → koçan → çekirdek → ağ → istemci çekirdeği → istemci koçanı → istemci. İstemci açısından topla sıradan bir prosedürdür; yalnız biraz yavaştır.

Görünüşteki bu sadelik birkaç zorluğu saklar:

• İşaretçiler. İstemcideki bir adres sunucunun adres alanında anlamsızdır. Bir dizi parametresi değer olarak kopyalanıp gönderilir, sunucunun yaptığı değişiklikler de dönüşte geri kopyalanır. Bu yönteme kopyala-geri yükle (copy-restore) denir. Bağlı liste gibi işaretçilerle kurulu yapılar ise bu yolla kolayca gönderilemez.
• Uzunluğu bilinmeyen diziler. C'de bir dizinin uzunluğu dizinin kendisinde yazmaz. Koçan kaç bayt göndereceğini bilemez; uzunluk ayrı bir parametre olarak verilmelidir.
• Küresel değişkenler. Sunucu, istemcinin küresel değişkenlerini göremez.
• Kısmi hatalar. Yerel bir çağrıda çağıran ve çağrılan birlikte çöker. RPC'de sunucu ya da ağ tek başına çökebilir. İstemci yanıt alamayınca çağrıyı yinelerse prosedür iki kez çalışabilir. Bu yüzden bir RPC sisteminin “en az bir kez” mi, “en çok bir kez” mi anlamını sağladığı belirtilmelidir.
• Veri gösterimi. İki makinenin bayt sırası ya da tamsayı boyutu farklı olabilir; koçan veriyi ortak bir biçime dönüştürür.

Koçanlar elle yazılmaz; bir arayüz tanımından otomatik üretilir. Bugün en yaygın örnekler gRPC ve onun arayüz dili Protocol Buffers, Apache Thrift ve Java RMI'dır.

12.6.8Dağıtık paylaşımlı bellek

RPC ileti geçirmeyi prosedür çağrısının arkasına gizler. Daha iddialı bir düşünce, belleği paylaşmayan makinelerde paylaşımlı bellek yanılsaması yaratmaktır. Bu düşünceye dağıtık paylaşımlı bellek (distributed shared memory, DSM) denir. Yanılsamayı sağlayan katman donanımda (NUMA), işletim sisteminde ya da bir kullanıcı kütüphanesinde olabilir. Li ve Hudak'ın 1989'da tanımladığı sayfa tabanlı DSM, işletim sisteminin sanal bellek düzeneğini kullanır.

Bütün makineler aynı sanal adres alanını paylaşır, ama her sayfa fiziksel olarak tek bir makinenin belleğindedir (Şekil 12.37). Bir CPU, belleğinde olmayan bir sayfaya erişince MMU sayfa hatası üretir. İşletim sistemi, örneğin bir dizin aracılığıyla, sayfanın hangi makinede olduğunu bulur ve onu ister. Sayfa ağ üzerinden bu CPU'ya taşınır, sayfa tablosu güncellenir ve hataya yol açan komut yeniden yürütülür. Süreç açısından bu, diskten gelen sıradan bir sayfa hatasından farksızdır; yalnız sayfa diskten değil başka bir makineden gelir.

Sık okunan sayfaları sürekli taşımak pahalıdır. Salt okunur bir sayfa bu yüzden çoğaltılır (replication): şekildeki sayfa 10'un hem CPU 0'da hem CPU 1'de kopyası vardır ve iki CPU da yerel okur. Bir CPU çoğaltılmış bir sayfaya yazmak isterse diğer kopyalar geçersiz kılınır. Bu, MESI'nin sayfa boyutundaki karşılığıdır. Aynı nedenle yanlış paylaşım da sayfa boyutunda ortaya çıkar. Farklı makinelerde kullanılan bağımsız iki değişken aynı sayfadaysa sayfa iki makine arasında gidip gelir.

Sayfa tabanlı DSM bugün yaygın değildir. 4 KiB'lık bir sayfayı ağ üzerinden taşımak pahalıdır ve sayfa paylaşım için kaba bir birimdir. Yüksek başarımlı hesaplama ileti geçirmeye (MPI) ve PGAS dillerine (bölümlenmiş küresel adres alanı) yöneldi. Düşüncenin bugünkü karşılığı donanımdadır: CXL standardı birden çok makinenin ortak bir bellek havuzunu kullanmasına olanak verir.

12.6.9Çizge kuramsal deterministik atama

Çoklu bilgisayarda süreçlerin hangi düğümde çalışacağı da önemlidir. Çok haberleşen iki süreç ayrı düğümlere konursa her iletileri ağdan geçer. Aynı düğüme konursa iletileri yerel kalır. Süreçler arasındaki trafik önceden biliniyorsa atama bir çizge problemi olarak çözülebilir. Süreçler düğümler, aralarındaki trafik kenar ağırlıklarıdır. Amaç, düğümleri eşit büyüklükte kümelere bölerken kümeler arasında kalan kenarların toplam ağırlığını en aza indirmektir.

Çok haberleşen süreçler aynı makinede toplanınca ağ trafiği üçte bir azalmıştır. Ama bu yöntemin iki sınırı vardır. Birincisi, trafik önceden bilinmelidir. İkincisi, problem genel hâlinde NP-zordur: süreç sayısı arttıkça olası bölümlemelerin sayısı patlar ve hepsi denenemez. Pratikte sezgisel yöntemler kullanılır.

12.6.10Dağıtık sezgisel yük dengeleme

Trafik bilinmiyorsa ya da işler sürekli gelip gidiyorsa yük, düğümlerin kendi aralarında yürüttüğü basit kurallarla dağıtılır. İki temel algoritma vardır.

Gönderici başlatmalı (sender-initiated) algoritmada yeni bir iş oluşturan düğüm kendi yüküne bakar. Yükü bir eşiği aşıyorsa rastgele seçtiği başka bir düğüme “yükün ne?” diye sorar (Şekil 12.39). Yoklama sınırlı sayıda yapılır, örneğin en fazla N = 3 düğüm. Eşiğin altında bir düğüm bulunursa iş ona gönderilir; bulunamazsa yerelde çalışır. Eager ve arkadaşları 1986'da bu algoritmayı incelediler. Şekildeki örnekte eşik 7'dir ve yükü 9 olan düğüm 3 ve 1 yüklü iki düğümü yoklar. İşi en az yüklü olana, yükü 1 olan düğüme gönderir.

Bu algoritmanın sakıncası, sistem bütünüyle yüklüyken ortaya çıkar. Her düğüm iş yollamaya çalışır, her yoklama boşa gider. Yoklamaların kendisi de ağa ve düğümlere ek yük bindirir. Yük arttıkça sistem daha çok zamanını yoklamaya harcar.

Alıcı başlatmalı (receiver-initiated) algoritma sorunu tersinden ele alır. Bir işi biten ve boş kalan düğüm kendisi iş arar. Rastgele düğümleri yoklar ve yüklü birini bulursa ondan bir iş alır (Şekil 12.40). Yoklama maliyeti zaten boş olan düğüme düşer. Sistem yüklüyken boş düğüm azdır ve yoklama da az olur. Bu yüzden alıcı başlatmalı algoritma yük yüksekken iyi çalışır; gönderici başlatmalı ise yük düşükken. İkisini birleştiren algoritmalar da vardır.

Alıcı başlatmalı dengelemenin bugünkü karşılığı iş çalmadır (work stealing). Her işçi iş parçacığının kendi iş kuyruğu vardır. Kuyruğu boşalan işçi başka bir işçinin kuyruğunun öbür ucundan iş çalar. Cilk, Java'nın ForkJoinPool'u, Go'nun ve Rust'taki Tokio'nun çalışma zamanları bu yöntemi kullanır.

12.7Sanallaştırma

Bir veri merkezindeki sunucuların çoğu zamanlarının büyük kısmında az yüklüdür. Her hizmet için ayrı bir fiziksel makine ayırmak donanımı, enerjiyi ve yer israf eder. Sanallaştırma tek bir fiziksel makinede birden çok sanal makine çalıştırarak bu sorunu çözer. Her sanal makine kendi işletim sistemini çalıştırır ve diğerlerinden yalıtılmıştır. Bu kesim sanal makineleri çalıştıran yazılımı, işlemcinin ve belleğin nasıl sanallaştırıldığını ve konteynerleri anlatır.

12.7.1Hipervizörler: tip 1 ve tip 2

Hipervizörler nerede çalıştıklarına göre ikiye ayrılır (Şekil 12.41). Tip 1 hipervizör doğrudan donanım üzerinde çalışır; altında başka bir işletim sistemi yoktur. Çıplak donanım (bare metal) hipervizörü de denir. VMware ESXi, Xen (bugün XCP-ng) ve Microsoft Hyper-V bu türdendir. Linux'un KVM modülü, Linux çekirdeğinin kendisini bir tip 1 hipervizöre dönüştürür. Bulutların çoğu KVM ya da onun türevlerini kullanır; AWS'nin Nitro sistemi ve Google'ın bulutu bunlara örnektir. Windows'ta Hyper-V etkinleştirildiğinde Windows da hipervizörün üzerinde, ayrıcalıklı bir “kök bölümde” çalışmaya başlar.

Tip 2 hipervizör ise sıradan bir uygulama gibi bir ana makine (host) işletim sistemi üzerinde çalışır. VirtualBox, VMware Workstation ve Fusion, Parallels ve UTM bu türdendir. Aygıt erişimini ana makine işletim sistemine bırakır; bu yüzden G/Ç'de ek yük daha fazladır. Saf bir tip 2 hipervizör misafirin komutlarını yorumlar ya da ikili çeviriyle dönüştürür; KVM'siz QEMU böyle çalışır. Uygulamadaki tip 2 hipervizörler ise bir çekirdek modülü yükleyerek işlemcinin sanallaştırma desteğini kullanır. Bir hipervizörün türünü, donanım desteği kullanıp kullanmadığı değil, nerede çalıştığı belirler.

Bir makinenin verimli biçimde sanallaştırılabilmesi için gereken koşulu Popek ve Goldberg 1974'te ortaya koydular. Komutları iki gruba ayıralım. Hassas komutlar makinenin durumunu, örneğin sayfa tablosunu ya da G/Ç'yi etkileyen ya da ona göre farklı davranan komutlardır. Ayrıcalıklı komutlar ise kullanıcı modunda yürütülmeye çalışıldığında tuzağa düşen komutlardır.

Koşulun anlamı şudur. Misafir işletim sistemi kullanıcı modunda çalıştırılır. Sıradan komutları doğrudan donanımda yürütülür. Hassas bir komut yürütmeye kalktığında tuzağa düşer ve denetim hipervizöre geçer. Hipervizör komutun etkisini sanal makine için taklit eder. Klasik x86 bu koşulu sağlamıyordu. Örneğin POPF komutu kesme bayrağını da değiştirir; ama kullanıcı modunda bu değişikliği tuzağa düşmeden, sessizce yok sayar. Misafir işletim sistemi kesmeleri kapattığını sanır, hipervizörün de bundan haberi olmaz. Bu sorun önce ikili çeviriyle, sonra donanım desteğiyle çözüldü.

Sanallaştırmanın kullanım nedenleri bugün iyi bilinir. Birçok sunucu tek bir makinede birleştirilir. Çalışan bir sanal makine başka bir fiziksel makineye kesintisiz taşınabilir; buna canlı göç denir. Bir sanal makinenin anlık görüntüsü alınıp gerektiğinde ona geri dönülebilir. Bulut bilişimin temeli de budur.

12.7.2Tuzak ve benzet: VT-x ve AMD-V

Intel 2005'te VT-x, AMD 2006'da AMD-V ile x86'ya donanım sanallaştırma desteği ekledi. Bu destek işlemciye yeni bir çalışma kipi kazandırır. Hipervizör root kipinde, misafir non-root kipinde çalışır. Misafir işletim sistemi non-root kipinin kendi çekirdek modunda çalışır ve kendini gerçekten çekirdek modunda sanar. Ama gerçek denetim hipervizördedir.

Misafir çekirdek hassas bir komut yürütmek istediğinde şunlar olur (Şekil 12.42):

1. Misafir çekirdek hassas bir komut yürütür: sayfa tablosu tabanını değiştiren mov cr3, bir G/Ç portuna yazan out ya da işlemciyi durduran hlt.
2. Donanım komutu çalıştırmaz. Bunun yerine bir VM çıkışı (VM exit) ile denetimi hipervizöre verir. Misafirin durumu ve çıkışın nedeni VMCS adlı bir bellek yapısına yazılır.
3. Hipervizör komutun etkisini benzetir (emulate). Örneğin gölge tablo ya da EPT'yi günceller, sanal aygıtın durumunu değiştirir.
4. Hipervizör bir VM girişi (VM entry) ile misafire geri döner; misafir bir sonraki komuttan devam eder.

Misafirin yalnız hassas komutları tuzağa düşer; geri kalan komutları doğrudan donanımda, tam hızda çalışır. Yine de bir VM çıkışı yaklaşık bir mikrosaniye sürer. Sık çıkış yapan bir iş yükü bu yüzden yavaşlar. Donanım desteğinden önce VMware (1999) bu sorunu ikili çeviriyle çözüyordu. Misafir çekirdeğin kodu çalıştırılmadan önce taranır, hassas komutlar hipervizörü çağıran güvenli kod parçalarıyla değiştirilir. Çevrilmiş kod önbelleğe alınır ve tekrar tekrar kullanılır.

12.7.3Yarı sanallaştırma

Tuzak ve benzetmenin bedelinden kaçmanın bir yolu daha vardır: misafir işletim sistemini değiştirmek.

Hiperçağrı bir sistem çağrısının bir alt katmandaki benzeridir. Uygulama işletim sisteminden nasıl hizmet istiyorsa, misafir işletim sistemi de hipervizörden öyle ister. Tuzak ve benzetme maliyeti olmadığı için yöntem daha hızlıdır. Bedeli, misafir işletim sisteminin kaynak kodunun değiştirilebilir olmasıdır. Xen (2003) bu yaklaşımı ilk yaygınlaştıran hipervizördür; Linux'un değiştirilmiş bir sürümü Xen üzerinde neredeyse doğal hızda çalışıyordu (Şekil 12.43).

Her hipervizörün kendi hiperçağrı arayüzü olması bir sorundu: bir çekirdeğin ayrı ayrı sürümleri gerekiyordu. Tek bir çekirdeğin hem çıplak donanımda hem de farklı hipervizörlerde çalışabilmesi için VMI (Virtual Machine Interface) adlı ortak bir arayüz önerildi. Donanım desteği yaygınlaşınca gerek kalmadı ve VMI 2011'de Linux'tan kaldırıldı. Bugün yarı sanallaştırma daha çok sürücülerde yaşar. virtio disk ve ağ sürücüleri, yarı sanal saat ve Hyper-V'nin “aydınlatmaları” (enlightenments) bunun örnekleridir. Günümüz bulutlarında CPU ve bellek donanım desteğiyle tam sanallaştırılır. G/Ç ise ya virtio gibi yarı sanal sürücülerle ya da SR-IOV ile bir aygıtın parçasının doğrudan sanal makineye atanmasıyla yapılır.

12.7.4Bellek sanallaştırma: gölge tablo ve EPT

Sanal makinede adres çevirisi iki katmanlıdır (Şekil 12.44). Misafirdeki bir süreç misafir sanal adresi (GVA) üretir. Misafir işletim sisteminin sayfa tabloları onu misafir fiziksel adresine (GPA) çevirir. Ama misafirin “fiziksel” belleği de aslında hipervizörün ayırdığı bir bellek parçasıdır. Hipervizör GPA'yı gerçek ana makine fiziksel adresine (HPA) çevirmelidir.

Donanım desteğinden önceki çözüm gölge sayfa tablolarıdır (shadow page tables). Hipervizör her misafir süreci için GVA'yı doğrudan HPA'ya eşleyen bir tablo tutar ve MMU'ya bu tabloyu verir. Misafirin kendi tablolarını salt okunur yapar. Misafir bir tablo girdisini değiştirmeye kalkınca tuzağa düşer; hipervizör değişikliği gölge tabloya da yansıtır. Çeviri hızlıdır, ama misafirin her tablo değişikliği bir VM çıkışı demektir. Süreç oluşturan ya da çok sayfa hatası alan iş yükleri bu yüzden çok yavaşlar.

Intel'in EPT'si (Extended Page Tables, 2008) ve AMD'nin NPT'si (Nested Page Tables) bu işi donanıma verir. MMU iki tabloyu birlikte yürür. Misafir kendi tablosunu tuzağa düşmeden değiştirir; hipervizör yalnız GPA → HPA tablosunu yönetir. Bedel TLB ıskasındadır. Misafir tablosunun her girdisi bir GPA'dır; okunabilmesi için önce EPT'den geçirilmelidir.

Bu uzun yürüyüşün etkisini azaltmanın iki yolu vardır. Büyük sayfalar (2 MiB ya da 1 GiB) hem tablo düzeyi sayısını hem de TLB ıskalarını azaltır. TLB girdilerinin sanal makine kimliğiyle etiketlenmesi (Intel'de VPID, AMD'de ASID) ise sanal makineler arasında geçişte TLB'nin boşaltılmasını gereksiz kılar.

Hipervizörler belleği misafirlere fiziksel bellekten fazla da dağıtabilir (aşırı tahsis). İki düzenek bunu destekler. Balon sürücüsü, misafirin içinde çalışan bir sürücüdür. Hipervizör bellek isteyince misafirden bellek ayırır ve bu sayfaları hipervizöre geri verir; misafir kendi sayfa değiştirme politikasıyla neyin diske gideceğine kendisi karar verir. Linux'un KSM (Kernel Same-page Merging) düzeneği ise farklı sanal makinelerdeki aynı içerikli sayfaları bulur ve tek bir kopyada birleştirir. Biri sayfaya yazarsa yazınca kopyala ile ayrı bir kopya çıkarılır.

12.7.5Konteynerler ve sanal makineler

Her sanal makine kendi çekirdeğini çalıştırır; başlaması saniyeler alır ve gigabaytlarca bellek tutar. Birçok uygulama için bu fazladır. Uygulamaları birbirinden yalıtmak çoğu zaman yeterlidir; ayrı bir çekirdek gerekmez.

Linux konteynerleri üç çekirdek düzeneğine dayanır. Ad alanları (namespaces) bir süreç grubuna kendi süreç numaralarını, dosya sistemi ağacını, ağ arayüzlerini ve makine adını gösterir; grup diğer süreçleri göremez. Denetim grupları (cgroups) grubun kullanabileceği CPU, bellek ve G/Ç miktarını sınırlar. seccomp ise grubun yapabileceği sistem çağrılarını kısıtlar. Bir konteynerin içinde bir dağıtımın kütüphaneleri ve araçları bulunur, ama çekirdek ana makinenindir (Şekil 12.45).

Konteynerin yalıtımı sanal makinenin yalıtımından zayıftır. Bütün konteynerler aynı çekirdeği paylaştığı için çekirdekteki bir güvenlik açığı hepsini etkiler. Arada kalan çözümler bu yüzden yaygınlaşıyor. AWS Lambda'nın kullandığı Firecracker, milisaniyeler içinde açılan küçük sanal makineler (mikro-VM) üretir. gVisor, konteynerin sistem çağrılarını kullanıcı alanındaki bir çekirdekte karşılar. Kata Containers her konteyneri hafif bir sanal makinede çalıştırır. Windows'taki WSL 2 de hafif bir Hyper-V sanal makinesinde gerçek bir Linux çekirdeği çalıştırır; Windows'taki Linux konteynerleri bu sanal makinede koşar.

12.8Dağıtık sistemler

Çoklu bilgisayarın düğümleri aynı odadadır, aynı kurumun yönetimindedir ve özel bir ağla bağlıdır. Dağıtık sistemde bu varsayımların hepsi gevşer. Bu kesim dağıtık sistemleri, onları bir arada tutan ağı ve ara yazılımın dört ana türünü anlatır.

12.8.1Dağıtık sistem ve ara yazılım

Dağıtık sistem, ağ üzerinden haberleşen özerk bilgisayarlardan oluşur. Her bilgisayar kendi işletim sistemini, belleğini ve kaynaklarını yönetir. Sistem kullanıcıya yine de tek ve tutarlı bir sistem gibi görünmeye çalışır. Düğümler farklı donanımlar ve farklı işletim sistemleri çalıştırabilir, farklı kurumlara ait olabilir ve dünyaya yayılabilir.

Farklı işletim sistemleri ortak bir dili ancak ara yazılım sayesinde konuşur (Şekil 12.46). Ara yazılım dört temel paradigmadan birine dayanır. Belge tabanlı ara yazılımda her şey bir belgedir; Web bunun örneğidir. Dosya tabanlı ara yazılımda her şey bir dosyadır; NFS ve SMB böyledir. Nesne tabanlı ara yazılımda her şey bir nesnedir; CORBA, Java RMI ve gRPC bu türdendir. Koordinasyon tabanlı ara yazılımda ise süreçler ortak bir uzay ya da aracı üzerinden haberleşir; Linda ve yayınla-abone ol sistemleri bu türdendir.

Bütün düğümleri tek bir işletim sistemi gibi yöneten gerçek dağıtık işletim sistemleri de denendi. Amoeba ve Plan 9 bunların en bilinenleridir. Bunlar araştırma sistemleri olarak kaldı. Bugün her düğüm kendi işletim sistemini çalıştırır; dağıtımı ara yazılım ve Kubernetes gibi küme yöneticileri üstlenir.

12.8.2Üç sistem türünün karşılaştırması

Bu bölümde üç paralel düzen ele alındı: çok işlemci, çoklu bilgisayar ve dağıtık sistem. Tablo 12.7 onları Tanenbaum'un karşılaştırmasıyla yan yana koyar.

12.8.3Ağ donanımı ve kapsülleme

Dağıtık sistemin düğümlerini bir ağ bağlar. Yerel ağların en yaygın türü Ethernet'tir (Şekil 12.48). 1976'daki klasik Ethernet'te bütün bilgisayarlar tek bir kabloyu paylaşıyordu. Bir bilgisayar göndermeden önce kabloyu dinler, boşsa gönderirdi. İki bilgisayar aynı anda gönderirse çarpışma olur, ikisi de rastgele bir süre geri çekilip yeniden denerdi. Bu yönteme CSMA/CD denir. Bugün her bilgisayar bir anahtara ayrı bir kabloyla bağlıdır. Bağlantılar 1 ile 400 Gb/s arasında hızlarda ve tam çift yönlü çalışır; çarpışma olmaz.

Yerel ağlar yönlendiricilerle birbirine bağlanır. Kurumların ağları İnternet servis sağlayıcılarına, onlar da İnternet'in omurgasına bağlanır. Omurga yüksek hızlı fiber hatlardan ve ağların birbirine bağlandığı değişim noktalarından oluşur.

Ağ yazılımı katmanlar hâlinde düzenlenir. Bir uygulama verisi gönderilirken her katman kendi başlığını ekler. Taşıma katmanı TCP başlığını, ağ katmanı IP başlığını, bağlantı katmanı Ethernet başlığını ve sondaki denetim toplamını (FCS). Buna kapsülleme denir. Alıcı tarafta başlıklar ters sırayla çıkarılır ve her katman kendi başlığını yorumlar.

12.8.4Ağ protokolleri ve hizmet türleri

Ağ hizmetleri iki açıdan sınıflandırılır. Bağlantı yönelimli hizmette önce bir bağlantı kurulur, sonra veri gönderilir, en sonda bağlantı sonlandırılır; telefon görüşmesine benzer. Bağlantısız hizmette kurulum maliyeti yoktur; her paket bağımsız gönderilir, posta gibi. Güvenilir hizmet verinin teslim edildiğini ve sırasını garanti eder; alıcı her paketi bir alındı onayıyla (ACK) bildirir. Güvenilmez hizmet bu garantiyi vermez. Tablo 12.8 İnternet'in temel protokollerini özetler.

UDP'nin sağlama toplamı bozuk bir paketi algılar, ama onu düzeltmez ve yeniden göndermez; bozuk paket yalnız atılır. Kayıp ya da bozuk paketleri yeniden göndermek TCP'nin ya da uygulamanın işidir.

12.8.5Belge tabanlı ara yazılım: Web

Web'de her şey bir belgedir. Belgeler birbirine bağlantılarla bağlanır ve dev bir yönlendirilmiş çizge oluşturur. Kullanıcı tarayıcıya www.ornek.org/index.html adresini yazdığında şunlar olur (Şekil 12.49):

1. Tarayıcı, işletim sisteminin çözücüsü üzerinden DNS'e www.ornek.org'un IP adresini sorar.
2. Yanıt gelir: 203.0.113.10. Yanıt bir süre önbellekte tutulur.
3. Tarayıcı sunucunun 443 numaralı portuna bir TCP bağlantısı açar ve TLS el sıkışmasını yapar. HTTP/3'te bu iki adım QUIC ile tek adımda birleşir.
4. Tarayıcı GET /index.html isteğini gönderir.
5. Sunucu HTML dosyasını döndürür ve tarayıcı metni görüntülemeye başlar.
6. HTML'nin başvurduğu resimler, CSS ve betikler aynı bağlantı üzerinden alınır; HTTP/2 ve HTTP/3 bunları paralel akışlarla taşır. Bağlantı bir süre açık kalır.

Eski ders kitaplarında port 80'e bağlanılır ve her nesne için yeni bir TCP bağlantısı açılıp kapatılırdı. Bu HTTP/1.0 dönemine aittir. Bugün varsayılan HTTPS'dir (port 443); bağlantılar kalıcıdır ve HTTP/2–3 çoğullama kullanır.

12.8.6Dosya sistemi tabanlı ara yazılım

Dosya tabanlı ara yazılım dağıtık sistemi bir dosya sistemi gibi gösterir. İlk tasarım sorusu, dosyaya nasıl erişileceğidir (Şekil 12.50). Yükleme/indirme modelinde istemci dosyanın tamamını kendine kopyalar, yerelde okur ve yazar, işi bitince yeni hâlini sunucuya geri yükler. Bu model basittir, ama büyük bir dosyanın birkaç baytını okumak için bütün dosyayı taşımak pahalıdır. FTP ve eski AFS bu modeli kullanır. Uzaktan erişim modelinde dosya sunucuda kalır. İstemci read ve write isteklerini ağ üzerinden gönderir ve yalnız istediği bloklar taşınır. NFS ve SMB bu modeli kullanır.

İkinci soru adlandırmadır. En basit çözümde dosya adı makine adını içerir: makine:/yol. Bu ad konum şeffaf değildir; dosya başka bir makineye taşınırsa adı değişir. Daha iyi bir çözüm, uzak dosya sistemini yerel ağacın bir dizinine bağlamaktır (mount). Bütün istemciler sunucuları aynı yere bağlarsa herkes tek ve ortak bir ad alanı görür. İstemciler farklı şeyler bağlarsa her biri farklı bir görünüm görür (Şekil 12.51). Aynı yol farklı istemcilerde farklı dosyaları gösterebilir. En güçlü çözüm, bütün makinelerde aynı olan ve dosyanın konumunu hiç içermeyen tek bir ad alanıdır. Buna konumdan bağımsızlık denir. Bugünkü örnekler NFSv4, SMB 3 ve Amazon S3 gibi nesne depolama sistemleridir.

12.8.7Dosya paylaşımının anlamı

Birden çok istemci aynı dosyayı paylaştığında bir yazmanın başkalarına ne zaman görüneceği tanımlanmalıdır. Tek bir makinede yanıt açıktır. A süreci bir dosyaya “c” ekler, ardından B okursa “abc” görür. Her okuma en son yazmayı görür. Buna UNIX semantiği ya da sıralı tutarlılık denir (Şekil 12.52, üstte).

Dağıtık sistemde istemciler performans için dosyaları önbelleğe alır. İstemci 1 dosyayı önbelleğinde değiştirir ama sunucu bunu henüz bilmez. İstemci 2 sunucudan okur ve eski “ab”yi görür. UNIX semantiğini korumanın tek yolu önbellek kullanmamak ve her işlemi sunucuya göndermektir; bu da çok yavaştır. Dağıtık sistemler bu yüzden daha gevşek anlamlar kullanır (Tablo 12.9).

Oturum semantiğinde bir istemcinin değişiklikleri dosyayı kapatana kadar yalnız kendisine görünür. Dosya kapatıldıktan sonra açan istemciler yeni sürümü görür. Değişmez dosyalarda sorun hiç çıkmaz, çünkü bir dosya hiçbir zaman değiştirilmez; değişiklik yeni bir dosya üretir. İşlemlerde bir dizi işlem ya bütünüyle ya da hiç yapılır ve eş zamanlı işlemler sanki sırayla yapılmış gibi sonuç verir. Her çözüm tutarlılık ile performans arasında farklı bir noktada durur.

12.8.8Nesne tabanlı ara yazılım: CORBA

Nesne tabanlı ara yazılımda dağıtık sistem bir nesneler topluluğudur. Bir istemci, başka bir makinedeki bir nesnenin yöntemini yerel bir nesneninki gibi çağırır. Bu yaklaşımın en kapsamlı örneği OMG'nin 1991'de tanımladığı CORBA'dır (Şekil 12.53).

• IDL (Interface Definition Language): nesnelerin arayüzleri programlama dilinden bağımsız bir dille tanımlanır. IDL derleyicisi bu tanımdan istemci koçanını ve sunucu tarafındaki iskeleti (skeleton) üretir.
• ORB (Object Request Broker, nesne istek aracısı): nesnenin yerini bulur, çağrıyı paketler ve IIOP protokolüyle karşı tarafa iletir. İstemci nesnenin hangi makinede olduğunu bilmez; buna ağ şeffaflığı denir.
• Statik çağırma (SII): istemci, derleme zamanında IDL'den üretilmiş koçanları kullanır. Hızlıdır ve türler derleme zamanında denetlenir.
• Dinamik çağırma (DII): istemci, çağıracağı arayüzü çalışma zamanında bir arayüz deposundan keşfeder ve çağrıyı kendisi kurar.

SII ve DII iki ayrı düzenektir; SII, DII'nin derlenmiş bir sürümü değildir. CORBA bugün daha çok eski sistemlerde yaşar. Yeni sistemlerde gRPC ile Protocol Buffers, REST ve Java RMI tercih edilir. Ama IDL'den koçan üretmek, ORB benzeri bir aracı ve konumdan bağımsız nesne başvuruları gibi fikirleri bu sistemlere geçmiştir.

12.8.9Koordinasyon tabanlı ara yazılım: Linda

Koordinasyon tabanlı ara yazılımda süreçler birbirini tanımaz. Doğrudan haberleşmek yerine ortak bir ortama veri koyar ve oradan veri alır. Bu yaklaşımın klasik örneği Gelernter'in 1985'te tanıttığı Linda'dır.

Linda'nın dört temel işlemi vardır (Şekil 12.54):

• out bir demeti uzaya koyar ve bloke olmaz.
• in bir şablonla eşleşen bir demeti arar, uzaydan çıkarır ve alanlarını değişkenlere atar. Eşleşen demet yoksa çağıran bloke olur ve uyan bir demet konana kadar bekler.
• rd in gibi çalışır, ama demeti uzaydan çıkarmaz; yalnız okur.
• eval yeni bir süreç başlatır; süreç bitince sonucu bir demet olarak uzaya konur.

Bir şablonun bir demetle eşleşmesi için üç koşul gerekir. Alan sayıları aynı olmalıdır. Karşılıklı alanlar aynı türde olmalıdır. Şablondaki sabit alanlar da demettekilere eşit olmalıdır. ? i biçimindeki alanlar biçimsel parametredir: türü uyan her değerle eşleşir ve o değer i'ye atanır. Birden çok demet eşleşirse hangisinin seçileceğini Linda tanımlamaz.

Bu basit işlemlerle senkronizasyon da kendiliğinden gelir. Örneğin bir semafor, uzaya konan özdeş demetlerle gerçeklenebilir: out("sem") V işlemi, in("sem") P işlemidir. Bir iş havuzu da benzer biçimde kurulur: yönetici işleri out ile koyar, işçiler in ile alır.

12.8.10Kod izleme: Linda in()

Aşağıdaki işlev, demet uzayını bir bağlı liste olarak tutan basit bir Linda gerçeklemesinde in()'in arama kısmıdır. s şablondur; n alan sayısını, tur[k] k. alanın türünü, sabit[k] o alanın sabit olup olmadığını tutar.

Demet *in_ara(Sablon *s) {
  for (Demet *d = uzay; d; d = d->snr) {
    if (d->n != s->n) continue;
    int ok = 1;
    for (int k = 0; ok && k < s->n; k++)
      if (d->tur[k] != s->tur[k] ||
          (s->sabit[k] && !esit(d, s, k)))
        ok = 0;          /* alan uymadı */
    if (ok) { cikar(d); return d; }
  }
  return NULL;           /* bloke ol */
}

Dış döngü uzaydaki demetleri sırayla dolaşır. Alan sayısı farklıysa demet hemen atlanır (continue). Aksi hâlde iç döngü alanları tek tek karşılaştırır. Tür farklıysa ya da alan sabit olup değeri farklıysa ok 0 olur ve iç döngü durur. Bütün alanlar uyarsa demet uzaydan çıkarılır ve döndürülür. Hiçbir demet uymazsa işlev NULL döndürür; çağıran süreç bloke olur.

12.8.11Yayınla-abone ol ve Jini

Koordinasyonun bugün en yaygın biçimi yayınla-abone ol (publish-subscribe) modelidir (Şekil 12.56). Yayıncı bir iletiyi bir konuya yayınlar. Abone ilgilendiği konulara abone olur. Aradaki aracı (broker) her iletiyi o konunun bütün abonelerine iletir. Yayıncı ile abone birbirinin kimliğini bilmez; aynı anda çalışmaları da gerekmez. Bu iki özelliğe uzayda ve zamanda ayrıklık denir.

Abone ve konular çalışma sırasında eklenip çıkarılabilir; sistem bu yüzden esnek ve ölçeklenebilirdir. Teslim garantisi aracının ayarına bağlıdır: en çok bir kez, en az bir kez ya da iletilerin kalıcı bir kuyrukta saklanması. Bugünkü örnekler nesnelerin interneti için MQTT, Apache Kafka, RabbitMQ ve bulut sağlayıcılarının kuyruk hizmetleridir.

Jini, Sun'ın 1998'de tanıttığı bir koordinasyon sistemidir. Ağa katılan Java aygıtları önceden yapılandırma gerekmeden bir arama hizmetini bulur ve sundukları hizmetleri ona kaydeder. Bir istemci arama hizmetinden uygun bir hizmet bulur ve onu Java RMI ile kullanır. Kayıtlar bir kiralama (lease) süresiyle yapılır. Süre yenilenmezse kayıt kendiliğinden düşer; böylece çöken aygıtlar hizmet listesinden temizlenir. Jini, Apache River adıyla sürdürüldü ama bugün etkin değildir. Fikirleri ise servis keşfinde yaşıyor: mDNS/DNS-SD, Consul ve Kubernetes servisleri.

12.8.12Bulut ve kümeler

Küme, hızlı bir ağla bağlı ve tek bir yönetim altındaki sunuculardır; yüksek başarımlı hesaplama kümeleri ve veri merkezleri buna örnektir. Bulut ise bu kaynakların ağ üzerinden, isteğe bağlı olarak ve kullandıkça öde biçiminde sunulmasıdır. AWS, Azure ve Google Cloud en büyük bulut sağlayıcılarıdır.

Bulut hizmetleri, katmanların ne kadarını sağlayıcının yönettiğine göre ayrılır (Şekil 12.57). Şirket içi bir sistemde her katmanı kullanıcı yönetir. IaaS'ta (Infrastructure as a Service) sağlayıcı sunucuları, depolamayı, ağı ve sanallaştırmayı yönetir; kullanıcı sanal makinesinde işletim sisteminden yukarısını yönetir. PaaS'ta (Platform as a Service) kullanıcı yalnız uygulamasını ve verisini getirir. FaaS'ta (Function as a Service) kullanıcı yalnız tek tek işlevler yazar; sağlayıcı onları her istekte çalıştırır. SaaS'ta (Software as a Service) kullanıcı hazır bir uygulamayı kullanır ve hiçbir katmanı yönetmez.

Bulutun altyapısı bu bölümün konularının bir araya gelmesidir. Fiziksel sunucular çok çekirdekli NUMA makineleridir. Üzerlerinde KVM ya da Nitro gibi hipervizörler sanal makineler çalıştırır. Sanal makinelerin ya da sunucuların üzerinde konteynerler koşar. Kubernetes bu konteynerleri (pod'ları) düğümlere çizelgeler, çökenleri yeniden başlatır ve yükü dağıtır; bir bakıma dağıtık işletim sisteminin bugünkü karşılığıdır. Düğümler RDMA destekli ağlarla bağlanır, iş yükleri yük dengeleyicilerle dağıtılır ve hizmetler yayınla-abone ol kuyruklarıyla haberleşir.

12.9Özet

• Paralel sistemler üç düzende kurulur: paylaşımlı bellekli çok işlemci, ileti geçiren çoklu bilgisayar ve geniş alana yayılmış dağıtık sistem. Saat hızı 2005'ten beri yerinde saydığı için transistör bütçesi çekirdek sayısına gidiyor. Amdahl yasasına göre hızlanma 1 / ((1 − p) + p / n)'dir ve 1 / (1 − p)'yi aşamaz.
• UMA makinelerinde her bellek sözcüğüne aynı sürede erişilir. Tek veri yolu birkaç CPU'da doyar. Çapraz çubuk engellemesizdir ama n² kesişim ister. Omega ağı (n/2)·log₂n anahtarla kurulur, hedef adresin bitleriyle yönlendirir ve engellemelidir.
• NUMA'da uzak erişim yerelden yavaştır; ortalama erişim y · t_yerel + (1 − y) · t_uzak'tır. İşletim sistemi ilk dokunma, afinite ve otomatik NUMA dengelemesiyle veriyi işin yanında tutar. CC-NUMA'da tutarlılık bir dizinle sağlanır; iletiler yalnız ilgili düğümlere gider.
• Önbellek tutarlılığı, aynı adrese yapılan yazmaların herkesçe aynı sırada görülmesidir. MESI'de E'deki satıra yazmak sessizdir, S'deki satıra yazmak geçersiz kılma ister, M'deki satır başkasına verilirken belleğe de yazılır.
• Yanlış paylaşımda bağımsız değişkenler aynı 64 baytlık satırda olduğu için satır çekirdekler arasında gidip gelir. Çözüm hizalama ve dolgudur.
• Çok çekirdekli yongalar yongacıklardan, büyük–küçük çekirdeklerden ve hızlandırıcılardan oluşur. SMT bir çekirdeği birden çok mantıksal CPU olarak gösterir; kazanç %10–30'dur ve güvenlik riski taşır.
• Üç işletim sistemi modeli vardır. Her CPU'nun kendi işletim sistemi paylaşım sunmaz. Usta-kölede usta darboğazdır. SMP'de herkes çekirdeği çalıştırır ve paylaşılan yapılar ince taneli kilitlerle korunur.
• Çok işlemcide TSL okuma ve yazma süresince yolu ya da satırı kilitlemelidir. Bilet kilidi adildir; TTAS bekleyenleri yerel kopyada döndürür; MCS her bekleyene ayrı bir bayrak verir. Beklenen bekleme 2C'den kısaysa dönmek, uzunsa uyumak ucuzdur; 2C dönüp sonra uyumak en kötü durumda iki kat maliyet verir.
• Ortak hazır kuyruğu yükü dengeler ama tek kilit ve soğuk önbellek sorunu taşır; bugünkü sistemler CPU başına kuyruk ve yük dengeleme kullanır. Alan paylaşımı bir işe CPU'ları bitene kadar ayırır. Çete çizelgelemede birbirine bağlı iş parçacıkları aynı dilimde, farklı CPU'larda çalışır.
• Çoklu bilgisayarda iletiler beş kez kopyalanabilir; RDMA kopyaları kaldırır. Topolojilerin çapı halkada n / 2, k × k ızgarada 2(k − 1), hiperküpte log₂n'dir. E-küp yönlendirmesi farklı bitleri soldan sağa düzeltir. Kesip geç, sakla ve iletin atlama sayısıyla büyüyen gecikmesini ortadan kaldırır.
• Gönderim bloke eden ya da etmeyen olabilir. RPC uzak çağrıyı koçanlarla yerel çağrı gibi gösterir; işaretçiler ve kısmi hatalar zorluk çıkarır. DSM sayfa hatalarıyla paylaşımlı bellek yanılsaması yaratır. Süreç ataması bir çizge bölümleme problemidir; dağıtık yük dengeleme gönderici ya da alıcı başlatmalı olabilir.
• Hipervizörler tip 1 (çıplak donanım) ve tip 2 (ana makine üzerinde) olarak ayrılır. Popek–Goldberg koşulunu sağlamayan x86 önce ikili çeviriyle, sonra VT-x/AMD-V ile sanallaştırıldı. Yarı sanallaştırma hiperçağrı kullanır. EPT gölge tabloların VM çıkışlarını kaldırır, ama TLB ıskası (n + 1)(m + 1) − 1 erişime çıkar. Konteynerler tek çekirdeği paylaşır.
• Dağıtık sistemde ara yazılım belge (Web), dosya (NFS, SMB), nesne (CORBA, gRPC) ya da koordinasyon (Linda, yayınla-abone ol) modeli sunar. Dosya paylaşımında UNIX semantiği pahalıdır; oturum semantiği, değişmez dosyalar ve işlemler ödünleşimlerdir. Bulut bütün bu katmanları hizmet olarak sunar.

12.10Kavram listesi

• Amdahl yasası Amdahl's law
• simetrik çok işlemci (SMP) symmetric multiprocessor
• UMA / NUMA uniform / non-uniform memory access
• çapraz çubuk anahtar crossbar switch
• omega ağı omega network
• önbellek tutarlılığı cache coherence
• dinleme / dizin snooping / directory
• MESI protokolü MESI protocol
• yanlış paylaşım false sharing
• çok çekirdekli multicore
• eş zamanlı çoklu iş parçacığı (SMT) simultaneous multithreading
• usta-köle modeli master-slave model
• spinlock spinlock
• bilet kilidi ticket lock
• işlemci afinitesi processor affinity
• yük dengeleme load balancing
• alan paylaşımı space sharing
• çete çizelgeleme gang scheduling
• çoklu bilgisayar multicomputer
• hiperküp hypercube
• ileti geçirme message passing
• uzak prosedür çağrısı (RPC) remote procedure call
• dağıtık paylaşımlı bellek distributed shared memory
• hipervizör hypervisor
• yarı sanallaştırma paravirtualization
• sanal makine virtual machine
• konteyner container
• ara yazılım middleware
• demet uzayı tuple space
• yayınla-abone ol publish-subscribe

12.11Kendini Dene

1. Bir programın %90'ı paralelleştirilebiliyor. 16 çekirdekte hızlanma nedir ve çekirdek başına verim (hızlanma / n) ne olur? Hızlanmanın üst sınırı kaçtır?

   Cevap

   S(16) = 1 / (0,1 + 0,9 / 16) = 1 / (0,1 + 0,05625) = 1 / 0,15625 = 6,4. Verim 6,4 / 16 = 0,4: çekirdeklerin gücünün ancak %40'ı kullanılır. Üst sınır 1 / 0,1 = 10'dur.

2. 8 × 8 omega ağında CPU 110, bellek 001'e erişiyor. İstek hangi anahtarlardan, hangi çıkışlarla geçer? Aynı anda CPU 000 bellek 000'ı okumak isterse çakışma olur mu?

   Cevap

   110 karıştırmayla 101 numaralı girişe, yani 1C'ye gelir. Hedef 001'in bitleri 0, 0, 1 olduğu için yol 1C (üst) → 2A (üst) → 3A (alt) olur. CPU 000'ın isteği 1A (üst) → 2A (üst) → 3A (üst) yolunu izler. İki istek de 2A'nın üst çıkışını kullanır; biri bekler. Hedef modüller farklı olduğu hâlde ağın içinde çakışma oluşmuştur.

3. Bir NUMA makinesinde yerel erişim 90 ns, uzak erişim 150 ns'dir. Erişimlerin %80'i yerelse ortalama süre nedir? Ortalamanın 100 ns'yi geçmemesi için yerel erişim oranı en az ne olmalıdır?

   Cevap

   0,8 · 90 + 0,2 · 150 = 72 + 30 = 102 ns. 90y + 150(1 − y) ≤ 100 koşulundan 150 − 60y ≤ 100, yani y ≥ 50 / 60 ≈ 0,833 bulunur. Erişimlerin en az yaklaşık %83,3'ü yerel olmalıdır.

4. 256 düğümlü, düğüm başına 16 MiB ve 64 baytlık satırlı dizin tabanlı sistemde 0x5A0003C4 adresinin satırı hangi düğümün belleğindedir? Blok numarası ve ofset nedir?

   Cevap

   En soldaki 8 bit 0x5A = 90'dır: satır düğüm 90'dadır. Kalan 24 bit 0x0003C4 = 964'tür. 964 = 15 · 64 + 4 olduğu için blok 15, ofset 4'tür. İstek düğüm 90'a gider ve onun dizininin 15. girdisine bakılır.

5. Üç çekirdekli bir MESI sisteminde x başlangıçta yalnız bellektedir ve 0'dır. Sırayla Ç0 x'i okur, Ç0 x = 5 yazar, Ç1 okur, Ç2 okur, Ç1 x = 6 yazar. Sonda satırın durumları nedir, kaç veri yolu işlemi oluşmuştur ve bellekte hangi değer vardır?

   Cevap

   Ç0 okur: E (BusRd). Ç0 yazar: E → M, sessiz. Ç1 okur: BusRd; Ç0 veriyi verir ve belleğe yazar, ikisi S. Ç2 okur: BusRd, üçü de S. Ç1 yazar: BusUpgr; Ç0 ve Ç2 I, Ç1 M. Son durumlar I, M, I'dır. Dört veri yolu işlemi oluşur. Bellekte 5 vardır; güncel değer 6 yalnız Ç1'dedir.

6. Bağlam değiştirme maliyeti C = 2 µs'dir. Bir kilidin beklenen bekleme süresi 3 µs ise ve 6 µs ise hangisi daha ucuzdur: dönmek mi, uyumak mı?

   Cevap

   Geçişin bedeli 2C = 4 µs'dir. 3 µs < 4 µs olduğu için ilk durumda dönmek ucuzdur. 6 µs > 4 µs olduğu için ikinci durumda uyumak ucuzdur. Bekleme süresi bilinmiyorsa 4 µs dönüp sonra uyumak, en kötü durumda idealin iki katı maliyet verir.

7. 4 CPU'lu bir sistemde dört iş çete çizelgelemeyle çalışacak: A 3, B 2, C 2, D 1 iş parçacığından oluşuyor. Bir tur en az kaç dilim sürer ve CPU kullanımı nedir?

   Cevap

   Toplam 8 iş parçacığı ve dilim başına 4 CPU vardır; en az ⌈8 / 4⌉ = 2 dilim gerekir. Yerleşim: dilim 0'da A (3) ve D (1), dilim 1'de B (2) ve C (2). Her dilim dolu olduğu için kullanım %100'dür.

8. 4 boyutlu hiperküpte e-küp yönlendirmesiyle 0101'den 1010'a giden ileti hangi düğümlerden geçer? Bu yol neden en kısadır?

   Cevap

   0101 ⊕ 1010 = 1111; dört bit de farklıdır. Bitler soldan sağa düzeltilir: 1101 → 1001 → 1011 → 1010. Her atlama tek bir farklı biti düzeltir ve hiçbir atlama farkı artırmaz; bu yüzden atlama sayısı Hamming uzaklığına, yani 4'e eşittir. Bu, 4 boyutlu hiperküpün çapıdır.

9. 1 KiB'lık bir paket 4 anahtar, yani 5 bağlantı üzerinden gidiyor. Bağlantılar 1 Gb/s'dir ve her anahtar başlığı 0,1 µs'de işler. Sakla ve ilet ile kesip geçin gecikmeleri nedir?

   Cevap

   Bir bağlantıdan geçiş 1024 × 8 / 10⁹ s = 8,192 µs'dir. Sakla ve ilette her bağlantıda paketin tamamı beklenir: 5 × 8,192 + 4 × 0,1 = 40,96 + 0,4 = 41,36 µs. Kesip geçte paket bir kez akar ve yalnız başlık gecikmeleri eklenir: 8,192 + 4 × 0,1 ≈ 8,59 µs.

10. 32 bitlik bir misafir işletim sistemi 2 düzeyli sayfa tabloları kullanıyor; ana makinenin EPT'si 4 düzeylidir. TLB ıskasında ve hiçbir girdi önbellekte değilken en kötü durumda kaç bellek erişimi gerekir (son veri erişimi hariç)?

    Cevap

    Misafir tablosunun her düzeyi için girdinin GPA'sı 4 EPT erişimiyle çevrilir ve girdi 1 erişimle okunur: 2 × 5 = 10. Verinin GPA'sı da 4 erişimle çevrilir. Toplam 10 + 4 = 14 = (2 + 1)(4 + 1) − 1.

12.12İleri okuma

• A. S. Tanenbaum ve H. Bos, Modern Operating Systems, Bölüm 8 “Multiple Processor Systems” ve Bölüm 7 “Virtualization and the Cloud”. Kitap, bu nottaki omega ağı, dizin, çete çizelgeleme ve yük dengeleme örneklerinin özgün kaynağıdır.
• R. H. Arpaci-Dusseau ve A. C. Arpaci-Dusseau, Operating Systems: Three Easy Pieces, “Multiprocessor Scheduling”, “Locks” ve “Distributed Systems” bölümleri: önbellek afinitesini, kilit gerçeklemelerini ve RPC'yi kısa ve anlaşılır biçimde anlatır; kitap ostep.org'da ücretsizdir.
• J. L. Hennessy ve D. A. Patterson, Computer Architecture: A Quantitative Approach, Bölüm 5: dinleme ve dizin tabanlı tutarlılık protokollerini, bellek tutarlılık modellerini ve senkronizasyon komutlarını donanım açısından ayrıntılı inceler.
• J. M. Mellor-Crummey ve M. L. Scott, “Algorithms for Scalable Synchronization on Shared-Memory Multiprocessors”, ACM TOCS, 1991: bilet ve MCS kilitlerini ölçümlerle karşılaştıran klasik makaledir.

12.13Kaynaklar

1. A. S. Tanenbaum, H. Bos, Modern Operating Systems, 4. baskı (2014) / 5. baskı (2023), Pearson — Bölüm 8: Multiple Processor Systems; Bölüm 7: Virtualization and the Cloud.
2. A. Silberschatz, P. B. Galvin, G. Gagne, Operating System Concepts, 10. baskı, Wiley, 2018 — Bölüm 5.5 (Multi-Processor Scheduling), 18 (Virtual Machines), 19 (Networks and Distributed Systems).
3. R. H. Arpaci-Dusseau, A. C. Arpaci-Dusseau, Operating Systems: Three Easy Pieces (OSTEP), ostep.org — “Multiprocessor Scheduling”, “Locks”, “Distributed Systems”, “Sun's NFS”, “AFS”, Ek: “Virtual Machine Monitors”.
4. J. L. Hennessy, D. A. Patterson, Computer Architecture: A Quantitative Approach, 6. baskı, Morgan Kaufmann, 2017 — Bölüm 5: Thread-Level Parallelism (tutarlılık, MESI, dizin protokolleri).
5. J. M. Mellor-Crummey, M. L. Scott, “Algorithms for Scalable Synchronization on Shared-Memory Multiprocessors”, ACM TOCS, 1991; A. D. Birrell, B. J. Nelson, “Implementing Remote Procedure Calls”, ACM TOCS, 1984; G. J. Popek, R. P. Goldberg, “Formal Requirements for Virtualizable Third Generation Architectures”, CACM, 1974.
6. Linux çekirdek belgeleri: “CFS/EEVDF Scheduler”, “Scheduler Domains”, “NUMA Memory Policy”, “Core Scheduling”; Intel 64 and IA-32 Architectures Software Developer's Manual, Cilt 3 (VMX, EPT).

İlgili sayfalar: Bölüm 12 sunumu · Çalışma soruları · Çok Çekirdekli Çizelgeleme ve Yük Dengeleme Simülatörü · Terim sözlüğü · © Sercan Külcü. Tüm hakları saklıdır.