İş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 =)
Planlama: Çok Düzeyli Geri Bildirim Kuyruğu
Bu derste en ünlü yaklaşımlardan birini geliştirmenin sorunları hakkında konuşacağız.
planlama denir Çok Düzeyli Geri Bildirim Kuyruğu (MLFQ). MLFQ zamanlayıcısı ilk olarak 1962'de Fernando J. Corbató tarafından adı verilen bir sistemde tanımlandı.
Uyumlu Zaman Paylaşım Sistemi (CTSS). Bu çalışmalar (daha sonra yapılan çalışmalar dahil)
Multics) daha sonra Turing Ödülü'ne aday gösterildi. Planlayıcı şuydu:
daha sonra geliştirildi ve halihazırda bulunabilecek görünümü elde etti.
bazı modern sistemler.
MLFQ algoritması 2 temel örtüşen problemi çözmeye çalışır.
Ilk olarak, önceki derste tartıştığımız gibi en çok kuyruğun başından başlama yöntemiyle optimize edilen geri dönüş süresini optimize etmeye çalışır.
kısa görevler. Ancak işletim sistemi belirli bir işlemin ne kadar süre çalışacağını bilmez ve bu
SJF, STCF algoritmalarının çalışması için gerekli bilgi. Ikinci olarak, MLFQ deniyor
sistemi kullanıcılar için duyarlı hale getirin (örneğin, oturanlar ve
Görevin tamamlanmasını bekleyerek ekrana bakın) ve böylece zamanı en aza indirin
cevap. Ne yazık ki, RR gibi algoritmalar yanıt süresini artırıyor, ancak son derece
geri dönüş süresi metriği üzerinde kötü bir etkiye sahiptir. Dolayısıyla sorunumuz: Nasıl tasarım yapılır?
hakkında hiçbir şey bilmeden gereksinimlerimizi karşılayacak bir zamanlayıcı
genel olarak sürecin doğası? Zamanlayıcı görevlerin özelliklerini nasıl öğrenebilir?
hangisini başlatıyor ve böylece daha iyi planlama kararları veriyor?
Sorunun özü: Mükemmel bilgi olmadan görevlerin belirlenmesi nasıl planlanır?
Yanıt süresini aynı anda en aza indiren bir zamanlayıcı nasıl tasarlanır
Etkileşimli görevler için ve aynı zamanda bilmeden geri dönüş süresini en aza indirir
görev yürütme süresi bilgisi?
Not: Önceki olaylardan ders alıyoruz
MLFQ kuyruğu, öğrenen bir sistemin mükemmel bir örneğidir.
Geleceği tahmin etmek için geçmiş olaylar. Benzer yaklaşımlar sıklıkla
işletim sisteminde bulunur (Ve bilgisayar biliminin diğer birçok dalı, dallar dahil)
donanım tahminleri ve önbellekleme algoritmaları). Benzer geziler
Görevler davranışsal aşamalara sahip olduğunda ve dolayısıyla öngörülebilir olduğunda tetiklenir.
Ancak tahminler çok kolay olduğundan bu tekniğe dikkat etmelisiniz.
yanlış olduğu ortaya çıkabilir ve sistemin daha kötü kararlar almasına yol açabilir
hiçbir bilgiden yoksun olurdu.
MLFQ: Temel Kurallar
MLFQ algoritmasının temel kurallarına bakalım. Her ne kadar bu algoritmanın uygulamaları
Birkaç tane var, temel yaklaşımlar benzer.
İnceleyeceğimiz uygulamada MLFQ'nun birkaç özelliği olacak
her biri farklı bir önceliğe sahip olacak ayrı kuyruklar. İstediğin zaman,
yürütmeye hazır bir görev bir kuyruktadır. MLFQ öncelikleri kullanır,
yürütme için hangi görevin çalıştırılacağına karar vermek, ör. daha yüksek olan görev
öncelik (en yüksek önceliğe sahip kuyruktaki görev) ilk önce başlatılacak
sıra.
Elbette belirli bir kuyrukta birden fazla görev olabilir, dolayısıyla
yani aynı önceliğe sahip olacaklar. Bu durumda mekanizma kullanılacaktır.
Bu görevler arasında bir çalıştırma planlamak için RR'yi kullanın.
Böylece MLFQ için iki temel kurala ulaşıyoruz:
- Kural 1: Öncelik(A) > Öncelik(B) ise, A görevi başlatılacaktır (B başlatılmayacaktır)
- Kural 2: Öncelik(A) = Öncelik(B) ise, A&B RR kullanılarak başlatılır
Yukarıdakilere dayanarak, MLFQ planlamasının temel unsurları
önceliklerdir. Her birine sabit bir öncelik vermek yerine
MLFQ, gözlemlenen davranışa bağlı olarak önceliğini değiştirir.
Örneğin, bir görev klavye girişini beklerken sürekli olarak CPU'ya iş atıyorsa,
MLFQ süreç önceliğini yüksek tutacak çünkü bu şekilde
interaktif bir süreç çalışmalıdır. Aksine, görev sürekli ve
CPU'yu uzun süre yoğun bir şekilde kullanır, MLFQ bunu düşürür
bir öncelik. Böylece MLFQ, süreçlerin çalışırkenki davranışlarını inceleyecektir.
ve davranışları kullanın.
Bir noktada kuyrukların nasıl görünebileceğine dair bir örnek çizelim
zaman ve sonra şöyle bir şey elde edersiniz:
Bu şemada 2 süreç A ve B en yüksek öncelik kuyruğundadır. İşlem
C ortada bir yerdedir ve D süreci kuyruğun en sonundadır. Yukarıdakilere göre
MLFQ algoritmasının açıklamalarına göre, zamanlayıcı görevleri yalnızca en yüksek değerde yürütecektir.
RR'ye göre öncelik ve C, D görevleri iş dışı olacaktır.
Doğal olarak statik bir anlık görüntü, MLFQ'nun nasıl çalıştığına dair tam bir resim sunmayacaktır.
Resmin zaman içinde nasıl değiştiğini tam olarak anlamak önemlidir.
Deneme 1: Öncelik nasıl değiştirilir?
Bu noktada MLFQ'nun öncelik düzeyini nasıl değiştireceğine karar vermeniz gerekir.
yaşam döngüsü boyunca ilerledikçe görevler (ve dolayısıyla görevin kuyruktaki konumu). İçin
iş akışını akılda tutmak için bu gereklidir: belirli bir miktar
kısa çalışma sürelerine sahip etkileşimli görevler (ve dolayısıyla sık sık yayınlanma)
CPU) ve tüm çalışma süreleri boyunca CPU'yu kullanan birkaç uzun süreli görev
Bu tür görevler için tepki süresi önemli değildir. Ve bu şekilde ilk denemenizi yapabilirsiniz
MLFQ algoritmasını aşağıdaki kurallarla uygulayın:
- Kural 3: Bir görev sisteme girdiğinde en yüksek sıradaki sıraya yerleştirilir.
- önceliği.
- Kural 4a: Bir görev kendisine ayrılan zaman aralığının tamamını kullanıyorsa, o zaman
- öncelik azalır.
- Kural 4b: Eğer bir Görev CPU'yu zaman penceresi dolmadan serbest bırakırsa, o zaman
- aynı öncelikte kalır.
Örnek 1: Uzun süren tek görev
Bu örnekte görülebileceği gibi, kabul görevi en yüksek değerle ayarlanmıştır.
öncelik. 10 ms'lik bir zaman penceresinden sonra işlemin önceliği düşürülür
planlayıcı. Bir sonraki zaman penceresinden sonra görev nihayet indirilir
kaldığı sistemdeki en düşük öncelik.
Örnek 2: Kısa bir görev teslim edildi
Şimdi MLFQ'nun SJF'ye nasıl yaklaşmaya çalışacağına dair bir örnek görelim. Şöyle
örneğin iki görev: A, sürekli olarak uzun süren bir görevdir
Kısa etkileşimli bir görev olan CPU ve B'yi işgal ediyor. Sanmak
B görevi geldiğinde A'nın zaten bir süredir çalışıyordu.
Bu grafik senaryonun sonuçlarını göstermektedir. Görev A, herhangi bir görev gibi,
CPU kullanımı en alttaydı. Görev B, T=100 zamanında varacak ve
en yüksek öncelikli sıraya yerleştirilir. Çalışma süresi kısa olduğundan
son sıraya ulaşmadan tamamlanacaktır.
Bu örnekten algoritmanın asıl amacı anlaşılmalıdır: çünkü algoritma
Bir görevin uzun mu kısa mı olduğunu biliyorsa, öncelikle görevin
kısadır ve ona en yüksek önceliği verir. Eğer bu gerçekten kısa bir görevse, o zaman
hızlı bir şekilde tamamlanacak, aksi takdirde uzun bir görevse yavaş ilerleyecektir
öncelik düştü ve yakında bunun gerçekten de uzun bir görev olduğunu kanıtlayacak
bir yanıt gerektirir.
Örnek 3: Peki ya G/Ç?
Şimdi bir G/Ç örneğine bakalım. Kural 4b'de belirtildiği gibi,
bir süreç, işlemci zamanının tamamını kullanmadan işlemciyi serbest bırakırsa,
daha sonra aynı öncelik seviyesinde kalır. Bu kuralın amacı oldukça basit
- etkileşimli iş, örneğin bekleme gibi çok sayıda G/Ç işlemi gerçekleştiriyorsa
Kullanıcı tuşuna veya fareye basıldığında böyle bir görev işlemciyi serbest bırakacaktır
ayrılan pencereden önce. Böyle bir görevin önceliğini düşürmek istemeyiz,
ve böylece aynı seviyede kalacaktır.
Bu örnek, algoritmanın bu tür işlemlerle nasıl çalışacağını gösterir - yürütmeden önce yalnızca 1 ms boyunca CPU'ya ihtiyaç duyan etkileşimli B işi
G/Ç işlemi ve tüm zamanını CPU kullanarak geçiren, uzun süredir devam eden İş A.
MLFQ, B sürecini en yüksek öncelikte tutar çünkü devam eder
CPU'yu serbest bırakın. Eğer B etkileşimli bir görev ise algoritma bunu başarmıştır.
Amacınız etkileşimli görevleri hızlı bir şekilde yürütmektir.
Mevcut MLFQ algoritmasıyla ilgili sorunlar
Önceki örneklerde MLFQ'nun temel bir sürümünü oluşturduk. Ve öyle görünüyor ki o
CPU zamanını aralarında adil bir şekilde dağıtarak işini iyi ve dürüst bir şekilde yapıyor.
uzun görevler ve kısa veya yüksek hacimli görevlere izin verme
G/Ç üzerinde hızla çalışın. Ne yazık ki, bu yaklaşım birkaç tane içeriyor
ciddi sorunlar.
Ilk olarakAçlık sorunu: Sistemde çok sayıda etkileşim varsa
görevler, o zaman tüm işlemci zamanını tüketecekler ve dolayısıyla uzun bir süre tek bir zamanı bile tüketmeyecekler
görev yürütülemeyecek (açlıktan ölüyorlar).
Ikinci olarak, akıllı kullanıcılar programlarını yazabilir, böylece
zamanlayıcıyı kandırmak. Aldatma, bir şeyi zorla yapmaktır
Zamanlayıcı sürece daha fazla CPU zamanı verir. Algoritma
yukarıda açıklanan benzer saldırılara karşı oldukça savunmasızdır: zaman penceresi pratik olarak dolmadan
sona erdiğinde, bir G/Ç işlemi gerçekleştirmeniz gerekir (bazıları için hangi dosya olursa olsun)
ve böylece CPU'yu serbest bırakırsınız. Bu tür davranışlar aynı durumda kalmanıza izin verecektir
kuyruğun kendisi ve yine daha büyük bir CPU zamanı yüzdesi elde eder. Yaparsan
bu doğrudur (örneğin, CPU'yu bırakmadan önce pencere süresinin %99'unu yürütün),
böyle bir görev işlemciyi tekeline alabilir.
Son olarak, bir program zamanla davranışını değiştirebilir. Bu görevler
CPU'yu kullanan etkileşimli hale gelebilir. Örneğimizde benzer
görevler, diğerleri gibi zamanlayıcıdan hak ettikleri muameleyi görmeyecek
(başlangıç) etkileşimli görevler.
İzleyicilere soru: Modern dünyada programlayıcıya hangi saldırılar yapılabilir?
2. Deneme: Önceliği artırma
Kuralları değiştirmeye çalışalım ve sorunlardan kaçınabilecek miyiz görelim.
oruç. ilgili olmasını sağlamak için ne yapabiliriz?
CPU görevleri zamanlarını alacaktır (uzun olmasa bile).
Soruna basit bir çözüm olarak periyodik olarak önerebilirsiniz
sistemdeki tüm bu tür görevlerin önceliğini yükseltin. Birçok yolu var
Bunu başarmak için örnek olarak basit bir şeyi uygulamaya çalışalım: tercüme et
tüm görevlere anında en yüksek öncelik verilir, dolayısıyla yeni kural şöyledir:
- Rule5: Belirli bir S süresinden sonra sistemdeki tüm görevleri en üst sıraya taşıyın.
Yeni kuralımız aynı anda iki sorunu çözüyor. Öncelikle süreçler
aç kalmamaları garanti edilir: en yüksek önceliğe sahip görevler bölünecektir
RR algoritmasına göre CPU zamanı ve dolayısıyla tüm işlemler alınacaktır
CPU zamanı. İkinci olarak, daha önce kullanılan bazı işlemler
yalnızca işlemci etkileşimli hale gelir, en yüksek sırada kalır
önceliği en yüksek seviyeye bir defalık artış aldıktan sonra öncelik.
Bir örneğe bakalım. Bu senaryoda, şunu kullanan bir işlemi düşünün:
CPU ve iki etkileşimli, kısa süreç. Şekilde solda, öncelikli terfi olmayan davranışı göstermektedir ve bu nedenle uzun süredir devam eden görev, sisteme iki etkileşimli görev geldikten sonra aç kalmaya başlar. Sağdaki şekilde her 50 ms'de bir öncelik artışı gerçekleştirilmekte ve bu sayede tüm işlemlerin CPU zamanı alması ve periyodik olarak başlatılması garanti edilmektedir. Bu durumda örnek olarak 50 ms alınmıştır; gerçekte bu sayı biraz daha yüksektir.
Açıkçası, S'nin yol açtığı periyodik artış süresinin eklenmesi
mantıklı bir soru: hangi değer ayarlanmalıdır? Onurlandırılanlardan biri
sistem mühendisleri John Ousterhout sistemlerdeki bu tür miktarları voo-doo olarak adlandırdı
sabitti, çünkü bir şekilde doğru sonuç için kara büyüye ihtiyaç duyuyorlardı.
sergiliyor. Ve ne yazık ki S'nin böyle bir kokusu var. Değeri de ayarlarsanız
büyük - uzun görevler açlıktan ölmeye başlayacak. Değeri çok düşük ayarlarsanız,
Etkileşimli görevler uygun CPU süresini almayacaktır.
3. Deneme: Daha İyi Muhasebe
Şimdi çözmemiz gereken başka bir sorun var: nasıl yapılmamalı?
programlayıcımızın kandırılmasına izin mi vereceğiz? Bu olasılıktan sorumlu olan kişiler
Bir işin önceliğini korumasına izin vererek işlemciye yer açan kurallar 4a, 4b
ayrılan süre dolmadan. Bununla nasıl başa çıkılır?
Bu durumda çözüm, her işlemcide CPU zamanının daha iyi hesaplanması olarak düşünülebilir.
MLFQ seviyesi. Programın kullandığı zamanı unutmak yerine
ayrılan süre boyunca işlemci dikkate alınmalı ve kaydedilmelidir. Sonrasında
süreç kendisine ayrılan süreyi tüketti, bir sonraki aşamaya indirilmesi gerekiyor
Öncelik seviyesi. Artık sürecin zamanını nasıl kullanacağı önemli değil - nasıl
sürekli olarak işlemci üzerinde bilgi işlem veya bir dizi çağrı olarak. Böylece,
kural 4 aşağıdaki biçimde yeniden yazılmalıdır:
- Rule4: Bir görev geçerli kuyrukta kendisine ayrılan süreyi tükettikten sonra (CPU'yu kaç kez serbest bıraktığına bakılmaksızın), o görevin önceliği düşürülür (kuyrukta aşağı doğru hareket eder).
Bir örneğe bakalım:
»
Şekil, zamanlayıcıyı kandırmaya çalışırsanız ne olacağını gösterir:
önceki kurallar 4a, 4b ile olsaydı soldaki sonuç elde edilirdi. Mutlu yeni
kural sağdaki sonuçtur. Korumadan önce herhangi bir işlem tamamlanmadan önce G/Ç'yi çağırabilir ve
Böylece davranıştan bağımsız olarak korumayı etkinleştirdikten sonra CPU'ya hakim olun
G/Ç, yine de kuyrukta aşağıya doğru ilerleyecek ve bu nedenle dürüst olmayan bir şekilde işlem yapamayacaktır.
CPU kaynaklarını ele geçirin.
MLFQ'nun ve diğer sorunların iyileştirilmesi
Yukarıdaki iyileştirmelerle birlikte yeni sorunlar da ortaya çıkıyor:
Sorular - böyle bir zamanlayıcı nasıl parametrelendirilir? Onlar. Ne kadar olmalı
kuyruklar mı? Kuyruktaki program penceresinin boyutu ne olmalıdır? Nasıl
Açlıktan kaçınmak için program önceliği sıklıkla artırılmalıdır.
Program davranışındaki değişikliği dikkate alıyor musunuz? Bu soruların basit bir cevabı yok
yanıtlama ve yalnızca yüklerle ve sonraki yapılandırmayla denemeler
Planlayıcı tatmin edici bir dengeye yol açabilir.
Örneğin, çoğu MLFQ uygulaması farklı atamalar yapmanıza izin verir.
farklı kuyruklar için zaman aralıkları. Yüksek öncelikli kuyruklar genellikle
kısa aralıklar öngörülmüştür. Bu kuyruklar etkileşimli görevlerden oluşur.
arasında geçiş oldukça hassastır ve 10 veya daha az sürer
Hanım. Bunun aksine, düşük öncelikli kuyruklar, uzun süre çalışan görevlerden oluşur.
İŞLEMCİ. Ve bu durumda uzun zaman aralıkları çok iyi uyum sağlıyor (100ms).
Bu örnekte, yüksek öncelikli kuyruk 2'de çalışan 20 görev vardır.
ms, 10 ms'lik pencerelere bölünmüştür. Orta kuyrukta (40 ms pencere) ve düşük öncelikte 20 ms
Görevlerin işlerini tamamladığı sıra süresi penceresi 40 ms oldu.
MLFQ'nun Solaris OS uygulaması, zaman paylaşımlı zamanlayıcıların bir sınıfıdır.
Planlayıcı tam olarak olması gerektiği gibi tanımlayan bir dizi tablo sağlayacaktır.
Sürecin önceliği ömrü boyunca değişir, boyutu ne olmalıdır?
tahsis edilen pencere ve görev önceliklerini ne sıklıkta yükseltmeniz gerektiği. Yönetici
sistemler bu tabloyla etkileşime girebilir ve zamanlayıcının davranmasına neden olabilir
farklı. Varsayılan olarak bu tablonun kademeli bir artışla 60 kuyruğu vardır
pencere boyutu 20 ms'den (yüksek öncelik) birkaç yüz ms'ye (düşük öncelik) kadar ve
ayrıca tüm görevlerin saniyede bir kez hızlandırılmasıyla.
Diğer MLFQ planlayıcıları bir tablo veya herhangi bir spesifik
Bu derste açıklanan kuralların aksine, öncelikleri kullanarak hesaplarlar.
matematiksel formüller. Örneğin, FreeBSD zamanlayıcısı aşağıdakiler için bir formül kullanır:
sürecin ne kadar sürdüğüne bağlı olarak bir görevin mevcut önceliğini hesaplayın
CPU'yu kullandı. Ayrıca CPU kullanımı zamanla azalır ve bu nedenle
Dolayısıyla öncelik artışı yukarıda açıklanandan biraz farklı şekilde gerçekleşir. Bu doğru
bozunma algoritmaları denir. FreeBSD, 7.1 sürümünden bu yana ULE zamanlayıcısını kullanıyor.
Son olarak, birçok zamanlayıcının başka özellikleri de vardır. Örneğin, bazıları
zamanlayıcılar işletim sisteminin çalışması için en yüksek seviyeleri ayırır ve dolayısıyla
Bu nedenle hiçbir kullanıcı işlemi en yüksek önceliği alamaz.
sistem. Bazı sistemler yardımcı olmak için tavsiye vermenize izin verir
Planlayıcı öncelikleri doğru bir şekilde belirleyebilir. Örneğin, komutu kullanarak güzel
bir görevin önceliğini artırabilir veya azaltabilir ve böylece artırabilir veya
programın CPU zamanını kullanma şansını azaltır.
MLFQ: Özet
MLFQ adı verilen bir planlama yaklaşımı tanımladık. Onun adı
Çalışma prensibine dahil edilmiştir - birkaç kuyruğu vardır ve geri bildirimi kullanır
Görev önceliğini belirlemek için.
Kuralların son hali şu şekilde olacaktır:
- Rule1: Öncelik(A) > Öncelik(B) ise, A görevi başlatılacak (B başlatılmayacak)
- Rule2: Öncelik(A) = Öncelik(B) ise, A&B RR kullanılarak başlatılır
- Rule3: Bir görev sisteme girdiğinde en yüksek öncelik sırasına yerleştirilir.
- Rule4: Bir görev geçerli kuyrukta kendisine ayrılan süreyi tükettikten sonra (CPU'yu kaç kez serbest bıraktığına bakılmaksızın), o görevin önceliği düşürülür (kuyrukta aşağı doğru hareket eder).
- Rule5: Belirli bir S süresinden sonra sistemdeki tüm görevleri en üst sıraya taşıyın.
MLFQ şu nedenden dolayı ilgi çekicidir: hakkında bilgi gerektirmek yerine
Görevin doğası gereği önceden algoritma, görevin geçmiş davranışını inceler ve ayarlar.
öncelikler buna göre. Böylece, aynı anda iki sandalyeye oturmaya çalışıyor - küçük görevler (SJF, STCF) için üretkenlik elde etmek ve dürüstçe uzun süre koşmak için,
CPU yükleme işleri. Bu nedenle BSD ve türevleri dahil olmak üzere birçok sistem
Solaris, Windows, Mac zamanlayıcı olarak bir çeşit algoritma kullanıyor
Temel olarak MLFQ.
Ek materyaller:
- (bilgi işlem)
Kaynak: habr.com