- •Расшифруйте понятия “протокол”, “интерфейс”. В чем разница между ними? Какие основные виды интерфейсов существуют у компьютерных программ согласно стандарта posix?
- •Что такое ядро ос? Какие особенности его работы по сравнению с другими программами? Какие архитектуры ос бывают? в чем их преимущества и недостатки
- •Какие принципиальные отличия языка Ассемблера от высокоуровневых языков программирования? Что такое байткод? в чём разница между язіком Ассемблера и байткодом?
- •Приведите примеры форматов исполняемых файлов и кратко охарактеризуйте их. Подробно формат elf.
- •Перечислите этапы загрузки компьютера от включения питания до активизации gui или cli ос. Охарактеризуйте роль каждого из них.
- •Что такое процесс ос? Чем он отличается от программы? Что такое нить? Какие есть подходы к созданию многонитевых (многопоточных программ)? Что такой фибр, в чем его отличие от нити?
- •Опишите жизненный цикл процесса. Какие требования обычно выдвигаются к алгоритмам планирования процессов?
- •Перечислите основные алгоритмы планирования процессов. Сформулируйте и охарактеризуйте алгоритм “Очередь” (fifo). Приведите простой пример. В каких системах он может применяться на практике?
- •2 Примера каждого из них:
- •Назовите и кратко опишите существующие способы синхронизации многопоточных приложений.
- •Что такое критическая область процесса? Что такое тупик? Какие виды тупиков бывают? Назовите прнципы разработки многопоточных программ, которые позволят избежать для них попадания в тупики.
- •Что представляет из себя примитив синхронизации “Семафор”? Опишите его интерфейс (набор операций) и приведите простой пример использования.
- •Что представляет из себя примитив синхронизации “Монитор”? Опишите его интерфейс (набор операций) и приведите простой пример использования.
- •Какие инструкции аппаратной синхронизации вы знаете? Сравните их. Приведите 2 примера, как на их основе можно построить различные примитивы синхронизации (условные переменные, семафоры, …).
- •Что такое оптимистическое и пессимистическое блокирование? в каких случаях какое предпочтительнее? Какие еще виды блокирования вы знаете?
- •Что такое программная транзакционная память (stm)? Какие качества имеют программы, которые ее используют?
- •Что такое конвейер (pipe)? Что такое именованный конвейер? Охарактеризуйте их. Как эти объекты можно использовать для взаимодействия программ (приведите несколько примеров)?
- •Что такое фрагментация? Какие виды фрагментации бывают? Какие виды фрагментации проявляются в 3 основных схемах размещения файлов?
- •Нарисуйте обобщенную структуру программы в памяти. Каким образом на нее может повлиять использование сегментной модели виртуальной памяти?
- •Опишите страничную и сегментную организацию виртуальной памяти. В чем преимущества и недостатки каждой из них?
- •Какая главная проблема эффективной реализации систем виртуальной памяти? Назовите несколько способов ее решения?
- •Сформулируйте алгоритм выбора кандидата на удаление из кэша “Наименее недавно использовавшийся” (lru). Опишите его работу на простом примере. В чем его преимущества и недостатки?
- •Назовите способы учета свободного места на диске, кратко опишите их. В каких файловых системах какие способы используются?
- •Управление свободным и занятым дисковым пространством
- •38. Что такое файловая система на основе журнала? Чем она отличается от классической файловой системы, какие у нее есть преимущества и недостатки, основные проблемы и особенности реализации?
- •39. Опишите Socket api ос. В чем его особенности, сильные и слабые стороны?
- •40. Опишите технологию удаленного вызова процедур (rpc). Сравните 2 подхода к предаче данных в ней. Какие уровни Интернет-стека участвуют в организации распределенного взаимодействия в ней?
- •41. Опишите сетевой стек tcp/ip. Чем он отличается от эталонной модели osi? Какой уровень к tcp/ip стеку добавляет rpc-приложение?
Назовите способы учета свободного места на диске, кратко опишите их. В каких файловых системах какие способы используются?
Дисковое пространство, не выделенное ни одному файлу, также должно быть управляемым. В современных ОС используется несколько способов учета используемого места на диске. Рассмотрим наиболее распространенные.
Учет при помощи организации битового вектора
Часто список свободных блоков диска реализован в виде битового вектора (bit map или bit vector). Каждый блок представлен одним битом, принимающим значение 0 или 1, в зависимости от того, занят он или свободен. Например, 00111100111100011000001 ... .
Главное преимущество этого подхода состоит в том, что он относительно прост и эффективен при нахождении первого свободного блока или n последовательных блоков на диске. Многие компьютеры имеют инструкции манипулирования битами, которые могут использоваться для этой цели. Например, компьютеры семейств Intel и Motorola имеют инструкции, при помощи которых можно легко локализовать первый единичный бит в слове.
Описываемый метод учета свободных блоков используется в Apple Macintosh.
Несмотря на то что размер описанного битового вектора наименьший из всех возможных структур, даже такой вектор может оказаться большого размера. Поэтому данный метод эффективен, только если битовый вектор помещается в памяти целиком, что возможно лишь для относительно небольших дисков. Например, диск размером 4 Гбайт с блоками по 4 Кбайт нуждается в таблице размером 128 Кбайт для управления свободными блоками. Иногда, если битовый вектор становится слишком большим, для ускорения поиска в нем его разбивают на регионы и организуют резюмирующие структуры данных, содержащие сведения о количестве свободных блоков для каждого региона.
Учет при помощи организации связного списка
Другой подход - связать в список все свободные блоки, размещая указатель на первый свободный блок в специально отведенном месте диска, попутно кэшируя в памяти эту информацию.
Подобная схема не всегда эффективна. Для трассирования списка нужно выполнить много обращений к диску. Однако, к счастью, нам необходим, как правило, только первый свободный блок.
Иногда прибегают к модификации подхода связного списка, организуя хранение адресов n свободных блоков в первом свободном блоке. Первые n-1 этих блоков действительно используются. Последний блок содержит адреса других n блоков и т. д.
Существуют и другие методы, например, свободное пространство можно рассматривать как файл и вести для него соответствующий индексный узел.
Опишите на примере непрерывную схему размещения файлов. Какие ее преимущества и недостатки? В каких случаях она используется (и в каких файловых системах)?
Непрерывное размещение - простейший вариант физической организации (рисунок 1, а), при котором файлу предоставляется последовательность блоков диска, образующих единый сплошной участок дисковой памяти. Для задания адреса файла в этом случае достаточно указать только номер начального блока. Другое достоинство этого метода - простота. Но имеются и два существенных недостатка. Во-первых, во время создания файла заранее не известна его длина, а значит не известно, сколько памяти надо зарезервировать для этого файла, во-вторых, при таком порядке размещения неизбежно возникает фрагментация, и пространство на диске используется не эффективно, так как отдельные участки маленького размера (минимально 1 блок) могут остаться не используемыми.
непрерывная (магнитные и оптические носители)
+ легко реализовать
+ самая лучшая производительность
- фрагментация
- необходимость реализовать учет дырок
- проблемы с ростом размера файла, записанного в дырку
При смежном размещении каждый файл занимает набор смежных блоков на диске. Преимущество данного метода - простота: требуется хранить только одну ссылку (номер блока) и длину (число блоков). Другим преимуществом является возможность произвольного доступа.
Недостатки данного метода следующие:
возможны потери дисковой памяти из-за фрагментации (метод аналогичен общей задаче динамического распределения памяти, рассмотренной ранее);
невозможность увеличения размера файла.
36. Опишите схему размещения файлов при помощи связного списка. Какие ее преимущества и недостатки? Какая ее основная практическая реализация, и какую проблему эта реализация решает? В каких файловых системах это используется?
Ссылочное размещение файла
При ссылочном размещении каждый файл представляется в виде связанного списка дисковых блоков, которые могут быть разбросаны по диску. Преимущества данного метода:
Простота – необходимо хранить только начальный адрес;
Отсутствие потерь дискового пространства; система хранит списки свободной памяти.
Недостатки:
Отсутствие произвольного доступа: для доступа к данным файла в общем случае необходимо выполнить просмотр части списка блоков файла.
Уменьшается размер блока из-за хранения служебной информации
При ссылочном размещении адрес по файлу представляется в виде (Q, R), где Q – номер блока, к которому выполняется доступ, в связанном списке блоков, представляющем файл; R - cмещение в блоке.
К файловым системам, использующим ссылочное размещение, относится файловая система File-allocation table (FAT), используемая в MS-DOS и OS/2 и до сих пор используемая в Windows