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

Вариант 1

 

  1. (6 баллов) Возможны ли следующие переходы процесса из одного состояния в другое?
     
    1. Из состояния готовность в состояние исполнение
      2.
    2. Из состояния ожидание в состояние исполнение
      3.
    3. Из состояния готовность в состояние ожидание

      4.  

    Если переход возможен, кратко сформулируйте, когда он происходит. Если невозможен, напишите почему.
  2. (3 балла) Кратко сформулируйте разницу между программой и процессом.

    3.  
  3. (12 баллов) Пусть в вычислительную систему поступают пять процессов различной длительности по следующей схеме:
     

    Номер процесса

    Время поступления в систему

    Время исполнения

    1

    3

    4

    2

    7

    8

    3

    4

    6

    4

    10

    1

    5

    0

    5

    Вычислите среднее время между стартом процесса и его завершением (turnaround time) и среднее время ожидания процесса (waiting time) для каждого из трех алгоритмов планирования FCFS (First Come First Served), RR (Round Robin) и SJF (Short Job First). При вычислениях считать, что процессы не совершают операций ввода-вывода, величину кванта времени принять равной 1, временем переключения контекста пренебречь. Процесс, поступающий в систему, считать готовым к исполнению в момент поступления. Для алгоритма RR принять, что вновь прибывший процесс помещается в начало очереди процессов, готовых к исполнению, и, следовательно, сразу выбирается на исполнение.

  4. (3 балла) Дайте краткое определение термина "критическая секция процесса".

    5.  
  5. (18 баллов) Рассмотрим следующее программное решение для прохождения процессами своих критических участков:
    6.

    int c1 = 1, c2 = 1, turn; /* Разделяемые переменные */

    Процесс P1:
     
    while(1){

    turn = 1;
    c1 = 0;
    while (!c2 && turn == 1);
    < критический участок 1>
    c1 = 1;
    < другие операции 1>
     }

    Процесс P2:
     
    while(1){

    turn = 2;
    c2 = 0;
    while (!c1 && turn == 2);
    < критический участок 2>
    c2 = 1;
    < другие операции 2>
     }

    Всем ли требованиям к алгоритмам синхронизации (mutual exclusion, progress, bound waiting) удовлетворяет данное решение? Обоснуйте свои утверждения.

  6. (5 баллов) В вычислительной системе со страничной организацией памяти из 32-х бит адреса старшие 6 его бит отводятся для номера страницы.
     
    1. Какое максимальное количество страниц может иметь процесс? Каков размер страницы?
    2. Для некоторого процесса таблица страниц имеет вид:

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

    Начальный адрес

    0

    0x4000000

    1

    0xC000000

    2

    0x8000000

    3

    0x0000000

    Каким физическим адресам соответствуют адреса виртуальной памяти 0х1234, 0x10000000, 0x03ab00de?
  7. (9 баллов) Для некоторого процесса известна следующая строка запросов страниц памяти

    7, 2, 0, 3, 2, 0, 3, 1, 2, 7, 4, 1, 7, 0, 7

    Сколько ситуаций отказа страницы (page fault) возникнет для данного процесса при каждом из трех алгоритмов замещения страниц - FIFO (Fist Input Fist Output) , LRU (the Least Recently Used), OPT (optimal) , если процессу выделено 3 кадра памяти?

  8. (15 баллов) Рассмотрим вычислительную систему со страничной организацией памяти, на которой выполняется одна программа, несколько раз последовательно сканирующая большой одномерный массив данных (это означает, что для массива, занимающего, например, в памяти четыре страницы, строка запроса страниц выглядит следующим образом: 1, 2, 3, 4, 1, 2, 3, 4, ...). Для каждого из трех алгоритмов замещения страниц - FIFO (First Input First Output), LRU (the Least Recently Used) и OPT (OPTimal) нарисуйте график зависимости частоты page faults от размеров массива. По оси y откладывается отношение числа page faults к длине строки запроса (если массив, занимающий четыре страницы памяти, сканируется 2 раза, то длина строки запроса равна 8), по оси x - размер массива: от размеров, требующих одну страницу, и до размеров, значительно превыщающих размер физической памяти. Опишите наиболее характерные точки на графике.

    9.