Заявен заем Получен заем Остатък

Заявен заем Получен заем Остатък

б

8	4	4
9	3	6

Наличност=3

в
Фиг. 4.4. Безопасно? състояние на банкера

Описаният алгоритьм дава възможност да се разпределят ресурси, така че да се избегнат мъртви хватки. Това позволява да продължи изпълнението на процеси, които при система с предпазване биха чакали. Но алгоритъмът има и сериозни недостатъци [7]:

1. Изхожда се от фиксиран брой ресурси, но техният брой се изменя при техническо обслужване, при неизправности, при профилактика.

2. Броят на работещите процеси е постоянен, но в съвременните мултипрограмни системи той се мени.

3. Алгоритъмът изисква банкерът да удовлетвори всички заявки за крайно време, но за реалните ОС са нужни по-конкретни изисквания.

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

5. Изисква се потребителите да указват максималните нужди от ресурси. В съвременните ОС разпределението на ресурси става все no-динамично и е все no-трудно да се прави подобна преценка. Като се има предвид, че компютрите стават все по-дружелюбни, може да има потребители, които да нямат представа за необходимостта си от ресурси.

заявен_заем, получен_заем: array [l..n] of integer; var състояние: boolean) var i: integer;

може_да_завърши: array [l..n] of boolean; продължи: boolean; begin

{оценка на текущото състояние на банкера и клиентите}
наличност: = капитал; {начален капитал на банкера}
for i := 1 to n do {за всички „ n " клиенты}
begin

наличност := наличност - получен_заем[1];

може_да_завърши [i] := false; {не е известно дали ще завърши

транзакцията}

остатък [i] := заявен_заем [i] - получен_заем [i];

end;

продължи := true;

продължи: = false;

може_да_завърши [i] := true;

наличност: = наличност + получен_заем [i];

продължи: = true;

end;

end;

end; {всички транзакции са довършени или повече}
{транзакции не могат да бъдат завършени}

if наличност = капитал then състояние: = true {безопасно състояние}

else състояние := false; {опасно състояние}

end.

Фиг. 4.5. Алгоритъм на банкера

Управление на файлове

Файлът е съвкупност от данни, обединени с общо име и предназначение. Най-често файловете се разполагат на носители като магнитки дискове или ленти. Файловете обикновено се делят на записи, които на свой ред се подразделят на полета, чиито брой и дължина могат да са фиксирани или променливи. Полетата съдържат стойност на някаква величина. Например запис на файл може да включва ред от текста на първична програма (в символна форма) или няколко машинни команди на изпълнима програма. Файлът лежи в основата на логическата организация на данните.

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

Файловите системи могат да са повече или по-малко сложни. Едно примерно множество от функции, което те могат да реализират, трябва да отговаря на изискванията [7, 9, 10, 88]:

- Потребителите да могат да създават, унищожават и модифицират файлове.

- Потребителите да имат контролиран достъп до файловете на други потребители. Те могат да споделят файлове за изпълнение на обща работа.

- Потребителите да могат да управляват типа на достъп до своите файлове.

- Потребителите да имат възможност да определят удобна за програмите си структура на файловете.

- Всеки потребител да може да прехвърля данни между файловете.

- Системата трябва да осигурява защита от загуба на данни при грешки в апаратурата или в програмното осигуряване, както и при намеса на друг потребител.

- Потребителите да могат да се обръщат към файловете чрез символично име (т.е. файловете да са независими от устройствата). Тук също трябва да се реши проблемът, когато различии имена се отнасят до един и същ файл или едно и също име се свързва с различии файлове.

- Файловата система да предоставя „дружелюбен" интерфейс с потреби телите.

Някои от функциите се изпълняват явно (в резултат на системните изисквания), а други - автоматично.

Файлът е обща единица за данни, която може да съхранява различни видове данни, чиито смисъл се дефинира от създателя. Файловете могат да съхраняват първични програми, обектни програми, текст, цифрови данни и др. Файлът има структура, която се определя от неговото приложение. Например текстовите файлове са последователност от знаци (символи), организирани в редове (възможно и страници); изпълнимият файл е последователност от думи разпределени в записи от зареждащата програма. В зависимост от начина на достъп, представянето (кодирането) и т.н., файловата система може да организира файловете по различии начини. Тези черти определят типа на файловете и обикновено файловете се класифицират по няколко признака: по съдържание - програмни файлове (първични, обектни и изпълними), файлов- данни, текстови; по форма на представяне - символни, двоични, смесени; п метод на достъп - последователни, директни, индексни и др. В повечето системи справочниците са реализирани като файлове, а в някои системи устройствата се идентифицират със специални имена на файлове. В тези системи файловете се класифицират и по признак за предназначение. Типичен приме са MS-DOS и UNIX, които различават обикновени файлове от данни справочници и специални файлове (съпоставени на устройствата) и използват единен подход при работа с тях.

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

Друга противоположност е ОС да не поддържа никакъв тип на файлове. Например UNIX разглежда всеки файл като последователност от байтове, без никаква интерпретация. Тази схема допуска максимална гъвкавост, но минимална поддръжка.

Над файловете и техните елементи могат да се дефинират различии операции:

1. Над файлове - създаване, унищожаване, откриване, закриване, преимепуване, пренавиване, копиране и др.

2. Над записи - четене, запис, модификация, включване, изключване и др.

10.1.2. Структура на файловата система

Основните компоненти на файловата система и техните функции могат да бъдат разяснени, като се проследи пътят, по който преминават заявките за достъп до файловете. Системата има развити средства за общуване с потребителя и той може чрез входен език да дефинира различии файлове и да зададе изпълнението на операции над тях. Когато се създава файл, системата трябва да му распредели пространство във външната памет, да оформи блок за управление {дескриптор) на файла и да запише дескриптора в справочник. Минималната информация, която се включва в дескриптора, е символично име на файла, вьтрешен идентификатор и физическо местоположение. Справочникът е основната структура от данни, която ОС поддържа за организиране на системата от файлове.

Потребителят се обръща към конкретен файл чрез името му. Ако желае да получи достъп до определен запис, той определя записа, като посочи например неговия номер във файла или укаже ключ (поле), еднозначно определящо записа. За да изпълни заявката, системата най-напред по името намира вътрешния идентификатор, който еднозначно определя файла в системата и осигурява бързо търсене на дескриптора му. Дескрипторът може да се намира в справочника на активните файлове (разположен в оперативната памет), ако вследствие на предишно обръщане или деклариране файлът е „отворен". В противен случай той се тьрси в справочника на всички файлове в системата, където с името му е свързан уникален вътрешен идентификатор (той може да е адрес на дескриптора във външната памет, номер на файл и др.). След това файлът трябва да се отвори, т.е. той да стане активен спрямо потребителя (процеса). Отварянето се свежда главно до следното. Търси се местоположението на тома, свързан с идентификатора (том се нарича отделният физически носител - една лента, един дисков пакет, една дискета). Файл може да бъде разположен върху част от него или върху няколко тома. Ако томът с търсения файл не е установен (например е автономен, разположен върху сменяем диск или лента), издава се съобщение за оператора с искане за поставянето му върху зададеното устройство. Чете се дескрипторът, проверява се допустимостта на заявената от потребителя операция, след което дескрипторът се записва в справочника на активните файлове (един общ или всеки потребител има собствен). След като файлът е отворен, при следващо обръщане към него не е нужно тьрсене в справочника на всички файлове. При отварянето на файла обикновено е необходимо да се посочи методът на достъп до данните (последователен, директен и т.н.), който ще се използва от процеса (въпреки че при някои операции е възможен само един метод за достъп), както и привата на достъп (защитата). Получава се и паметта, необходима за буфериране на данните.

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

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

Някои системи неявно отварят файлове при първо обръщане към тях и ги затварят при завършване на програмата. Повечето обаче изискват явно указване на операциите чрез системни извиквания.

Въпреки голямото разнообразие на съществуващите файлови системи, функциите им са подобни на описаните. Обикновено те са групирани в модули по най-различен начин в конкретните системи, но за съжалсние функциите на модули с еднакво наименование могат много да се различават в разните системи. При реализацията на файловите системи може да се приложи йерархичен подход (вж. гл. V). Разнообразието на функциите на файловите системи е предпоставка за съществуването на различии начини за организирането им в иерархия [ 9,10, 23,43,75, 85,88]. По-долу е даден пример за обобщена файлова система (трябва да се отбележи, че много реални файлови системи имат подобна организация):

Методи за достъп. Най-високото ниво, интерфейсът на потребителя, включва стандартни програми за логически достъп до данните. С всеки метод за достъп е свързана логическа организация на файловете, която може да е съвършено различна от физическата (т. 10.2),

Логическа файлова система. Символичното име на файла се преобразува във вътрешен идентификатор. За целта се извършва търсене в справочник (т. 10.3).

Базова файлова система. Намира се дескрипторът на файла, активира се (деактивира) файлът чрез процедурите за откриване (закриване) и евентуално се проверяват правата на достъп (т.т. 10.3, 10.6).

Методи за физическа организация. Началната заявка за достъп се трансформира в заявка по физически адреси на външната памет, отразяващи действителното местоположение и организацията на записите (т. 10.5.3). Тук се включват и модулите за управление на външната памет (т. 10.5) и на буферите в оперативната памет (т. 10.4).

Методи за работа с устройствата. Заявената операция и физическият запис се трансформират в последователност от команди за вход/изход и за наличната апаратура (канал, контролер). Пример за процесите на това ниво могат да бъдат описаните в гл. IX.

Система за управление на входа/изхода. Извършва се планиране, иници-иране на операциите и обработка на прекъсванията по вход/изход (вж. гл. IX). Това ниво непосредствено е свързано с входно-изходната апаратура.

В обратна посока, нагоре по йерархията, обикновено се изпращат съобщения за завършване. В разглежданите в литературата модели се правят някои опростявания, например не се разгаежда възстановяването след грешка (т. 10.7). Също така не се разглежда разпределението на устройствата - предполага се, че те са разпределени статично при първо обръщане към съответен файл. В други системи, при първо обръщане към файл, се генерира заявка за устройство и то се разпределя динамично (гл. IX).

Файлът е абстрактна структура от данни и при работа с нея потребителят използва „логически" единици за данни. Например йерархията от единици файл-запис-поле-знак определя една от най-употребяваните логически организации на данните, която води началото си от най-стария носител на данни -перфокартата.

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

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

На фиг. 10.1 са дадени някои възможни начини за разполагане на записи от данни върху диск (за компютри на IBM). Показани са форматите на записи с фиксирана дължина(10.1 а и 10.1 б неблокувани, 10.1 в - блокувани) и записи с променлива дължина (10.1 г - блокувани, където RL е дължина на запис в байтове, a BL е дължина на блок). За облекчаване на достъпа до данните, всеки

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

От логическа гледна точка метод за достьп е начин за търсене или добавяне на единица данни (например запис) в един файл. Файлът може да се разглежда като виртуален (абстрактен) носител, за който се определят методи за достъп. Вески метод за достъп определя избрано логическо представяне на данните. Физическата организация на данните върху устройствата може да е съвсем различна, но потребителят работи с логическа (въображаема) организация на данните (с логически модел), предоставена му от метода за достъп.

Когато записите са наредени така, че i-тият запис следва (i-1)-вия запис и достъпът до записите се извършва последователно в реда на нареждането им, говори се за последователна организация на файла (последователен файл) или за лентов модел на файла.

Основните операции над файла са четене (четене на единица данни и увеличаване на показалеца с 1) и запис (добавяне на единица данни накрая и придвижване на показалеца). Могат да се включат и други операции, като пренавиване, пропускане (напред/назад) на п записа.

Този метод на достъп се използва главно при работа с устройства с последователен достъп (лентови, печатащи и др.), където последователната структура на файла е реализирана и физически. Методът се прилага и при устройствата с пряк достьп.

Вариант е потокоориентираният метод за достьп, където данните се четат в непрекъснат поток. Например в UNIX се предполага, че всeки запис е низ от знаци, завършващ с байт от нули. Адрес на следващия запис е винаги текущата позиция във файла след последната операция.

Метод с директен достьп

Файлът се разглежда като номерирана последователност от записи, а достъпът до даден запис се осъществява независимо от това, какъв запис е бил обработeн по-рано (т.е. използва се дисков модел на файла). Потребителят има възможност да обработва записите в произволен ред и затова естествената среда за реализацията на файловете с директна организация (с директен достъп) са устройствата с директен достъп, като дисковите.

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

Често се прилага пряко (директно) адресиране, в което се използва относителните номера на записите във файла. Програмистът задава номер на записа, който се преобразува от системата в относителен номер на писта и блок по следния начин. Предполага се, че върху всяка заемана от файла писта могат да се разположат еднакъв брой неблокувани записи (броят е известен например записите са с фиксирана дължина). Номерът на записа се дели на този брой и полученото частно е относителен номер на писта, а остатъкът е относителен номер на блок в пистата. Абсолютният адрес на началото на файл е известен и се прибавя към относителния номер на пистата. Възможна е лесна преместваемост на файла. Номерът на записа може да се използва и като ключ, като по този начин се осигурява контрол на търсенето (на съответствието ключ -номер на блок).

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

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

Друг разпространен метод с използване на непряко адресиране се базира на изграждането на таблица на индексите или просто индекс. Самият файл се нарича индексен с директен достъп. Логическият модел на такъв файл е показан на фиг. 10.2.

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

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

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