Развитие на ос. Основни типове

ОС могат да бъдат класифицирани : -според броя на едновременно изпълняваните програми – еднопрограмни и мултипрограмни, по предназначение – универсални и специализирани.

1.1. Ранни системи- Първите компютри не са имали ОС и потребителите са програмирали на машинен език, като са разполагали с цялата машина, управлявайки я от операторската конзола. Установява се, че е удобно комп. да се снабди с прости програмни средства с помощта, на които да се улесни въвеждането на програмата, а по-късно с развитието на асемблерните езици, да се изпълнява програма за: четене на асемблера, транслация на програмата, запис в/у перфокарти, четене и зареждане на изпълнимата програма в паметта и накрая изпълнение.Режим на работа, при който потребителя получава на разположение комп. с-ма и има пряк достъп до нея, се нарича открит режим (режим на “отворения магазин”).

Следващият етап на автоматизацията на програмирането е появяването на сложни асемблерни езици и езици от високо ниво като FORTRAN. Най-важни са били процедурите по организиране на входа и изхода, т.нар. драйвери за устройства. За припокриване на работата на процесора и входа/изхода се използва буфериране.

Възниква нужда от използване на общи подпрограми в обектна форма.

Появява се преместваемата форма на програмите, като всеки модул се транслира с относителен начален адрес.

Изпълнението на една програма включва изпълнението на много стъпки и всяка от тях се управлява ръчно, като се поставят или свалят перфоленти и магнитни карти. Това е и основният недостатък – твърде малкото използване на процесора (около 7%).

Пакетни системи. При пакетната обработка потребителите се отделят от комп. чрез оператор. Потребителят предоставя задание, състоящо се от програма и данни, предшествано от описание. Описанието включва една или няколко управляващи карти. Така възникват езиците за управление на заданията. Заданията се събират в “пакети”, образувайки т.нар. поток от задания. За да се осигури последователната обработка, с автоматичен преход от едно към друго задание се създават управляващи програми наречени монитори. Мониторите са резидентни. Мониторът чете управляващите карти, определящи каква програма да бъде изпълнена ( компилатор, асемблер), зарежда я и й предава управлението, след нейното изпълнение управлението се връща към монитора.

Мониторът се състои от : интерпретатор на управляващите карти, който използва зареждащата програма за зареждане на системни и приложни програми. Интерпретаторът и зареждащата програма имат нужда от входно-изходни операции и за това мониторът включа драйвери за устройства.

Основните функции на ОС от първо поколение са били автоматизация на операторската дейност. Работата на оператора се е свеждала до стандартни манипулации. Времето на използване на процесора е нараснало до 55%.

Поради бавните периферни устройства, процесорът принудително е стоял. За това започва да се прилага автономна работа на четеца на перфокарти, разработват се устройства които директно извеждат/въвеждат от/на магнитна лента, която е била по бърза от перфокартите. Така загубите се намаляват и използването на процесора достига 90%.

М
ултипрограмни пакетни системи.

Докато “А”, чака изпълнението на входно-изходна операция, “Б” се изпълнява. След завършване на входно-изходната операция управлението отново се предава на А. Мултипрограмирането се базира на разделяне на времето на процесора и разделяне на пространството на паметта. Реализирането на вътрешната опашка на заданията е важен етап към прехода към ОС с мултипрограмиране. Заданията се въвеждат и записват, след това се планира реда на изпълнението им. Избира се задание с най-висок приоритет – въвежда се параметър определящ приоритета. Някои ОС подържат няколко опашки. За програмите които се намират едновременно в паметта при мултипрограмен режим, може предварително да бъде фиксирана памет или да се определя динамично. Повишеното бързодействие изисква и по голяма памет, но тъй като паметта не може да нараства неограничено, създава се виртуална памет.

Преминаването на заданията в ОС с времеделене и в пакетните ОС е аналогично, но при ОС с времеделене те не минават през фазата на входния спулинг. При пакетната обработка информацията се въвежда на порции по инициатива на ОС, при времеделението това се извършва по инициатива на потребителя. Пакетните системи са удобни за дълги задания, докато с времеделене се изисква заданието да е кратко за да бъде малко и времето за отговор. ОС с времеделене работят по-добре, когато отделните задания са близки по характеристики, и използват едни и същи функции на ОС.

придобива концепцията “виртуална машина”. Мрежа от компютри: свързани чрез комуникационни линии. Разделят се по географски признак на глобални мрежи (WAN) и локални мрежи (LAN). При отдалечения достъп възникват проблеми с осведомеността на потребителя относно мястото на изпълнение на програмата му, кога данните се прехвърлят към програмите и обратно, и как се организира общуването между различните ОС.

Въпросът за взаимодействието м/у отделните компютри се решава по два начина. Първия е създаване на мрежова ОС, като се разширява съществуващото немрежово програмно осигуряване със средства за връзка. С тяхна помощ ОС общува с други подобни или специални системи. Всяка машина е със своя собствена ОС и потребители, които знаят за съществуването на други отдалечени машини, и могат да влизат в тях.

При другия подход се изгражда една хомогенна разпределена ОС, която се изпълнява на множество машини. Потребителите не знаят къде се изпълняват програмите им или къде се намират файловете им, това се подържа автоматично от ОС.

Когато пакетно задание постъпи в системата, се създава процес. В някои системи могат да се създадат подпроцеси , които се изпълняват паралелно. Ситемна задача, например спулинг, също е процес.

1. Избран е процес за изпълнение. 2. Изтекъл е квантът, отделен на процеса. 3. Чакане на събитие или завършване на вход/изход. 4. Настъпило е събитие или е завършил вхид/изход. 5. Преъстоновяване. 6. Възобновяване. 7. Включване. 8. Унищожаване.

Като се направи обобщение процесът може да преуста-нови сам себе си или да бъде преустановен от друг процес(родител или ОС) за да се спре изпълнението му. Преустановеният процес може да прдълижи изпълнението си , само ако друг процес го възобнови. При създаването на процес той не се предоставя веднага за изпълнение , а се поставя в преустановено състояние. Преустановяването е вжна операция и в разичните ОС се реализира по разли-чен начин – обикновено е свързано с освобожда-ване на някои ресурси. Целта е да се регулира натоварването или мултипрограмната смес.

Изпълнението на процесите може по-добре да се управлява, ако се въведат още 2 с-я: нов(току що създаден,но не е включен в опашката за изпълнение. ОС създава процеса на два етапа: най-напред тя изпълнява действия , като присъединяване на идентификатор, оформяне на блок за управление и други. Това е състояние нов. После в подходящ момент( напр. Когто ОС не е натроварена), процесът ще бъде вклюен в опашката на готовите процеси.

Подобно процесът напуска системата на два етапа. Процесът е завършил, когато програмата му се е изпелнила, или е прекъснат по някаква причина. В това състовние процесът е на разположение за изпълнение, обече неговият блок за управление и други данни се пазят – различни пмощни програми могат да ги ползват. Когато те не са нуижни ОС изважда процесаот системата.

Управление на преходите между състоянията се извършва чрез извикване на съответни примитиви (основни, примитивни операции).

Когато два или повече процеса се припокриват във времето, те са за паралелни. Биват: 1.Независими – работят с независими променливи и не оказват влияние на други процеси; 2.Взаимодействащи си–имат достъп до общи променливи и си влияят.

Има и решение, при което процесите си сътрудничат- възможна е появата на времезависими грешки. Решението на проблема се решава с определяне на критична секция (област на процеса, в която той работи с критичния ресурс). Необходимо е: 1.Само един процес може да се намира в критичната си секция в даден момент; 2.Процес може да остане в критичната си секция крайно време; 3.Ако процес иска да влезе в критичната си секция, трябва да му се даде такава възможност в крайно време. Решения:

Използва се управляващата конструкция parbegin/parend (cobegin/coend). Ако имаме: S0;parbegin s1;s2;..;sn;parend;S(n+1). Операторите заключени между скобите parbegin/parend, се изпълняват паралелно и S(n+1) се преминава, когато се изпълнят всички оператори в тези скоби.

2.3.1 Програмно решение: операциите за запис и четене на данни в паметта взаимно се изключват във времето- т. нар. блокировка на паметта. Операциите запис и четене представляват критични секции за кратки интервали от време, реализирани на апаратно ниво.

Първи вариант: използва се една променлива. При влизане в критична секция се зацикля и се проверява променливата. Когато единият процес е в критична секция, то другият процес цикли, а след като излезе от критичната секция- другият влиза. Проблем:хаби се процесорно време, тъй като имаме стриктно редуване на процесите, а не паралелно.Освен това ако единият процес е блокиран, а другият излезе от критичната секция, то другият няма да завърши:
Program взаимно_изключване;

Var ред_на:integer;

Procedure процес_1;

Begin

Begin

Критична секция

Ред_на:=2;

……………………

End;

Until false;

Procedure процес_2;

Begin

Repeat

While ред_на<>2 do;

Критична секция

Ред_на:=1;

……………………

End;

End;

Ред_на:=1;

Parbegin процес_1; процес_2; Parend;

End.

Procedure процес_1; procedure proces_2;

Begin begin

Repeat repeat

While red_na_2 do; while red_na_1 do;

Red_na_1:=true; red_na_2:=true;

Kriti4na sekciq kriti4na sekciq

Red_na_1:=false; red_na_2:=false;

Until false; until false;

End; end;

Алгоритъмът осигурява изискването само един процес да е в критична секция. Слабото място е че мажду момента когато един процес се намира в цикъла на очакване и открие, че може да продължи, и момента, когато установява флага си има достатъчно времме и другият процес да провери все още неустановения флаг и да влезе в критичната секция.

Трети вариант: комбиниран. Необходимо е когато един процес изпълнява цикъл на очакване, другият да не може да излезе от своя. За целта всеки процес ще преустановява флага си, преди да влезе в цикъла:

Procedure процес_1; procedure proces_2;

Begin begin

Repeat repeat

Red_na_1:=true; red_na_2:=true;

While red_na_2 do; while red_na_1 do;

Kriti4na sekciq kriti4na sekciq

Red_na_1:=false; red_na_2:=false;

…………………. …………………..

Until false; until false;

End; end;

В това решение се изпълнява изискването за взаимно изключване, но е възможно и двата процеса да вдигнат флаговете, преди да влязат в цикъла, т.е не е изпълнено условието, че нито един процес не трябва да чака безкрайно дълго, за да влезе в критичната си секция- това е пример за т.нар. мъртва хватка. Ако и двата процеса вдигнат флаговете преди да влязат в цикъла, то те ще зациклят и това се нар. мъртва хватка.

Мъртвата хватка ще се избегне ,ако се въведе нулиране на флага(перидично) във false и кратко-временна задръжка на всеки влязъл в цикъл на очакване процес, благодарение на което другият процес излиза от цикъл на очакване, след като е установил флага си.

Procedure процес_1; procedure proces_2;

Begin begin

Repeat repeat

Red_na_1:=true; red_na_2:=true;

While red_na_2 do; while red_na_1 do;

Begin begin

Red_na_1:=false; red_na_2:=flase;

Случайна задръжка Случайна задръжка

Red_na_1:=true; red_na_2:=true;

Kriti4na sekciq kriti4na sekciq

End; end;

Red_na_1:=false; red_na_2:=false;

…………………. …………………..

Until false; until false;

End; end;

По този начин се гарантира взаимното изключванер и се избягва мъртвата хватка, но възниква т.нар, безкрайно отлагане. Относителните скорости на асинхронните парарелни процеси не са известни и затова трябва да се анализират възможните последователности на изпълнение. Например процесите могат да се изпълняват в тандем един след друг в последователност: установяване на флага в true, проверка за начало на цикъла, изпълнение на тялото на цикъла, нулиране на флага, установяване на флага и пак да се повторят операторите на цикъла.

Взаимното изключване е осигурено от условието в while. Ако и двата процеса искат да влязат в критична секция, то rad_na_1=red_na_2=true, a proces_nomer може да бъде равен на 1 или на 2( но не и на двете)

Program vzaimno_izklju4vane;

Var red_na_1, red_na_2: boolean;

Proces_nomer: integer;

Procedure процес_1;

Begin

Repeat

Proces_nomer:=2;

While (red_na_2 and proces_nomer=2) do;

Критична секция

Ред_на_1:=false;

……………………

Until false;

End;

Begin

Red_na_2:=true;

Proces_nomer:=1;

While (red_na_1 and proces_nomer=1) do;

Критична секция

Ред_на_2:=false;

……………………

Until false;

End;

Begin

Parbegin proces_1; proces_2; parend;

End.
Нека например proces_1 да може да бъде спрян пред влизане в критична секция, само ако цикли в while при изпълнено условие. Ако proces_2 не желае да влезе в критичната секция, то red_na_2=false и proces_1 влиза. . Ако proces_2 иска да влезе в критичната секция, то се изпълнява оператор while и кой ще влезе зависи от стойността на porces_nomer. Влезлият процес нека да е proces_n2 при напускане на критичната секция ще направи red_na_2:=falseи ще разредши на prces_1 да влезе. Така, тъй като proces_1 не променя процес_номер (докато изпълнявава while) a процес_2, устано-вявайки red_na_2=true, ще се устонови и proces_nomer=1, proces_1 ще влезе в критичната си секция най-много след едно влизане на proces_2 в критичната му секция. Или, изпълнени са и останалите изисквания за критични секции и няма да възникне мъртва хватка или безкрайно отлагане.
Взаимно изключване на N процеса
Обслужва се процес с най-малък номер, но алгоритъмът не гарантира, че два процесса не получават еднакъв номер. В случай на конфликт, пурви се обслужва процесът с най-малък идентификатор.

Декларация на общите данни:

Nomer : array[0..n-1] of integer;

Тези данни првоначално се инициализират с false, респ. с 0. За ъдобство се дефинира следната нотация

(a,b)<(c,d), ако a

max(a(0), ….., a(n-1)) има число К ,така че К>=а(i) za i=0, …, n-1.

Тогава процес I може да се организира по следния начин:

Repeat

izbor[i]:=true;

izbor[i]:=false;

for j:=0 to n-1 do

begin

while nomer[j] <>0;

and(nomer[j], j) < (nomer[i], I) do;

end;

nomer[i]:=0;

until false;

За да се провери дали алгоритъмът е верен, първо трябва да се покаже, че ако процес i e в критичната си секция и процес (k<>i) вече е избрал неговия номер[k]<>0, тогава (номер[i], i) < (номер[k], k).

Взаимното изключване е осигурено. Нека процес i е в критичната си секция и процес к се опитва да влезе. Когато процес к изпълнява втория цикъл while за j=i той ще открие че номер[i]<>0 и (номер[i], i) < (номер[k], k). Процесът че повтаря цикъла, докато процес i не напусне критичната секция.

За да се докаже, и че другите условия са изпълнени, достатъчно е да се опкаже, че процесите влизат в критичните си секции в ред “първи дошъл – първи обслужен” (FCFS).

Програмното решение е неудобно,затова всички процесори имат машинни команди

-решение с машинна команда TS. (Test & Set – провери и установи). TS(a,b) има 2 логически параметъра. Командата чете стойността на променливата b, записва я в a (a:=b) и установява b:=true. Всеки процес има локална променлива, но  и обща глобална променлива за всички процеси, конкуриращи се за някакъв ресурс обща =false в началото. Процес (пр. proces_1) влиза в критичната си секция в зависимост от състоянието на локалната си променлива. Ако няма друг процес в критична секция, то обща= false. При изпълнение на ТS в цикъла while, локалната= false, обща=true. proces_1 влиза в критичната си секция, а другите са в процес на очакване.При излизане от критичната секция proces_1 указва обща= false, с което се разрешава на друг чакащ процес да влезе в критичната си секция..
Program vzaimno_izklju4vane;

Var обща: boolean;

Proces_nomer: integer;

Procedure процес_1;

Var локална_1:boolean;

Begin

локална_1:=true;

while локална_1 do;

TS(локална_1, обща)

Критична секция

Обща:= false;

……………………

Until false;

End;

Procedure процес_2;

Begin

локална_2:=true;

while локална_2 do;

TS(локална_2, обща)

Критична секция

Обща:= false;

……………………

Until false;

End;

Begin

Parbegin proces_1; proces_2; parend;

End.

Решението осигурява взаимно изключване, но е възможно попадане в “безкрайно отлагане”. Когато процес излезе от критичната си секция, правейки обща:=false, команда ТS на друг процес най-вероятно ще направи обща:=true до времето, когато първият процес успее да мине през цикъла, за да установи обща:=true. За да се избегне тази опасност, може да се въведе допълнителна променлива.

Класическата дефиниция на P и V

1.P(s): while s=0 do skip ; s=s-1;Извиквайки P(s), процесът чака про стойност на семафора s=0, докато друг процес не го освободи чрез V(s). Тогава стойността на S се намалява и процесът продължава.

2. V(s): s=s+1 ;Стойността на семафора s се увеличава и процесът продължава.

В началото има инизиализация s=<цяла константа>.

Тъй като S е обща променлива, операциите P и V над нея трябва да са хеделими, т.е те са критични секции спрямо S. Когато един процес променя стойността на S (или прави проверка), никой друг процес не може в същото време да модифицира същия семафор. Единствено по време на празната операция skip може да се направи модификация.