1. Булеви функции. Теорема на Пост-Яблонски за пълнота. Нека J2 = { 0, 1}. Всяка функция f : J2n  J

• 
  2B за номера на индексния описател на файла;
  
• 
  14B за собственото име на файла.
  

2¹⁶ = 65536 индексни описатели. Хубавото е, че всички записи са с фиксиран размер – постига се простота на структурата.

Записите в каталога не са сортирани - те са в хронологичен ред, т.е. в реда на създаване на файловете. При изтриване на файл, записът му в каталога не се изтрива, а се записва 0 като номер на индексен описател. Да напомним, че индексните описатели се адресират от 1, така че номер 0 може да се използва като признак за свободен запис. При създаване на файл, в каталога се търси свободен запис (с номер 0), в който да се запише информация за създадения файл или се добавя нов запис, ако няма свободни записи. Това води до неприятен ефект – каталозите могат само да нарастват, но е невъзможно да се свиват. Като цяло за обработка на каталозите не се използват ефективни алгоритми.

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

При създаване на твърда връзка на файл трябва да се увеличи броячът nlink в индексния описател на файла.

Всички твърди връзки на един файл са напълно равноправни – няма значение кой е оригиналния файл. Поради тази причина броячът nlink помага на системата да установи кога е нужно един файл да се изтрие физически, а не само от каталога - при всяко изтриване на един файл броячът nlink намалява с 1 и ако е станал 0, то файлът трябва да се изтрие физически. Важно е, че твърди връзки могат да се създават само към обикновени файлове.
Символните връзки дават същата възможност, както твърдите връзки но имат по-различна реализация. Символните връзки са тип файл – всяка символна връзка има собствен inode, в който тип на файла е символна връзка, запис в каталога и област за данни. В първия адресен блок в индексния описател за символна връзка е записан адрес на блок от областта за данни, в който е записано пълното име на файла, към който се осъществява връзката.

Предимствата на символните връзки пред твърдите са следните:

• 
  символни връзки могат да се създават към файлове от
  

• 
  възможно е символни връзки да се създават между файлове в различни файлови системи, което е невъзможно за твърдите връзки.
  

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

• 
  суперблок;
  
• 
  описатели на групи;
  
• 
  битова карта на блоковете;
  
• 
  битова карта на inode;
  
• 
  индексна област;
  
• 
  област за данни.
  

UNIX System 5 е, че той има много копия – по едно за всяка група.

Частта описатели на групи съдържа последователност от описатели на всички групи на файловата система.

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

Размерът на една група се определя така, че битовата карта на свободните блокове да заема точно един блок. Например,

ако блокът е 1K, то групата е малко повече от 8MB.
Един описател на група е 32B и съдържа информация за групата:

• 
  адрес на блока с битовата карта на блоковете;
  
• 
  адрес на блока с битовата карта на inode;
  
• 
  адрес на първия индексен описател в индексната област;
  
• 
  брой свободни блокове в областта за данни на групата;
  
• 
  брой свободни inode в индексната област на групата;
  
• 
  брой файлове с тип каталог в групата.
  

Размерът на всеки inode е 128B. В сравнение с UNIX System 5 са добавени нови атрибути:

• 
  брой блокове, заети от файла;
  
• 
  нов атрибут за време dtime – дата/време на последното изтриване на файла;
  
• 
  атрибути-флагове – реализират се чрез 1 бит и са поместени в поле от 4B; някои от тях са: флаг secure deletion (при изтриване на файла се форматират всички блокове), флаг undelete (когато файлът се унищожава, за него се съхранява информация, подмогаща евентуалното му възстановяване), флаг immutable (не могат да се променят нито атрибутите, нито данните на файла), флаг compress (данните на файла се компресират при запис и декомпресират при четене), флаг synchronous write (операцията за запис е синхронна с физическото записване на данните върху диска).
  

Адресът е увеличен на 4B, за разлика от UNIX System 5, където той е 3B. По този начин могат да се адресират по-голям брой блокове –

до 4 милиарда, което при размер на блока 1K е напълно достатъчно за съвременното състояние на технологиите.

Каталогът, за разлика от UNIX System 5, има различна структура на записите:

• 
  номер на inode на файла (4B);
  
• 
  дължина на записа (2B);
  
• 
  дължина на името на файла (2B);
  
• 
  име на файла (до 255B).
  

От размера на полето за номер на inode се вижда, че броят на inode може да достигне 4 милиарда.

LINUX EXT2 поддържа твърди и символни връзки по същия начин, по който те се поддържат от UNIX System 5.
Дисковото пространство при файловата система на MSDOS е последователност от сектори. Минималната единица за разпределение на дисково пространство се нарича клъстер и представя един или няколко (степен на двойката) физически съседни сектора. Размерът на клъстера е фиксиран.

Дисковото пространство се разпределя на следните части:

• 
  boot sector;
  
• 
  FAT;
  
• 
  копие на FAT;
  
• 
  коренен каталог;
  
• 
  област за данни.
  

В boot sector се съхранява програмата за зареждане на операционната система плюс някои общи параметри на файловата система.

• 
  размера на клъстера;
  
• 
  размера на таблицата FAT;
  
• 
  броя на копията на таблицата FAT, които се съхраняват;
  
• 
  размер на коренния каталог;
  
• 
  размер на цялата файлова система.
  

FAT е масив от елементи с определен размер. Всеки елемент позиционно съответства на един клъстер в областта за данни и описва неговото състояние. Първите два елемента от масива съдържат служебна информация и те нямат отношение към клъстерите. Елементите с номера от 2 нататък съответстват на клъстерите, затова адресацията на клъстерите в областта за данни започва от 2. Всеки клъстер може да е в три състояния:

• 
  свободен – тогава съответният му елемент във FAT съдържа код 0;
  
• 
  разпределен за файл – тогава съответният му елемент във FAT съдържа адресът на логически следващия клъстер, който е разпределен за файла или маркер за край на файла (само единици), ако това е логически последният клъстер, който е разпределен за файла;
  
• 
  повреден – тогава съответният му елемент във FAT съдържа специален код, който като стойност е по-голям от максималния адрес на клъстер.
  

В по-старите версии на файловата системи на MSDOS размерът на елементите в масива е 12 бита, клъстерът е 1K (два съседни сектора). Така могат да се адресират до 2¹² = 4096 клъстера, т.е. до 4MB дисково пространство, което е крайно недостатъчно. Поради това таблицата се разширява. Появява се FAT16, където размерът на елементите на масива е 16 бита и могат да се адресират до

2¹⁶ = 65536 клъстера. Освен това се увеличава и максималният размер на клъстера – във FAT16 един клъстер може да достигне 64KB. Така максималният размер на дисковото пространство достига 4GB. В WINDOWS/95 таблицата се разширява до FAT32 – 32-битови елементи на масива. Файловата система на MSDOS е пример за файлова система, която е неефективно разширяема.

При всяко стартиране на операционната система цялата таблица FAT се зарежда в оперативната памет за да има бърз достъп до информацията за разпределените и свободните клъстери. Увеличаване на размера на таблицата води до неудобство цялата таблица да се държи в паметта. Освен това увеличаването на размера на клъстера води до неефективно използване на паметта – за всеки файл задължително са разпределени цяло число клъстери.

В MSDOS каталозите са тип файлове. Всеки каталог съдържа записи с фиксиран размер (32B), като всеки запис описва един файл в каталога.

Разпределението на тези 32B е следното

• 
  име на файла (8B);
  
• 
  разширение на файла (3B);
  
• 
  атрибути-флагове на файла (1B);
  
• 
  резервирано пространство (10B) за разширяване;
  
• 
  дата на последна модификация (2B);
  
• 
  време на последна модификация (2B);
  
• 
  номер на първи клъстер (2B);
  
• 
  размер на файла в байтове (4B).
  

• 
  read-only – ако е 1, файлът е само за четене;
  
• 
  system – ако е 1, файлът е системен, т.е. съдържа част от операционната система;
  
• 
  hidden – ако е 1, файлът е скрит за някои команди на операционната система;
  
• 
  catalog – ако е 1, файлът е каталог;
  
• 
  archive – ако е 1, файлът се включва следващия back-up на файловата система.
  

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

В термините на NTFS дисковото пространство се нарича том (volume), като един том може да заема няколко дискови дяла.

• 
  LCN (logical cluster number) – логически адрес на клъстера в рамките на тома;
  
• 
  VCN (virtual cluster number) – логически адрес на клъстера в рамките на файла, ако клъстера е разпределен за някакъв файл.
  

Основният принцип на файловата система NTFS е, че цялата информация за файловата система се съхранява във файлове, т.е. върху диска няма системни области. Така в NTFS има три типа файлове – обикновени, специални и системни файлове. В системните файлове се съхраняват метаданните.

Предимството на този принцип е, че по този начин системните файлове могат да нарастват динамично, подобно на обикновените файлове.

Дисковото пространство се разпределя на следните области:

• 
  boot файл;
  
• 
  MFT файл;
  
• 
  MFT зона;
  
• 
  първа половина на областта за данни;
  
• 
  други системни файлове;
  
• 
  втора половина на областта за данни;
  
• 
  копие на boot файла.
  

Клъстери за системните файлове се разпределят някъде по средата на тома.

MFT файла съдържа записи с фиксиран размер от 1K, които се адресират от 0 нататък. Всеки файл в тома е описан с поне един основен запис в MFT файла. Адресът на този запис се използва като идентификатор на файла в рамките на файловата система.

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

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

• 
  атрибут $FILE_NAME – съдържа собственото име на файла;
  
• 
  атрибут $STANDART_INFORMATION – съдържа информация за файла – размер на файла, дата/време на създаване, дата/време на последен достъп, дата/време на последна модификация и др.;
  
• 
  атрибут $DATA – съдържа данни на файла;
  
• 
  атрибути $INDEX_ROOT, $INDEX_ALLOCATION, $BITMAP, които се използват при представянето на каталозите.
  

Например, атрибутите $FILE_NAME, $STANDART_INFORMATION и $INDEX_ROOT винаги са резидентни.

Обикновено нерезидентни са онези атрибути, които динамично нарастват много бързо.

Всеки MFT–запис има заглавие, последвано от един или повече атрибути. В заглавието се съдържат общи параметри за записа.

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

Ако атрибутът е резидентен, съдържанието му е поместено в

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

• 
  VCN на началния клъстер на екстента;
  
• 
  LCN на началния клъстер на екстента;
  
• 
  размер на екстента в брой клъстери.
  

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

• 
  собствено име на файла;
  
• 
  адресът на основния запис на файла в рамките на MFT-файла;
  
• 
  копие на атрибута $STANDART_INFORMATION на файла.
  

Записите във всеки каталог са съдържание на атрибута $INDEX_ROOT и са сортирани в азбучен ред по името на файла. Ако записите не се побират в атрибута $INDEX_ROOT, тогава за каталога се разпределят допълнителни екстенти, наречени index buffers с дължина 4K. Адресите на разпределените index buffers са съдържание на атрибута $INDEX_ALLOCATION. Атрибутът $BITMAP съдържа информация за свободните клъстери във всички индексни буфери. Записите от $INDEX_ROOT заедно със допълнителните записи в index buffers са организирани в B-дърво. Целта на тази структура е ускоряване на търсенето на файл по име.

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

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

Системният примитив open има следния прототип:

int open (const char *filename, int flag[, mode_t mode]).

Той може да се използва както за отваряне на съществуващ файл, така и за създаване на нов файл. С open могат да се отварят и специални файлове, но могат да се създават само обикновени файлове. Аргументът filename задава името на файла – абсолютно, собствено или относително спрямо текущия каталог в текущия процес. Аргументът flag е цяло число, което се интепретира като флагове, задаващи режима на отваряне. Аргументът mode се използва само при създаване на файл и той задава код на защита.

При изпълнението на open, с отворения файл се свързва първият свободен файлов дескпритор на текущия процес. При успешно завършване open връща файловият дескриптор на отворения файл. При неуспех open връща -1.
В по-ранните UNIX системи чрез системния примитив open не може да се създава файл. За тази цел се използва системният примитив creat, който е запазен и в по-новите UNIX системи. Подобно на open, чрез creat могат да се създават само обикновени файлове. Системният примитив creat има следния прототип:

int creat (char *filename, mode_t mode).

Той създава файл с име filename и код на защита mode и след това го отваря в режим само за писане. Ако файлът е съществувал, информацията в него се изтрива. При успех creat връща файловият дескриптор на отворения файл, при неуспех creat връща -1.
Системният примитив close се използва за затваряне на вече отворени файлове, т.е. за прекъсване на връзката между процеса и файл. По-прецизно, чрез close се освобождава файлов дескпритор. Той има следния прототип: int close (int fd).

Аргументът fd задава файлов дескриптор на файла, който ще се затваря. При успешно завършване close връща 0, иначе -1.

Аргументът fd задава файлов дескриптор на отворен файл, от който ще се чете. Аргументът buf задава адрес в паметта, където ще се записват прочетените данни. Аргументът count задава брой байтове, които ще се прочетат. Четенето от файла започва от текущата позиция. При успех read връща броя на действително прочетените байтове, който може да е по-малък от count. При неуспех read връща -1. След изпълнението на read текущата позиция се увеличава с броя на действително прочетените байтове. При опит да се чете от текуща позиция след края на файла, read връща 0.