Контрольная работа 1-07 Вариант 03 (решения) - davaiknam.ru o_O
Главная
Поиск по ключевым словам:
страница 1
Похожие работы
Название работы Кол-во страниц Размер
Контрольная работа по дисциплине Математика 1 76.72kb.
Контрольная работа по курсу «Социология» Вариант 8 1 106.66kb.
Контрольная работа по английскому языку для 9 класса Часть А 1 31.71kb.
Контрольная работа Конт зольная работа Вариант задач 1 и 2 Номера... 4 465.7kb.
Контрольная работа №1 5 appendix 28 контрольная работа №2 39 appendix... 5 683.62kb.
Контрольная работа вариант 9 Задание 1 1 176.41kb.
Контрольная работа №1, домашняя контрольная работа №2 (№1 №4) 1 26.97kb.
Контрольная работа по Новой истории 1 вариант. Часть 1 1 61.67kb.
Контрольная работа 7 класс Вариант 1 Задание А 1 45.79kb.
Контрольная работа № по дисциплине Вариант № Выполнил(а) студент(ка) 5 559.96kb.
Контрольная работа №2 «Квадратичная функция. Степенная функция» (9... 1 48.17kb.
Министерство транспорта 1 58.82kb.
Направления изучения представлений о справедливости 1 202.17kb.

Контрольная работа 1-07 Вариант 03 (решения) - страница №1/1

Контрольная работа 1-07

Вариант 03 (решения)

За разговоры с соседом — –3 балла за каждый разговор.



  1. (14 баллов) Рассмотрим однопроцессорную вычислительную систему с объемом оперативной памяти 200 Mb, в которой используется схема организации памяти с динамическими (переменными) разделами. Для долгосрочного планирования процессов в ней применен алгоритм FCFS. В систему поступают пять заданий с различной длительностью и различным объемом занимаемой памяти по следующей схеме:

Номер задания

Момент поступления в очередь заданий

Время исполнения (CPU burst)

Объем занимаемой памяти

1

0

3

80 Mb

2

2

5

60 Mb

3

3

4

60 Mb

4

4

2

80 Mb

5

5

1

20 Mb

Вычислите среднее время между стартом задания и его завершением (turnaround time) и среднее время ожидания (waiting time) для следующих комбинаций алгоритмов краткосрочного планирования и стратегий размещения процессов в памяти:

  1. RR (Round Robin) и first fit (первый подходящий);

  2. RR и best fit (наиболее подходящий);

  3. вытесняющий SJF (Short Job First) и first fit;

  4. вытесняющий SJF и best fit.

При вычислениях считать, что процессы не совершают операций ввода-вывода, величину кванта времени принять равной 1. Временами переключения контекста, рождения процессов и работы алгоритмов планирования пренебречь. Освобождение памяти, занятой процессами, происходит немедленно по истечении их CPU burst. Краткосрочное планирование осуществляется после рождения новых процессов в текущий момент времени. Для алгоритма RR принять, что родившиеся процессы добавляются в САМЫЙ конец очереди готовых процессов (ПОСЛЕ процесса, перешедшего в состояние готовность из состояния исполнение в это время).

Решение:

    1. Рассмотрим выполнение процессов в системе для алгоритма RR и стратегии first fit. По вертикали в таблице отложены номера процессов, по горизонтали — промежутки времени. Столбец 0 соответствует временному интервалу от 0 до 1. Буква «И» означает состояние исполнения, буква «Г» — состояние готовности, буква «О» — ожидание в очереди заданий. Под таблицей приведено распределение памяти, а еще ниже — содержимое очереди заданий.




0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

1

И

И

И





































2







Г

И

Г

И

Г

И

Г

И

Г

И










3










Г

И

Г

И

Г

И

Г

И













4













О

О

О

О

О

О

О

Г

И

Г

И

5
















О

О

О

О

О

О

Г

Г

И




 

80 P1

80 P1

80 P1

60 P3

60 P3

60 P3

60 P3

60 P3

60 P3

60 P3

60 P3

80 P4

80 P4

80 P4

80 P4

20

20

20

20

20

20

20

20













120

120

60 P2

60 P2

60 P2

60 P2

60 P2

60 P2

60 P2

60 P2

60 P2

60 P2

60

60

120

60

60

60

60

60

60

60

60

60

20 P5

20 P5

20 P5

40

40

40





0

1

2

3

4

5

6

7

8

9

10

11

12

13

14













P4

P4

P4

P4

P4

P4

P4




























P5

P5

P5

P5

P5

P5













Среднее время между стартом задания и его завершением: tt = (3 + 10 + 8 + 11 + 9)/5 = 8.2.
Среднее время ожидания: wt = (0 + 5 + 4 + 9 + 8)/5 = 5.2.

    1. Рассмотрим выполнение процессов в системе для алгоритма RR и стратегии best fit.




0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

1

И

И

И





































2







Г

И

Г

И

Г

Г

И

Г

Г

И

Г

Г

И

3










Г

И

Г

Г

И

Г

Г

И

Г

Г

И




4













Г

Г

И

Г

Г

И
















5
















О

О

О

О

О

Г

Г

И







 

80 P1

80 P1

80 P1

80

80 P4

80 P4

80 P4

80 P4

80 P4

80 P4

20 P5

20 P5

20 P5

80

80



















60

60

60







120

120

60 P2

60 P2

60 P2

60 P2

60 P2

60 P2

60 P2

60 P2

60 P2

60 P2

60 P2

60 P2

60 P2

60

60 P3

60 P3

60 P3

60 P3

60 P3

60 P3

60 P3

60 P3

60 P3

60 P3

60 P3

60





0

1

2

3

4

5

6

7

8

9

10

11

12

13

14
















P5

P5

P5

P5

P5





























































Среднее время между стартом задания и его завершением: tt = (3 + 13 + 11 + 6 + 8)/5 = 8.2.
Среднее время ожидания: wt = (0 + 8 + 7 + 4 + 7)/5 = 5.2.

    1. Рассмотрим выполнение процессов в системе для вытесняющего алгоритма SJF и стратегии first fit.




0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

1

И

И

И





































2







Г

Г

Г

Г

Г

Г

Г

Г

И

И

И

И

И

3










И

И

И

И

























4













О

О

О

Г

И

И
















5
















О

О

И






















 

80 P1

80 P1

80 P1

60 P3

60 P3

60 P3

60 P3

80 P4

80 P4

80 P4

80

80

80

80

80

20

20

20

20

























120

120

60 P2

60 P2

60 P2

60 P2

60 P2

60 P2

60 P2

60 P2

60 P2

60 P2

60 P2

60 P2

60 P2

60

60

60

60

60

20 P5

60

60

60

60

60

60

60

40



0

1

2

3

4

5

6

7

8

9

10

11

12

13

14













P4

P4

P4








































P5

P5

























Среднее время между стартом задания и его завершением: tt = (3 + 13 + 4 + 6 + 3)/5 = 5.8.
Среднее время ожидания: wt = (0 + 8 + 0 + 4 + 2)/5 = 2.8.

    1. Рассмотрим выполнение процессов в системе для вытесняющего алгоритма SJF и стратегии best fit.




0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

1

И

И

И





































2







Г

Г

Г

Г

Г

Г

Г

Г

И

И

И

И

И

3










И

Г

Г

Г

И

И

И
















4













И

И




























5
















О

И

























 

80 P1

80 P1

80 P1

80

80 P4

80 P4

20 P5

80

80

80

80

80

80

80

80







60

























120

120

60 P2

60 P2

60 P2

60 P2

60 P2

60 P2

60 P2

60 P2

60 P2

60 P2

60 P2

60 P2

60 P2

60

60 P3

60 P3

60 P3

60 P3

60 P3

60 P3

60 P3

60

60

60

60

60





0

1

2

3

4

5

6

7

8

9

10

11

12

13

14
















P5









































































Среднее время между стартом задания и его завершением: tt = (3 + 13 + 7 + 2 + 2)/5 = 5.4.
Среднее время ожидания: wt = (0 + 8 + 3 + 0 + 1)/5 = 2.4.

Оценка:

За каждый алгоритм со стратегией — по 3 балла. Если времена нахождения в очереди заданий включены в подсчет времен — еще 2 балла на всю задачу



  1. (12 баллов) При завершении пребывания в санатории отдыхающие должны получить отметки в санаторной карте от библиотекаря и физрука о сданном инвентаре, после чего с этими отметками посетить главврача. Если отдыхающему необходимо получить несколько отметок, то сначала он идет в кабинет, к которому очередь меньше. Используя классические очереди сообщений, постройте корректную модель работы выписки из санатория, описав поведение каждого отдыхающего с помощью отдельного процесса. Классические очереди сообщений используют примитивы send(A,message) и receive(A,message), где A - имя очереди сообщений.

Примечание: Допускается создание дополнительного инициализирующего процесса, заносящего сообщения в очереди сообщений до пробуждения отдыхающих.

Возможное решение:

Заводим 4 очереди сообщений F (для посещения физрука), B (для посещения библиотекаря), G(для посещения главврача) и Lock —для ограничения доступа к общим данным. Введем обозначения:

send(Q, ) для отправки сообщения, содержащего значения переменных A, B, C, в очередь сообщений Q;

receive(Q, ) для приема сообщения из очереди сообщений Q и размещения содержащейся в нем информации в переменные A, B, C.



Инициализирующий процесс:

send(Lock, <0, 0>); send(G,<>); send(F,<>); send(B,<>);



Процесс пациент:

int Nf, Nb;

receive(Lock, );

if(Nf < Nb){

Nf++; send(Lock, ); receive(F, <>); Посещение физрука;

receive(Lock, ); Nf--; Nb++; send(Lock, ); send(F, <>);

Nb++; send(Lock, ); receive(B, <>); Посещение библиотекаря;

receive(Lock, ); Nb--; send(Lock, ); send(B, <>);

} else {

Nb++; send(Lock, ); receive(B, <>); Посещение библиотекаря;

receive(Lock, ); Nb--; Nf++; send(Lock, ); send(B, <>);

Nf++; send(Lock, ); receive(F, <>); Посещение физрука;

receive(Lock, ); Nf--; send(Lock, ); send(F, <>);

}

receive(G, < >); Посещение главврача; send(G, <>);



Оценка:

Грубые ошибки: нет взаимоисключения, тупиковые ситуации, не получение одной отметки—  –8 баллов, средней тяжести: циклы ожидания, возможность бесконечного ожидания одним из отдыхающих — –4 балла. Полный балл только за полностью корректное решение.



  1. (6 баллов) В вычислительной системе с сегментно-страничной организацией памяти и 32-х битовым адресом максимальный размер сегмента составляет 4 Mb, а размер страницы памяти 512 Kb. Для некоторого процесса в этой системе таблица сегментов имеет вид:

Номер сегмента

Длина сегмента

0

0x180000

1

0x080000

Таблицы страниц, находящихся в памяти, для сегментов 0 и 1 приведены ниже:

Сегмент 0




Сегмент 1

Номер страницы

Номер кадра

(десятичный)






Номер страницы

Номер кадра

(десятичный)



0

18




0

32

3

0




1

63

Каким физическим адресам соответствуют логические адреса: 0x000f0236, 0х00470111, 0x00502005?

Решение:

4 Mb — это 222 байт, т.е. под номер сегмента в логическом адресе отводится 10 бит, а 22 бита — под смещение внутри сегмента. Размер страницы 512 Kb — это 219 байт, т.е. из смещения внутри сегмента 19 бит отводится под смещение внутри страницы, а 3 бита — под номер страницы.



0x000f0236 —> сегмент 0, смещение 0x0f0236 —> сегмент 0, страница 1, смещение 0x00070236 —>page fault,
0x00470111 —> сегмент 1, смещение 0x070111 —> сегмент 1, страница 0, смещение 0x00070111 —>  кадр 32, смещение 0x00070111—> кадр 0x20, смещение 0x00070111—> 0x01000000+0x00070111—> 0x01070111,
0x00502005 —> сегмент 1, смещение 0x102005 —> смещение больше размера сегмента —> error.

Оценка: По 2 балла за адрес:

  1. (6 баллов) Ответьте на следующие вопросы:

  1. Что понимается под термином «внешняя фрагментация» в различных схемах выделения процессам оперативной памяти? В каких известных вам схемах она возникает?

  2. В чем заключается разница между процессом и нитями исполнения (thread’ами), реализованными на уровне ядра ОС?

Решение:

  1. Под термином «внешняя фрагментация» в мультипрограммных вычислительных системах по отношению к схемам выделения памяти обычно понимается явление, когда в оперативной памяти между занятыми участками возникают свободные участки, не приписанные никакому процессу, которые, в силу своей малости, не могут быть задействованы. Из рассматриваемых в курсе схем выделения памяти внешней фрагментации подвержены схема с динамическими разделами и сегментная организация памяти.

  2. В системах, поддерживающих нити исполнения на уровне ядра, thread’ы представляют собой единицы исполнения, а процессы — единицы выделения ресурсов. Процесс представляется как совокупность взаимодействующих нитей и выделенных ему ресурсов. Нити процесса разделяют его программный код, глобальные переменные и системные ресурсы, но каждая нить имеет свой собственный программный счетчик, свое содержимое регистров и свой собственный стек. Планирование использования процессора происходит в терминах нитей, а управление памятью и другими системными ресурсами остается в терминах процессов.

Оценка:

За каждый пункт предполагается по 3 балла.



В пункте a): если нет четкого понимания термина «внешняя фрагментация» —  –2 балла.




Знание — принудительно, вера — свободна. Николай Бердяев
ещё >>