1. Булеви функции. Теорема на Пост-Яблонски за пълнота. Нека J2 = { 0, 1}. Всяка функция f : J2n J
Изтегляне 5.91 Mb.
|
- Навигация на страницата:
- 7. Файлова система. Логическа организация и физическо представяне. Основни системни примитиви. Файлът
- Програмните канали
- UNIX System 5
- Индексната област
Системата за прекъсване цели във всеки момент да се даде възможност за регистрация на случващо се събитие. Механизмът на прекъсванията е ефективен начин за обмяна на информация с бавните входни-изходни устройства и за сигнализиция за особени състояния в работата на централния процесор. Чрез нея се избягва необходимостта от периодични проверки на флагове за дадени събития. На всяко прекъсване се съпоставя точно определен номер. За всеки вид прекъсване има специална програма, която се изпълнява при възникването на този вид прекъсване. В основната памет има специална фиксирана област, наречена таблица на векторите на прекъсванията. Всеки вектор на прекъсване съдържа указател към подпрограма за обработка на прекъсването и състояние. Когато възникне прекъсване, централният процесор прекъсва изпълнението на текущата програма и съдържанието на програмния брояч PC и регистъра на състоянието MSW се запазват в стек за да може да има вложени прекъсвания. Новото състояние на процесора при влизане в прекъсване се взима от съответния вектор на прекъсване, който се намира по номера на прекъсването. Всяка програма, която обслужва прекъсване завършва с инструкция за връщане от прекъсване, която от върха на стека прочита предишното състояние на PC и MSW и ги зарежда в процесора и по този начин изпълнението се връща към прекъснатата програма. За да се отчете важността на събитията, които може да настъпят се въвежда приоритет на прекъсванията. По време на изпълнението си програмата за обработка на едно прекъсване може да бъде прекъсната само от прекъсване с по-висок приоритет. Същестуват различни видове прекъсвания:
Друго разделяне на прекъсванията е на маскируеми и немаскируеми. Маскируемите прекъсвания могат да се игнорират, т.е. да не се обработват, докато немаскируемите прекъсвания задължително се обработват. Така немаскируемите прекъсвания винаги имат приоритет пред маскируемите. 7. Файлова система. Логическа организация и физическо представяне. Основни системни примитиви. Файлът е основната единица, чрез която операционните системи осигуряват съхраняването на постоянни обекти данни. Името на файл е символен низ с определена максимална дължина. Допустимите символи за името на файла, както и максималната дължина варират в различните операционни системи. В UNIX/LINUX системите се допускат всички възможни символи и не се прави разлика между малки и главни латински букви. В MSDOS са допустими само цифрите, буквите и символът за подчертаване (_) и не се прави разлика между малки и главни латински букви. В някои операционни системи името на файла има следната форма: име_на_файл[.разширение]. Разширението се използва за да се означи типа или формата на файла и то не е задължително. Пример за такава операционна система е MSDOS. Основният момент е доколко ядрото на операционната система прави разлика между името и разширението. В UNIX/LINUX системите за ядрото няма име и разширение – името на файла е едно цяло. Разширенията могат да се поставят за по-удобна връзка между потребителя и обслужващите програми в обвивката на ядрото, но това не засяга самото ядро. За разлика от UNIX/LINUX системите, в MSDOS разделянето е заложено в ядрото – например, файловете с изпълним код задължително имат разширение exe или com. В по-старите операционни системи има единствен тип файлове. В по-новите операционни системи такива файлове се наричат обикновени файлове - служат за съхраняване на информация върху външен носител. В съвременните операционни системи има и други типове файлове. Те са файлове, свързани с входно-изходни устройства или файлове, свързани с услуги, предоставени от ядрото. В UNIX/LINUX файловете за входно-изходни устройства се наричат специални файлове. Те са два типа – символен специален файл и блоков специален файл. Ползата от тях е, че програмите стават независими от устройствата – системните примитиви за четене и писане са едни и същи за всички устройства. В UNIX/LINUX файловете, свързани с услуги, предоставяни от ядрото са няколко вида. Програмните канали са файлове, които осигуряват механизъм за комуникация между паралелно работещи процеси. Такъв тип файлове са и така наречените socket, но те се използват за процеси в мрежова среда. В по-новите UNIX системи има символни връзки. Символните връзки са тип файлове, чрез които се дава възможност един файл да е достъпен с различни имена. Същата възможност предоставят и така наречените твърди връзки, но за разлика от символните връзки те не се разглеждат като тип файлове.
В по-старите системи като OS/360 файловете върху един диск са организирани в един каталог, който не е тип файл – поместен е отделно от файловата система върху диска. В съвременните операционни системи каталозите са реализирани като тип системни файлове. Всеки каталог съдържа информация за файловете в него – за всеки файл има поне един запис, който съдържа името на файла и допълнителна информация.
В съвременните операционни системи файлът се разглежда като последователност от байтове. Това опростява структурата на файла и съответно опростява системните примитиви за работа с файлове. Най-съществено е, че такава структура може да се приложи към всички изброени по-горе типове файлове. Атрибутите са допълнителна информация за файловете, която операционната система съхранява. Основните атрибути са:
флагове има и във версиите на LINUX – например, флагът security deletion (ако е 1 за някой файл, то при неговото унищожаване се форматират всички блокове, които е заемал файла) и флагът undelete (ако е 1 при изтриване на файла се съхранява информация, подмогаща евентуалното му възстановяване). Най-простата организация на файловата система е за всеки диск да се изгради един каталог, който съдържа информация (име, атрибути, дискови адреси) за всички файлове, разположени върху диска. Такава организация има при по-старите операционни системи, например OS/360. Такава организация създава редица неудобства – всички файлове върху един диск трябва да са с различни имена, което е проблем при многопотребителски системи, освен това се затруднява търсенето на файлове. Поради тези причини в по-новите операционни системи се изгражда йерархична организация на файловата система. В началото тя е била с фиксиран брой нива – пример е операционната система CTSS на MIT, в която файловата система е на три нива. По-новите операционни системи поддържат йерархична организация с произволен брой нива. Най-горното ниво е главен каталог. Всеки каталог може да съдържа както информация за файлове, така и информация за други каталози. По този начин се получава дървовидна организация – в листата на дървото са файловете, а във вътрешните върхове на дървото са каталозите. Имената на файловете трябва да са уникални само в рамките на един каталог. В такава организация трябва да има начин за унифициране на името на всеки файл. За целта се въвеждат пълни имена на файлове. Абсолютното пълно име на файл се образува от имената на каталозите по единствения път от корена на дървото до листото с файла. Относителното пълно име на файл е свързано с понятието текущ каталог. Това име се образува от имената на каталозите по единствения път от текущия каталог до листото с файла. В UNIX/LINUX системите има единна йерархия за всички файлове и за всички устройства. Това се постига с техниката на монтиране. Поддържа се текущ каталог за всеки отделен процес. В MSDOS системите специалните файлове не са част от йерархичната структура. Освен това за всяко дисково устройство се изгражда собствена йерархична структура със собствен корен. Въвеждат се имена на различните устройства и се поддържа текущо устройство. Текущ каталог се поддържа само за отделните устройства, но не и за всички процеси. Стратегиите за управление на дисковото пространство се обуславят в зависимост от комбинирането на решението на три основни въпроса. Първият основен въпрос е кога се разпределя дискова памет за файловете. Съществуват два основни подхода:
Статичното разпределение затруднява потребителя – той трябва предварително да знае колко голям ще бъде файла, за да може да задели достатъчно памет. Динамичното разпределение е по-гъвкава стратегия, но е по-трудна за реализация. Вторият основен въпрос е колко непрекъснати дискови области заема един файл. Под непрекъсната дискова област разбираме последователни сектори върху една писта, последователни писти върху един цилиндър, т.е. физически съседни области, отчитайки физическата организация на диска. Тук отново има два подхода:
Третият основен въпрос е каква е единицата за разпределение върху дисковото пространство:
В по-старите операционни системи се използва статично и непрекъснато разпределение. Предимства на такава организация са лесната реализация и ефективен достъп при последователна обработка. Недостатък на статичното непрекъснато разпределение е силната фрагментация на свободното дисково пространство – върху диска има много области, които са свободни, но файловата система не може да разпредели дискова памет за файл, защото няма достатъчно голяма непрекъсната област, въпреки че сумарно дисковото пространство е достатъчно. При съвременните операционни системи се използва динамично и поблоково разпределение. Всеки файл се разделя на блокове, като всички блокове на всички файлове имат еднакъв размер. Всеки блок на един файл се разполага в една непрекъсната област. Логически съседните блокове на файла, обаче, не са физически съседни върху диска. Дискова памет за блок се разпределя когато файлът нараства, а не при неговото създаване. Такава организация решава повечето проблеми на статичното непрекъснато разпределение. Основният въпрос е какъв да бъде размера на блока. Ако блокът е прекалено голям, то ще се появят проблеми от фрагментацията, въпреки че последователният достъп ще е по-ефективен. Ако блокът е прекалено малък, то обратно - ще се постигне ефективно използване на дисковата памет, но последователният достъп ще е неефективен. При по-малък блок се появява и друг проблем – файловата система трябва да помни всички адреси на блоковете на един голям файл, т.е. обемът на системната информация на файловата система нараства. Оттук нататък ще се спрем по-подробно на динамичното поблоково разпределение. При такава организация на файловата система дискът представлява последователност от блокове, номерирани от 0 нататък. Файловата система трябва да съхранява структури върху диска, които да дават информация за текущото разпределение на дисковата памет. Тези структури се наричат системни структури и те трябва да съдържат информация за свободните блокове, за разпределените блокове за всеки файл и за други параметри на файловата система. Когато операционната система трябва да задели памет, тя се нуждае от информация кои от блоковете са свободни – тази информация се съхранява в системна структура за свободните блокове. Ще разгледаме трите най-популярни реализации. Първата реализация на тази структура е свързан списък на свободните блокове. При нея всеки свободен блок съдържа адреса на следващия свободен блок. Файловата система трябва да разполага с адреса на първия свободен блок – този адрес е параметър на файловата система. При заделяне на памет се заделя първия свободен блок, а адреса на следващия свободен блок се записва като адрес на първи свободен блок. Предимство на подхода е лесната реализация. Основният недостатък е ненадеждност – структурата е пръсната по всички свободни блокове. Втората реализация е свързан списък от свободни блокове с номера на свободните блокове. При тази структура първият свободен блок съдържа не само адреса на втория свободен блок, но и адресите на следващите няколко свободни блока, доколкото позволява размера. Следващият свободен блок, който се използва от структурата е последния блок, чийто адрес е записан в първия свободен блок и т.н. По този начин структурата става по-компактна. Освен това, тя дава възможност да се реализират по-ефективни алгоритми за разпределяне и освобождаване на блокове. Файловата система отново трябва да разполага с адреса на първия свободен блок. Третата реализация е така наречената карта или таблица на свободните блокове. Структурата е масив от елементи, като всеки елемент позиционно съответства на блок върху диска, т.е. съседни елементи на масива съответстват на физически съседни блокове. Всеки елемент описва състоянието на съответния блок. При най-простата реализация е достатъчен един бит за един елемент – 1 означава, че блокът е свободен, 0 означава, че блокът е зает. В този случай картата се нарича битова карта (bitmap). Предимство на битовата карта е компактността на структурата – тя е с фиксиран размер в зависимост от размера на диска. Основно предимство, обаче, е възможността за разработка на ефективни алгоритми за разпределение на блокове, които отчитат физическото съседство на блоковете – може да се постигне по-голяма непрекъснатост на файловете, въпреки че разпределението е поблоково.
При такава организация за всеки един файл трябва да се пази адрес на първия блок, разпределен за файла. Обикновено, този адрес е записан в каталога заедно с името и атрибутите на файла. Недостатък на такава реализация е ненадежността – смесват се данни и адреси, адресите са пръснати по всички блокове. Друг недостатък е неефективност при обработка на файловете с произволен достъп. Втората реализация на структурата е карта или таблица, подобно на системната структура за свободните блокове. Размерът на елементите на битовата карта, обаче, трябва да се увеличи – състоянието на един блок отново е свободен или зает, но ако блокът е зает той съдържа адреса на логически следващия блок във файла или маркера за край на файла, ако той е последният блок във файла. Отново за всеки един файл трябва да се пази адрес на първия разпределен за него блок и обикновено тази информация се пази в каталога. Предимствата на такава структура са, че цялата нужна информация се съдържа в структура с фиксиран размер, разположена на фиксирано място в диска. По отношение на надеждността – възможно е създаване на няколко копия на таблицата. Основен недостатък на таблицата е неразширяемост, поради фиксирания размер. Третата реализация е структура, в която за всеки файл се съхранява логическата последователност от блоковете, разпределени за този файл. Такава структура се нарича индекс. Физическата организация на индекса трябва да е такава, че да не ограничава размера на файловете и да осигурява бърз произволен достъп. В различните операционни системи се използват свързани списъци, дървета, B+ дървета и др. Освен системните структури за свободните блокове и за блоковете, разпределени за файлове, операционната система трябва да разполага и със системни структури за общите параметри на файловата система – те съхраняват важна информация за файловата система на глобално ниво, например, размер на блока, размер на цялата файлова система, адреси на началото и размери на различните области, общ брой свободни блокове и др. Ще разгледаме някои конкретни примери за физическа организация на файловата система. При файловата система UNIX System 5, дисковото пространство е последователност от блокове, номерирани от 0 до N, където N зависи от големината на дисковото пространство. Размерът на блока най-често е 1K, 2K или 4K. Дисковото пространство при UNIX System 5 се разпределя на четири области: boot block, super block, индексна област и област за данни. Блокът с номер 0 се нарича boot block и подобен блок има във всяка файлова система. Той съдържа програмата, с която се зарежда операционната система. Блокът с номер 1 се нарича super block и той съдържа общи параметри на файловата система.
В областта за данни са блоковете данни на файловете. Освен тях в тази област има блокове за системна информация – косвени блокове и блокове, които реализират списъка на свободните блокове. Ще разгледаме структурата на индексния описател (inode). За всеки файл има точно един inode, който съдържа атрибутите на файла и адресна информация. Индексните описатели имат фиксиран размер 64B в UNIX System 5. Първите 24B в inode е частта за атрибути на файла, а останалите 40B служат за адресна информация. Първият атрибут е mode. Той заема 2B и съдържа следните полета:
Вторият атрибут е nlink. Той заема 2B и съдържа броя на твърдите връзки на файла. Третият атрибут е uid. Той е 2B и съдържа числов идентификатор на собственика на файла. Четвъртият атрибут е gid. Той е 2B и съдържа числов идентификатор на групата на собственика на файла. Следващият атрибут е size. Toй е 4B и съдържа размера на файла в брой байтове. Последните три атрибута са по 4B и са атрибути за време. Атрибутът atime показва дата/време на последен достъп до файла. Атрибутът mtime показва дата/време на последна промяна на файла. Атрибутът ctime показва дата/време на последната промяна на индексния описател на файла. Адресната част се разпределя на 13 адресни полета по 3B и един свободен байт за подравняване. Тези адресни полета съдържат адреси на блокове в областта за данни. Първите десет адресни полета съдържат адресите на първите десет блокове данни на файла. Единадесетото адресно поле съдържа адрес на косвен блок в областта за данни, който съдържа адреси на следващите блокове данни на файла. По този начин се реализира косвена адресация. Дванадесетото адресно поле съдържа адрес на косвен блок, който съдържа адреси на косвени блокове, които съдържат адреси на следващите блокове данни на файла. По този начин се реализира двойна косвена адресация. Чрез тринадесетото адресно поле се реализира тройна косвена адресация. По този начин блоковете от данни на файла са организирани в дърво, което има дълбочина най-много три. Това означава ефективен произволен достъп до файла – всеки блок от данни на файла е достъпен най-много с четири дискови операции.
От дървовидната структура се пресмята, че максималният размер на един файл при размер на блока 1К е 16GB. Суперблокът съдържа общи параметри на файловата система:
Последните два компонента на суперблока са свързани с механизмите за разпределяне и освобождаване на блокове в областта за данни и inode в индексната област. В UNIX System 5 системната структура, която съдържа информация за свободните блокове е списък от блокове, които съдържат номера на свободни блокове. Към тази структура се включва и масива s_free. Всеки от блоковете в структурата в началото си съдържа адрес към следващия блок от структурата и още B-1 адреса на свободни блокове. За начало на структурата се счита масива s_free. Така в елемента s_free[0] се съдържа адреса на първия блок от областта за данни, който съдържа номера на свободни блокове. При зареждането на операционната система целият суперблок се копира в оперативната памет и по този начин чрез масива s_free системата има бърз достъп до номера на свободни блокове. Масивът s_inode се използва по аналогичен начин на s_free, само че при разпределянето и освобождаването на inode. Номера на свободни inode се съдържат само в масива s_inode, но не и в областта за данни както при свободните блокове. Естествено, s_inode не може да съдържа номерата на всички свободни inode. Системата, обаче, може да разпознава свободните inode – те имат тип на файла 0000. Така, ако номерата на свободни inode в s_inode се изчерпят системата може да организира търсене за свободни inode. Каталог: fmi fmi -> Софтуерни технологии fmi -> Лекции и семинарни занятия по аналитична геометрия fmi -> 3d-алгоритъм на Chaikin fmi -> Лекции по увод в програмирането fmi -> Лекции и семинарни занятия по линейна алгебра fmi -> Конкурентно Програмиране fmi -> Лекции по компютърни мрежи и комуникации fmi -> Ще предпочетеш да наблюдаваш света отстрани или ще се присъединиш към най-голяма студентска организация? fmi -> Лекции по обектно-ориентирано програмиране Изтегляне 5.91 Mb. Сподели с приятели:
|