# Подготовка к рубежке по ОС

## Из задачника

**1.4** Рассмотрим гипотетический микропроцессор, генерирующий 16-битовые адреса
( предположим, например, что счетчик команд и адресные регистры имеют размер 16 бит ) и обладающий 16-битовой шиной данных.
a. Какое максимальное адресное пространство памяти может быть непосредственно доступно этому процессору, если он соединен с "16-битовой памятью"?
b. Какое максимальное адресное пространство может быть непосредственно доступно этому процессору, если он соединен с "8-битовой памятью"?
c. Какие особенности архитектуры позволят этому микропроцессору получить доступ к
отдельному "пространству ввода-вывода"?
d. Сколько портов ввода-вывода способен поддерживать этот микропроцессор, если в командах ввода и вывода задаются 8-битовые номера портов? Сколько портов ввода-вывода он может поддерживать с 16-битовыми портами?
**Решение:**
a. $2^{16}\cdot 16b = 128Kb$
b. $2^{16}\cdot 8b = 64Kb$
c. I/O Memomy Mapping
d. $2^8 = 256$; $2^{16}=65536$

**1.5** Рассмотрим 32-битовый микропроцессор с 16-битовой внешней шиной данных, которая управляется тактовым генератором с тактовой частотой 8 МГц. Пусть цикл шины этого микропроцессора по длительности равен четырем циклам тактового генератора. Какую максимальную скорость передачи данных может поддерживать этот процессор? Что будет лучше для повышения производительности: сменить его внешнюю шину данных на 32-битовую или удвоить частоту сигнала тактового генератора, поступающего на микропроцессор?
Указание: определите количество байтов, которое может быть передано при каждом цикле шины.
**Решение:**
$$
\frac{8\cdot 10^6}{4}\cdot 16bit = 4\ 000\ 000b
$$
$$
\frac{8\cdot 10^6}{4}\cdot 32bit = 8\ 000\ 000b\\
\frac{16\cdot 10^6}{4}\cdot 16bit = 8\ 000\ 000b
$$
По вычислениям не важно, число передаваемых данных одинаково.

**1.8** Контроллер DМА передает символы из внешнего устройства в основную память со скоростью 9600 бит в секунду. Процессор может выбирать команды со скоростью 1 млн команд в секунду. Насколько процессор замедлит свою работу из-за работы DМА?
**Решение:**
$$
( 1:( 1:\frac{9600/8}{10^6} ) ) \cdot 100\% = 0.12\%
$$

**2.1** Предположим, у нас есть многозадачный компьютер, в котором каждое задание имеет идентичные характеристики. В течение цикла вычисления одного задания Т половину времени занимает ввод-вывод, а вторую половину работа процессора. Для выполнения каждого задания требуется N-циклов. Допустим, что для планирования используется простой алгоритм циклического обслуживания и что ввод-вывод может выполняться одновременно с работой процессора. Определите значения следующих величин:
+ Реальное время, затрачиваемое на выполнение задания.
+ Среднее количество заданий, которые выполняются в течение одного цикла Т.
+ Доля времени, в течение которого процессор активен (не находится в режиме ожидания).

Вычислите эти значения для одного, двух и четырех одновременно выполняющихся заданий, считая, что время цикла Т распределяется одним из следующих способов.
a. В течение первой половины периода выполняется ввод-вывод, а в течение второй - работа процессора.
b. В течение первой и четвертой четвертей выполняется ввод-вывод, а в течение второй и третьей - работа процессора.
**Решение:**
**Важное замечание. В столлингсе многозадачнный рассматривается как термин Multiprogramming – A computer running more than one program at a time (like running Excel and Firefox simultaneously)**
В случае если мы имеем только 1 выполнняемую задачу(job), то это выглядит следующим образом и имеет следущие ответы.
* Реальное время = $N\cdot T$
* Среднее количество jobs за T = $\frac{1}{N}$
* Доля времени, в течение которого процессор активен = 50\%


В случае если мы имеем 2 задачи

* Реальное время = $N\cdot T$
* Среднее количество jobs за T = $\frac{2}{N}$
* Доля времени, в течение которого процессор активен = 100\%

**3.2** Предположим, что в момент времени 5 не используются никакие системные ресурсы, за исключением процессора и памяти. Теперь рассмотрим следующие события.
* В момент 5: Р1 выполняет команду чтения с дискового устройства 3
* В момент 15: Истекает квант времени Р5
* В момент 18: Р7 выполняет команду записи на дисковое устройство 3
* В момент 20: РЗ выполняет команду чтения с дискового устройства 2
* В момент 24: Р5 выполняет команду записи на дисковое устройство 3
* В момент 28: Выполняется выгрузка процесса Р5 на диск
* В момент 33: Прерывание от дискового устройства 2: чтение Р3 завершено
* В момент 36: Прерывание от дискового устройства 3: чтение Р1 завершено
* В момент 38: Процесс Р8 завершается
* В момент 40: Прерывание от дискового устройства 3: запись Р5 завершена
* В момент 44: Загрузка процесса Р5 с диска
* В момент 48: Прерывание от дискового устройства 3: запись Р7 завершена
Для каждого из моментов времени 22, 37 и 47 укажите состояние, в котором находится каждый процесс. Если процесс блокирован, укажите событие, которое к этому привело.
**Решение:**
В момент 22:
P1 -- чтение с дискового устройства 3 [wait blocked]
P3 -- чтение с дискового устройства 2 [wait blocked]
P5 -- ждет в очереди ожидания [runnable]
P7 -- запись на дисковое устройство 3 [wait blocked]
P8 -- выполняется на процессоре [on cpu]
В момент 37.
P1 -- ждет в очереди ожидания [runnable]
P3 -- ждет в очереди ожидания [runnable]
P5 -- [wait suspended]
P7 -- запись на дисковое устройство 3 [wait blocked]
P8 -- выполняется на процессоре [on cpu]
В момент 47.
P1 -- ждет в очереди ожидания [runnable]
P3 -- ждет в очереди ожидания [runnable]
P5 -- ждет в очереди ожидания [runnable]
P7 -- запись на дисковое устройство 3 [wait blocked]
P8 -- процесс завершен [exit]

| || moment № ||
| -- | ------------ | -------------- | ------------ |
| P# | 22 | 37 | 47 |
| P1 | wait blocked | runnable | runnable |
| P3 | wait blocked | runnable | runnable |
| P5 | runnable | wait suspended | runnable |
| P7 | wait blocked | wait blocked | wait blocked |
| P8 | on cpu | on cpu | exit |

**7.2** Рассмотрим схему фиксированного распределения с разделами равного размера, равного 2^16 байт, и общим количеством основной памяти 2^24 байт. Поддерживается таблица процессов, включающая указатель на раздел для каждого резидентного процесса. Сколько битов требуется для этого указателя?
**Решение:**
Всего одновременно в памяти можно разместить $\frac{2^{24}}{2^{16}}=2^8\Rightarrow ptr=8$ бит

**7.12** Рассмотрим простую страничную систему со следующими параметрами: 2^32 байт физической памяти; размер страниц - 2^10 байт; 2^16 страниц логического адресного пространства.
+ Сколько битов в логическом адресе?
+ Сколько байт в кадре?
+ Сколько битов физического адреса определяет кадр?
+ Сколько записей в таблице страниц?
+ Сколько битов в каждой записи таблицы страниц? Предполагаем, что каждая запись таблицы страниц содержит бит корректности страницы.

**Решение:**
a. 16 бит логический адрес (26?)
б. $2^{10}$ байт
в. $\frac{2^{32}}{2^{10}}=2^{22}\Rightarrow 22$ бит
г. $2^{16}$ записей
д. 22 + 1 бит

**7.14** Рассмотрим простую систему сегментации, при которой используется следующая таблица сегментов:

Начальный адрес    Длина (байты)
---------------------------
     660             248
    1752             422
     222             198
     996             604

Для каждого из следующих логических адресов определите физический адрес или
укажите, что заданный адрес ошибочен.
a. 0, 198
б. 2, 156
в. 1, 530
г. 3, 444
д. 0, 222
**Решение:**
a. $[0] + 0198 = 0660 + 0198 = 0858$
б. $[2] + 0156 = 0222 + 0156 = 0378$
в. $[1] + 0530 \Rightarrow Invalid$
г. $[3] + 0444 = 0996 + 0444 = 1440$
д. $[0] + 0222 = 0660 + 0222 = 0882$

**8.1** Предположим, что таблица страниц текущего процесса выглядит так, как показано ниже. Все числа в таблице - десятичные, вся нумерация начинается с нуля, а все адреса представляют собой адреса отдельных байтов памяти. Размер страницы равен 1024 байтам.

| Номер виртуальной страницы | Бит присутствия в памяти | Бит обращений | Бит модификации | Номер кадра |
| -------------------------- | ------------------------ | ------------- | --------------- | ----------- |
| 0 | 1 | 1 | 0 | 4 |
| 1 | 1 | 1 | 1 | 7 |
| 2 | 0 | 0 | 0 | - |
| 3 | 1 | 0 | 0 | 2 |
| 4 | 0 | 0 | 0 | - |
| 5 | 1 | 0 | 1 | 0 |

а. Опишите, как именно виртуальный адрес транслируется в физический адрес основной памяти.
б. Какой физический адрес (если таковой имеется) соответствует каждому из приведенных виртуальных адресов? (Вы не должны пытаться обработать прерывание из-за отсутствия страницы).
+ 1052
+ 2221
+ 5499

**Решение:**
а. находим номер виртуальной страницы, как сдвиг на 3 позиции вправо ( адресуется 1024 байт ) по нему находим номер кадра, прибавляем смещение от логическего адреса, не забыв сдвинуть на 3 позиции влево.
б.
**Решение**:
+ $1052 = 1:28\Rightarrow 7\cdot 1024 + 28 = 7196$
+ $2221 = 2:173\Rightarrow Page Fault$
+ $5499 = 5:379\Rightarrow 0\cdot 1024 + 379 = 379$

**8.4** Рассмотрим последовательность обращений к страницам 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2. Изобразите диаграмму, подобную показанной на рис. 8.14 и демонстрирующую распределение кадров для стратегий.
а. FIFO ("первым вошел первым вышел").
б. LRU (последний использовавшийся).
в. Часовой.
г. Оптимальный (в предположении, что последовательность обращений продолжается как 1, 2, 0, 1, 7, 0, 1).
д. Перечислите общее количество ошибок страниц и частоту промахов для каждой стратегии.
Подсчитайте количество ошибок страницы, происшедших после того, как все кадры были инициализированы.
**Решение:**

**8.6** Процесс содержит восемь виртуальных страниц на диске, и ему выделено четыре фиксированных кадра в основной памяти. Далее выполняются обращения к следующим страницам: 1, 0, 2, 2, 1, 7, 6, 7, 0, 1, 2, 0, 3, 0, 4, 5, 1, 5, 2, 4, 5, 6, 7, 6, 7, 2, 4, 2, 7, 3, 3, 2, 3.
а. Укажите последовательность размещения страниц в кадрах при использовании алгоритма замещения наиболее долго не использовавшейся страницы. Вычислите результативность обращения к основной памяти (считаем, что изначально все кадры пусты).
б. Выполните то же задание для алгоритма "первым вошел - первым вышел".
в. Сравните результативности обращения к основной памяти, вычисленные в первых двух заданиях, и прокомментируйте эффективность использования ука занных алгоритмов применительно к данной последовательности обращений.
**Решение:**
Аналогично 8.4

**8.10** Предположим, что размер страницы занимает 4 Кбайт и что запись таблицы страниц занимает 4 байт. Сколько уровней таблиц страниц потребуется для отображения 64-битового адресного пространства, если таблица верхнего уровня занимает одну страницу?
**Решение:**
Одна запись таблицы страниц занимает 4 байт, следовательно, каждая запись на последнем уровне адресует $2^{4\cdot8} = 2^{32}$ кадров. Размер одного кадра ( страницы ) -- 4096 байт, т.е., чтобы адресовать по конкретному байту одного кадра достаточно $log_24096 = 12$ бит. Т.е. из адреса уже можно выкинуть 12 бит под смещение. Остается $64 - 12 = 52$ бит под адреса в таблицах страниц. Для таблицы верхнего уровня нам нужно уметь адресовать $4096 / 4 = 1024$ записи, поэтому достаточно 10 бит. Следовательно под остальные уровни остается от адреса $52 - 10 = 42$ бит. Если предположить, что размеры следующих таблиц также около размера страницы, то нужно еще откусить на 4 таблицы по 10-12 бит. Итого: 5 уровней.
**Ответ:** 5.

**8.17** Предположим, что задание разделено на четыре сегмента одинакового размера и что для каждого сегмента система строит таблицу дескрипторов страниц с восемью записями. Таким образом, описанная система представляет собой комбинацию сегментации и страничной организации. Предположим также, что размер страницы равен 2 Кбайт.
а. Чему равен максимальный объем каждого сегмента?
б. Каково максимальное логическое адресное пространство одного задания?
в. Предположим, что рассматриваемое задание обратилось к ячейке памяти с физическим адресом 00021АВС[32]. Каков формат генерируемого для этого логического адреса? Каково максимально возможное физическое адресное пространство в этой системе?
**Решение:**
а. $2 Кбайт \cdot 8 = 16$ Кбайт
б. $16 Кбайт \cdot 4 = 64$ Кбайт
в. 16 на каждое задание + 2 бит на сегмент + 3 бит на номер страницы + 11 бит смещение = логический адрес. $2^{32} байт = 4 Гб$

**9.16**
Пять пакетных заданий, от А до Е, поступают в вычислительный центр одновременно. Их ожидаемое время работы - 15, 9, 3, 6 и 12 минут соответственно. Их приоритеты, определенные при передаче заданий, равны соответственно 6, 3, 7, 9 и 4, причем меньшее значение означает более высокий приоритет. Для каждого из перечисленных ниже алгоритмов определите время оборота каждого процесса и среднее время оборота всех процессов. Накладные расходы, связанные с переключением процессов, не учитываются. Поясните, как вы пришли к данному ответу. В трех последних случаях предполагается, что в определенный момент времени работает только один процесс, вытеснения не происходит и все задания
ориентированы на вычисления.
а. Круговое планирование с размером кванта, равным 1 минуте.
б. Планирование с учетом приоритетов.
в. FCFS при запуске процессов в следующем порядке: 15, 9, 3, 6 и 12.
г. Первым выполняется самое короткое задание
**Решение:**
а.

 A  B  C  D  E  5
 A  B  C  D  E  5
 A  B  C  D  E  5
 A  B     D  E  4
 A  B     D  E  4
 A  B     D  E  4
 A  B        E  3
 A  B        E  3
 A  B        E  3
 A           E  2
 A           E  2
 A           E  2
 A              1
 A              1
 A              1
45 36 15 27 42 45

A: $1\cdot 15 + 3\cdot ( 4 + 3 + 2 + 1 + 0 ) = 45$
B: 35
C: 13
D: 26
E: 42
Total: $\frac{1}{5}( 45 + 35 + 13 + 26 + 42 ) = 32.2$

б.

 B B B B B  5
 B B B B E 10
 E E E E E 15
 E E E E E 20
 E A A A A 25
 A A A A A 30
 A A A A A 35
 A C C C D 40
 D D D D D 45

A: $9 + 12 + 15 = 36$
B: $9$
C: $3 + 36 = 39$
D: $39 + 6 = 45$
E: $9 + 12 = 21$
Total: $\frac{1}{5}( 36 + 9 + 39 + 45 + 21 ) = 30$

в.
A: $15$
B: $24$
C: $27$
D: $33$
E: $45$
Total: $\frac{1}{5}( 15 + 24 + 27 + 33 + 45 ) = 28.8$

г.

 С  С  C  D  D   5
 D  D  D  D  B  10
 B  B  B  B  B  15
 B  B  B  E  E  20
 E  E  E  E  E  25
 E  E  E  E  E  30
 A  A  A  A  A  35
 A  A  A  A  A  40
 A  A  A  A  A  45

A: $15 + 12 + 9 + 6 + 3 = 45$
B: $9 + 9 = 18$
C: $3$
D: $3 + 6 = 9$
E: $3 + 6 + 9 + 12 = 30$
Total: $\frac{1}{5}( 45 + 18 + 3 + 9 + 30 ) = 21$

**11.7** Рассчитайте количество дискового пространства (в секторах, дорожках и поверхностях), необходимого для хранения 300 000 120-байтных логических записей, если диск разбит на секторы размером 512 байт, с 96 секторами на дорожке, 110 дорожками на поверхности и 8 используемыми поверхностями. Служебные записи о файле во внимание не принимайте; считайте также, что запись не может быть разбита и размещена на двух секторах.
**Решение:**
Всего нужно: $300000\cdot 120 = 36\cdot 10^6$ byte

**11.12** Рассмотрим RАID-массив из четырех 200-гигабайтных дисков. Какова доступная для хранения данных емкость в случае использования каждого из уровней RAID - 0,1, 3, 4, 5, 6?
**Решение:**
RAID0: $4 \cdot 200 = 800 Gb$
RAID1: $2 \cdot 200 = 400 Gb$
RAID3: $3 \cdot 200 = 600 Gb$
RAID4: $3 \cdot 200 = 600 Gb$
RAID5: $3 \cdot 200 = 600 Gb$
RAID6: $2 \cdot 200 = 400 Gb$

**12.7** Игнорируя накладные расходы на дескрипторы каталогов и файлов, рассмотрите файловую систему, в которой файлы хранятся в блоках размером 16 Кбайт. Для каждого из следующих размеров файлов рассчитайте процент потерянного файлового пространства из-за неполного заполнения последнего блока: 41 600, 640 000, 4 064 000 байт.
**Решение:**
1. $\frac{(3 \cdot 16\cdot 1024 - 41600)}{3 \cdot 16\cdot 1024}\cdot 100\% = 15.36\%$
2. $\frac{(40 \cdot 16\cdot 1024 - 640000)}{40 \cdot 16\cdot 1024}\cdot 100\% = 0.16\%$
3. $\frac{(249 \cdot 16\cdot 1024 - 4064000)}{249 \cdot 16\cdot 1024}\cdot 100\% = 0.38\%$

**12.12** В UNIX System V длина блока составляет 1 Кбайт, а каждый блок может содержать до 256 адресов блоков. Каков максимальный размер файла при использовании схемы индексных узлов?
**Решение:**
$$
1\ \text{Kbyte} \cdot \left( 12\ \text{direct blocks} + 256 \left( 1\ \text{ib_0} + 256\ \text{ib_1} + 256 \cdot 256\ \text{ib_2}\right)\right) \approx 16\ \text{Gbyte}
$$

**12.13** Рассмотрим организацию файлов UNIX, представленную на рис. 12.15. Пусть в каждом узле содержится 12 прямых указателей блоков, а также одинарный, двойной и тройной указатели. Далее положим, что размер системного блока и размер дискового сектора равны 8 Кбайт. Допустим, что размер указателя дискового блока – 32 бита (8 бит для указания физического диска и 24 бита для указания физического блока).
*а.* Какой максимальный размер файла, поддерживаемый в этой системе?
*б.* Какой максимальный размер раздела файловой системы, поддерживаемого в этой системе?
*в.* Предположим, что в основной памяти не содержится ничего, кроме индексного узла. Сколько обращений к диску потребуется для доступа к байту в позиции 13 423 956?
**Решение:**
$$
NumberOfBlocksInIndex = 8192\ \text{byte}:\frac{32\ \text{bit}}{8} = 2048
$$
*а.* $8\ \text{Kbyte}\cdot (12 + 2048 + 2048^2 + 2048^3 ) \approx 64\ \text{Tbyte}$
*б.* $8\ \text{Kbyte} \cdot 2^{32 - 8} = 128\ \text{Gbyte}$
*в.* $\frac{13423956 - 12\cdot 8\cdot 1024}{2048\cdot 8\cdot 1024} < 1\Rightarrow$ байт можно найти, воспользовавшись косвенным одинарным указателем на данные. 1 для взятия блока первого указателя + 1 для взятия блока с данными по указателю. **2**

## Прошлый год
**Решение:**

  +---+----+  +---+----+  +---+----+  +---+----+  +---+----+
1 | C | IO |  | C | IO |  | C | IO |  | C | IO |  | C | IO |
  +---+----+  +---+----+  +---+----+  +---+----+  +---+----+
      +---+----+  +---+----+  +---+----+  +---+----+  +---+----+
2     | C | IO |  | C | IO |  | C | IO |  | C | IO |  | C | IO |
      +---+----+  +---+----+  +---+----+  +---+----+  +---+----+
          +---+----+  +---+----+  +---+----+  +---+----+  +---+----+
3         | C | IO |  | C | IO |  | C | IO |  | C | IO |  | C | IO |
          +---+----+  +---+----+  +---+----+  +---+----+  +---+----+
        
--+---+---++--++--++--++--++--++--++--++--++--++--++--++--++--++---+
  0   6   12  18  24  30  36  42  48  54  60  66  72  78  84  90   97

**Ответ:** 5


$$
Records = \frac{2048}{142} \approx 14\\
Offset = 2048 - 14\cdot 142 = 60\ byte\\
Total = 2299\cdot 60 + ( 2048 - 7\cdot 142 ) \approx 135,7\ KByte
$$