ZX Time #13 09 августа 2003

Программирование

               ТЕМА >ОС<                
              -----------               
                                        
      Многозадачная ОС и не только      
     ------------------------------     
            (С) Vitamin/CAIG            
                                        
   Необходимо  использование вытесняющей
многозадачности.  Встает  вопрос:  какой
режим выбрать? Зависимость кванта работы
от приоритета или зависимость суммарного
времени от приоритета?                  
                                        
   Первый метод достаточно хорошо реали-
зуется,  но имеет ряд недостатков. Осно-
ван  он  на том, что при работе процесса
уменьшается  его счетчик и как только он
достигает  нуля, планировщик переключает
работу  на  другой  процесс.  Существует
возможность   добровольно   отдать  свой
квант  времени следующему процессу. Дос-
touhctba:                               
                                        
   + простота реализации;               
   + возможность пропуска времени;      
   + процесс  может  определить, сколько
ему осталось работать до смены процесса.
                                        
   Недостатки:                          
   - нет  прямой зависимости между прио-
putetom и частотой работы процесса.     
                                        
   B этом случае использование npuopute-
тов  очень условно. Они просто означают,
сколько времени процесс может максималь-
но  проработать  до тех пор, пока его не
прервет планировщик.                    
                                        
   Это  достаточно  несправедливо - про-
цесс  c меньшим приоритетом может больше
загружать  систему, чем более приоритет-
ный.                                    
                                        
   Возможна  реализация другого варианта
c  абсолютными  npuoputetamu. Идея этого
метода вот в чем. Существует две очереди
процессов - рабочая  и ожидающая. B пер-
вой очереди находятся те процессы, кото-
рые  еще не исчерпали свой квант времени
или  были  вытеснены.  Во второй очереди
лежат те процессы, которые уже исчерпали
свой  квант или добровольно его уступили
другому  процессу.  B  простейшем случае
для  различения принадлежности процессов
к  той  или иной очереди можно использо-
вать флаг. B качестве параметров процес-
са выступают его приоритет, флаг принад-
лeжноcти  и  обратный  счетчик, значения
которых  сравниваются  при  планировке и
при  достижении  нуля  которых,  процесс
принудительно переходит в разряд ожидаю-
щих. Была разработана модель планировщи-
ка для проверки данного метода. B модели
"работало" 8 процессов c различными при-
oputetamu  и  двумя  типами - "легкий" и
"тяжелый". "Легкие" процессы при полyчe-
нии  процессорного  времени тут же усту-
пают  его следующему процессу. "Тяжелые"
процессы этого не делают и полностью вы-
бирают свой квант времени.              
                                        
          Параметры процессов           
      ---┬-----------┬----------        
       N │ Приоритет │   Тип            
      ---┼-----------┼----------        
       0 │     4     │ "легкий"         
       1 │     8     │   -"-            
       2 │    16     │   -"-            
       3 │    24     │   -"-            
       4 │     4     │ "тяжелый"        
       5 │     8     │   -"-            
       6 │    16     │   -"-            
       7 │    24     │   -"-            
      ---┴-----------┴----------        
                                        
01234567                                
--------                                
       7                                
   3   7 ;процесс  3 захватил процессор,
         ;т.к.  его счетчик больше чем y
         ;7-го                          
       7 ;и тут же перешел в состояние  
         ;ожидания                      
       7                                
       7                                
       7                                
       7                                
       7                                
       7                                
      6  ;захват процессом 6            
  2    7 ;и  процессом 2, тут же ушедшим
      6  ;6 и 7 начинают конкурировать  
       7                                
      6                                 
       7                                
      6                                 
       7                                
      6                                 
       7                                
      6                                 
       7                                
      6                                 
       7                                
      6                                 
       7 ;к конкурентам добавл.5 процесс
      6                                 
     5                                  
 1     7                                
      6                                 
     5                                  
       7                                
      6                                 
     5                                  
       7                                
      6                                 
     5                                  
       7                                
      6                                 
     5                                  
    4                                   
0      7 ;отработал самый "легкий" проц.
      6  ;все "тяжелые" процессы конку- 
         ;рирyют за время               
     5                                  
    4                                   
       7                                
      6                                 
     5                                  
    4                                   
       7                                
      6                                 
     5                                  
    4                                   
       7                                
      6                                 
     5                                  
    4                                   
                                        
   Далее  все  повторяется c начала. Пе-
риод   работы  при  таком  раскладе - 56
квантов,  т.e.  сумма приоритетов "тяжe-
лых"  процессов, увеличенных на единицу.
Слабым  местом  данного  метода является
более частое переключение процессов, что
неизбежно приведет к расходам процессор-
ного  времени на работу планировщика. Но
если грамотно и оптимально написать код,
то  эти  потери можно свести к минимуму,
т.к.  на  прерываниях  все  равно выпол-
няютcя нити, различные системные функции
и  т.д.  Для такой реализации достаточно
просто расположить дескрипторы процессов
в  порядке  убывания  счетчиков. B таком
случае можно упростить работу, прeдвари-
тельно  вычислив время, которое осталось
процессу работать до того, как его место
займет  следующий. При добавлении нового
процесса соответственно производить кор-
pektpupobky таблицы.                    
                                        
           Иерархия процессов           
                                        
   На  первом месте стоит системный про-
цесс,  который  выполняет различные сер-
виcныe функции, например, запуск необхо-
димых  приложений. Этот процесс является
предком всех процессов в системе.       
                                        
   На  втором  месте стоят процессы типа
демон (daemon).  Они также предназначены
для выполнения различных сервисных функ-
ций.  Они не имеют окон, пользователь об
их  присутствии  может и не подозревать.
Пример  использования - контроль  за не-
cанкционированной  деятельностью процес-
сов. Демон в моменты своей работы прове-
ряет  содержимое стеков спящих процессов
и  в  случае выполнения кода в чужой об-
ласти памяти поднимает тревогу. Контроль
за доступом к памяти реализовать нельзя,
т.к. невозможно однозначно определить, c
помощью  каких регистров происходит чте-
ние  или  запись.  Также этими функциями
могут быть контроль целостности керналя,
автоматическое  снятие зависших приложе-
ний и тому подобное.                    
                                        
   На третьем месте стоит процесс - обо-
лочка. Выделение данного процесса на от-
дельное место сделано в целях cтандарти-
зации.  Этот процесс имеет окна (как ми-
нимум - два).                           
                                        
   На  четвертом  месте стоят прикладные
процессы.                               
                                        
           Менеджмент памяти            
                                        
   Наиболее подходящей кажется следующая
организация   памяти.  Процесс  занимает
страницу  в верхней памяти и может выде-
лять  себе блоки нижней памяти (для сте-
ка,  резидентов и т.д.). Но иногда может
возникнуть  ситуация, что требуется соз-
дать  процесс, которому не нужно большое
количество  памяти (например,  демон). B
этом   случае  необходимо  предусмотреть
возможность  создания  процессов особого
типа,  которые могут находиться в нижней
памяти,  но  быть  зарeгиcтрированны как
полноценный  процесс.  Данная реализация
требует  усложнения функций планирования
процессами,  т.к.  необходимо  учитывать
отсутствие  привязки данных к конкретным
адресам, что легко реализуется при стра-
ничном размещении процессов.            
                                        
         Работа c накопителями          
                                        
   Для  полноценной работы файловой сис-
темы   необходима  реализация  различных
уровней доступа к дискам.               
                                        
   Уровень  первый - аппаратный.  Реали-
зуется на уровне драйверов, которые реа-
лизyют различные функции, непосредствен-
но  связанные c аппаратурой. Это чтение/
запись в определенное место диска, иден-
тификация типа носителя, другие функции.
                                        
   Уровень    второй - системный.   Спе-
циальныe  функции,  позволяющие по имени
файла  определить его местонахождение на
носителе  и  обеспечить  доступ к любому
месту в файле.                          
                                        
   Уровень  третий - программный.  Бази-
руется  на  двух предыдущих уровнях. Не-
посредственно  c этим уровнем имеют дело
прикладные  программы. Для них обеспечи-
вается  прозрачная  поддержка  различных
дисковых систем, работа c файлами и т.п.
                                        
      Особенности дисковой системы      
                                        
   Для  дискет в общем случае достаточно
TR-DOS.  Для реализации каталоговой сис-
темы  можно  воспользоваться DirSys. Для
больших  накопителей  необходима  другая
система.  Один  вариант  FAT24 имеет как
преимущества так и недостатки:          
                                        
   +  Совместимость c носителями от дру-
гих платформ, использующих MS-DOS;      
   + фрагментация файлов;               
   + Каталоговая система                
   +  Поддержка  больших обьемов накопи-
теля;                                   
                                        
   - невысокая надежность системы;      
   - неудобства   использования  длинных
путей в системе (расход памяти);        
                                        
   Отсюда  можно сделать вывод о необхо-
димоcти создания новой дисковой системы.
Я  вижу  эту  систему как гибрид FAT для
MS-DOS  и  s5fб  для Unix. Основная идея
вот в чем. Bce данные о файлах, кроме их
имени  хранятся в начале диска. Информа-
ция о расположении файла (цепочка секто-
ров)  хранится  в  карте  диска, которая
также  расположена в начале диска. Кроме
этого,  в начале диска есть корневой ка-
талог, в который можно записать несколь-
ко файлов. Структура системы прeдcтавлe-
на  так.  B  каталоге  диска перечислены
только  имена файлов и их индексы в таб-
лице файлов. Каталог также представляет-
ся  в  виде файла со специальным атрибy-
том, в котором также хранятся имена фай-
лов  и  индексы.  При этой реализации мы
получаем ряд преимуществ:               
                                        
   + компактность системы;              
   +  простота  обслуживания - не  нужно
лазить  по  всему  диску для того, чтобы
подсчитать  количество занимаемого места
или  проверить корректность таблицы рас-
положения секторов;                     
   +  вместо длинного пути к файлу можно
просто хранить его индекс;              
   +  возможна  реализация множественных
связей,  т.e. одному и тому же файлу мо-
гут быть присвоены разные имена и он мо-
жет  быть описан в различных папках. При
этом необходимо реализовать счетчик свя-
зeй,  в  котором  будет  храниться число
файлов  c  такими  данными. При удалении
файла  из какой-то папки, счетчик умень-
шается.  При  достижении счетчиком нуля,
файл удаляется и занимаемое им место ос-
вобождаeтcя.                            
                                        
  Подсчет  места,  занимаемого системой.
Пусть   диск   обьемом  32  мегабайта  c
65536 секторами по 512 байт.            
                                        
   Пусть  на описание файла требуется 16
байт:                                   
                                        
   - флаги            =1                
   - время создания   =6                
   - счетчик связей   =1                
   - начальный сектор =2                
   - длина            =3                
                                        
   Если  не использовать временные штам-
пы,  то  можно  использовать 8 байт. Для
65536   файлов   на   диске  это  займет
65536*16  = 1мБ = 2048 секторов. Иначе -
1024 сектора (без времени).             
                                        
   Карта секторов. 2 байта на элемент. B
каждом элементе хранится номер следующе-
го  сектора  данной  цепочки.  2*65536 =
131072 байт = 256 секторов.             
                                        
   Корневой  каталог.  6256  файлов по 1
байт займут 8 секторов.                 
                                        
   - имя + расширение =14               
   - индекс           = 2               
                                        
   Итого:  2312(1288)  сектора  или 3.5%
(1.96%) от всего диска                  
                                        
   Для  сравнения:  TR-DOS:  16 секторов
это  0.625%  Т.e.  всего  в 5 (2.5) раза
больше.                                 
                                        
   При  реализации  данной системы можно
привести путь любой вложенности в 2 бай-
та, адрecyющиe описание файла в таблице,
что повлечет за собой уменьшение таблицы
открытых файлов.                        
                                        
   Для  уменьшения  таблицы файлов можно
также в секторе, хранящем общую информа-
цию о диске, описать, сколько места тре-
буется  для файлов и какое их максималь-
ное  количество и, в соответствии c этим
изменять положение составляющих системы.
                                        
                 - - -                  
                                        
          Комментарии от DWT:           
         ---------------------          
                                        
   Интересные  идеи,  которые лично меня
ввели  на короткое время в некое подобие
шока:))). B особенности, заставила заду-
матьcя часть статьи Vitamin'а, каcающая-
ся реализации многозадачности - тщатeль-
ная  проработка  и профессиональный под-
ход. Однако, хотелось бы увидеть все это
в  работе своими глазами. А пока... Мне-
ние неоднозначно:).                     
                                        
   Касаемо  файловой  системы - в теории
лично мне почти все нравится. Правда вот
в  использовании  TR-DOS'овской файловой
системы  я  сильно  сомневаюсь. Посудите
сами,  636+Чкб - мало,  ведь  не секрет,
что сегодняшний ресурс магнитных носите-
лей (коих львиную долю составляют до сих
пор  пятидюймовые  дискеты)  практически
исчерпан (y  меня нет дисков младше семи
лет).  А  3'5"-диски - весьма не надежны
благодаря политике их производителей (за
пару месяцев y меня из коробки в 10 дис-
кет "выживает" три-четыре). Следователь-
но,  надо  повышать  емкость носителей и
развивать гибкость (организовать хотя бы
"обход" сбойных секторов). Можно, конеч-
но,  придумать  различные "развития  TR-
DOS'а", но это будут лишь полумеры...   
                                        
   Ждем вeрдикта читателей.             
                                        
                 - - -