фиксирано разпределение
В повечето схеми за управление на склад, ние ще приемем, че операционната система отнема известно определена част от основната памет и останалата част от основната памет е на разположение за ползване от множество процеси. Най-простият на разположение схема на управление на паметта - това в райони с фиксирано разпределение граници.
размерите на дяловете
Фиг. 7.2 показва два примера за фиксиран разпределение. Една от възможностите е да се използват части от същия размер. В този случай, всеки процес, чийто размер не надвишава размера на дяла, може да се зарежда по всяко достъпно дял. Ако всички дялове са заети и няма процес в състояние на готовност или работа, операционната система може да се разтоварят процес от всяка точка и изтегляне на другия процес, като по този начин осигурява на процесора.
При използване на стени със същия размер, има два трудности.
Програмата може да бъде твърде голям, за да постави в секцията. В този случай, програмистът трябва да се разработи програма, която използва наслагвания, така че във всеки един момент тя се нуждаеше само една част от основната памет. Когато се изисква модула, които в момента не съществува в основната памет, на самата програма, потребителят трябва да изтеглите този модул в раздела за програмата памет (независимо от това дали модула код или данни).
Използване на основната памет в същото време е изключително неефективна. Всяка програма, независимо от неговия размер, заема участъка в своята цялост. Така че, в нашия пример, по-малко от мегабайт в размер програма ще продължи да заема цялото раздел 8 MB; по този начин остава неизползван блок 7 Mbytes. Този феномен е появата на неизползвана съхранение дължи на факта, че за сваляне блок са по-малки вписванията се нарича вътрешен фрагментация (вътрешна фрагментация).
За да се справи с тези трудности (макар и не напълно) може да бъде чрез използването на секции с различни размери (вж. Фиг. 7.2 б). В този случай, размерът на 16 MB програма може без наслоявания и участъци с малки размери може да намали фрагментацията на вътрешния при изтегляне на малки програми.
алгоритъм разположение
В случай, че секциите са със същия размер, razmeschenieprotsessov памет е тривиална задача. Няма значение кой от свободните участъци на процеса ще бъдат публикувани. Ако всички раздели на процеса се използват, които не са готови за незабавна операция, нито един от тях може да се разтоварват, за да освободите памет за нов процес. Вземането на решение, което трябва да се разтоварят процес - планиране проблем (ние ще обсъдим това в част 4, "Планиране").
Когато разделите имат различни размери, има два възможни подхода към секциите на паметта дестинация процесор. Най-простият начин е да се обработва всеки помещава в най-малкото сечение способен напълно активен настанят protsess.1 В този случай, за всеки участък изисква Scheduler опашка, която съхранява освободен от процеси с паметта за тази секция на памет (вж. Фиг. 7.3 както и). Предимството на този подход е, че процесът може да бъде разпределен между секциите на паметта, така че да се намали вътрешния фрагментация.
Въпреки че този метод изглежда е оптимална от гледна точка на отделния раздел на това, не е оптимално от гледна точка на системата като цяло на. Представете си, че в системата е показано на фиг. 7.2,6, в някакъв момент от време не е процес, в размер от 12 до 16 MB. В резултат на това част от 16 MB ще бъде празна, а може да се използва успешно малки процеси. Така, предпочитан подход е да се използва един опашка за всички процеси (вж. Фиг. 7.3, б). В момента, когато искате да се зареди един процес в основната памет, най-малкият дял е избран за този, който може да побере този процес. Ако всички дялове са заети, трябва да вземе решение за освобождаването на един от тях. Очевидно е, че е необходимо да се даде предимство на процеса на заемане на най-малката дивизия, които могат да се настанят за изтегляне процес. Възможно е да се вземат предвид и други фактори, като например приоритет или състоянието на процес (блокиран или е активна).
Използването на различни по големина участъци върху използването на части от един и същ размер дава по-голяма гъвкавост на този метод. Освен това, схеми с фиксирани дялове са относително прости, минималните изисквания към операционната система; режийните на процесора е малък. Въпреки това, тези схеми имат сериозни недостатъци.
Броят на дялове, определени по време на производството на система, ограничава броя на активните (не суспендират) процеси.
Тъй като размерите на преградни са определени предварително, по време на система за генериране на малки процеси води до неефективно използване на памет. В среда, където изискванията са известни предварително в паметта на всички задачи, използването на описаните схеми може да бъде оправдано, но в повечето случаи на ефективността на тази технология е изключително ниска.
Отстранен разпределение в момента е малко използван. Един пример за успешна операционна система с помощта на тази технология може да служи като ранен операционна система за IBM мейнфрейм OS / MFT (многозадачност с фиксирана сума zadach- Multiprogramming с фиксиран брой задачи).
динамично разпределение
алгоритъм разположение
Тъй като уплътнението на паметта е срещу допълнително заплащане на процесорно време, операционна система разработчик трябва да направи интелигентни решения за това как да се разпределят процеси свързани с паметта (образно казано, как да се включите дупки). Когато към момента на vosnovnom паметта на процеса на зареждане, а има и някои безплатни памет блокове с достатъчно големи размери, операционната система трябва да реши кой свободен блок да го използвате.
Ние можем да разгледа три основни алгоритми - най-подходящ, първи годни, следващата е подходящо. Всички от тях, разбира се, се ограничава до един свободен размер на блока достатъчно голям, за да побере този процес. Методът избира най-добре блок, чийто размер е най-близо до целта; метод първо годни сканира всички свободни блокове от началото и избира първия памет с достатъчен размер, за да се настанят на процеса. Методът следващата подходяща работа по същия начин, както на метода на първа добре, но започва да се консултирате с мястото, където апаратът е бил изолиран за последен път (след достигане на края на паметта, той продължава да работи с неговото начало).
Фиг. 7.5, и показва пример на конфигурация памет след няколко разположения и разтоварване процеси на паметта. Unit последното използване на Мок размер 22 MB, която е създадена в раздел 14 МВ. Фиг. 7,5,6 показва разликата в най-добрата технология, първият и следващия подходящ при извършване на исканото размер разпределение на 16 мегабайт блок. Метод най-добре сканира всички свободни блокове и избира най-сходен размер на блока от 18 МВ, оставяйки фрагмент от 2 мегабайта. Методът първо съвпадение в тази ситуация оставя свободно пространство размер фрагмент използва MB, и подходящ метод е следните - 20 УС.
Кой от тези методи ще бъде най-добрият, това ще зависи от точната последователност на зареждане и разреждане на процесите и техните размери. Въпреки това, можем да говорим за някои общи заключения (вж. [BREN89], [SHOR75], [BAYS77]). Обикновено първото съвпадение алгоритъм не само лесно, но също така и по-бързо и дава по-добри резултати. Следващата съвпадение алгоритъм обикновено дава по-малко по-лоши резултати. Това се дължи на факта, че на следващото съвпадение алгоритъм също има тенденция да се по-често освобождаването на свободни блокове памет в края на паметта. В резултат на това най-големите блокове безплатно памет (които обикновено се намират в края на памет) бързо се разбиват на по-малки фрагменти и затова, когато се използва метода на следващия подходящ уплътнението трябва да се извършват по-често. От друга страна, първата форма алгоритъм е най-често малки носилки, започващи на свободните блокове памет, което води до увеличаване на времето за търсене в следващ подходящ уред. Най-добър метод за добре, въпреки името си, обикновено е най-лошото. Тъй като тя търси блоковете най-близо до желания размер, оставя няколко много малки единици. В резултат на това, въпреки че всеки посветен на отпадъците възможно най-малко количество памет, основната памет, много бързо се задръсти с много малки единици, неизпълнение на всяко искане (така че, когато уплътняването на алгоритъм памет трябва да се извършва много по-често).
подмяна алгоритъм
В многозадачна система, която използва динамично разпределение се случва, когато всички процеси в основната памет са в запечатано състояние, и за по-нататъшно процес памет недостатъчни дори и след уплътняване. За да се избегнат загуби на процесорно време в очакване на освобождаването на активен процес, операционната система може да се разтоварят един от процесите от основната памет, и по този начин да направи място за новия процес, или процес, в състояние на готовност. система задача операционната - да се определи кой процес е да бъдат разтоварени от паметта. Тъй като темата за подмяна алгоритъм ще бъде преразгледана в подробности във връзка с различни виртуални схеми с памет, но ние отложи обсъждането на този въпрос.
близнак система
Фиксирани и динамично разпределение на паметта имат недостатъци. Фиксирана разпределение ограничава броя на активните процеси и неефективно използване на памет при несъответствие между размерите на прегради и процеси. Динамичното разпределение се осъществява по-трудно и включва над уплътняване на паметта. Интересен компромис в това отношение е партньори системата ([KNUT97], [RBTE77]).
близнак системната памет се разпределя на блокове с размер от 2 до <К
21 - минималният размер на разпределените блок памет;
2u - най-голямата сума на блока; Най-общо казано, 2 и представлява размера на цялата памет е на разположение за разпределение.
Първоначално, всички от наличното пространство за разпределение се третира като един размер единица 2u. При искане на размер S, така че 2u-л нищожен get_hole (инт и)
ако: (а = = (U + 1))
<Ошибка>;
ако (<Список 1 пуст>)
get_hole (I + L);
<Разделить дыру на двойники>;
<Поместить двойники в списокi>;
>
<Взять первую дыру из спискаi>;
>
Фиг. 7.6 е пример на блок с първоначалния размер от 1 мегабайт. Първата заявка - 100 KB (128 KB изисква размер на блока за него); За този първоначален блок е разделен на две близнак 512-КВ. Първият от тях е разделена на близнаци 256KB, и на свой ред, първият да се получи разделяне на близнаци също се намалява наполовина. Един от постигнатия размер близнак 128 KB стои искане А. следната заявка изисква 256KB. Този блок е на разположение и разпределени. Процесът продължава с разделянето и сливането се удвоява, ако е необходимо. Имайте предвид, че след освобождението на блок Е слеят близнаци 128 KB в един размер на блока от 256 KB, което, от своя страна, веднага се сля с неговия колега.
Фиг. 7.7 показва представяне на системата удвоява като двоично дърво, непосредствено след освобождаване на блок В. Листата представляват текущата разпределението памет. Ако двама близнаци са листата, а след това най-малко един от тях е зает; в противен случай те трябва да се слеят в по-голяма блок.
изместване
Свързани статии