Развитие на ос. Основни типове
Изтегляне 2.7 Mb.
|
- Навигация на страницата:
- Променливи раздели
- Преместваеми раздели
- Използване на няколко базови регистри
- Управление на паметта
- Друго виждане за страничната организация
Фиксирани разделиПри този подход паметта се разбива на раздели с фиксирани граници, което се осъществява при генерацията на ОС. Така нивото на мултипрограмиране се определя от броя на разделите. В някои ОС се дава възможност на оператора да променя броя и размера на разделите. Този метод е подходящ когато се знаят размерите е честотата на изпълнение на заданията. Ф-иите по управление на паметта се реализират леко, като определянето кому ще се разпредели памет в голяма степен се извършва от програмата за планиране на високо ниво. При влизане в системата заданията се нареждат във вътрешната опашка и планиращата програма, въз основа на изискванията за памет и свободните раздели определя кои задания да получат памет. След завършване на заданието се освобождава раздел, който може да бъде зареден от планиращата програма с друго задание. Недостатък на метода е получаване на неизползвани части от паметта т. Нар. фрагментация. Тя е вътрешна, ако не се използва част от разпределения раздел и ако има свободни раздели – външна. Разпределението може да се допълни и с размяна. Обикновено заданията се въвеждат отново в едни и същи раздели. Това ограничение се диктува от метода за преместване и от политиката за разпределение на разделите. За да се използва процесорното време ефективно, необходимо е времето за изпълнение на всяко задание да бъде относително дълго спрямо времето за размяна. За да се намали това време трябва да се следи колко памет действително заема потребителската програма, вместо колко би използвала. Така ще може да се приложи размяна не върху целия раздел, а само върху актуално използваната част. Друго ограничение е свързано с входно-изходните операции. Прехвърлянето на данни между ОС и процеса става само тогава, когато той е в паметта.
В някои случаи на процесите се дава възможност да управляват донякъде оперативната памет чрез макрокоманди, но само в рамките на собствените им, предварително отделени раздели. Въпреки, че използването на паметта при променливи размери е по-добро, тя не решава напълно фрагментацията, тъй като между разделите остават неизползвани области.
Възможен е и друг подход – всяка дума на паметта се разширява с признак, указващ типа на информация в думата. Проблемът възниква при преместване на раздели, защото трябва да бъдат коригирани не само адресите на премествания раздел, но и адреси в регистрите на процесора или изпратени към подпрограми. Освен това възниква въпросът кога да се прави сгъстяване – то може да се извършва или при всяко освобождаване, или в момента, когато няма раздел с необходимата дължина, но сборът на паметта е достатъчен за ново задание. При втория подход има две алтернативи – или да се направи пълно сгъстяване, или то да се приложи само частично, колкото да се освободи необходимата част. Използване на няколко базови регистриДруг метод да се намали фрагментацията при използването на раздели с променлива дължина е да се раздели необходимата памет за всяко задание на няколко части. За да се постигне това са необходими няколко базови регистри и механизъм за преадресация. Паметта може да се дели по различни начини: Един от тях е тя да се раздели на две независими части. В едната част се поместват постоянните стойности, а в другата променливите. Друг начин е да се раздели програмата на две части – код и данни. Процесорът знае дали чете команда или данни. Регистрите за командите автоматично определят, че кодът е само четене(програмите могат да се използват от различни потребители). Управление на паметта Управляващата програма при работа с променливи размери се базира на информация за състоянието на паметта – кои блокове са разпределени и кои са свободни. Използване на свързани списъци. За управление на паметта може да се използва свързан списък на разпределените и свободните блокове на паметта. Всеки блок съдържа елемент на списъка, включващ вид на блока, стартов адрес, дължина и указател към следващия елемент. За разпределение на свободната памет при постъпване на заявка се прилагат различни стратегии. Най-разпространени са : избор на първи подходящ блок и избор на най-подходящ блок. Стратегията за избор на първи подходящ блок е по-бърза, но големите блокове се раздробяват. Стратегията за избор на най-подходящ блок изисква да се преглежда целия списък и нейното ползване води до създаване на много блокове с малки размери. Предимството и е, че оставя свободни големи блокове. Вариант на първи подходящ блок се нарича следващ подходящ. Работи като първи подходящ, но се помни мястото, където е намерен последния подходящ блок и при следващото търсене се продължава оттам. Бързодействието на алгоритмите маже да се повиши чрез използване на отделни списъци на заетите от процесите блокове и на свободните блокове. Отделните списъци обаче пораждат друг проблем-освобождаването на блокове и прехвърлянето им в списъка на дупките поражда усложнение и намаляване на бързодийствието. За пълнота трябва трябва да се споменат още два алгоритъма. Среща се и стратегията за избор на най-малко подходящ блок. Обосновката е, че остават по-големи дупки памет, които могат да се окажат по-полезни в сравнение с малките дупки при “най-подходящ”. Бързо подходящ – поддържащ отделните списъци за най-използваните размери на свободните блокове. Използване на битова карта Паметта се разделя на единици за разпределение и на всяка единица отговаря бит от битовата карта, показващ дали единицата свободна или заето. При този метод просто се освобождава заета памет, но се усложнява търсенето на свободна памет със зададен размер, защото трябва да се намерят в битовата карта съответния брой последователни нули. Затова методът не се използва често. Използване на системата на “близнаците”. Този подход ускорява сливането на свободните блокове, като се използва фактът, че адресите са двоични. Памет се предоставя на блокове с дължина представляваща степен на 2. При освобождаването на блок най-напред се проверява дали е свободен неговият “близнак”. Ако е така те се обединяват в един, който може да се обедини с “близнака” и т.н. Разпределение на дисково пространство при размяна
Друга възможност за борба с фрагментацията е да се използва странична организация. Оперативната памет се разделя на еднакво дълги блокове – странични кадри. Адресното пространство на заданието също се подразделя на еднакви части с дължина равна на кадрите. Деленето на страници се осъществява при транслацията на програмите, като указаните в командите адреси се състоят от 2 компоненти – номер на страница (Р) и отместване (D) спрямо началото на страницата.
На всяко задание се поставя таблица на страницата, чрез които се установява съответствие между разпределените на заданието блокове памет и записаните в тях страници. Всеки елемент на таблицата съдържа указател към началото на блок – предполага се че Р служи като индекс на таблицата. Абсолютните адреси на паметта се определят динамично по време на изпълнението по следният начин. Към съдържанието на PTR се прибавя номерът на страницата и от таблицата се чете указателят към съответният кадър. Когато таблицата е в паметта, бързодействието се намалява на половина. Времето може да се намали с използването на апаратни средства за реализация на таблицата, например бързодействащ регистър или буферна памет. Стандартното решение е използването на асоциативна памет. Всеки регистър съдържа: ключ и стойност. При обръщане към паметта се извършва сравнение с всички ключове едновременно и при съвпадение се извежда номер на кадър. Управление на паметтаВ разгледаните схеми за странична организация всички страници на дадено задание са поместени в оперативната памет преди началото на изпълнението му. Това предполага статично разпределение, което се извършва лесно. Управляващата програма използва две системни таблици за разпределение – таблица на кадрите и на заданията. Когато трябва да се разпредели памет, най-напред се проверява в таблиците на кадрите дали има достатъчен брой свободни кадри. Както и преди управлението на паметта влияе върху управлението на заданието. Когато пристигне задание, планиращата на високо ниво програма определя дължината му в страници и се обръща към програмата за управление на паметта. Друго предимство на страничната организация е възможността за съвместно използване на програми. Страничната организация решава проблема с фрагментацията, макар и не напълно така възниква вътрешна фрагментация – кадърът, който е записан в последната страница на всяко задание, се използва средно на половина, тъй като дължината на разпределената памет трябва да се закръгля на цял брой кадри.
Статичното разпределение предполага припокриване, определяно от потребителя. Страничната организация е подходяща за организиране на размяна, тъй като не е нужно изведените на диска програми да се записват на същото място в паметта – достатъчно е само да се промени таблицата на страниците. Друго виждане за страничната организацияСтраничната организация може да се използва за разширение на адресното пространство. Този подход масово е използван при мини компютрите за увеличение на обема на паметта, без да се променя системата команди. Компютрите от 60-те години използват най-често 15 или 16 битови адреси. По късно става възможно да се разшири адресното пространство на 17 или 18 бита, но това означава, че трябва или да се промени системата команди или да се увеличи думата. Оттук следва, че са неизползваеми всички съществуващи програми и документация. 7.2.4. Разпределение на сегменти При изложените методи адресното пространство на заданието се разглежда, като непрекъснато линейно, отговарящо на представата за физическа памет. Такъв поглед на нещата съвсем не е задължителен. Сегментирането предоставя друго виждане – при него адресното пространство на всяко задание се разкъсва на няколко сегмента с различна дължина, които обикновено съответстват съдържателно на отделните части на заданието. Сегментът е определен от потребителя обект, който може да се разглежда като логическа независима единица, процедура, блок или масив от данни. Всеки сегмент е свързан с име и размер, а възможно е и други атрибути, като правила на достъп, име на притежател и др… За простота на реализация сегментите се означават с номера вместо с имена. Обикновено потребителската програма се транслира, като компилаторът автоматично създава сегментите, отразявайки структурата на първичната програма. Адресацията в сегментираната програма е двуразмерна – номер на сегмент и отместване. С всяко задание се свързва таблица на сегментите. При изпълнението на програмата абсолютните адреси се определят динамично, като с помощта на таблицата номера на сегмента се превръща в базов адрес на сегмента. За това в много системи описаните действия по изчисление на адреса, както и проверката на дължината на сегмента се извършват апаратно. Едно от предимствата на сегментирането е възможността за точно управление на защитата. Също така сегментирането улеснява организацията и достъпа.до реентрантните програми. Сегментите се използват съвместно, когато техните начални адреси в паметта записани в таблиците на различни процеси. Така всяка информация може да се дели, ако се оформи като сегмент. Въпреки че описаното – съвместно използване на сегменти изглежда просто, все пак възникват проблеми - например, ако в кодов сегмент има преход, където адресът на прехода се състои от номер на сегмент и отместване, тогава всички процеси трябва да използват един и същи номер за делимия сегмент, което води до трудности или програмата да е позиционно-независимия. Сегментирането облекчава свързването на обектните модули. Те могат да бъдат програмирани като сегменти, с което съществено се опростява обработката на външните обръщения, тъй като свързващата програма не трябва да работи с абсолютни адреси. Описаната организация има и някои недостатъци поради променливия характер на сегментите и поради сложността на дисциплината за тяхното разместване в паметта. Програмата за планиране на заданията трябва да намери памет за всички сегменти на потребителската програма. Разпределението на паметта се решава подобно на схемата с променливи раздели, например първи подходящ или най-подходящ. 7.2.5. Разпределение на сегменти и страници В някои системи двата подхода се обединяват за да се използват предимствата им. Сегментирането на адресното пространство позволява лесно да се решават външните обръщания и използването на реентрантните програми. Страничната организация позволява, като се използва не сложната стратегия за сегментация, да се опрости разпределението на паметта и да се изключи външната фрагментация. 9.1.Организация на подсистема за вход и изход. Повечето комп. имат машинни коман-ди за пряко управление на входа и из-хода. 
Процесорът изпраща сигнали и данни които се интерпретират от контролер, който управлява у-вото. За да се син-хронизира работа на процесора с по-бавните у-ва се използва механизма на буферирането. За да се изпълни вх./изх. операция, процесорът записва команда на съответния контролер. Ко-гато командата се приеме, процесорът може да продължи работата си пара-лелно с вх./изх. операция. След като бъде изпълнена командата, контроле-рът изпраща, прекъсване към процесо-ра. Друг начин за съгласуване работа-та на процесора, е вместо прекъсване, периодично да се проверяват флагове-те на контролера. Предимството е, че обработка се извършва само когато процесорът е готов, но също така се губи и време за проверка когато няма заявки. Много контролери поддържат директен достъп до паметта (DMA). Използва се за освобождаване на про-цесора от работа по прехвърляне на данни м/у контролера и паметта. Про-цесора трябва да изпрати допълнител-на информация адрес от паметта, къ-дето да се разположи блока от данни. При прехвърлянето на данни, контро-лерът заема системните шини, като изпраща сигнал към процесора, и пое-ма управлението им. Контролерът мо-же да заема шините до предаване на целия блок или след всеки предаден байт да връща управлението на шини-те на процесора и да ги заявява пак за следващия байт. В големите системи се използват канали за данни (входно изходни процесори), които се включ-ват м/у процесора и контролерите. Ка-налът е програмируем процесор, из-пълняващ канална програма. Някой канали могат да изпълняват едно-ко-мандни програми, а други да изпълня-ват последователност от команди. Тъй като процесор и канал се конкурират за достъп до паметта по-голям прио-ритет има канала. Когато канала може да обслужва само едно у-во., той се нарича селекторен и към него се включват бързите у-ва. Бавните се свързват към мултиплексорен канал, който може едновременно да обслуж-ва повече у-ва. Блок-мултиплексор-ният канал съчетава принципите на горните два – изпълнява едновремен-но няколко канални програми. Ето и типична дървоидна организация на входа/изхода, прилагана в големите комп. системи. 
За да се повиши гъвкавостта на из-ползване на каналите и блоковете за управление, както и да се повиши си-гурността, могат да се въведат алтер-нативни пътища към у-во, т.е. един контролер да се свърже с няколко ка-нала, и едно у-во към няколко контро-лера. 9.2. Принципи за управление на устройствата. Използват се три основни начина за управление и разпределение: -моно-полно използване (прикрепено у-во.), съвместно използване (делимо у-во) и виртуално използване на у-во. (вир-туално у-во). Разделението на у-ва мо-же да бъде статично (постоянно по време на изпълнение на процеса) или динамично (при всяка заявка). Обик-новено се използва динамично. Функ-циите на входно-изходния супервай-зор могат да се разпределят на три части: 1.Планиране на заявките за вход/изход. 2.Регистриране на инфор-мация за състоянието на входно/из-ходната апаратура. 3.Управление на работата на у-вата (драйвери). Достъп до у-вата може да има само, когато те са свободни. Когато заявките са пове-че от достъпните пътища, необходимо е планиране на заявките, като се стре-мим да постигнем максимална ско-рост за предаване на данни. За да се определи дали у-во е достъпно, трябва да се провери съществува ли път към него. Когато има алтернативни пъти-ща, трябва да се проверят всички и да се избере свободен. Това се изпълнява от входно-изходен контролер. Всеки тип у-во има драйвер, който извършва динамично планиране на достъпа, уп-равлява работата на у-вото и обработ-ва прекъсванията (на 2-ро ниво) по вход/изход. Преди да се състави ка-нална програма се прави проверка за правилността на заявката. След стар-тиране на каналната програма, драйве-рът се самоблокира до завършване на операцията. 9.3. Устройства и процеси. Процес може да се използва за моде-лиране на у-во, а у-во за моделиране на процес. Вместо у-вото да се смята за процес, по удобно е в процеса да се включат програмите за управлението му. Такава организация на супервай-зора дава възможност за независимост на у-вата и замяна на едно у-во с дру-го при минимални изменения на ОС. Друго важно свойство на третирането на у-ва, като процес е създаването на виртуални у-ва, разработката на прог-рамно осигуряване за у-ва, които още не са готови. Важно приложение на виртуалните у-ва е спулингът. 9.4.Планиране на работата с диска. Данните в диска се разполагат в кон-центрични пътеки (писти). Пистите една над друга образуват цилиндър. Данните в цилиндрите се записват на блокове с постоянна или променлива дължина, наречени сектори. Секторът е най-малката физическа еденица, с която се работи при входно-изходните операции. За да се прехвърли блок от данни, той трябва да се адресира, като се зададе номер на пистата (цилиндъ-ра), номер на глава (повърхност) и номер на сектор. За ОС, обаче, дис-кът е едномерен масив от блокове от данни(всели блок е един сектор). Бър-зодействието на работата с диска се определя от три фактора:времето за търсене на цилиндър (свързано с пред-вижването на главата до зададена пис-та); вревмето за очакване (докато на-чалото на търсения сектор на застане под главата);времето за прехвърляне на блока от данни между диска и па-метта. Драйвера, ако има номера на цилиндъра иномер на сектор и зна-ейки текущото положение на диска, може да се изчисли най-оптималният ход за действие (ред на изпълнение на заявките) с оглед на минимално задър-жане. Този процес се нарича планира-не на работата с диска, но той е много скъп за това се прилага оптимизация само по намера на цилиндъра или са-мо по номера на сектора, при което също се получават добри резултати. Критерии за оценка на бързодейст-вието:1.Пропускателна възможност (броя обслужени заявки за еденица време). 2.Средно време за отговор. 3.Дисперсия на времето за отговор (дисперсията е мярка за отклонението на отделните елементи от средната стойност за тоьи елемент). 9.4.1.Оптимизация на търсенето на цилиндър. FCTS. Най-простия алгоритъм е FCTS - първата постъпка се обслужва първа. Този метод е справедлив, защото се обслужват по реда на пристигане. Тук се игнорират позиционните връзки между заявките и нищо не се оптими-зира. Прилага се при малко натоварва-не на дисковото пространство, осигу-рява добра дисперсия, но това не носи полза на чакащата на опашката заявка, въпреки, че главата може да е преми-нала многократно през желания ци-линдрия. SSTF. При планирането на принципа SSTF (Shortest-Seek-Time-First) първа се обслужва заявката с най - кратко търсене от текущото положе-ние на главата.SSTF рязко дискрими-нира заявките, възможно е да се пре-дизвика отлагане на заявка. Обръще-нията към диска изявяват тннденция към концентрация (пристигат после-дователен набор от заявки разполо-жени близо една до друга), което мо-же да предизвика отлагане на обслуж-ването в най-външните и най-вътреш-ни писти. SSTF осигурява по-добра пропускателна способност от FCTS и по-добро средно време за отговор при умерени натоварвания, но има увели-чена дисперсия във връзка с дискри-минирането на крайните писти. При-емлива при пакетни системи, но не и при интерактивни с времеделене. SСAN. За да отстрани дискримина-цията на на крайните писти, подобно на SSTF се избира заявка с минимал-но време на търсене, но в дадено нап-равление (навътре или навън). Главата се движи от единият край към другия, като обслужва всички заявки по пътя си като срешне необходимите писти. Главата на сменя посоката на движе-ние докато на стигне края на диска. SCAN повишава пропускателната спо-собност и намалява средното време за отговор, но за разлика от SSTF снижа-ва дискриминацията на на крайните цилиндри и осигурява по-малка дисперсия. Разновидности на SCAN понякога са наричани LOOK са: 1. N-STEP-SCAN –Представлява модифи-кация на горния алгоритъм. Главите се движат в двете посоки, но обслуж-ват само заявките пристигнали преди началото на движението. Заявките пристигнали по време на движението се записват и подреждат за да бъдат оптимално обслужени. Осигурява добри показатели на пропускателна възможност и средно време на отго-вор, както и по-малка дисперсия в сравнение с SSTF и SCAN. Изключва се възможността за безкрайно отла-гане, което възниква при пристигане на поток от заявки към текущия ци-линдър, респективно близък. 2.C-SCAN. Следващата модификация на SCAN е цикличното сканиране C-SСАN, което отстранява дискримина-цията на крайните цилиндри. Както и при SCAN, главите се движат от вън-шните цилиндри към вътрешните, об-служвайки заявките по най-краткото време за търсене. Когато правия ход завърши, те скокообразно се връщат към външния цилиндър( без да об-служват заявките по пътя си ) и започ-ват да ги обслужват при правия ход на главата към вътрешния цилиндър. Тук се приема като в кръг, че пос-ледния цилиндър е съседен на първия. Тази стратегия избягва дискриминира-нето на крайните цилиндри. 9.4.2.Оптимизиране по време на очакване на сектор. Необходимостта от подобна оптими-зация възниква при големи натовар-вания. Освен това, с развитието на технологиите за производство на дисковете се намалява времето за тър-сене на цилиндър (което се приближа-ва до времеот на на очакване), което показва важността на тази оптимиза-ция. Оптимизация по време на очак-ване от дълго време се прилага при устройства с фиксирани глави, където няма движение на главите и избор на цилиндър. SLTF(Shortest-Latency -Time-First) съгласно, която първа е заявката с най-малко време за очаква-не на сектор. Когато главите се прид-вижват на определен цилиндър, оказва се че съществуват много заявки към различните писти на този цилиндър. Анализират се всички заявки и първа се обслужва заявката с минимално очакване на сектор.
Организацията на входно-изходната апаратура също оказва влияние върху бързодействието. Могат да се появят тесни места в някои от компонентите и канал, контролер, дискова памет. Те-зи места се откриват чрез програмни и апаратни монитори( за каналите и контролерите) и се отстраняват чрез реконфигурация на апаратните сред-ства или чрез програмни средства. За да се намали вероятността за прето-варване на каналите, в някои системи се включват средства за следене на положението на въртене на дисковете (RPS-Rotational Position Sensing). Ко-гато постъпва заявка за достъп до блок от данни, RPS освобождава кана-ла за изпълнение на други операции до момента на пристигане на сектора под главата( при някои операции, като движение на главите, каналът не е не-обходим – той трябва например при четене и запис). Този механизъм поз-волява да се обработват няколко заяв-ки, като се повишава коефициента на използване на апаратурата. Важна черта на контролерите е възможността за търсене на цилиндър с припокрива-не- едновременно търсене в две и по-вече устройства. Много контролери могат да записват или да четат от едно устройство и всъщото време да извър-шват търсене с припокриване. Това е допълнителна възможност за намаля-ване на средното време на достъп (из-ползвана особенно в малките маши-ни). Ако някои от устройствата без-действат, тъй като в момента се извър-шва трансфер на данни с друго, въз-можно е да се започне обслужването на следващите заявки към тях, като се издават команди за търсене на цилин-дър. Някои контролери отиват по- на-татък и организират запис в собствена памет (прозрачно за драйвера). Така трансфера между контролера и памет да се извърши от DMA ( или канал). 9.4.4. Избор на алгоритъм на планиране. Съществуването на голям брой плани-ращи алгоритми поставя въпроса за избор на подходящ алгоритъм. Нато-варването на диска и разпределението на заявките зависят от степента на мултипрограмиране. Може да се ока-же нецелесъобразно въвеждане на планиране в пакетни ОС с ниска степен на мултипрограмиране, където в опашката рядко има повече от 2,3 заявки. Разпределението на заявките силно се влияе от методите за разпре-деление на дисковото пространство. При непрекъснато разпр4еделение на дисковото пространство файлът се разполага в един цилиндър, респек-тивно в съседни цилиндри. При ра-бота с такъв файл (особенно ако е пос-ледователен) движевнието на главите ще бъде минимално. Напротив, при използването на индексен блок или на свързан списък за разпределение, дви-жението ще бъде голямо. Логическата организация на файловете от данни има голямо влияние върху броя на заяявките. Файловете със сложна ор-ганизация ( като индексно-последова-телните) могат да предизвикат голям брой заявки с дълги времена на тър-сене. Затова и местоположението на на справочниците и индексните бло-кове е важно. Те често се използват и тяхното разположение в средата на диска, вместо в края, може да намали движението на главите. Също така, някои системи предвиждат проверка на пистите и замяна на дефектите. Тези писти могат да се разполагат на различни места и да предизвикат допълнително движение. X.Управление на файловете. Файла е съвкупност от данни, с общо име и предназначение. Файловете обикновено се делят на записи, които пък се делят на полета. Дължината на полетата може да е с фиксирана или променлива дължина. Компонент на ОС наричан файлов система, реализира концепцията за файловете, като осъществява управлението на файловете, които се пазят във външната (вторична) памет. Файловата система е надстройка на физическото ниво на управление на данните. С помощта на това, потребителя е освободен от проблемите с физическото представяне на данните и с физическите особености на запаметяващите устройства. Файловата система управлява достъпа до файловете и ефективното използване на заеманите от тях ресурси. Основните изисквания към файловата система са: 1.Потребителите да могат да създават, унищожават и модифицират файловете; 2.Потребителите да имат контролиран достъп до файловете на други потребители. Да могат да споделят файлове за изпълнение на обща работа; 3.Потребителите да могат да управляват типа на достъп да файловете си; 4.Всеки потребител да може да прехвърля данни между файловете; 5.Системата трябва д може да защити от загуба на данни или поява на грешки файловете на потребителите си; 6.Потребителите да могат да се обръщат към файловете със символично име; Някои от функциите обикновено се изпълняват явно, а други неявно за потребителя. 10.1 Структура на файловата система. 10.1.1.Типове файлове и операции над тях. Файлът е обща единица за данни, чийто смисъл се определя от потребителя. Файловете могат да съхраняват първични програми, обектни програми, текст, цифрови данни и др. Файлът има структура, която се определя от неговото приложение. Файловата система може да организира фаловете по различен начин. Това определя типа на файла и обикновено файловете се класифицират по съдържание: обектни, изпълними, файлове-данни, текстови; по форма на представяне – символни, двоични, индексни и др. В повечето системи справочниците са реализирани като файлове, а в някои системи и устройствата се идентифицират като имена на файлове (UNIX). В описанието на файла се съхранява типа му, като съвкупност от няколко атрибута. Друг вариант на ОС е да не поддържа никакъв тип на файловете. В UNIX всеки файл се разглежда като последоваелност от байтове. Тази схема позволява максимална гъвкавост. Над файловете могат да се дефинират различни операции: 1.над файлове-създаване, унищожаване, откриване, закриване, преименуване, пренавиване, копиране и др.; 2.над записи – четене, запис, модификация, включване, изключване и др. 10.1.2. Структура на файловата система. Съвременните ОС имат развити средства за общуване с потребителя и чрез входен език, той може да дефинира различни файлове и да зададе изпълнение на операции върху тях. Когато се създаде файл, системата трябва да му разпредели пространсво със външната памет, да оформи блок за управление (дескриптор) и да го запише в справочника. Потребителя се обръща към файл, чрез името му. Ако желае да получи достъп до определен запис от файла, той определя записа като посочи номера му, или укаже ключ (поле) определящо записа. За да изпълни заявката, системата по името намира вътрешния идентификатор, като еднозначно определя файла в системата и осигурява търсене на дескриптора му. Дескриптора може да се намира в справочника на активните файлове (в оперативната памет), в противен случай той се търси в справочника на всички файлове на системата. След това файла трябва да стане активен за потребителя (да се отвори). При отварянето му, трябва да се посочи типа на достъп до данните (последователен, директен и др.), който ще се използва от процеса, както и правата на достъп. Ако операцията е разрешена, заявката на потребителя, се трансформира в заявка по физически адрес на външната памет, генерира се входни-изходна програма, която прехвърля блок данни във физическата памет. В повечето ОС се използва буфериране и кеширане. При завършване на работа с файла се извикват процедурите за затваряне на файла и освобождаване на заеманите от него ресурси. Методи за достъп. Интерфейса на потребителя включва стандартни програми за логически достъп до данните. С всеки метод за достъп е свързана логическа организация на файловете. Логическа файлова система. Символичното име на файла се преобразува във вътрешен идентификатор. За целта се извършва търсене в справочник. Базова файлова система. Намира се дескриптора на файла, активира се файла с процедурите за откриване (закриване) и се проверяват правата за достъп. Методи за физическа организация. Началната заявка за достъп се трансформира в заявка по физически адреси на външната памет, отразяващи действителното разположение и организацията на записите. Тук се включват и модулите за управление на външната памет и на буферите на оперативната памет. Методи за работа с устройствата. Заявената операция и физическия запис се трансформират в последователност от команди за вход-изход и за наличния хардуер. Система за управление на входа/изхода. Извършва се планиране иницииране на операциите и обработка на прекъсванията по вход/изход. Това ниви е свързано с I/O хардуер. 10.2 Организация на файловете и методи за достъп.10.21. Разполагане на данните върху носителите. Файловете се съхраняват върху различни носители. За облекчаване достъпа до данните, всеки блок от данни е свързан с брояч, а в някои случаи с ключ, разделени с интервали. Ключа е число или име, избрано от потребителя за идентифициране на записа, или е резултат от някакви преобразувания над първоначално зададения ключ и др. Когато данните са блокувани, в блока от данни се включват и полетата на ключовете, свързани с отделните записи. Обикновено ключа на блока е равен на последния запис в блока и търсеният запис се намира в блок, чийто ключ е равен или по-голям от зададения. В брояча може да се запише относителния номер на блока в пистата, номер на писта, дължина на ключ и данни и др.фигура1. 10.2.2. Методи за достъп. Метод с последователен достъп. Когато записите са наредени така, че I-тия запис следва I-1 - вия запис и достъпа до записите се извършва последователно, в реда на нареждането им, се говори за последователна организация на файла. Основните операции са четене, запис, пренавиване, пропускане и др. Този метод се използва основно при устройства с последователен достъп (ленти), където структурата на файла е реализирана и физически последователно. Друг вариант е потокоориентирания метод за достъп, където данните се четат в непрекъснат поток. В UNIX се предполага че всеки запис е низ от знаци, завършващ с байт от нули. Метод с директен достъп. Файла се разглежда като номерирана последователност от записи, а достъпа до даден запис се осъществава независимо от това, какъв запис е бил обработен по-рано (дисков модел на файла). Потребителя има възможност да обработва записите в произволен ред. За определяне местоположението на записите върху носителя, се използват физически адреси. Прякото адресиране се използва, когато се използват относителни номера на записите във файла. Предполага се, че върху всяка писта могат да се разположат еднакъв брой неблокувани записи. Абсолютния адрес на файла е известен и към него се добавя относителния номер на пистата. Прякото адресиране не е изгодно в случаите, когато потребителите използват ключ, представляващ характерно за файла поле на записа. В много случаи ключа не може да се преобразува пряко, тъй като е много голям (шифър на изделие). Тогава се прилага непряко адресиране, основано на т.нар. хеширане. Друг разпространен метод е чрез таблица на индексите. Файла се нарича индексен с директен достъп. Всеки елемент на таблицата съдържа ключ-указател към съответния елемент на файла. Недостатък се появява, когато файла нарастне и не е ефективно съдържането на таблицата в паметта. Фигура2. Метод с индексно-последователен достъп. Организацията на файловете при този метод предполага подреждане на записите в нарастваща последователност на ключовете. Достъпа може да е последователен и директен-по ключ. Индекса се опростява, той съдържа толкова елемети, колкото области от записи заема файла. Всеки елемент на индекса на пистите съдържа номера на писта в цилиндъра и ключ на последния запис в пистата. Ако файла е разположен върху няколко цилиндъра, необходимо е изграждането на индекс на цилиндрите. Възможно е да се изгради и главен индекс, който е индекс на индекса на цилиндрите. Метода има основно два недостатъка – 1.всеки достъп до файл изисква преминаване през всички предходни на елемента записи. 2.Трудно се изпълнява операция запис във файла. Метод на достъп до библиотеки. Основен елемент в библиотечния файл е т.нар. раздел, който може да е програма, подпрограма, сегмент от данни и др. Всеки раздел носи име, по което може да бъде намерен във файла. Раздел-справочник в началото на файла съдържа името и разположението на всеки раздел. Библиотечните файлове обикновено се обработват на раздели, а самите раздели са организирани като последователни файлове. Фигура3. 10.3. Справочници. За идентифициране местоположението на файловете всички файлови системи притежават справочници. В справочника се съхранява дескриптора на файла или името и физическият адрес на даден файл. Справочника често е файл със специално предназначение. Глобална стратегия съществува при единно непрекъснато файлово пространство. Така потребителя работи с логически (глобален) справочник и напълно се игнорира проблема с физическото разпределение на пространството за файловете. При повреда обаче отказва цялата система. Усложнена е работата със сменяемите носители. При локалната стратегия всяко запомнящо устройство има свои справочник, което кара потребителя да познава устройствата за съхраняване на данни в системата. Много от системите имат справочник за устройството и за файловата сртуктура. Справочника на устройствата е записан на всяко физическо устройство и описва файловете в него (разположение, дължина), справочника на файловете описва име, тип, притежател, защита и др. 10.3.1. Блок за управление на файла. Дескриптора, свързан с всеки файл, съдържа информацията, необходима на файловата система. Съдържанието на дескриптора при различните ОС се различава. Той може да съдържа: символично име на файла; вътрешен идентификатор на файла; физическо разположение; организация (последователна, индексна и др); устройство (указател към дескриптора); диспозиция на файла(временен или постоянен); тип; информация за управление на достъпа до файла; административна информация. Дескриптора се изгражда при създаване на файла и се актуализира при работа с файла. Най-често дескриптора се пази в отделна област на паметта, а в справочника има указател към него.Обикновенно той се записва в оперативната памет при отварянето на файла и седи там до затварянето му. 10.3.2. Организация на входа в справочниците. Ако справочника се разглежда като таблица на имената, която транслира, той може да се организира по различни начини. Един от тях е новите елементи да се записват в реда на постъпване. Търсенето е последователно. Търсенето може да се ускори, ако елементите са подредени. Преглеждането е по т.нар. двоично търсене. Най-широкио прилагания принцип е използване на хеш-финкция. Която превръща символния низ в число. 10.3.3.Организация на справочниците. Справочника е таблица с имена. ОС намира в него посочен файл по име, Над справочника мога да се извършват операциите: включване на елемент, изключване на елемент, търсене на елемент, модификация на елемент, създаване (унищожаване) на подсправочници, извежане на листинг на справочник, защита. Справочник на едно ниво. Всички файлове са в един и същ справочник, което налага ограничения, когато броя на файловете нарасне. Обикновено мястото на файла е фиксирано. Справочниците на устройствата са пример за такъв. Справочник на две нива. Файловата система съдържа един главен справочник и поне един потребителски справочник. Обикновено главния справочник е достъпен само за ОС. Потребителите имат достъп само до потребителския справочник. Всеки файл трябва да е уникален за справочника си. Проблем възникво при т.нар. share файлове. Някои системи забранявт такъв достъп, но такъв е разрешен всеки потребител трябва да има възможност да именува файл в чужд справочник. При търсене на файл системата най-често търси първо в потребителския справочник, и ако не намери името, започва търсене в допълнителните справочници. Последовятелността от справочници, претърсвани за намиране на файл, се нарича пътека на търсене. Дървовидна организация на справочник. Това е развитие на организацията на две нива в произволо дърво. На потребителя е разрешено да създава собствени справочници и да организира своите файлове. Корена се нарича главен справочник, листата са файлове от данни, вътрешните върхове са подсправочници. Всеки файл има уникално име-пътека. Този начин на образуване на уникално име на файла е общоприет при йерархичните файлови системи. Обикновено всеки потребител има текущ (работен) справочник. Справочник се изтрива ако той е празен, в неговия справочник-родител се изтрива съответния елемент. Ако справочника не е празен обикновено не се разрешава изтриване. Възможно е движение от корена към листата и обратно. Някои ОС разрешават на потребителите си да дефинират собствени пътеки за търсене. Възможно е и да се направи link към файл от друг справочник. Справочника като ацикличен граф. В някои случаи се налага използването на един справочник от няколко потребителя. Ацикличната структура на граф разрешава използването на общи файлове с прилагане на индиректна адресация. Съвместното използване на файлове от данни може да се реши чрез нов елемент в справочника (връзка), предствляваща указател към действителния файл. Друг начин е чрез разпространяване на файла във всички справочници. При системите със символични връзки, изтриването на връзка не влияе върху файла, но проблем настъпва при изтриването на файла-оригинал. Сериозен проблем е появата на цикли. Ако цикли са разрепени в справочника, желаелно е да се избегне повторното търсене. 10.3.4.Сегментиране и файлова си-ма. Сегментната организация на паметта може да служи и за управление на файловете. Сегментирането може да се използва при управлението на данни или като механизъм, отделен от самата файлова система, или като вграден в самата файлова система механизъм. И двете понятия имат сходно отношение към логическата организация на данните; и файла и сегментът имат произволни размери и допускат динамична промяна на дължините си; използват двумерна адресация; Съвместното използване на файлове се решава със запис на един и същ номер на сегмент в таблиците на различни потребители, независимо дали се обръщат към файла с едно и също име или с различни имена. Справочника се реализира чрез обединяване на всички таблици на сегментите, без да са необходимми за работата специални програми. Справочника на всички сегменти има форма на дърво, чиито възли (с изключение на листата) са сегменти-справочници. 10.4.Буфериране Буферирането е метод за припокриване на входно-изходните операции и изчисленията в процеса. Буферите са области на основната памет, които се използват при въвеждане/извеждане на данни от/към у-вата. Чрез буферите се намалява влиянието на разликата в скоростта на процесора и устройствата и се повишава ефективността от използването на процесора. Буферите отстраняват разликата м/у дължините на логическия запис (с който работи процесът) и на физическия запис (с който работи устройството). При изпълнение на заявка за четене от у-вото, в буфера се записва блок от данни, след което търсеният запис се извлича от буфера и се прехвърля в работната област на процеса. При всяка нова заявка от буфера се взима следващия запис,докато блокът се изчерпи. Обратното, при запис, от работната област се прехвърля в буфера запис. И така докато блокът се изпълни, след което той се извежда към у-вото. Буферите подобни на другите ресурси, могат да се управляват статични или динамично. Те могат да се отделят при създаване на процес или преди началото на операция. При простото буф. се отделят един входен и един изходен буфер- по време на работа с файла те се прикрепят към у-вото и изпълняват само една функция. При двойното буф. се отделят по два буфера за вход и изход. Докато при четене се изпълва единият буф., процесът има достъп до втория. Когато в него няма вече записи, двата буфера си разменят ролите. За да няма копиране на данни м/у буф. и работната област се прилага буф. размяна. Дадена област от паметта отначало е входен буф., след това става работна област и най-накрая изходен буф. Когато входът и изходът са достатъчно добре синхронизирани може да се приложи буферна размяна-циклично буф. При този подход входът, обработката и изходът се изпълняват последователно и синхронно над м-вото от буф. При интензивни входно-изходни операции могат да се използват отделни множества от буф. за вход и изход, свързани в цикличен списък. Друг разпространен метод е използване на буф. пул (делим ресурс) от еднакви по размер буф., както за вход така и за изход. Буф. динамично се заемат и връщат в пула. 10.5.Управление на вторичната памет Предназначението на вторичната памет е да съхранява големи количества данни. Като вторична памет се използват дискове. Основните ф-ии на управляващата програма са свързани с удовлетворяването на заявките за място в дисковата памет.пространството на паметта се разпределя във физически единици-блокове, всеки включващ един или няколко сектора, писти, цилиндри. Блоковете могат да са с фиксирана или с променлива дължина, но обикновено се използват блокове с фикс. дълж. Определянето дължината на блока е един от най-големите проблеми.
При системи със странична организация минималният обем данни, предаван м/у паметите е страница. Затова има смисъл вторичната памет да се разделя с размер равен или кратен на страница. Ако е желателно да се разполагат файловете компактно пространството на вторичната памет трябва периодично да се реорганизира поради непрестанното създаване и унищожаване на файлове пространството трябва да се фрагментира (реорганизация на файлове). 10.5.1.Статично и динамично разпределение При статичното разпределение потребителят трябва да окаже пълният размер на файла при създаването му и ОС веднага разпределя пространство, ако това е възможно. Често размерът на файла не е известен предварително и се заделя максималния възможен обем за него така се получава загуба на памет. Тази стратегия също така ограничава и разширяването на файла. При динамичното разпределение се отделя такъв брой блокове, какъвто е необходим за удовлетворяване на заявката. Такава стратегия може да доведе до мъртва хватка-може да настъпи безизходна ситуация, при което два или повече процеса чакат за условие което никога няма да се изпълни, за да се избегне това потребителят маже д а заяви максимално пространство необходимо за заданието му.
Тъй като на лице е ограничено дисково пространство, необходимо е да се използва и освободеното от изтритите файлове пространство. Затова системата трябва да води списък на свободното пространство. При задаването на нов файл се търси в списъка и се отделя пространство за файла. Това пространство се изважда от списъка. Когато файлът се унищожи неговото пространство се добавя в списъка. Списък на свободните блокове. Свободните дискови блокове се свързват в общ списък, като всеки блок съдържа указател за следващия свободен блок. ОС трябва да знае началото на списъка. Методът е прост, но не е много ефективен, защото работата със списъци изисква много входно-изходни операции.  Групиране на свободните блокове. Представлява модификация на горния метод, като се свързват в списък групи от n свободни блока. В първия блок на всяка група се записват адресите на останалите блокове в групата и адресът на следващата група. По този начин бързо се намират адресите на голяма група от блокове.
Броене на свободните блокове. При заемане и освобождаване на непрекъснати области може да се пази начало и брой на свободни, последователно разположени блокове. Така списъкът е значително по-кратък.  Таблици. Често се използват таблици за свободното пространство на всяко устройство. Таблиците могат да представляват свързан списък. За всеки блок на вторичната памет се определя се определя една дума, а свободните блокове се свързват в списък. Тук лесно се разпределят и освобождават блокове, но се изисква много памет. Много по-малко памет се изисква, ако всеки блок се представи с един бит, при което 0 означава свободен блок, а 1-зает. Тази таблица се нарича още битова карта или вектор. Откриването на свободни блокове изисква повече време отколкото при свързаната таблица, но има по-бързо освобождаване на блокове.
10.5.3.Разпределение на свободното пространство: Съществуват няколко основни метода.
непрекъсната област от дисковото адресно пространство. Местоположението на файла се определя по началния адрес и дължината на файла. Едно от предимствата на свързаното разпределение е, че последователните логически записи се разполагат физически последователно. Това намалява времето за работа с файла. Това разпределение разрешава последователен и дискретен достъп. При последователния достъп се помни адресът на последния прочетен блок и веднага може да бъде прочетен следващият. При директен достъп до файла лесно се изчислява адреса на блок, след като се знае началото на файла. Методът има няколко недостатъка. Един от тях е свързан с намирането на свободно пространство за нов файл. При създаване и унищожаване на файлове дисковото пространство се накъсва на голям брой малки дупки. Достатъчно пространство може да има но то не е свързано. Тогава е необходимо съседните области да се обединяват. Друг проблем е размерът за необходимото пространство за файл. При създаването на файл потребителя указва размер и ако няма такава област той не го създава. Също така проблем е включването на нов запис във файл. Необходим е презапис на част от файл. Ако се надвиши размера включването няма да е успешно. Разпределение чрез свързване в списък. Тези проблеми може да се разрешат чрез други методи при които файловете не заемат свързани области на вторичната памет. Всеки файл може да се организира като свързан списък на блокове от данни, които могат да бъдат разпръснати произволно в дисковата памет.В справочника се записва указател към първия блок. Всеки блок съдържа, освен данните, указател към следващия блок. Тук няма фрагментация. Когато се записва във файл се взема първият блок от свободните. Файлът може да расте докато има свободни блокове, тук не е необходимо да се уплътнява паметта, както и да се декларира дължината на файла преди създаването му. Лесно е и унищожаването. При този метод е голям разходът на време при достъп до блок по веригата от указатели. Съхраняването на указатели води до намаляване обема на паметта. При апаратна или програмна грешка може да бъде взет грешен указател, тъй като указателите са пръснати по целия диск. За да се намали загубата на време при търсенето дисковото пространство трябва да се разделя на по-големи физически единици. Разделяне с индексен блок: Този метод подържа директния достъп до файлове. Всички указатели са събрани в една таблица, наречена индексен блок (индекс). Всеки файл има свой индексен блок. Подреждането на указателите в индексния блок отразява подреждането на блоковете от данни във файла. Достъпът до i-я блок на файла става като се ползува указателя в i-я елемент на индексния блок.Фигура4. При създаването на файл всички указатели са Nil. Желателно е индексния блок да бъде малък за да няма загуба на пространство, тъй като индексния блок се отделя дори и в него да има един указател. Свързване на индекси. Индексния блок за удобство нека да заема един дисков блок. Когато файловете са големи, заемат се няколко индексни блока. За съкращаване на времето за търсене индексните блокове могат да се разположат един след друг. Индекс на повече нива.Използва се отделен индексен блок, който да сочи индексни блокове които от своя страна сочат блокове данни. Комбиниран метод. Използват се 13 указатели (по системата UNIX), първите 10 адресират директно първите 10 блока на файла. Така за малки файлове не е необходимо отделен индексен блок. Следващите 3 указ. сочат индексни блокове. Първият указател е адрес на индексен блок от второ ниво, вторият сочи към индексен блок от трето ниво, а третият указател съдържа адрес на блок. Недостатък на разпределението с индекси е, че включването и изключването на блокове от данни предизвиква изменение на целия индексен блок. Карта на файловете(таблица на блоковото изображение). Включването и изключването на блокове може да се улесни, като се състави единна карта за всички файлове в която вместо указатели се използват номера на блокове. В картата за всеки физ. блок на диска се заделя една дума. Разположението на даден файл се изобразява ч/з верига от номера на блокове-съответният елемент на картата съдържа номера на следващия блок от файла, а в справочника се помества номерът на първият блок на файла. В елемента на картата, съответстващ на последния блок, се записва Nil. По картата може да се съди за физическото съседство на блоковете и да се разпредели нов блок до останалите блокове на файл. Възможна е загуба на доста време при файлове с разпръснати блокове, понеже за достъпа до всеки блок трябва обръщане към картата.фигура5. 10.6.УПРАВЛЕНИЕ НА ДОСТЪПА ДО ФАЙЛА Данните, които се съхраняват в изчислителната система, трябва да се предпазват от физическо разрушаване(предмет на надеждността) и от непозволен достъп(работа на защитата).Защитата на файловете може да се реализира по много начини.В едно потребителска система просто може да се извади носителя и да се заключи. В многопотребителските системи изискването за защита произтича от възможността за достъп до файловете на един потребител от друг. Системите, където не е разрешен достъпа до файловете на друг потребител, защита не е необходима(налице е пълна защита чрез забрана на достъпа). Друга крайност е свободен достъп без защита.В повечето системи се предоставя някаква ограничена форма на защита, представляваща компромис между степента на защита и свързаните в нея разходи.Защитата е важен проблем при проектирането на ОС, изискващ широки познания относно различните методи за реализация на защитата. Механизмите за защита трябва да дават възможност за управляван(контролиран) достъп. Тези механизми разрешават и забраняват достъпа в зависимост от някои фактори, един от които е типът на желаният достъп. Във файловете системи могат да бъдат определени няколко основни типове на достъп:
Защитата може да бъде свързана с файл или с пътеката за спецификацията му.Защитата на пътеката е по- обща схема – потребителят трябва да има разрешен достъп и до справочника (съдържащ файла) и до файла. В системите ,където може да има различни пътеки до файл (напр.ацикличен обобщен граф), потребител може да има различни права в зависимост от пътеката. 10.6.1.КОМПОНЕНТИ НА СИСТЕМАТА ЗА ЗАЩИТА Защитата има четири компонента: обекти на защитата,разрешени типове за достъп до файлове, потребители ,желаещи достъп до файловете, и процедури за защита на файловете.Всеки файл има собственик – потребителят ,който го е създал.Ако той реши , че файлът може да бъде използван от други потребители, трябва да укаже кой и как може да се обръща към файла.Процедурите за защита, реализиращи тези възможности, могат да използват глобални или локални методи ( свързани с всички файлове или с всеки файл). Процедурата трябва да има възможност да идентифицира потребителя. 10.6.2.НАЧИНИ ЗА ЗАЩИТА Именуване на файлове.При някои ОС се разчита на невъзможността потребител да достигне до файл, който не може да именува и следователно не може да работи с него. ПАРОЛИ. Достъпът до всеки файл може да бъде управляван подобно на достъпа до изчислителните системи чрез пароли. Идентификацията на потребителя при достъп до файл става, като му се даде парола.Система с пароли може да се реализира различно- с използване на глобални или локални методи.Възможно е да се определи една парола за достъп до всички файлове или по една парола за всеки за всеки тип на достъп. Всеки потребител, използващ някаква привилегия (право), знае съответната парола и назовавайки файл, въвежда и паролата за вида на достъп.Недостатък на този подход е, че колкото повече са потребителите, толкова е по-голяма възможността да се узнае паролата от потребителя без права.Стойността на подобна реализация е относително ниска.Друга възможност е да се свърже парола с всеки файл и да се свърже парола със всеки файл(и трябва да се реализира по- детайлна защита, трябват повече пароли).Вариант е с всеки файл да се свърже списък на достъпа (води се от собственика), съдържащ идентификатор на потребителя и парола(обикновено е достатъчна една парола за всички типове достъп).Всеки потребител има различна парола. Така ако се разкрие парола, засяга се само един потребител.Използват се и други схеми.Например някои системи позволяват да се свързва парола с подчправочник, а не с файл. Каталог: files -> tu files tu files -> Увод в компютърната графика tu files -> Xii. Защита и безопасност на ос tu files -> Електрически апарати tu files -> Средства за описание на синтаксиса tu files -> Stratofortress tu files -> Начало Решаване на проблеми tu files -> Писане на скриптове за bash шел : версия 2 tu files -> 6Технологии на компютърната графика 1Модели на изображението tu files -> Z=f(x), където x- входни данни; z Изтегляне 2.7 Mb. Сподели с приятели:
|
