İşletim Sistemlerine Giriş
Ey Habr! Bence ilginç bir literatür olan OSTEP'in bir dizi makale-çevirisini dikkatinize sunmak istiyorum. Bu materyal, unix benzeri işletim sistemlerinin çalışmasını, yani modern bir işletim sistemini oluşturan süreçler, çeşitli zamanlayıcılar, bellek ve diğer benzer bileşenlerle çalışmayı oldukça derinlemesine tartışıyor. Tüm malzemelerin orijinalini burada görebilirsiniz . Lütfen çevirinin profesyonelce yapılmadığını (oldukça özgürce) unutmayın, ancak umarım genel anlamı korumuşumdur.
Bu konudaki laboratuvar çalışmasına buradan ulaşabilirsiniz:
Diğer parçalar:
kanalıma da bakabilirsin =)
Zamanlayıcıya Giriş
Sorunun özü: Bir zamanlayıcı politikası nasıl geliştirilir?
Temel planlayıcı politika çerçeveleri nasıl tasarlanmalıdır? Temel varsayımlar neler olmalıdır? Hangi metrikler önemlidir? İlk bilgisayar sistemlerinde hangi temel teknikler kullanıldı?
İş Yükü Varsayımları
Olası politikaları tartışmadan önce, topluca adı verilen ve sistemde çalışan süreçler hakkında birkaç basitleştirici açıklama yapalım. iş yoğunluğu. İş yükünü tanımlamak politika oluşturmanın kritik bir parçasıdır ve iş yükü hakkında ne kadar çok şey bilirseniz politikayı o kadar iyi yazabilirsiniz.
Sistemde çalışan işlemler hakkında, bazen şu şekilde de adlandırılan, aşağıdaki varsayımları yapalım: iş fırsatları (görevler). Bu varsayımların hemen hepsi gerçekçi olmayıp düşüncenin gelişimi için gereklidir.
- Her görev aynı süre boyunca çalışır,
- Tüm görevler aynı anda ayarlanır,
- Atanan görev tamamlanıncaya kadar çalışır,
- Tüm görevler yalnızca CPU kullanır,
- Her görevin çalışma süresi bilinmektedir.
Zamanlayıcı Metrikleri
Yükle ilgili bazı varsayımlara ek olarak, farklı planlama politikalarını karşılaştırmak için başka bir araca ihtiyaç vardır: zamanlayıcı ölçümleri. Bir metrik, bir şeyin yalnızca bir ölçüsüdür. Zamanlayıcıları karşılaştırmak için kullanılabilecek bir dizi ölçüm vardır.
Örneğin, adı verilen bir metrik kullanacağız. geri dönüş süresi (geri dönüş süresi). Görev geri dönüş süresi, görevin tamamlanma süresi ile görevin sisteme varış süresi arasındaki fark olarak tanımlanır.
Tdönüş=Ttamamlanma−Varış
Tüm görevlerin aynı anda geldiğini varsaydığımız için Ta=0 ve dolayısıyla Tt=Tc olur. Yukarıdaki varsayımları değiştirdiğimizde bu değer doğal olarak değişecektir.
Başka bir metrik - adalet (adalet, dürüstlük). Verimlilik ve adalet genellikle planlamada birbirine zıt özelliklerdir. Örneğin, zamanlayıcı performansı optimize edebilir, ancak bunu diğer görevlerin yürütülmesini beklemek pahasına adaleti azaltır.
İLK GİREN İLK ÇIKAR (FIFO)
Uygulayabileceğimiz en temel algoritmaya FIFO veya denir. ilk gelen (giren), ilk servis alan (çıkan). Bu algoritmanın birçok avantajı var: Uygulanması çok kolay, tüm varsayımlarımıza uyuyor ve işini oldukça iyi yapıyor.
Basit bir örneğe bakalım. Diyelim ki 3 görev aynı anda ayarlandı. Ancak A görevinin diğerlerinden biraz daha erken geldiğini varsayalım, yani tıpkı B'nin C'ye göre olduğu gibi yürütme listesinde diğerlerinden daha önce görünecektir. Her birinin 10 saniye boyunca yürütüleceğini varsayalım. Bu durumda bu görevleri tamamlamak için ortalama süre ne kadar olacaktır?
- 10+20+30 değerlerini sayıp 3'e bölerek ortalama program yürütme süresini 20 saniyeye eşitliyoruz.
Şimdi varsayımlarımızı değiştirmeye çalışalım. Özellikle varsayım 1 ve bu nedenle artık her görevin yürütülmesinin aynı miktarda zaman aldığını varsaymayacağız. FIFO bu kez nasıl bir performans sergileyecek?
Görünen o ki, farklı görev yürütme süreleri FIFO algoritmasının verimliliği üzerinde son derece olumsuz bir etkiye sahip. A görevinin tamamlanmasının 100 saniye süreceğini, B ve C görevinin ise yine 10 saniye süreceğini varsayalım.
Şekilden de görüleceği üzere sistemin ortalama süresi (100+110+120)/3=110 olacaktır. Bu etki denir konvoy etkisi, bir kaynağın bazı kısa vadeli tüketicileri yoğun bir tüketicinin peşinden sıraya girdiğinde. Bu, önünüzde sepeti dolu bir müşteri olduğunda bakkaldaki kuyruk gibidir. Sorunun en iyi çözümü kasayı değiştirmeye çalışmak veya rahatlayıp derin nefes almaktır.
Önce En Kısa İş
Benzer bir durumu ağır süreçlerle bir şekilde çözmek mümkün mü? Kesinlikle. Başka bir planlama türüne denirÖnce En Kısa İş (SJF). Algoritması da oldukça ilkeldir; adından da anlaşılacağı gibi, en kısa görevler birbiri ardına ilk önce başlatılacaktır.
Bu örnekte, aynı süreçlerin çalıştırılmasının sonucu, ortalama program geri dönüş süresinde bir iyileşme olacak ve şuna eşit olacaktır: 50 yerine 110ki bu neredeyse 2 kat daha iyi.
Dolayısıyla, tüm görevlerin aynı anda geldiği varsayımı altında SJF algoritması en uygun algoritma gibi görünmektedir. Ancak varsayımlarımız hâlâ gerçekçi görünmüyor. Bu sefer varsayım 2'yi değiştiriyoruz ve bu sefer görevlerin hepsinin aynı anda değil, herhangi bir zamanda mevcut olabileceğini hayal ediyoruz. Bu ne gibi sorunlara yol açabilir?
Önce A görevinin (100c) geldiğini ve yürütülmeye başladığını düşünelim. T=10'da her biri 10 saniye sürecek olan B ve C görevleri gelir. Yani ortalama yürütme süresi (100+(110-10)+(120-10))3 = 103'tür. Zamanlayıcı bunu geliştirmek için ne yapabilir?
En Kısa Önce Tamamlanma Süresi (STCF)
Durumu iyileştirmek için programın başlatıldığı ve tamamlanana kadar çalıştırıldığı varsayımı 3'ü atlıyoruz. Ayrıca donanım desteğine de ihtiyacımız olacak ve tahmin edebileceğiniz gibi kullanacağız. kronometre Çalışan bir görevi kesintiye uğratmak ve bağlam değiştirme. Böylece, zamanlayıcı, B, C görevleri geldiğinde bir şeyler yapabilir - A görevini yürütmeyi durdurabilir ve B ve C görevlerini işleme koyabilir ve tamamlandıktan sonra A sürecini yürütmeye devam edebilir. Böyle bir zamanlayıcıya denir. STCFveya Önce Önleyici İş.
Bu planlayıcının sonucu şu sonuç olacaktır: ((120-0)+(20-10)+(30-10))/3=50. Böylece böyle bir zamanlayıcı görevlerimiz için daha da optimal hale gelir.
Metrik Yanıt Süresi
Dolayısıyla görevlerin çalışma süresini biliyorsak ve bu görevlerin yalnızca CPU kullandığını biliyorsak STCF en iyi çözüm olacaktır. Ve ilk zamanlarda bu algoritmalar oldukça iyi çalışıyordu. Ancak kullanıcı artık zamanının çoğunu terminalde geçiriyor ve verimli bir interaktif deneyim bekliyor. Böylece yeni bir metrik doğdu - Tepki Süresi (cevap).
Yanıt süresi şu şekilde hesaplanır:
Tresponse=Tilkçalışma−Varış
Dolayısıyla önceki örnek için yanıt süresi şöyle olacaktır: A=0, B=0, C=10 (abg=3,33).
Ve STCF algoritmasının, 3 görevin aynı anda geldiği bir durumda o kadar da iyi olmadığı ortaya çıktı - küçük görevler tamamen tamamlanana kadar beklemek zorunda kalacak. Yani algoritma, geri dönüş süresi ölçütü açısından iyi, ancak etkileşim ölçütü açısından kötü. Bir terminalde oturup düzenleyiciye karakter yazmaya çalıştığınızı ve başka bir görevin CPU'yu meşgul etmesi nedeniyle 10 saniyeden fazla beklemek zorunda kaldığınızı hayal edin. Pek hoş değil.
Yani başka bir sorunla karşı karşıyayız: Yanıt süresine duyarlı bir zamanlayıcıyı nasıl oluşturabiliriz?
daire şeklinde imzalanan dilekçe
Bu sorunu çözmek için bir algoritma geliştirildi daire şeklinde imzalanan dilekçe (RR). Temel fikir oldukça basit: Görevleri tamamlanana kadar çalıştırmak yerine, görevi belirli bir süre (zaman dilimi olarak adlandırılır) çalıştıracağız ve ardından kuyruktan başka bir göreve geçeceğiz. Algoritma, tüm görevler tamamlanana kadar çalışmasını tekrarlar. Bu durumda programın çalışma süresi, zamanlayıcının işlemi kesintiye uğratacağı sürenin katları olmalıdır. Örneğin, bir zamanlayıcı bir işlemi her x=10ms'de bir kesiyorsa, işlem yürütme penceresinin boyutu 10'un katı ve 10,20 veya x*10 olmalıdır.
Bir örnek verelim: ABC görevleri sisteme aynı anda geliyor ve her biri 5 saniye çalıştırmak istiyor. SJF algoritması, diğerine başlamadan önce her görevi tamamlayacaktır. Buna karşılık, başlatma penceresi = 1s olan RR algoritması görevleri aşağıdaki gibi gerçekleştirecektir (Şekil 4.3):
(Yine SJF (Tepki Süresi Açısından Kötü)
(Round Robin (Tepki Süresi İçin İyi)
RR algoritması için ortalama yanıt süresi (0+1+2)/3=1 iken SJF için (0+5+10)/3=5'tir.
Zaman penceresinin RR için çok önemli bir parametre olduğunu varsaymak mantıklıdır; pencere ne kadar küçükse yanıt süresi de o kadar yüksek olur. Ancak bağlam değiştirme süresi de genel performansta rol oynayacağından bunu çok küçük yapmamalısınız. Bu nedenle, yürütme penceresi süresinin seçimi işletim sistemi mimarı tarafından belirlenir ve içinde yürütülmesi planlanan görevlere bağlıdır. Bağlamın değiştirilmesi, zaman kaybına neden olan tek hizmet işlemi değildir; çalışan program, örneğin çeşitli önbellekler gibi birçok başka şey üzerinde çalışır ve her geçişte, bu ortamın kaydedilmesi ve geri yüklenmesi gerekir; bu da çok fazla zaman alabilir. zaman.
Yalnızca yanıt süresi ölçümünden bahsediyorsak, RR harika bir planlayıcıdır. Peki görevin geri dönüş süresi metriği bu algoritmayla nasıl davranacak? Yukarıdaki örneği düşünün, A, B, C'nin çalışma süresi = 5s ve aynı anda varıyor. A görevi 13, B 14, C 15 saniyede bitecek ve ortalama geri dönüş süresi 14 saniye olacaktır. Dolayısıyla RR, ciro ölçümü için en kötü algoritmadır.
Daha genel bir ifadeyle, herhangi bir RR tipi algoritma adildir; CPU zamanını tüm işlemler arasında eşit olarak böler. Dolayısıyla bu metrikler sürekli birbiriyle çatışıyor.
Bu nedenle, elimizde birkaç zıt algoritma var ve aynı zamanda hala birkaç varsayımımız var: görev süresinin bilindiği ve görevin yalnızca CPU'yu kullandığı.
G/Ç ile karıştırma
Öncelikle prosesin sadece CPU'yu kullandığı varsayımı 4'ü kaldıralım; doğal olarak durum böyle değil ve prosesler diğer ekipmanlara erişebilir.
Herhangi bir süreç bir G/Ç işlemi talep ettiği anda süreç bloke durumuna girer ve G/Ç'nin tamamlanmasını bekler. G/Ç sabit sürücüye gönderilirse, bu tür bir işlem birkaç ms veya daha uzun sürebilir ve işlemci şu anda boşta olacaktır. Bu süre zarfında zamanlayıcı işlemciyi başka herhangi bir işlemle meşgul edebilir. Zamanlayıcının vermesi gereken bir sonraki karar, sürecin G/Ç'sini ne zaman tamamlayacağıdır. Bu olduğunda, bir kesinti meydana gelecek ve işletim sistemi, G/Ç'yi çağıran işlemi hazır durumuna geçirecektir.
Çeşitli görevlerin bir örneğine bakalım. Her biri 50ms CPU zamanı gerektirir. Ancak ilki her 10 ms'de bir G/Ç'ye erişecektir (bu da her 10 ms'de bir yürütülecektir). Ve B süreci, G/Ç'siz 50 ms'lik bir işlemci kullanıyor.
Bu örnekte STCF zamanlayıcısını kullanacağız. A gibi bir süreç başlatılırsa zamanlayıcı nasıl davranacak? Şunu yapacak: önce A sürecini, sonra da B sürecini tamamen çözecek.
Bu sorunu çözmeye yönelik geleneksel yaklaşım, A sürecinin her 10 ms'lik alt görevini ayrı bir görev olarak ele almaktır. Böylece STJF algoritmasıyla başlarken 50 ms'lik bir görev ile 10 ms'lik bir görev arasındaki seçim açıktır. Daha sonra A alt görevi tamamlandığında B süreci ve G/Ç başlatılacaktır. G/Ç tamamlandıktan sonra, B işlemi yerine 10 ms'lik A işlemini yeniden başlatmak geleneksel olacaktır. Bu şekilde, birincisi beklerken CPU'nun başka bir işlem tarafından kullanıldığı örtüşmeyi uygulamak mümkündür. G/Ç. Sonuç olarak sistem daha iyi kullanılır; etkileşimli işlemler G/Ç'yi beklerken, işlemci üzerinde diğer işlemler yürütülebilir.
Oracle artık yok
Şimdi görevin çalışma süresinin bilindiği varsayımından kurtulmaya çalışalım. Bu genellikle listenin tamamındaki en kötü ve en gerçekçi olmayan varsayımdır. Aslında, ortalama sıradan işletim sisteminde, işletim sisteminin kendisi genellikle görevlerin yürütme süresi hakkında çok az şey bilir; o halde görevin yürütülmesinin ne kadar süreceğini bilmeden nasıl bir zamanlayıcı oluşturabilirsiniz? Belki bu sorunu çözmek için bazı RR ilkelerini kullanabiliriz?
sonuç
Görev zamanlamanın temel fikirlerine baktık ve 2 zamanlayıcı ailesine baktık. Birincisi en kısa görevi ilk önce başlatarak geri dönüş süresini artırırken, ikincisi tüm görevler arasında eşit olarak bölünerek yanıt süresini artırır. Diğer ailenin algoritmaları iyiyken her iki algoritma da kötüdür. Ayrıca CPU ve G/Ç'nin paralel kullanımının performansı nasıl artırabileceğine de baktık ancak işletim sistemi öngörüsüyle ilgili sorunu çözemedik. Bir sonraki derste yakın geçmişe bakan ve geleceği tahmin etmeye çalışan bir planlamacıya bakacağız. Ve buna çok seviyeli geri bildirim kuyruğu denir.
Kaynak: habr.com