Главная страница
Навигация по странице:

  • 1.3. Выполнение работы

  • Средневзвешенное время обращения W = 1,9382143 .

  • Сводная таблица

  • Средневзвешенное время обращения W = 1,5472024 .

    		•

    Операционные сети. Курсовая ОС Исаенко (last). Планирование верхнего уровня управления заданиями


    Скачать 217.5 Kb.
    НазваниеПланирование верхнего уровня управления заданиями
    АнкорОперационные сети
    Дата12.05.2023
    Размер217.5 Kb.
    Формат файлаdoc
    Имя файлаКурсовая ОС Исаенко (last).doc
    ТипДокументы
    #1124697
    страница1 из 2
      1   2

    Раздел 1. Планирование верхнего уровня управления заданиями




    1.1. Общие сведения о планировании заданий



    Функцией службы управления процессом является распределение аппаратных ресурсов центрального процессора.

    Можно выделить следующие компоненты этой службы:

    – планировщик заданий,

    – планировщик задач (планировщик процессов).

    Задание представляет собой описание комплекса работ, которые пользователь хочет выполнить на ЭВМ. Этот комплекс может быть представлен в виде последовательности некоторых частных работ, описываемых с помощью шагов задания. Из шагов задания формируются задачи. Для выполнения задач система создает процессы.

    Объектами работы планировщика заданий являются задания, а планировщик задач управляет процессами.

    Планировщик заданий выбирает, какие задания и в какой последовательности должны поступать на обработку (своего рода «макропланировщик»).

    Планировщик задач выступает в роли «микропланировщика», распределяющего процессор между процессами.

    В случае мультипрограммирования планировщик заданий выбирает несколько заданий из множества всех представленных и вводит их в систему. Для каждого задания формируется таблица задания JCB (Job Control Block).

    Для программного выполнения этих заданий планировщик заданий создает процессы и выделяет им необходимые ресурсы (память, внешние устройства).

    Планировщик процессов должен решить, какому из созданных процессов предоставить процессор, в какой момент и на какое время.

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

    Дисциплины обслуживания


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

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

    Классификация дисциплин обслуживания приведена на рис.1.

    В

    Рис. 1. Классификация дисциплин обслуживания.

    настоящей работе рассматриваются 2 дисциплины обслуживания:

    1 - линейная дисциплина обслуживания FIFO (First In – First Out). Из очереди заявок на обслуживание выбирается заявка, поступившая в очередь первой.

    2 - дисциплина обслуживания с фиксированным приоритетом SJF (Short Job First). Из очереди заявок на обслуживание выбирается заявка с минимальным временем обслуживания.

    Оценки эффективности планирования


    Существует несколько оценок эффективности планирования. Одной из них является время обращения задания – время, прошедшее с момента поступления задания в систему до момента завершения его выполнения.

    t = tЗ – tП, где

    t – время обращения задания,

    tЗ – время завершения задания,

    tП – время поступления задания.

    Но эта оценка не является универсальной. Например, если сравнивать время обращения одночасового и одноминутного задания (при условии, что задания начнут выполняться сразу же, как только поступят в систему), то время обращения одночасового задания будет значительно больше, чем время обращения одноминутного. Но это совсем не значит, что одночасовое задание было обслужено плохо, т.к. время обращения задания не может быть меньше времени выполнения.

    Более универсальной оценкой, позволяющей сравнивать между собой задания любой длины, является взвешенное время обращения

    W = (tЗ – tП) / T, где

    W – взвешенное время обращения,

    T – действительное время выполнения задания.

    Для случая M заданий можно провести оценку по среднему взвешенному времени обращения



    WСР – средневзвешенное время обращения,

    Wi – взвешенное время обращения i -го задания,

    M – количество заданий.

    1.2. Задание и исходные данные




    Задание


    Вычислительная система располагает оперативной памятью (ОП) V и внешним объемом памяти Н (НМД). ОП память выделяется перемещаемым разделами, которые исключают влияние фрагментации. Реали­зуется режим мультипрограммирования: если одновременно выполня­ется несколько задач, то процессорное время распределяется между ними равномерно. В систему поступает поток из М заданий, очеред­ное задание поступает через время ti, для простоты каждое задание состоит из одной задачи и требует объем ОП - vi, объем внешней памяти hi, процессорное время. Каждое задание использует свою внешнюю память только для ввода данных в течение времени q*hi , после чего начинается счет. Однако закрепленные за каждым заданием носители освобождаются только после завершения задания. Предположим, возможно параллельное использование внешней памяти заданиями без задержки друг друга. Если бы задания выполнялись по одному, то на каждое задание было бы затрачено время Тi = q*hi + ti. Вновь поступившие задания помещаются в очередь. Для выбора заданий из очереди на выполнение используются два алгоритма:

     

    1)среди заданий в очереди, для которых достаточно свободных ре­сурсов, выбирается задание, поступившее первым (правило FIFO);

    2)среди заданий в очереди, для которых достаточно свободных ре­сурсов, выбирается задание с наименьшим ti (правило SJF).

     

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

    ,

    где - время завершения задания,

    - время поступления задания в систему.

    Для нормирования различных вариантов последовательностей заданий используется набор из 10 типов задач (см. таблицу 1). Каждое задание включает одну из этих 10 задач. В одном потоке заданий могут встретиться задания, содержащие одинаковые задачи. Номер задачи Кi для очередного задания определяется по формулам:

    Xi = [7 * Xi-1 + 417] mod 1000;

    Ki = [Xi / 7] mod 10, i=1M, Xo = N,

    где [c] - целая часть числа с,

    y mod z - остаток от деления y на z,

    Xo = N - шифр (последние три цифры из зачетной книжки; если четное число, то +1, чтобы получилось нечетное).

    Значение используемых параметров : V=16, H=12, q=5, M=10, последовательность периодов времени (интервал поступления заданий) ti=ki .
    N = 711
    X0=711
    X1 = [7 * 711 + 417] mod 1000 = 394

    K1 = [394/ 7] mod 10 = 6
    X2 = [7 * 394 + 417] mod 1000 = 175

    K2 = [175/ 7] mod 10 = 5
    X3 = [7 * 175+ 417] mod 1000 = 642

    K3 = [642 / 7] mod 10 = 1
    X4 = [7 * 642 + 417] mod 1000 = 911

    K4 = [911/ 7] mod 10 = 0
    X5 = [7 * 911 + 417] mod 1000 = 794

    K5 = [794 / 7] mod 10 = 3
    X6 = [7 * 794 + 417] mod 1000 = 975

    K6 = [975 / 7] mod 10 = 9
    X7 = [7 * 975 + 417] mod 1000 = 242

    K7 = [242/ 7] mod 10 = 4
    X8 = [7 * 242 + 417] mod 1000 = 111

    K8 = [111 / 7] mod 10 = 5
    X9 = [7 * 111 + 417] mod 1000 = 194

    K9 = [194 / 7] mod 10 = 7
    X10 = [7 * 194 + 417] mod 1000 = 775

    K10 = [775/ 7] mod 10 = 0

    Таблица 1.


    K
    0
    1
    2
    3
    4
    5
    6
    7
    8
    9

    v
    6
    3
    2
    4
    3
    5
    7
    9
    4
    1

    h
    2
    4
    3
    1
    2
    0
    4
    1
    6
    3



    70
    90
    40
    10
    60
    30
    20
    30
    40
    50

    Исходные данные



    Последовательность заданий задается таблицей:

    № задания
    X
    K
    t поступ.
    v
    h
    τ
    t загр. (q*h)
    T

    1
    394
    6
    6
    7
    4
    20
    20
    40

    2
    175
    5
    11
    5
    0
    30
    0
    30

    3
    642
    1
    12
    3
    4
    90
    20
    110

    4
    911
    0
    12
    6
    2
    70
    10
    80

    5
    794
    3
    15
    4
    1
    10
    5
    15

    6
    975
    9
    24
    1
    3
    50
    15
    65

    7
    242
    4
    28
    3
    2
    60
    10
    70

    8
    111
    5
    33
    5
    0
    30
    0
    30

    9
    194
    7
    40
    9
    1
    30
    5
    35

    10
    775
    0
    40
    6
    2
    70
    10
    80



    Значение используемых параметров: V=16, H=12, q=5, M=10, последовательность периодов времени (интервал поступления заданий) ti=ki .
    1.3. Выполнение работы

    1.3.1. Алгоритм FIFO

    Трассировка



    16
    12

    время
    событие
    V
    H

    6
    поступило задание 1. (7, 4)- начало загрузки (1). Процессор простаивает.
    9
    8

    11
    поступило задание 2. (5, 0)- загрузка не требуется.
    4
    8

    12
    поступило задание 3. (3, 4)- начало загрузки (3). Задания на процессоре: 2
    1
    4

    12
    поступило задание 4. (6, 2)- нехватка ресурсов, ожидание.
    1
    4

    15
    поступило задание 5. (4, 1)- нехватка ресурсов, ожидание.
    1
    4

    24
    поступило задание 6. (1, 3)- начало загрузки (6).
    0
    1

    26
    завершена загрузка (1). Задания на процессоре: 1, 2
    0
    1

    28
    поступило задание 7. (3, 2)- нехватка ресурсов, ожидание.
    0
    1

    32
    завершена загрузка (3). Задания на процессоре: 1, 2, 3
    0
    1

    33
    поступило задание 8. (5, 0)- нехватка ресурсов, ожидание
    0
    1

    39
    завершена загрузка(6). Задания на процессоре: 1, 2, 3, 6
    0
    1

    40
    поступило задание 9. (9, 1)- нехватка ресурсов, ожидание.
    поступило задание 10. (6, 2)- нехватка ресурсов, ожидание.
    0
    1

    41
    завершение задания 2. (5, 0)+ освобождение ресурсов.
    Задания на процессоре: 1, 3, 6
    5
    1

    41
    начало загрузки (5). (4, 1)-
    1
    0

    46
    завершение задания 1. (7, 4)+ освобождение ресурсов.

    8
    4

    46
    начало загрузки (4). (6, 2)-. Завершена загрузка (5).
    Задания на процессоре: 3, 5, 6
    2
    2

    56
    завершение задания 5. (4, 1)+ освобождение ресурсов.
    Завершена загрузка (4). Задания на процессоре: 3, 4, 6
    6
    3

    56
    начало загрузки (7). (3, 2)-
    3
    1

    66
    завершена загрузка(7). Задания на процессоре: 3, 4, 6, 7
    3
    1

    89
    завершение задания 6. (1, 3)+ освобождение ресурсов.
    Задания на процессоре: 3, 4, 7
    4
    4

    122
    завершение задания 3. (3, 4)+ освобождение ресурсов. Задания на процессоре: 4, 7
    7
    8

    122
    начало работы (8), загрузки не требует. (5, 0)-.
    Задания на процессоре: 4, 7, 8
    2
    8

    126
    завершение задания 4. (6, 2)+. Завершение задания 7.
    (3, 2)+. Задания на процессоре: 8
    11
    12

    126
    начало загрузки (9). (9, 1)-
    2
    11

    131
    завершена загрузка (9). Задания на процессоре: 8, 9
    2
    11

    152
    завершение задания 8. (5, 0)+ Задания на процессоре: 9
    7
    11

    152
    начало загрузки (10). (6, 2)-
    1
    9

    161
    завершение задания 9. (9, 1)+
    10
    10

    162
    Завершена загрузка (10). Задания на процессоре: 10
    10
    10

    232
    завершение задания 10. (6, 2)+
    16
    12



    Сводная таблица





    Задание
    t поступления i
    t завершения i
    Ti
    Wi

    1
    6
    46
    40
    1

    2
    11
    41
    30
    1

    3
    12
    122
    110
    1

    4
    12
    126
    80
    1,425

    5
    15
    56
    15
    2,7333333

    6
    24
    89
    65
    1

    7
    28
    126
    70
    1,4

    8
    33
    152
    30
    3,9666667

    9
    40
    161
    35
    3,4571429

    10
    40
    232
    80
    2,4


    Средневзвешенное время обращения W = 1,9382143.

    Временная диаграмма FIFO приведена в приложении 1.

    1.3.2. Алгоритм SJF

    Трассировка



    16
    12

    время
    событие
    V
    H

    6
    поступило задание 1. (7, 4)- начало загрузки (1). Процессор простаивает.
    9
    8

    11
    поступило задание 2. (5, 0)- загрузка не требуется.
    4
    8

    12
    поступило задание 3. (3, 4)- начало загрузки (3).
    Задания на процессоре: 2
    1
    4

    12
    поступило задание 4. (6, 2)- нехватка ресурсов, ожидание.
    1
    4

    15
    поступило задание 5. (4, 1)- нехватка ресурсов, ожидание.
    1
    4

    24
    поступило задание 6. (1, 3)- начало загрузки (6).
    0
    1

    26
    завершена загрузка (1). Задания на процессоре: 1, 2
    0
    1

    28
    поступило задание 7. (3, 2)- нехватка ресурсов, ожидание.
    0
    1

    32
    завершена загрузка (3). Задания на процессоре: 1, 2, 3
    0
    1

    33
    поступило задание 8. (5, 0)- нехватка ресурсов, ожидание
    0
    1

    39
    завершена загрузка(6). Задания на процессоре: 1, 2, 3, 6
    0
    1

    40
    поступило задание 9. (9, 1)- нехватка ресурсов, ожидание.
    поступило задание 10. (6, 2)- нехватка ресурсов, ожидание.
    0
    1

    41
    завершение задания 2. (5, 0)+ освобождение ресурсов. Задания на процессоре: 1, 3, 6
    5
    1

    41
    начало загрузки (5). (4, 1)-
    1
    0

    46
    завершение задания 1. (7, 4)+ освобождение ресурсов.
    Завершена загрузка (5). Задания на процессоре: 3, 5, 6

    8
    4

    46
    начало работы (8). (5, 0)-. Загрузки не требует.
    Задания на процессоре: 3, 5, 6, 8
    3
    4

    46
    начало загрузки (7). (3, 2)-
    0
    2

    56
    завершение задания 5. (4, 1)+. Задания на процессоре: 3, 6, 8
    4
    3

    56
    завершена загрузка 7. задания на процессоре: 3, 6, 7, 8
    4
    3

    76
    завершение задания 8. (5, 0)+. Задания на ЦП: 3, 6, 7
    9
    3

    76
    начало загрузки (9). (9, 1)-
    0
    2

    81
    завершена загрузка (9). Задания на ЦП: 3, 6, 7, 9
    0
    2

    89
    завершение задания 6. (1, 3)+. Задания на ЦП: 3, 7, 9
    1
    5

    106
    завершение задания 7. (3, 2)+. Задания на ЦП: 3, 9
    4
    7

    111
    завершение задания 9 (9, 1)+. Задания на ЦП: 3
    13
    8

    111
    начало загрузки (4). (6, 2)-
    7
    6

    111
    начало загрузки (10). (6, 2)-
    1
    4

    121
    завершена загрузка (4, 10). Задания на ЦП: 3, 4, 10
    1
    4

    122
    завершение задания 3. (3, 4)+. Задания на ЦП: 4, 10.
    4
    8

    192
    завершение задания 4. (6, 2)+, 10. (6, 2)+
    16
    12




    Сводная таблица


    Задание
    t поступления i
    t завершения i
    Ti
    Wi

    1
    6
    46
    40
    1

    2
    11
    41
    30
    1

    3
    12
    122
    110
    1

    4
    12
    192
    80
    2,25

    5
    15
    56
    15
    2,7333333

    6
    24
    89
    65
    1

    7
    28
    106
    70
    1,1142857

    8
    33
    76
    30
    1,4333333

    9
    40
    111
    35
    2,0285714

    10
    40
    193
    80
    1,9125


    Средневзвешенное время обращения W = 1,5472024.

    Временная диаграмма SJF приведена в приложении 2.


    1.3.3. Выводы



    Планирование по принципу SJF «сначала короткие задания» обеспечивает уменьшение среднего времени обращения (1.9 FIFO, 1.5 SJF) и нахождения задач в системе (232 FIFO, 192 SJF), но отдает явное предпочтение коротким заданиям, которые преобладают в заданной последовательности задач, задерживая при этом длинные.

    Применение принципа FIFO несколько увеличивает среднюю длительность времени ожидания и общее время нахождения в системе.

    Максимальные коэффициенты мультипрограммирования совпадают для обеих дисциплин (Кmax=4).

    В данной последовательности задач предпочтительней использовать ДО SJF, т.к. в системе преобладают короткие задачи.

      1   2

    написать администратору сайта