🗊 Презентация Развитие концепций и возможностей ОС

Категория: Образование
Нажмите для полного просмотра!
Развитие концепций и возможностей ОС, слайд №1 Развитие концепций и возможностей ОС, слайд №2 Развитие концепций и возможностей ОС, слайд №3 Развитие концепций и возможностей ОС, слайд №4 Развитие концепций и возможностей ОС, слайд №5 Развитие концепций и возможностей ОС, слайд №6 Развитие концепций и возможностей ОС, слайд №7 Развитие концепций и возможностей ОС, слайд №8 Развитие концепций и возможностей ОС, слайд №9 Развитие концепций и возможностей ОС, слайд №10 Развитие концепций и возможностей ОС, слайд №11 Развитие концепций и возможностей ОС, слайд №12 Развитие концепций и возможностей ОС, слайд №13 Развитие концепций и возможностей ОС, слайд №14 Развитие концепций и возможностей ОС, слайд №15 Развитие концепций и возможностей ОС, слайд №16 Развитие концепций и возможностей ОС, слайд №17 Развитие концепций и возможностей ОС, слайд №18 Развитие концепций и возможностей ОС, слайд №19 Развитие концепций и возможностей ОС, слайд №20 Развитие концепций и возможностей ОС, слайд №21 Развитие концепций и возможностей ОС, слайд №22 Развитие концепций и возможностей ОС, слайд №23 Развитие концепций и возможностей ОС, слайд №24 Развитие концепций и возможностей ОС, слайд №25 Развитие концепций и возможностей ОС, слайд №26 Развитие концепций и возможностей ОС, слайд №27 Развитие концепций и возможностей ОС, слайд №28 Развитие концепций и возможностей ОС, слайд №29 Развитие концепций и возможностей ОС, слайд №30 Развитие концепций и возможностей ОС, слайд №31 Развитие концепций и возможностей ОС, слайд №32 Развитие концепций и возможностей ОС, слайд №33 Развитие концепций и возможностей ОС, слайд №34 Развитие концепций и возможностей ОС, слайд №35 Развитие концепций и возможностей ОС, слайд №36 Развитие концепций и возможностей ОС, слайд №37 Развитие концепций и возможностей ОС, слайд №38 Развитие концепций и возможностей ОС, слайд №39 Развитие концепций и возможностей ОС, слайд №40 Развитие концепций и возможностей ОС, слайд №41 Развитие концепций и возможностей ОС, слайд №42 Развитие концепций и возможностей ОС, слайд №43 Развитие концепций и возможностей ОС, слайд №44 Развитие концепций и возможностей ОС, слайд №45 Развитие концепций и возможностей ОС, слайд №46 Развитие концепций и возможностей ОС, слайд №47 Развитие концепций и возможностей ОС, слайд №48 Развитие концепций и возможностей ОС, слайд №49 Развитие концепций и возможностей ОС, слайд №50 Развитие концепций и возможностей ОС, слайд №51 Развитие концепций и возможностей ОС, слайд №52 Развитие концепций и возможностей ОС, слайд №53 Развитие концепций и возможностей ОС, слайд №54 Развитие концепций и возможностей ОС, слайд №55 Развитие концепций и возможностей ОС, слайд №56 Развитие концепций и возможностей ОС, слайд №57 Развитие концепций и возможностей ОС, слайд №58 Развитие концепций и возможностей ОС, слайд №59 Развитие концепций и возможностей ОС, слайд №60 Развитие концепций и возможностей ОС, слайд №61 Развитие концепций и возможностей ОС, слайд №62 Развитие концепций и возможностей ОС, слайд №63 Развитие концепций и возможностей ОС, слайд №64 Развитие концепций и возможностей ОС, слайд №65 Развитие концепций и возможностей ОС, слайд №66 Развитие концепций и возможностей ОС, слайд №67 Развитие концепций и возможностей ОС, слайд №68 Развитие концепций и возможностей ОС, слайд №69 Развитие концепций и возможностей ОС, слайд №70 Развитие концепций и возможностей ОС, слайд №71 Развитие концепций и возможностей ОС, слайд №72 Развитие концепций и возможностей ОС, слайд №73 Развитие концепций и возможностей ОС, слайд №74 Развитие концепций и возможностей ОС, слайд №75 Развитие концепций и возможностей ОС, слайд №76 Развитие концепций и возможностей ОС, слайд №77 Развитие концепций и возможностей ОС, слайд №78 Развитие концепций и возможностей ОС, слайд №79 Развитие концепций и возможностей ОС, слайд №80 Развитие концепций и возможностей ОС, слайд №81 Развитие концепций и возможностей ОС, слайд №82 Развитие концепций и возможностей ОС, слайд №83 Развитие концепций и возможностей ОС, слайд №84 Развитие концепций и возможностей ОС, слайд №85 Развитие концепций и возможностей ОС, слайд №86 Развитие концепций и возможностей ОС, слайд №87 Развитие концепций и возможностей ОС, слайд №88 Развитие концепций и возможностей ОС, слайд №89 Развитие концепций и возможностей ОС, слайд №90 Развитие концепций и возможностей ОС, слайд №91 Развитие концепций и возможностей ОС, слайд №92 Развитие концепций и возможностей ОС, слайд №93 Развитие концепций и возможностей ОС, слайд №94 Развитие концепций и возможностей ОС, слайд №95 Развитие концепций и возможностей ОС, слайд №96 Развитие концепций и возможностей ОС, слайд №97 Развитие концепций и возможностей ОС, слайд №98 Развитие концепций и возможностей ОС, слайд №99 Развитие концепций и возможностей ОС, слайд №100 Развитие концепций и возможностей ОС, слайд №101 Развитие концепций и возможностей ОС, слайд №102 Развитие концепций и возможностей ОС, слайд №103 Развитие концепций и возможностей ОС, слайд №104 Развитие концепций и возможностей ОС, слайд №105 Развитие концепций и возможностей ОС, слайд №106 Развитие концепций и возможностей ОС, слайд №107 Развитие концепций и возможностей ОС, слайд №108 Развитие концепций и возможностей ОС, слайд №109 Развитие концепций и возможностей ОС, слайд №110 Развитие концепций и возможностей ОС, слайд №111 Развитие концепций и возможностей ОС, слайд №112 Развитие концепций и возможностей ОС, слайд №113 Развитие концепций и возможностей ОС, слайд №114 Развитие концепций и возможностей ОС, слайд №115 Развитие концепций и возможностей ОС, слайд №116 Развитие концепций и возможностей ОС, слайд №117 Развитие концепций и возможностей ОС, слайд №118 Развитие концепций и возможностей ОС, слайд №119 Развитие концепций и возможностей ОС, слайд №120 Развитие концепций и возможностей ОС, слайд №121 Развитие концепций и возможностей ОС, слайд №122 Развитие концепций и возможностей ОС, слайд №123 Развитие концепций и возможностей ОС, слайд №124 Развитие концепций и возможностей ОС, слайд №125 Развитие концепций и возможностей ОС, слайд №126 Развитие концепций и возможностей ОС, слайд №127 Развитие концепций и возможностей ОС, слайд №128 Развитие концепций и возможностей ОС, слайд №129 Развитие концепций и возможностей ОС, слайд №130 Развитие концепций и возможностей ОС, слайд №131 Развитие концепций и возможностей ОС, слайд №132 Развитие концепций и возможностей ОС, слайд №133 Развитие концепций и возможностей ОС, слайд №134 Развитие концепций и возможностей ОС, слайд №135 Развитие концепций и возможностей ОС, слайд №136 Развитие концепций и возможностей ОС, слайд №137 Развитие концепций и возможностей ОС, слайд №138 Развитие концепций и возможностей ОС, слайд №139 Развитие концепций и возможностей ОС, слайд №140 Развитие концепций и возможностей ОС, слайд №141 Развитие концепций и возможностей ОС, слайд №142 Развитие концепций и возможностей ОС, слайд №143 Развитие концепций и возможностей ОС, слайд №144 Развитие концепций и возможностей ОС, слайд №145 Развитие концепций и возможностей ОС, слайд №146 Развитие концепций и возможностей ОС, слайд №147 Развитие концепций и возможностей ОС, слайд №148 Развитие концепций и возможностей ОС, слайд №149 Развитие концепций и возможностей ОС, слайд №150 Развитие концепций и возможностей ОС, слайд №151 Развитие концепций и возможностей ОС, слайд №152 Развитие концепций и возможностей ОС, слайд №153 Развитие концепций и возможностей ОС, слайд №154 Развитие концепций и возможностей ОС, слайд №155 Развитие концепций и возможностей ОС, слайд №156 Развитие концепций и возможностей ОС, слайд №157 Развитие концепций и возможностей ОС, слайд №158 Развитие концепций и возможностей ОС, слайд №159 Развитие концепций и возможностей ОС, слайд №160 Развитие концепций и возможностей ОС, слайд №161 Развитие концепций и возможностей ОС, слайд №162 Развитие концепций и возможностей ОС, слайд №163 Развитие концепций и возможностей ОС, слайд №164 Развитие концепций и возможностей ОС, слайд №165 Развитие концепций и возможностей ОС, слайд №166 Развитие концепций и возможностей ОС, слайд №167 Развитие концепций и возможностей ОС, слайд №168 Развитие концепций и возможностей ОС, слайд №169 Развитие концепций и возможностей ОС, слайд №170 Развитие концепций и возможностей ОС, слайд №171 Развитие концепций и возможностей ОС, слайд №172 Развитие концепций и возможностей ОС, слайд №173 Развитие концепций и возможностей ОС, слайд №174 Развитие концепций и возможностей ОС, слайд №175 Развитие концепций и возможностей ОС, слайд №176 Развитие концепций и возможностей ОС, слайд №177 Развитие концепций и возможностей ОС, слайд №178 Развитие концепций и возможностей ОС, слайд №179 Развитие концепций и возможностей ОС, слайд №180 Развитие концепций и возможностей ОС, слайд №181 Развитие концепций и возможностей ОС, слайд №182 Развитие концепций и возможностей ОС, слайд №183 Развитие концепций и возможностей ОС, слайд №184 Развитие концепций и возможностей ОС, слайд №185 Развитие концепций и возможностей ОС, слайд №186 Развитие концепций и возможностей ОС, слайд №187 Развитие концепций и возможностей ОС, слайд №188 Развитие концепций и возможностей ОС, слайд №189 Развитие концепций и возможностей ОС, слайд №190 Развитие концепций и возможностей ОС, слайд №191 Развитие концепций и возможностей ОС, слайд №192 Развитие концепций и возможностей ОС, слайд №193 Развитие концепций и возможностей ОС, слайд №194 Развитие концепций и возможностей ОС, слайд №195 Развитие концепций и возможностей ОС, слайд №196 Развитие концепций и возможностей ОС, слайд №197 Развитие концепций и возможностей ОС, слайд №198 Развитие концепций и возможностей ОС, слайд №199 Развитие концепций и возможностей ОС, слайд №200 Развитие концепций и возможностей ОС, слайд №201 Развитие концепций и возможностей ОС, слайд №202 Развитие концепций и возможностей ОС, слайд №203 Развитие концепций и возможностей ОС, слайд №204 Развитие концепций и возможностей ОС, слайд №205 Развитие концепций и возможностей ОС, слайд №206 Развитие концепций и возможностей ОС, слайд №207 Развитие концепций и возможностей ОС, слайд №208 Развитие концепций и возможностей ОС, слайд №209 Развитие концепций и возможностей ОС, слайд №210 Развитие концепций и возможностей ОС, слайд №211 Развитие концепций и возможностей ОС, слайд №212 Развитие концепций и возможностей ОС, слайд №213 Развитие концепций и возможностей ОС, слайд №214 Развитие концепций и возможностей ОС, слайд №215 Развитие концепций и возможностей ОС, слайд №216 Развитие концепций и возможностей ОС, слайд №217 Развитие концепций и возможностей ОС, слайд №218 Развитие концепций и возможностей ОС, слайд №219 Развитие концепций и возможностей ОС, слайд №220 Развитие концепций и возможностей ОС, слайд №221 Развитие концепций и возможностей ОС, слайд №222 Развитие концепций и возможностей ОС, слайд №223 Развитие концепций и возможностей ОС, слайд №224 Развитие концепций и возможностей ОС, слайд №225
Скачать

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Развитие концепций и возможностей ОС. Доклад-сообщение содержит 225 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1


Развитие концепций и возможностей ОС
Описание слайда:
Развитие концепций и возможностей ОС

Слайд 2


Общая картина функционирования компьютерной системы
Описание слайда:
Общая картина функционирования компьютерной системы

Слайд 3


Распределение памяти в простой системе пакетной обработки
Описание слайда:
Распределение памяти в простой системе пакетной обработки

Слайд 4


Системы пакетной обработки с поддержкой мультипрограммирования
Описание слайда:
Системы пакетной обработки с поддержкой мультипрограммирования

Слайд 5


SMP-архитектура
Описание слайда:
SMP-архитектура

Слайд 6


Общая структура клиент-серверной системы
Описание слайда:
Общая структура клиент-серверной системы

Слайд 7


Архитектура компьютерных систем 2/2
Описание слайда:
Архитектура компьютерных систем 2/2

Слайд 8


Временной график прерываний процесса, выполняющего вывод
Описание слайда:
Временной график прерываний процесса, выполняющего вывод

Слайд 9


Два метода ввода-вывода: синхронный и асинхронный
Описание слайда:
Два метода ввода-вывода: синхронный и асинхронный

Слайд 10


Таблица состояния устройств
Описание слайда:
Таблица состояния устройств

Слайд 11


Устройство диска
Описание слайда:
Устройство диска

Слайд 12


Иерархия устройств памяти
Описание слайда:
Иерархия устройств памяти

Слайд 13


Использование системного вызова для выполнения ввода-вывода
Описание слайда:
Использование системного вызова для выполнения ввода-вывода

Слайд 14


Использование базового регистра и регистра границы
Описание слайда:
Использование базового регистра и регистра границы

Слайд 15


Аппаратная защита адресов памяти
Описание слайда:
Аппаратная защита адресов памяти

Слайд 16


Передача параметров в таблице
Описание слайда:
Передача параметров в таблице

Слайд 17


Исполнение программ в MS-DOS
Описание слайда:
Исполнение программ в MS-DOS

Слайд 18


Исполнение нескольких программ в UNIX
Описание слайда:
Исполнение нескольких программ в UNIX

Слайд 19


Коммуникационные модели Могут реализовываться с помощью общей памяти или передачи сообщений
Описание слайда:
Коммуникационные модели Могут реализовываться с помощью общей памяти или передачи сообщений

Слайд 20


Уровни (абстракции) модулей MS-DOS
Описание слайда:
Уровни (абстракции) модулей MS-DOS

Слайд 21


Структура системы UNIX
Описание слайда:
Структура системы UNIX

Слайд 22


Уровни абстракции ОС
Описание слайда:
Уровни абстракции ОС

Слайд 23


Структура уровней абстракции OS/2
Описание слайда:
Структура уровней абстракции OS/2

Слайд 24


Клиент-серверная структура Windows NT
Описание слайда:
Клиент-серверная структура Windows NT

Слайд 25


Модели ОС без использования виртуальных машин и на основе виртуальных машин
Описание слайда:
Модели ОС без использования виртуальных машин и на основе виртуальных машин

Слайд 26


Виртуальная машина Java
Описание слайда:
Виртуальная машина Java

Слайд 27


Диаграмма состояний процесса
Описание слайда:
Диаграмма состояний процесса

Слайд 28


Блок управления процессом (PCB)
Описание слайда:
Блок управления процессом (PCB)

Слайд 29


Переключение процессора с одного процесса на другой
Описание слайда:
Переключение процессора с одного процесса на другой

Слайд 30


Очередь готовых процессов и очереди для различных устройств ввода-вывода
Описание слайда:
Очередь готовых процессов и очереди для различных устройств ввода-вывода

Слайд 31


Графическое представление диспетчеризации процессов
Описание слайда:
Графическое представление диспетчеризации процессов

Слайд 32


Добавление диспетчера выгруженных процессов
Описание слайда:
Добавление диспетчера выгруженных процессов

Слайд 33


Дерево процессов в системе UNIX
Описание слайда:
Дерево процессов в системе UNIX

Слайд 34


Ограниченный буфер – реализация с помощью общей памяти Общие данные #define BUFFER_SIZE 1000 /* или другое конкретное значение */ typedef struct { ....
Описание слайда:
Ограниченный буфер – реализация с помощью общей памяти Общие данные #define BUFFER_SIZE 1000 /* или другое конкретное значение */ typedef struct { . . . } item; item buffer[BUFFER_SIZE]; int in = 0; int out = 0;

Слайд 35


Ограниченный буфер: процесс-производитель item nextProduced; item nextProduced; /* следующий генерируемый элемент */ while (1) { /* бесконечный цикл...
Описание слайда:
Ограниченный буфер: процесс-производитель item nextProduced; item nextProduced; /* следующий генерируемый элемент */ while (1) { /* бесконечный цикл */ while (((in + 1) % BUFFER_SIZE) == out) ; /* ждать, пока буфер переполнен*/ buffer[in] = nextProduced; /* генерация элемента */ in = (in + 1) % BUFFER_SIZE; }

Слайд 36


Ограниченный буфер: процесс-потребитель item nextConsumed; /* следующий используемый элемент */ while (1) { /* бесконечный цикл */ while (in == out)...
Описание слайда:
Ограниченный буфер: процесс-потребитель item nextConsumed; /* следующий используемый элемент */ while (1) { /* бесконечный цикл */ while (in == out) ; /* ждать, пока буфер пуст */ nextConsumed = buffer[out]; /* использование элемента */ out = (out + 1) % BUFFER_SIZE; }

Слайд 37


Взаимодействие с помощью сокетов
Описание слайда:
Взаимодействие с помощью сокетов

Слайд 38


Исполнение RPC
Описание слайда:
Исполнение RPC

Слайд 39


Удаленный вызов метода (RMI) - Java Remote Method Invocation (RMI) – механизм в Java-технологии, аналогичный RPC RMI позволяет Java-приложению на...
Описание слайда:
Удаленный вызов метода (RMI) - Java Remote Method Invocation (RMI) – механизм в Java-технологии, аналогичный RPC RMI позволяет Java-приложению на одной машине вызвать метод удаленного объекта.

Слайд 40


Выстраивание параметров (marshaling)
Описание слайда:
Выстраивание параметров (marshaling)

Слайд 41


Однопоточные и многопоточные процессы
Описание слайда:
Однопоточные и многопоточные процессы

Слайд 42


Схема модели “много / один”
Описание слайда:
Схема модели “много / один”

Слайд 43


Схема модели “один / один”
Описание слайда:
Схема модели “один / один”

Слайд 44


Схема модели “много/много”
Описание слайда:
Схема модели “много/много”

Слайд 45


Потоки в Solaris
Описание слайда:
Потоки в Solaris

Слайд 46


Процесс в Solaris
Описание слайда:
Процесс в Solaris

Слайд 47


Состояния потоков в Java
Описание слайда:
Состояния потоков в Java

Слайд 48


Последовательность активных фаз (bursts) процессора и ввода-вывода
Описание слайда:
Последовательность активных фаз (bursts) процессора и ввода-вывода

Слайд 49


Гистограмма периодов активности процессора
Описание слайда:
Гистограмма периодов активности процессора

Слайд 50


Стратегия диспетчеризации First-Come-First-Served (FCFS) Процесс Период активности P1 24 P2 3 P3 3 Пусть порядок процессов таков: P1 , P2 , P3...
Описание слайда:
Стратегия диспетчеризации First-Come-First-Served (FCFS) Процесс Период активности P1 24 P2 3 P3 3 Пусть порядок процессов таков: P1 , P2 , P3 Диаграмма Ганта (Gantt Chart) для их распределения:

Слайд 51


Стратегия FCFS (продолжение) Пусть порядок процессов таков: P2 , P3 , P1 . Диаграмма Ганта для их распределения:
Описание слайда:
Стратегия FCFS (продолжение) Пусть порядок процессов таков: P2 , P3 , P1 . Диаграмма Ганта для их распределения:

Слайд 52


Пример: SJF с опережением Процесс Время появления Время активности P1 0.0 7 P2 2.0 4 P3 4.0 1 P4 5.0 4 SJF (с опережением) Среднее время ожидания =...
Описание слайда:
Пример: SJF с опережением Процесс Время появления Время активности P1 0.0 7 P2 2.0 4 P3 4.0 1 P4 5.0 4 SJF (с опережением) Среднее время ожидания = (9 + 1 + 0 +2)/4 = 3

Слайд 53


Определение длины следующего периода активности Является лишь оценкой длины. Может быть выполнено с использованием длин предыдущих периодов...
Описание слайда:
Определение длины следующего периода активности Является лишь оценкой длины. Может быть выполнено с использованием длин предыдущих периодов активности, используя экспоненциальное усреднение

Слайд 54


Предсказание длины следующего периода активности
Описание слайда:
Предсказание длины следующего периода активности

Слайд 55


Примеры экспоненциального усреднения  =0 n+1 = n Недавняя история не учитывается.  =1 n+1 = tn Учитывается только фактическая длина последнего...
Описание слайда:
Примеры экспоненциального усреднения  =0 n+1 = n Недавняя история не учитывается.  =1 n+1 = tn Учитывается только фактическая длина последнего периода активности. Если обобщить формулу, получим: n+1 =  tn+(1 - )  tn -1 + … +(1 -  )j  tn -1 + … +(1 -  )n=1 tn 0 Так как  и(1 - ) не превосходят 1, каждый последующий терм имеет меньший вес, чем его предшественник

Слайд 56


Пример RR (квант времени = 20) Пример RR с квантом времени = 20 Процес Время активности P1 53 P2 17 P3 68 P4 24 Диаграмма Ганта: Обычно RR имеет...
Описание слайда:
Пример RR (квант времени = 20) Пример RR с квантом времени = 20 Процес Время активности P1 53 P2 17 P3 68 P4 24 Диаграмма Ганта: Обычно RR имеет худшее время оборота, чем SJF, но лучшее время ответа.

Слайд 57


Квант времени ЦП и время переключения контекста
Описание слайда:
Квант времени ЦП и время переключения контекста

Слайд 58


Изменение времени оборота, в зависимости от кванта времени
Описание слайда:
Изменение времени оборота, в зависимости от кванта времени

Слайд 59


Диспетчеризация по принципу многоуровневой очереди
Описание слайда:
Диспетчеризация по принципу многоуровневой очереди

Слайд 60


Многоуровневые аналитические очереди
Описание слайда:
Многоуровневые аналитические очереди

Слайд 61


Латентность диспетчера (dispatch latency)– время, требуемое для диспетчера, чтобы остановить один процесс и стартовать другой.
Описание слайда:
Латентность диспетчера (dispatch latency)– время, требуемое для диспетчера, чтобы остановить один процесс и стартовать другой.

Слайд 62


Оценка планировщиков ЦП посредством моделирования
Описание слайда:
Оценка планировщиков ЦП посредством моделирования

Слайд 63


Планирование в Solaris
Описание слайда:
Планирование в Solaris

Слайд 64


Приоритеты в Windows NT 5 и выше
Описание слайда:
Приоритеты в Windows NT 5 и выше

Слайд 65


Ограниченный буфер Имеется общий буфер ограниченной длины. Процесс-производитель добавляет в него сгенерированные элементы, процесс-потребитель...
Описание слайда:
Ограниченный буфер Имеется общий буфер ограниченной длины. Процесс-производитель добавляет в него сгенерированные элементы, процесс-потребитель использует и удаляет использованные элементы. Добавим в представление ограниченного буфера переменную counter,которую увеличивает процесс-производитель, добавляя очередной элемент к буферу, и уменьшает процесс-потребитель, используя и удаляя элемент из буфера. Общие данные #define BUFFER_SIZE 10 typedef struct { . . . } item; item buffer[BUFFER_SIZE]; int in = 0; int out = 0; int counter = 0;

Слайд 66


Ограниченный буфер Процесс-производитель item nextProduced; while (1) { while (counter == BUFFER_SIZE) ; /* do nothing */ buffer[in] = nextProduced;...
Описание слайда:
Ограниченный буфер Процесс-производитель item nextProduced; while (1) { while (counter == BUFFER_SIZE) ; /* do nothing */ buffer[in] = nextProduced; in = (in + 1) % BUFFER_SIZE; counter++; }

Слайд 67


Ограниченный буфер Процесс-потребитель item nextConsumed; while (1) { while (counter == 0) ; /* do nothing */ nextConsumed = buffer[out]; out = (out...
Описание слайда:
Ограниченный буфер Процесс-потребитель item nextConsumed; while (1) { while (counter == 0) ; /* do nothing */ nextConsumed = buffer[out]; out = (out + 1) % BUFFER_SIZE; counter--; }

Слайд 68


Ограниченный буфер Оператор “count++” может быть реализован на языке ассемблерного уровня как: register1 = counter register1 = register1 + 1 counter...
Описание слайда:
Ограниченный буфер Оператор “count++” может быть реализован на языке ассемблерного уровня как: register1 = counter register1 = register1 + 1 counter = register1 Оператор “count—” может быть реализован как: register2 = counter register2 = register2 – 1 counter = register2 Проблема в том, что если и производитель, и потребитель пытаются изменить переменную counter одновременно, то указанные ассемблерные операторы тоже должны быть выполнены совместно (interleaved).

Слайд 69


Ограниченный буфер Предположим, counter вначале равно 5. Исполнение процессов в совместном режиме (interleaving) приводит к следующему: producer:...
Описание слайда:
Ограниченный буфер Предположим, counter вначале равно 5. Исполнение процессов в совместном режиме (interleaving) приводит к следующему: producer: register1 = counter (register1 = 5) producer: register1 = register1 + 1 (register1 = 6) consumer: register2 = counter (register2 = 5) consumer: register2 = register2 – 1 (register2 = 4) producer: counter = register1 (counter = 6) consumer: counter = register2 (counter = 4) Значение counter может оказаться равным 4 или 6, в то время как правильное значение counter равно 5. Ситуация, при которой взаимодействующие процессы могут параллельно (одновременно) обращаться к общим данным, называется конкуренцией за общие данные (race condition).Для предотвращения подобных ситуаций процессы следует синхронизировать.

Слайд 70


Синхронизация процессов по критическим секциям Рассмотрим проанализированную проблему в общем виде. Пусть имеются n параллельных процессов, каждый из...
Описание слайда:
Синхронизация процессов по критическим секциям Рассмотрим проанализированную проблему в общем виде. Пусть имеются n параллельных процессов, каждый из которых может обратиться к общим для них данным. Назовем критической секцией фрагмент кода каждого процесса, в котором происходит обращение к общим данным. Проблема синхронизации процессов по критическим секциям заключается в том, чтобы обеспечить следующий режим выполнения: если один процесс вошел в свою критическую секцию, то до ее завершения никакой другой процесс не смог бы одновременно войти в свою критическую секцию. Можно показать, что для решения проблемы критической секции необходимо и достаточно выполнение следующих трех условий: Взаимное исключение. Если некоторый процесс исполняет свою критическую секцию, то никакой другой процесс не должен в этот момент исполнять свою. Прогресс.Если в данный момент нет процессов, исполняющих критическую секцию, но есть несколько процессов, желающих начать исполнение критической секции, то выбор системой процесса, которому будет разрешен запуск критической секции, не может продолжаться бесконечно. Ограниченное ожидание.В системе должно существовать ограничение на число раз, которое процессам разрешено входить в свои критические секции, начиная от момента, когда некоторый процесс сделал запрос о входе в критическую секцию, и до момента, когда этот запрос удовлетворен. При этом предполагается, что каждый процесс исполняется с ненулевой скоростью, но не делается никаких предположений о соотношении скоростей процессов.

Слайд 71


Первоначальные попытки решения проблемы Есть только два процесса, P0 и P1 Общая структура процесса Pi: do { entry section critical section exit...
Описание слайда:
Первоначальные попытки решения проблемы Есть только два процесса, P0 и P1 Общая структура процесса Pi: do { entry section critical section exit section remainder section } while (1); Процессы могут использовать общие переменные для синхронизации своих действий.

Слайд 72


Алгоритм 1 Общие переменные: shared int turn; первоначально turn = 0 turn == i  процесс Pi может войти в критическую секцию Процесс Pi : do { while...
Описание слайда:
Алгоритм 1 Общие переменные: shared int turn; первоначально turn = 0 turn == i  процесс Pi может войти в критическую секцию Процесс Pi : do { while (turn != i) ; critical section turn = j; remainder section } while (1); Удовлетворяет принципу “взаимное исключение”, но не принципу “прогресс”: алгоритм не предпринимает никаких мер, чтобы огран время выбора проца, желающего начать критическую секцию. Причина в следующем: алгоритм не хранит информацию о том, какие процессы желают войти в свои критические секции.

Слайд 73


Алгоритм 2 Общие переменные boolean flag[2]; первоначально flag [0] = flag [1] = false. flag [i] == true  Pi готов войти в критическую секцию...
Описание слайда:
Алгоритм 2 Общие переменные boolean flag[2]; первоначально flag [0] = flag [1] = false. flag [i] == true  Pi готов войти в критическую секцию Процесс Pi : do { flag[i] := true; while (flag[j]) ; critical section flag [i] = false; remainder section } while (1); Удовлетв принципу “взаимное исключение”, но не принципу “прогресс” алгоритм не различает информацию о том, что процесс еще только готов войти в свою критическую секцию, и о том, что он в нее уже вошел.

Слайд 74


Алгоритм 3 (Петерсона, 1981) Объединяет общие переменные алгоритмов 1 и 2. Процесс Pi : do { flag [i]:= true; turn = j; while (flag [j] and turn = j)...
Описание слайда:
Алгоритм 3 (Петерсона, 1981) Объединяет общие переменные алгоритмов 1 и 2. Процесс Pi : do { flag [i]:= true; turn = j; while (flag [j] and turn = j) ; critical section flag [i] = false; remainder section } while (1); Удовлетворяет всем трем принципам и решает проблему взаимного исключения. перед входом в критическую секцию процесс сначала заявляет о своем намерении в нее войти, но затем пытается предоставить право на вход в критическую секцию другому процессу и только после того, как другой процесс ее выполнил и больше не желает в нее войти, входит сам в свою критическую секцию.

Слайд 75


Алгоритм булочной (bakery algorithm) алгоритм как бы воспроизводит стратегию автомата в (американской) булочной, где каждому клиенту присваивается...
Описание слайда:
Алгоритм булочной (bakery algorithm) алгоритм как бы воспроизводит стратегию автомата в (американской) булочной, где каждому клиенту присваивается его номер в очереди. Обозначения: <  лексикографический порядок (a,b) < (c,d) если a < c or if a = c and b < d max (a0,…, an-1)- число k, такое, что k  ai for i - 0, …, n – 1 Общие данные: boolean choosing[n]; int number[n]; Структуры данных инициализируются, соответственно, false и 0

Слайд 76


Алгоритм булочной do { choosing[i] = true; number [i] = max (number[0], number[1], …, number[n-1]) + 1; choosing[i] = false; for (j = 0; j < n; j++)...
Описание слайда:
Алгоритм булочной do { choosing[i] = true; number [i] = max (number[0], number[1], …, number[n-1]) + 1; choosing[i] = false; for (j = 0; j < n; j++) { while choosing[j]; while ((number[j] != 0) && (number[j] < number[i])); } критическая секция number [i] = 0; остальная часть кода } while (1)

Слайд 77


Аппаратная поддержка синхронизации Атомарная операция проверки и модификации значения переменной TestAndSet, которая атомарно выполняет считывание и...
Описание слайда:
Аппаратная поддержка синхронизации Атомарная операция проверки и модификации значения переменной TestAndSet, которая атомарно выполняет считывание и запоминание значения переменной, затем изменяет его на заданное значение, но в результате выдает первоначальное значение переменной. . boolean TestAndSet(boolean &target) { boolean rv = target; target = true; return rv; }

Слайд 78


Взаимное исключение с помощью TestAndSet Общие данные: boolean lock = false; Процесс Pi do { while (TestAndSet(lock)) ; critical section lock =...
Описание слайда:
Взаимное исключение с помощью TestAndSet Общие данные: boolean lock = false; Процесс Pi do { while (TestAndSet(lock)) ; critical section lock = false; remainder section } while (1) Значение переменной lock, равное true,означает, что вход в критическую секцию заблокирован. Каждый процесс ждет, пока он не разблокируется, затем, в свою очередь, выполняет блокировку и входит в критическую секцию. При ее завершении процесс разблокирует критическую секцию присваиванием lock значения false.

Слайд 79


Аппаратное решение для синхронизации Атомарная перестановка значений двух переменных. Другое распространенное аппаратное решение для синхронизации –...
Описание слайда:
Аппаратное решение для синхронизации Атомарная перестановка значений двух переменных. Другое распространенное аппаратное решение для синхронизации – атомарная операция Swap, выполняющая перестановку значений двух переменных: void Swap (boolean * a, boolean * b) { boolean temp = * a; * a = * b; * b = temp; }

Слайд 80


Взаимное исключение с помощью Swap Общие данные (инициализируемые false): boolean lock; boolean waiting[n]; Процесс Pi do { key = true; while (key ==...
Описание слайда:
Взаимное исключение с помощью Swap Общие данные (инициализируемые false): boolean lock; boolean waiting[n]; Процесс Pi do { key = true; while (key == true) Swap(&lock, &key); critical section lock = false; remainder section } while (1) При данной реализации, условием ожидания процесса перед входом в критическую секцию является условия (key == true),которое фактически означает то же, что и в предыдущей реализации, - закрытое состояние блокировщика, т.е., то, что другой процесс находится в своей критической секции. Когда критическая секция освободится (освобождение осуществляется присваиванием lock = false после завершения критической секции в исполнившем ее процессе), ее начнет исполнять текущий процесс.

Слайд 81


Общие семафоры – counting semaphores (по Э. Дейкстре) Семафо́р — объект, позволяющий войти в заданный участок кода не более чем n потокам. Семафор —...
Описание слайда:
Общие семафоры – counting semaphores (по Э. Дейкстре) Семафо́р — объект, позволяющий войти в заданный участок кода не более чем n потокам. Семафор — это объект, с которым можно выполнить три операции. init(n):счётчик := n enter():ждать пока счётчик станет больше 0; после этого уменьшить счётчик на единицу. leave():увеличить счётчик на единицу. Средство синхронизации, не требующее активного ожидания. (Общий) семафор S – целая переменная Может использоваться только для двух атомарных операций: wait (S): while S 0 do no-op; S--; signal (S): S++;

Слайд 82


Критическая секция для N процессов Общие данные: semaphore mutex; //initially mutex = 1 Процесс Pi: do { wait(mutex); critical section signal(mutex);...
Описание слайда:
Критическая секция для N процессов Общие данные: semaphore mutex; //initially mutex = 1 Процесс Pi: do { wait(mutex); critical section signal(mutex); remainder section } while (1);

Слайд 83


Реализация семафора Семафор, по существу, является структурой из двух полей – целого значения и указателя на список ждущих процессов:: typedef struct...
Описание слайда:
Реализация семафора Семафор, по существу, является структурой из двух полей – целого значения и указателя на список ждущих процессов:: typedef struct { int value; struct process *L; } semaphore; Предполагаем наличие двух простейших операций: block – задерживает исполнение процесса, исполнившего данную операцию. wakeup(P) возобновляет исполнение приостановленного процесса P.

Слайд 84


Реализация Определим семафорные операции следующим образом: wait(S): S.value--; if (S.value < 0) { добавить текущий процесс к S.L; block; }...
Описание слайда:
Реализация Определим семафорные операции следующим образом: wait(S): S.value--; if (S.value < 0) { добавить текущий процесс к S.L; block; } signal(S): S.value++; if (S.value

Слайд 85


Семафоры как общее средство синхронизации Исполнить действие B в процессе Pj только после того, как действие A исполнено в процессе Pi Использовать...
Описание слайда:
Семафоры как общее средство синхронизации Исполнить действие B в процессе Pj только после того, как действие A исполнено в процессе Pi Использовать семафор flag , инициализированный 0 Код: Pi Pj   A wait(flag) signal(flag) B Общие и двоичные семафоры Из рассмотренного ясно, что имеется два вида семафоров: общий - целая переменная с теоретически неограниченным значением - и двоичный - целая переменная, значениями которой могут быть только 0 или 1. Преимуществом двоичного семафора является его возможная более простая аппаратная реализация. Например, в системах "Эльбрус" и Burroughs 5000 реализованы команды атомарного семафорного считывания с проверкойсемафорного бита.

Слайд 86


Реализация общего семафора S с помощью двоичных семафоров Структуры данных: binary-semaphore S1, S2; int C: Инициализация: S1 = 1 S2 = 0 C =...
Описание слайда:
Реализация общего семафора S с помощью двоичных семафоров Структуры данных: binary-semaphore S1, S2; int C: Инициализация: S1 = 1 S2 = 0 C = начальное значение общего семафора S В данной реализации семафор S1 используется для взаимного исключения доступа к общей целой переменной C. Семафор S2 используется для хранения очереди ждущих процессов в случае, если общий семафор переходит в закрытое состояние.

Слайд 87


Реализация операций над семафором S Операция wait: wait(S1); C--; if (C < 0) { signal(S1); wait(S2); } signal(S1); Операция signal: wait(S1); C ++;...
Описание слайда:
Реализация операций над семафором S Операция wait: wait(S1); C--; if (C < 0) { signal(S1); wait(S2); } signal(S1); Операция signal: wait(S1); C ++; if (C

Слайд 88


Задача “ограниченный буфер” ограниченный буфер:имеются процесс-производитель и процесс-потребитель, взаимодействующие с помощью циклического буфера...
Описание слайда:
Задача “ограниченный буфер” ограниченный буфер:имеются процесс-производитель и процесс-потребитель, взаимодействующие с помощью циклического буфера ограниченной длины; производитель генерирует элементы информации и записывает в буфер; потребитель использует информационные элементы из буфера и удаляет их. Общие данные: semaphore full, empty, mutex; Начальные значения: full = 0, empty = n, mutex = 1

Слайд 89


Процесс-производитель ограниченного буфера do { … сгенерировать элемент в nextp … wait(empty); wait(mutex); … добавить nextp к буферу …...
Описание слайда:
Процесс-производитель ограниченного буфера do { … сгенерировать элемент в nextp … wait(empty); wait(mutex); … добавить nextp к буферу … signal(mutex); signal(full); } while (1);

Слайд 90


Процесс-потребитель ограниченного буфера do { wait(full) wait(mutex); … взять (и удалить) элемент из буфера в nextc … signal(mutex); signal(empty); …...
Описание слайда:
Процесс-потребитель ограниченного буфера do { wait(full) wait(mutex); … взять (и удалить) элемент из буфера в nextc … signal(mutex); signal(empty); … использовать элемент из nextc … } while (1); Поясним использование семафоров. Семафор mutex используется "симметрично"; над ним выполняется пара операций: wait … signal – семафорные скобки. Его роль – чисто взаимное исключение критических секций.

Слайд 91


Задача “читатели-писатели” Суть задачи читатели-писатели в следующем: имеется общий ресурс и две группы процессов: читатели (которые могут только...
Описание слайда:
Задача “читатели-писатели” Суть задачи читатели-писатели в следующем: имеется общий ресурс и две группы процессов: читатели (которые могут только читать ресурс) и писатели (которые изменяют ресурс). В каждый момент работать с ресурсом может сразу несколько читателей (когда ресурс не изменяется писателями), но не более одного писателя. Необходимо синхронизировать их действия над ресурсом и обеспечить взаимное исключение соответствующих критических секций. Общие данные: semaphore mutex, wrt; Начальные значения: mutex = 1, wrt = 1, readcount = 0

Слайд 92


Процесс-писатель wait(wrt); … выполняется запись … signal(wrt); Процесс-читатель, во-первых, должен увеличить значение readcount, причем обеспечить...
Описание слайда:
Процесс-писатель wait(wrt); … выполняется запись … signal(wrt); Процесс-читатель, во-первых, должен увеличить значение readcount, причем обеспечить взаимное исключение для действий над readcount с помощью семафора mutex.Далее, если процесс является первым читателем, он должен закрыть семафор wrt, чтобы исключить одновременное с чтением изменение ресурса писателями. По окончании чтения ресурса, читатель в аналогичном стиле вновь уменьшает readcount. Если при этом оно обнуляется (т.е. это последний на данный момент читатель), то читатель открывает семафор wrt, сигнализируя писателям, что они могут изменять ресурс.

Слайд 93


Процесс-читатель wait(mutex); readcount++; if (readcount == 1){ wait(rt); } signal(mutex); … выполняется чтение … wait(mutex); readcount--; if...
Описание слайда:
Процесс-читатель wait(mutex); readcount++; if (readcount == 1){ wait(rt); } signal(mutex); … выполняется чтение … wait(mutex); readcount--; if (readcount == 0){ signal(wrt); signal(mutex): }

Слайд 94


Задача “обедающие философы”
Описание слайда:
Задача “обедающие философы”

Слайд 95


Задача “обедающие философы” Имеется круглый стол, за которым сидят пять философов (впрочем, их число принципиального значения не имеет – для другого...
Описание слайда:
Задача “обедающие философы” Имеется круглый стол, за которым сидят пять философов (впрочем, их число принципиального значения не имеет – для другого числа философов решение будет аналогичным). Перед каждым из них лежит тарелка с едой, слева и справа от каждого – две китайские палочки. Философ может находиться в трех состояниях: проголодаться, думать и обедать. На голодный желудок философ думать не может. Но начать обедать он может, только если обе палочки слева и справа от него свободны. Требуется синхронизировать действия философов. В данном случае общим ресурсом являются палочки. Иллюстрацией условий задачи является Философ i: do { wait(chopstick[i]); wait(chopstick[(i+1) % 5]); … dine … signal(chopstick[i]); signal(chopstick[(i+1) % 5]); … think … } while (1);

Слайд 96


Пример: ограниченный буфер Общие данные: struct buffer { int pool[n]; int count, in, out; } Критические области (critical regions) – более...
Описание слайда:
Пример: ограниченный буфер Общие данные: struct buffer { int pool[n]; int count, in, out; } Критические области (critical regions) – более высокоуровневая и надежная конструкция для синхронизации, чем семафоры. Общий ресурс описывается в виде особого описания переменной: v: shared T Доступ к переменной v возможен только с помощью специальной конструкции: region v when B do S где v – общий ресурс; B – булевское условие, S – оператор (содержащий действия над v ). Семантика данной конструкции следующая. Пока B ложно, процесс, ее исполняющий, должен ждать. Когда Bстановится истинным, процесс получает доступ к ресурсу v и выполняет над ним операции S. Пока исполняется оператор S, больше ни один процесс не имеет доступа к переменной v.

Слайд 97


Процесс-производитель Процесс-производитель добавляет nextp к общему буферу region buffer when (count < n) { pool[in] = nextp; in:= (in+1) % n;...
Описание слайда:
Процесс-производитель Процесс-производитель добавляет nextp к общему буферу region buffer when (count < n) { pool[in] = nextp; in:= (in+1) % n; count++; } проверка переполнения буфера выполняется при входе в конструкцию region, и потребитель ждет, пока в буфере освободится хотя бы один элемент.

Слайд 98


Процесс-потребитель Процесс-потребитель удаляет элемент из буфера и запоминает его в nextc region buffer when (count > 0) { nextc = pool[out]; out =...
Описание слайда:
Процесс-потребитель Процесс-потребитель удаляет элемент из буфера и запоминает его в nextc region buffer when (count > 0) { nextc = pool[out]; out = (out+1) % n; count--; }

Слайд 99


Реализация оператора region x when B do S Свяжем с общей переменной x следующие переменные: semaphore mutex, first-delay, second-delay; int...
Описание слайда:
Реализация оператора region x when B do S Свяжем с общей переменной x следующие переменные: semaphore mutex, first-delay, second-delay; int first-count, second-count; Взаимное исключение доступа к критической секции обеспечивается семафором mutex. Если процесс не может войти в критическую секцию, т.к. булевское выражение B ложно, он ждет на семафоре first-delay; затем он “перевешивается” на семафор second-delay, до тех пор, пока ему не будет разрешено вновь вычислить B.

Слайд 100


Мониторы (C. A. R. Hoare) Высокоуровневая конструкция для синхронизации, которая позволяет синхронизировать доступ к абстрактному типу данных....
Описание слайда:
Мониторы (C. A. R. Hoare) Высокоуровневая конструкция для синхронизации, которая позволяет синхронизировать доступ к абстрактному типу данных. monitor monitor-name { описания общих переменных procedure body P1 (…) { . . . } procedure body P2 (…) { . . . } procedure body Pn (…) { . . . } { код инициализации } }

Слайд 101


Мониторы: условные переменные Для реализации ожидания процесса внутри монитора, вводятся условные переменные: condition x, y; Условные переменные...
Описание слайда:
Мониторы: условные переменные Для реализации ожидания процесса внутри монитора, вводятся условные переменные: condition x, y; Условные переменные могут использоваться только в операциях wait и signal. Операция: x.wait(); означает, что выполнивший ее процесс задерживается до того момента, пока другой процесс не выполнит операцию: x.signal(); Операция x.signal возобновляет ровно один приостановленный процесс. Если приостановленных процессов нет, эта операция не выполняет никаких действий. Монитор является многовходовым модулем особого рода. Он содержит описания общих для нескольких параллельных процессов данных и операций над этими данными в виде процедур P1, …, Pn. Пользователи монитора – параллельные процессы – имеют доступ к описанным в нем общим данным только через его операции, причем в каждый момент времени не более чем один процесс может выполнять какую-либо операцию монитора; остальные процессы, желающие выполнить операцию монитора, должны ждать, пока первый процесс закончит выполнять мониторную операцию.

Слайд 102


Схематическое представление монитора
Описание слайда:
Схематическое представление монитора

Слайд 103


Монитор с условными переменными
Описание слайда:
Монитор с условными переменными

Слайд 104


Синхронизации Синхронизация в ОС Solaris Система Solaris предоставляет разнообразные виды блокировщиков для поддержки многозадачности,...
Описание слайда:
Синхронизации Синхронизация в ОС Solaris Система Solaris предоставляет разнообразные виды блокировщиков для поддержки многозадачности, многопоточности (включая потоки реального времени) и мультипроцессирования. Используются адаптивные мюьтексы (adaptive mutexes) – эффективное средство синхронизации доступа к данным при их обработке короткими сегментами кода. Для более длинных сегментов кода используются условные переменные и блокировщики читателей-писателей (reader-writer locks; rwlocks).Для синхронизации потоков используются "вертушки" (turnstiles) – синхронизирующие примитивы, которые позволяют использовать либо adaptive mutex, либо rwlock. Синхронизация в Windows 2000 Для защиты доступа к данным на однопроцессорных системах используются маски прерываний. Для многопроцессорных систем используются spinlocks (" вертящиеся замки. В системе реализованы также объекты-диспетчеры, которые могут функционировать как мьютексы и как семафоры. Объекты-диспетчеры генерируют события, семантика которых аналогична семантике условной переменной.

Слайд 105


Пример: обедающие философы monitor dp { enum {thinking, hungry, eating} state[5]; condition self[5]; void pickup(int i) // following slides void...
Описание слайда:
Пример: обедающие философы monitor dp { enum {thinking, hungry, eating} state[5]; condition self[5]; void pickup(int i) // following slides void putdown(int i) // following slides void test(int i) // following slides void init() { for (int i = 0; i < 5; i++) state[i] = thinking; } }

Слайд 106


Обедающие философы: реализация операций pickup и putdown void pickup(int i) { state[i] = hungry; test[i]; if (state[i] != eating) self[i].wait(); }...
Описание слайда:
Обедающие философы: реализация операций pickup и putdown void pickup(int i) { state[i] = hungry; test[i]; if (state[i] != eating) self[i].wait(); } void putdown(int i) { state[i] = thinking; // test left and right neighbors test((i+4) % 5); test((i+1) % 5); }

Слайд 107


Обедающие философы: реализация операции test void test(int i) { if ( (state[(i + 4) % 5] != eating) && (state[i] == hungry) && (state[(i + 1) % 5] !=...
Описание слайда:
Обедающие философы: реализация операции test void test(int i) { if ( (state[(i + 4) % 5] != eating) && (state[i] == hungry) && (state[(i + 1) % 5] != eating)) { state[i] = eating; self[i].signal(); } }

Слайд 108


Реализация мониторов с помощью семафоров Используем семафоры mutex – для взаимного исключения процессов, next –для реализации очереди входа в...
Описание слайда:
Реализация мониторов с помощью семафоров Используем семафоры mutex – для взаимного исключения процессов, next –для реализации очереди входа в монитор; переменную next-count – счетчик процессов в очереди на вход: Переменные semaphore mutex; // (initially = 1) semaphore next; // (initially = 0) int next-count = 0; Каждая внешняя процедура F заменяется на: wait(mutex); … тело F; … if (next-count > 0) signal(next) else signal(mutex); Обеспечивается взаимное исключение внутри монитора.

Слайд 109


Реализация мониторов Для каждой условной переменной x: semaphore x-sem; // (initially = 0) int x-count = 0; Реализация операции x.wait: x-count++; if...
Описание слайда:
Реализация мониторов Для каждой условной переменной x: semaphore x-sem; // (initially = 0) int x-count = 0; Реализация операции x.wait: x-count++; if (next-count > 0) signal(next); else signal(mutex); wait(x-sem); x-count--;

Слайд 110


Реализация мониторов Реализация операции x.signal: if (x-count > 0) { next-count++; signal(x-sem); wait(next); next-count--; } Таким образом,...
Описание слайда:
Реализация мониторов Реализация операции x.signal: if (x-count > 0) { next-count++; signal(x-sem); wait(next); next-count--; } Таким образом, обеспечивается, что процесс, освобожденный из очереди к условной переменной, помещается во входную очередь монитора. Дополнительная операция над монитором, обеспечивающая организацию очереди к условной переменной по приоритетам, - x.wait(с),где c – целочисленный параметр, играющий роль приоритета. При выполнении операцииsignal первым будет освобожден из очереди процесс с меньшим значением приоритета. При реализации монитора необходимо проверять следующие условия: процессы должны выполнять вызовы операций монитора в правильной последовательности, своевременно вызывая все семафорные операции; никакой процесс не пытается обратиться к общим данным непосредственно, минуя протокол взаимодействия с монитором.

Слайд 111


Тупики Модель системы Для описания и исследования подобных ситуаций введем формальную модель системы в общем виде. С помощью модели будем...
Описание слайда:
Тупики Модель системы Для описания и исследования подобных ситуаций введем формальную модель системы в общем виде. С помощью модели будем представлять информацию о запросах процессов к ресурсам, о фактическом владении процессов ресурсами и об освобождении ресурсов. Пусть в системе имеется m видов ресурсов (например, процессор, память, устройства ввода-вывода). Будем обозначать типы ресурсов в системе R1, R2, … Rm. Пусть каждый тип ресурса Ri имеет Wi экземпляров. Каждый процесс может использовать ресурс одним из следующих способов: запрос (request) использование (use) освобождение (release). Тупик может возникнуть, если одновременно выполняются следующие четыре условия: взаимное исключение: только один процесс в каждый момент времени может получить доступ к ресурсу; удержание и ожидание: процесс, удерживающий один ресурс, ожидает приобретения других ресурсов, которыми обладают другие процессы; отсутствие прерываний: процесс может освободить ресурс только добровольно, когда завершит свою работу; циклическое ожидание: существует множество {P0, P1, … P0}, такое, что P0 ожидает ресурса, которым обладает P1; P1 ожидает ресурса, которым обладает P2 … Pn ожидает ресурса, которым обладает P0.

Слайд 112


Граф распределения ресурсов Множество вершин V и множество дуг E. V подразделяется на два типа вершин: P = {P1, P2, …, Pn}, множество всех процессов...
Описание слайда:
Граф распределения ресурсов Множество вершин V и множество дуг E. V подразделяется на два типа вершин: P = {P1, P2, …, Pn}, множество всех процессов в системе. R = {R1, R2, …, Rm}, множество всех ресурсов в системе. Дуга типа “запрос” (request edge) – направленная дуга Pi  Rj Дуга типа “присваивание” (assignment edge) – направленная дуга Rj  Pi Смысл различных направленностей дуг в следующем. Если процесс претендует на какой-либо ресурс, то дуга проводится из вершины-процесса в вершину-ресурс. Когда же конкретная единица ресурса уже выделена какому-либо конкретному процессу, то дуга, в знак этой принадлежности, и проводится из вершины-ресурса в вершину процесс.

Слайд 113


Граф распределения ресурсов (продолжение) Процесс Тип ресурса, имеющий 4 экземпляра Pi запрашивает экземпляр ресурса Rj Pi удерживает экземпляр...
Описание слайда:
Граф распределения ресурсов (продолжение) Процесс Тип ресурса, имеющий 4 экземпляра Pi запрашивает экземпляр ресурса Rj Pi удерживает экземпляр ресурса Rj

Слайд 114


Пример графа распределения ресурсов
Описание слайда:
Пример графа распределения ресурсов

Слайд 115


Граф распределения ресурсов с тупиком
Описание слайда:
Граф распределения ресурсов с тупиком

Слайд 116


Граф распределения ресурсов с циклом, но без тупика
Описание слайда:
Граф распределения ресурсов с циклом, но без тупика

Слайд 117


Если граф распределения ресурсов не содержит циклов, то в системе тупиков нет; Если граф распределения ресурсов не содержит циклов, то в системе...
Описание слайда:
Если граф распределения ресурсов не содержит циклов, то в системе тупиков нет; Если граф распределения ресурсов не содержит циклов, то в системе тупиков нет; Если граф распределения ресурсов содержит цикл, то возможно два случая: Если ресурсов каждого вида имеется только по одному экземпляру, то имеет место тупик; Если ресурсов по несколько экземпляров, то тупик возможен. Методы обработки тупиков Теоретически возможны следующие методы обработки тупиков: Убедиться в том, что система никогда не войдет в состояние тупика; Допустить, чтобы система могла входить в состояние тупика, но предусмотреть возможность восстановленияпосле тупика. К сожалению, на практике во многих ОС (включая UNIX) используется и третий "метод" борьбы с тупиками: проблема тупиков игнорируется, но авторы ОС без каких-либо обоснований претендуют на то, что в системе тупики невозможны.

Слайд 118


Предотвращение тупиков Основная идея – ограничить методы запросов ресурсов со стороны процессов. Чтобы ограничить возможность взаимного исключения...
Описание слайда:
Предотвращение тупиков Основная идея – ограничить методы запросов ресурсов со стороны процессов. Чтобы ограничить возможность взаимного исключения владения ресурсами (первое условие тупика), необходимо заметить, что оно требуется не для всех ресурсов. Для разделяемых ресурсов (например, массивов констант, кодов, файлов) оно не требуется. Чтобы ограничить возможность удержания и ожидания (второе условие тупика), можно потребовать, чтобы процесс, запрашивающий некоторый ресурс, не обладал бы больше никакими ресурсами. Альтернативным вариантом является требование, чтобы все процессы приобретали все необходимые им ресурсы до фактического начала их исполнения. Более разумной представляется стратегия перераспределения ресурсов при каждом ожидании процессом ресурса. Если процесс обладает некоторым ресурсом A и запрашивает другой ресурс B, который не может быть ему немедленно выделен, то процесс должен ждать. При этом ресурс A, занимаемый процессом, должен быть немедленно освобожден. Ресурс A добавляется к списку ресурсов, которые ожидает процесс. Процесс может быть возобновлен, только если ему могут быть выделены одновременно все старые ресурсы, которыми он обладал, и те новые ресурсы, которых он ожидает. Для предотвращения ситуации циклического ожидания самое простое решение – ввести упорядочение по номерам всех видов ресурсов и требовать, чтобы процесс запрашивал ресурсы только в порядке возрастания их номеров.

Слайд 119


Избежание тупиков Методы избежания тупиков требуют, чтобы система обладала дополнительной априорной информацией о процессе и его потребностях в...
Описание слайда:
Избежание тупиков Методы избежания тупиков требуют, чтобы система обладала дополнительной априорной информацией о процессе и его потребностях в ресурсах с момента ввода каждого процесса в систему. Наиболее простая и полезная модель требует, чтобы каждый процесс при вводе в систему указывал максимальный объем ресурсов каждого типа, которые могут ему понадобиться. Данный подход был реализован даже в ранних ОС и носит название паспорт задачи – список максимальных потребностей процесса в ресурсах каждого типа – оперативной и внешней памяти, времени выполнения, листах печати и др. Алгоритм избежания тупиков должен анализировать состояние распределения ресурсов, чтобы убедиться, что никогда не может возникнуть ситуация циклического ожидания. Состояние распределения ресурсов описывается как объем доступных ресурсов, объем распределенных ресурсов и максимальные требования процессов.

Слайд 120


Безопасное состояние системы Б С назовем такое состояние, перевод системы в которое не приведет к появлению тупиков. Общий принцип избежания тупиков...
Описание слайда:
Безопасное состояние системы Б С назовем такое состояние, перевод системы в которое не приведет к появлению тупиков. Общий принцип избежания тупиков состоит в следующем. Когда процесс запрашивает доступный ресурс, система должна определить, приведет ли немедленное выделение данного ресурса к безопасному состоянию системы. Система находится в безопасном состоянии, если существует безопасная последовательность, состоящая из всех процессов в системе. Безопасной последовательностью процессов называется последовательность процессов , такая, что для каждого процесса Pi ресурсы, которые он может еще запросить, могут быть выделены из текущих доступных ресурсов и ресурсов, удерживаемых процессами Pj , где j < i. Если последовательность процессов безопасна, то система может придерживаться следующей безопасной стратегии, с точки зрения распределения ресурсов и исполнения процессов: Если потребности процесса Pi в ресурсах не могут быть немедленно удовлетворены, то процесс может подождать, пока завершатся процессы Pj (где j < i), удерживающие требуемые ресурсы; Когда процессы Pj завершены, процесс Pi может получить требуемые ресурсы, выполниться, вернуть удерживаемые ресурсы и завершиться; После завершения процесса Pi , процесс Pi+1 может получить требуемые им ресурсы, и т.д. Таким образом, справедливы следующие утверждения: Если система в безопасном состоянии, тупиков нет; Если системы в небезопасном состоянии, тупики возможны; Для того, чтобы избежать тупиков, необходимо проверять перед выделением ресурсов, что система никогда не придет в небезопасное состояние.

Слайд 121


Граф распределения ресурсов для стратегии избежания тупиков
Описание слайда:
Граф распределения ресурсов для стратегии избежания тупиков

Слайд 122


Небезопасное состояние на графе распределения ресурсов
Описание слайда:
Небезопасное состояние на графе распределения ресурсов

Слайд 123


Алгоритм банкира Алгоритм банкира для безопасного распределения ресурсов операционной системой (с избежанием тупиков) был предложен Э. Дейкстрой и...
Описание слайда:
Алгоритм банкира Алгоритм банкира для безопасного распределения ресурсов операционной системой (с избежанием тупиков) был предложен Э. Дейкстрой и впервые реализован в операционной системе THE в конце 1960-х гг. Происхождение названия связано с тем, что поведение алгоритма напоминает осторожную стратегию банкира при проведении банковских операций. Принципы алгоритма банкира следующие. Каждый процесс должен априорно обозначить свои потребности в ресурсах по максимуму. Когда процесс запрашивает ресурс, ему, возможно придется подождать (выделение ресурсов по запросу не всегда может произойти немедленно). Когда процесс получает требуемые ресурсы, он должен их вернуть системе за ограниченный период времени. Структуры данных для алгоритма банкира Пусть n = число процессов; m = число типов ресурсов Avaliable: Вектор длины m. Если available [j] = k, до в данный момент доступны k экземпляров ресурса типа Rj . Max: Матрица n * m. Если Max [i,j] = k, то процесс Pi может запросить самое большее k экземпляров ресурса типа Rj. Allocation: Матрица n *m. Если Allocation[i,j] = k , то процессу Pi в данный момент выделено k экземпляров ресурса типа Rj. Need: Матрица n * m. Если Need[i,j] = k, то Pi может потребоваться еще k экземпляров ресурса Rj для завершения своей работы. Need [i,j] = Max[i,j] – Allocation [i,j].

Слайд 124


Алгоритм безопасности 1.Пусть Work и Finish – векторы длин m и n, соответственно. Инициализация: Work = Available Finish [i] = false для i = 1,2, …,...
Описание слайда:
Алгоритм безопасности 1.Пусть Work и Finish – векторы длин m и n, соответственно. Инициализация: Work = Available Finish [i] = false для i = 1,2, …, n. 2. Находим i такое, что: (a) Finish [i] = false (b) Need[i]  Work Если такого i нет, переходим к шагу 4. Work = Work + Allocation[I] Finish[i] = true Переход к шагу 2. Если Finish [i] == true для всех i, то система в безопасном состоянии. Алгоритм строит безопасную последовательность номеров процессов i, если она существует. На каждом шаге, после обнаружения очередного элемента последовательности, алгоритм моделирует освобождение i - мпроцессом ресурсов после его завершения. На шаге 1 присваивание векторов выполняется поэлементно. На шаге 2, Need – матрица потребностей (n * m); Need[i] - строка матрицы, представляющая вектор потребностей (длины m) процесса i. Сравнение выполняется поэлементно, и его результат считается истинным, если соотношение выполнено для всех элементов векторов На шаге 3, Allocation [i] С помощью вектора Work моделируется освобождение ресурсов i – м процессом, после чего процессу присваивается признак завершаемости.

Слайд 125


Алгоритм запроса ресурсов для процесса Pi Request = вектор запросов для процесса Pi. Если Requesti [j] = k , то процесс Pi запрашивает k экземпляров...
Описание слайда:
Алгоритм запроса ресурсов для процесса Pi Request = вектор запросов для процесса Pi. Если Requesti [j] = k , то процесс Pi запрашивает k экземпляров ресурса типа Rj. 1. Если Requesti  Needi , перейти к шагу 2. Иначе сгенерировать исключительную ситуацию, т.к. Процесс превысил свои максимальные потребности. 2. Если Requesti  Available, перейти к шагу 3. Иначе процесс Pi должен ждать, так как ресурс недоступен. 3. Спланировать выделение ресурса процессу Pi , модифицируя состояние следующим образом: Available = Available - Requesti; Allocationi = Allocationi + Requesti; Needi = Needi – Requesti;; Если состояние безопасно  ресурс выделяется Pi. Если состояние небезопасно  Pi должен ждать; восстанавливается предыдущее состояние распределения ресурсов

Слайд 126


Пример (продолжение) Состояние матрицы. Need определяется как (Max – Allocation). Need A B C P0 7 4 3 P1 1 2 2 P2 6 0 0 P3 0 1 1 P4 4 3 1 Система в...
Описание слайда:
Пример (продолжение) Состояние матрицы. Need определяется как (Max – Allocation). Need A B C P0 7 4 3 P1 1 2 2 P2 6 0 0 P3 0 1 1 P4 4 3 1 Система в безопасном состоянии, т.к. < P1, P3, P4, P2, P0> удовлетворяет критерию безопасности.

Слайд 127


Пример (продолжение). Запрос процесса P1: (1,0,2) Проверяем, что Request  Available, то есть, (1,0,2)  (3,3,2)  true. Allocation Need Available A...
Описание слайда:
Пример (продолжение). Запрос процесса P1: (1,0,2) Проверяем, что Request  Available, то есть, (1,0,2)  (3,3,2)  true. Allocation Need Available A B C A B C A B C P0 0 1 0 7 4 3 2 3 0 P1 3 0 2 0 2 0 P2 3 0 1 6 0 0 P3 2 1 1 0 1 1 P4 0 0 2 4 3 1 Исполнение алгоритма безопасности показывает, что удовлетворяет критерию безопасности.

Слайд 128


Случай, когда каждый тип ресурса имеет единственный экземпляр Строим и поддерживаем wait-for граф Вершины - процессы. Pi  Pj , если Pi ожидает Pj....
Описание слайда:
Случай, когда каждый тип ресурса имеет единственный экземпляр Строим и поддерживаем wait-for граф Вершины - процессы. Pi  Pj , если Pi ожидает Pj. Периодически вызываем алгоритм, который проверяет отсутствие циклов в этом графе. Алгоритм обнаружения цикла в графе требует O(n2) операций, где n – число вершин в графе.

Слайд 129


Граф распределения ресурсов и граф wait-for
Описание слайда:
Граф распределения ресурсов и граф wait-for

Слайд 130


Случай, когда ресурсы существуют в нескольких экземплярах для каждого типа Available: Вектор длины m; указывает наличие ресурсов каждого типа....
Описание слайда:
Случай, когда ресурсы существуют в нескольких экземплярах для каждого типа Available: Вектор длины m; указывает наличие ресурсов каждого типа. Allocation: Матрица n x m , определяющая число ресурсов каждого типа, выделенных каждому процессу. Request: Матрица n x m , задающая запросы для каждого процесса. Если Request [ij] = k, то процесс Pi запрашивает (еще) k экземпляров ресурса типа Rj.

Слайд 131


Алгоритм обнаружения тупиков Пусть Work и Finish – векторы длин m и n, соответственно. 1. Инициализация: (a) Work = Available (b) For i = 1,2, …, n,...
Описание слайда:
Алгоритм обнаружения тупиков Пусть Work и Finish – векторы длин m и n, соответственно. 1. Инициализация: (a) Work = Available (b) For i = 1,2, …, n, if Allocationi  0, then Finish[i] = false; otherwise, Finish[i] = true. 2. Найти индекс i такой, что: (a) Finish[i] == false (b) Requesti  Work Если нет такого i , перейти к шагу 4. 3. Work = Work + Allocationi Finish[i] = true перейти к шагу 2. 4. Если Finish[i] == false для некоторого i, 1  i  n, то система в состоянии тупика. Более того, если Finish[i] == false, то Pi – в состоянии тупика. Алгоритм требует O(m x n2) операций для определения того, находится ли система в тупиковом состоянии.

Слайд 132


Алгоритм обнаружения: пример Пусть имеются пять процессов P0 - P4 и три типа ресурсов A (7 экземпляров), B (2 экземпляра) и C (6 экземпляров). В...
Описание слайда:
Алгоритм обнаружения: пример Пусть имеются пять процессов P0 - P4 и три типа ресурсов A (7 экземпляров), B (2 экземпляра) и C (6 экземпляров). В момент времени T0: Распределение__Запрос A B C A B C A B C P0 0 1 0 0 0 0 0 0 0 P1 2 0 0 2 0 2 P2 3 0 3 0 0 0 P3 2 1 1 1 0 0 P4 0 0 2 0 0 2 Последовательность будет завершена Finish[i] = true для всех i. >системе следует использовать рассмотренный алгоритм обнаружения тупиков, зависит от того, как часто, по всей вероятности, будет иметь место тупик и сколько процессов будет необходимо откатить назад, чтобы выйти из тупика. Ответ на последний вопрос: по одному процессу для каждого из не пересекающихся циклов.

Слайд 133


Алгоритм обнаружения: продолжение P2 запрашивает дополнительный ресурс типа C. Запрос A B C P0 0 0 0 P1 2 0 1 P2 0 0 1 P3 1 0 0 P4 0 0 2 Состояние...
Описание слайда:
Алгоритм обнаружения: продолжение P2 запрашивает дополнительный ресурс типа C. Запрос A B C P0 0 0 0 P1 2 0 1 P2 0 0 1 P3 1 0 0 P4 0 0 2 Состояние системы? Может вновь запросить ресурсы, которыми обладает процесс P0, но не имеет достаточно ресурсов, чтобы удовлетворить запросы друих процесов. Имеет место тупик, в котором находятся процессы P1, P2, P3 и P4.

Слайд 134


Восстановление после тупика Для выхода из тупика, очевидно, система должна прекратить все заблокированные процессы и освободить занимаемые ими...
Описание слайда:
Восстановление после тупика Для выхода из тупика, очевидно, система должна прекратить все заблокированные процессы и освободить занимаемые ими ресурсы. Для более оптимального выполнения данного действия, система может прекращать на каждом шаге по одному процессу и после этого анализировать, ликвидирован ли тупик. Важный вопрос – в каком порядке необходимо прекращать процессы? Существуют различные подходы: В порядке приоритетов процессов; В зависимости то того, насколько долго процесс уже выполняется и сколько времени осталось до его завершения; В зависимости от объема ресурсов, которые удерживал процесс; В зависимости от объема ресурсов, требуемого для завершения процесса; В зависимости от того, сколько всего процессов требуется прекратить; В зависимости от того, является ли процесс интерактивным или пакетным. После выбора процесса-"жертвы" с минимальной стоимостью (по одному из приведенных критериев), система прекращает выбранный процесс (процессы), освобождает их ресурсы и выполняет перераспределение ресурсов. Система выполняет "откат" к какому-либо предыдущему безопасному состоянию. В результате многократного выполнения подобных действий системы, возможно "голодание", так как в качестве жертвы может многократно выбираться один и тот же процесс.

Слайд 135


Управление памятью Основные положения размещения процессов в памяти Любая прога,введ в сист, д.б. размещ в памяти и оформл в виде проца для ее выпо....
Описание слайда:
Управление памятью Основные положения размещения процессов в памяти Любая прога,введ в сист, д.б. размещ в памяти и оформл в виде проца для ее выпо. Каждая прога при вводе в систему помещ во вх очередь – совокупн процессов на диске, ожидающих размещения в памяти для выполнения своих программ. До своего выполнения пользовательские программы проходят в системе несколько стадий. Связывание прог и данных с адресами в памяти Перед загр данных или кода в память они должны быть в какой-либо момент связ с определ адресами в памяти. Связыв может вып-ся на разных этапах:-Связ во время компиляции (compile-time). Если адрес в памяти априорно известен, компилятором может быть сгенерирован код с абсолютными адресами. -Связ во время загрузки (load-time). Загрузка программы в память – стадия ее обработки системой, предшествующая выполнению программы. Связывание во время исполнения (runtime), или динамическое (позднее) связывание. Используется, если процесс во время выполнения может быть перемещен из одного сегмента памяти в другой.

Слайд 136


Многоэтапная обработка пользовательской программы
Описание слайда:
Многоэтапная обработка пользовательской программы

Слайд 137


Исходный код программы (в форме текстового файла) на языке высокого уровня или на ассемблере преобразуется компилятором или ассемблером в объектный...
Описание слайда:
Исходный код программы (в форме текстового файла) на языке высокого уровня или на ассемблере преобразуется компилятором или ассемблером в объектный модуль, содержащий бинарные выполняемые машинные команды итаблицу символов, определенных и использованных в данном модуле кода. Рассмотренная фаза называетсявременем компиляции. Исходный код программы (в форме текстового файла) на языке высокого уровня или на ассемблере преобразуется компилятором или ассемблером в объектный модуль, содержащий бинарные выполняемые машинные команды итаблицу символов, определенных и использованных в данном модуле кода. Рассмотренная фаза называетсявременем компиляции. Следующая фаза обработки программы – редактирование связей. Редактор связей (linker) – системная программа, которая получает на вход один или несколько объектных модулей, а на выходе выдает загрузочный модуль – двоичный код, образованный кодом нескольких объектных модулей, в котором разрешены все межмодульные ссылки - для каждого символа. Загрузочный модуль может быть загружен в память для исполнения с помощью еще одной системной программы –загрузчика (loader), который получает на вход загрузочный модуль и файлы с бинарными кодами системных библиотек, которые использует программа. Загрузчик, объединяя код программы с кодами системных библиотек, создает бинарный образ программы в памяти.

Слайд 138


Логическое и физическое адресное пространство Концепция логического адресного пространства, связанного с соответствующим физическим адресным...
Описание слайда:
Логическое и физическое адресное пространство Концепция логического адресного пространства, связанного с соответствующим физическим адресным пространством, является одной из основных для управления памятью. Логическим адресом называется адрес, генерируемый процессором при выполнении машинной команды. Физический адрес – это реальный адрес в памяти, который "видит" и "понимает" устройство управления памятью (Memory Management Unit – MMU). Логические адреса совпадают с физическими при связывании адресов во время компиляции или во время загрузки (т.е. до исполнения программы). Однако при связывании адресов во время выполнения логические адреса отличаются от физических. Далее рассмотрим этот вопрос подробнее. устройство управления памятью (Memory Management Unit – MMU) – это один из модулей аппаратуры, отвечающий за адресацию памяти и связанный с процессором и другими устройствами системной шиной. Аппаратура MMU использует значение регистра перемещения, содержащего адрес начала области памяти, выделенной ОС для программы пользователя. Программа пользователя работает только с логическими адресами и не "видит" физических адресов.

Слайд 139


Динамическое перемещение с использованием регистра перемещения
Описание слайда:
Динамическое перемещение с использованием регистра перемещения

Слайд 140


Динамическая загрузка и динамическая линковка Под динамической загрузкой понимается загрузка подпрограммы в память при первом обращении к ней из...
Описание слайда:
Динамическая загрузка и динамическая линковка Под динамической загрузкой понимается загрузка подпрограммы в память при первом обращении к ней из пользовательской программы. Это весьма полезный принцип, если требуется сэкономить память, поскольку никакой "лишний" код в этом случае в память не загружается. Линковка (linking) – то же, что и редактирование связей и загрузка. С динамической загрузкой вызываемых подпрограмм тесно связан другой родственный механизм – динамическая линковка: линковка во время исполнения программы. В коде программы размещается заглушка для исполнения (execution stub) – небольшой фрагмент кода, выполняющий системный вызов модуля ОС, размещающего в памяти код динамически линкуемой библиотечной подпрограммы.

Слайд 141


Оверлейная структура для двухпросмотрового ассемблера
Описание слайда:
Оверлейная структура для двухпросмотрового ассемблера

Слайд 142


Схема откачки и подкачки
Описание слайда:
Схема откачки и подкачки

Слайд 143


Аппаратная поддержка регистров перемещения и границы Смежное распределение памяти
Описание слайда:
Аппаратная поддержка регистров перемещения и границы Смежное распределение памяти

Слайд 144


Фрагментация Фрагментация – это дробление памяти на мелкие не смежные свободные области маленького размера. Фрагментация возникает после выполнения...
Описание слайда:
Фрагментация Фрагментация – это дробление памяти на мелкие не смежные свободные области маленького размера. Фрагментация возникает после выполнения системой большого числа запросов на память, таких, что размеры подходящих свободных участков памяти оказываются немного больше, чем требуемые. Фрагментация бывает внутренняя и внешняя. внешней фрагментации имеется достаточно большая область свободной памяти, но она не является непрерывной. Внутренняя фрагментация может возникнуть вследствие применения системой специфической стратегии выделения памяти, при которой фактически в ответ на запрос память выделяется несколько большего размера, чем требуется, - например, с точностью до страницы (листа ), размер которого – степень двойки. Страничная организация памяти подробно рассматривается далее в данной лекции. Внешняя фрагментация может быть уменьшена или ликвидирована путем применения компактировки (compaction) –сдвига или перемешивания памяти с целью объединения всех не смежных свободных областей в один непрерывный блок. При компактировке памяти и анализе свободных областей может быть выявлена проблема зависшей задачи: какая-либо задача может "застрять" в памяти, так как выполняет ввод-вывод в свою область памяти (по этой причине откачать ее невозможно). Решение данной проблемы: ввод-вывод должен выполняться только в специальные буфера,выделяемой для этой цели операционной системой.

Слайд 145


Архитектура трансляции адресов
Описание слайда:
Архитектура трансляции адресов

Слайд 146


Пример страничной организации
Описание слайда:
Пример страничной организации

Слайд 147


Список свободных фреймов
Описание слайда:
Список свободных фреймов

Слайд 148


Аппаратная поддержка страничной организации: TLB
Описание слайда:
Аппаратная поддержка страничной организации: TLB

Слайд 149


Эффективное время поиска (effective access time – EAT) Ассоциативный поиск =  единиц времени Предположим, что цикл памяти – 1 микросекунда Hit ratio...
Описание слайда:
Эффективное время поиска (effective access time – EAT) Ассоциативный поиск =  единиц времени Предположим, что цикл памяти – 1 микросекунда Hit ratio – отношение, указывающее, сколько раз (в среднем) номер страницы будет найден по ассоциативным регистрам. Отношение зависит от размера кэш-памяти . Hit ratio =  TLB- эмпирическую вероятность нахождения номера страницы в ассоциативной памяти. Вычислим математическое ожидание времени доступа – Effective Access Time (EAT).Вероятность того, что номер страницы не будет найден в TLB, равна 1 – . Тогда получим: Effective Access Time (EAT) EAT = (1 + )  + (2 + )(1 – ) = 2 +  – 

Слайд 150


Бит valid/invalid в таблице страниц
Описание слайда:
Бит valid/invalid в таблице страниц

Слайд 151


Схема двухуровневых таблиц страниц
Описание слайда:
Схема двухуровневых таблиц страниц

Слайд 152


Схема адресной трансляции
Описание слайда:
Схема адресной трансляции

Слайд 153


Хешированная таблица страниц
Описание слайда:
Хешированная таблица страниц

Слайд 154


Архитектура инвертированной таблицы страниц
Описание слайда:
Архитектура инвертированной таблицы страниц

Слайд 155


Пример: разделяемые страницы
Описание слайда:
Пример: разделяемые страницы

Слайд 156


Программа с точки зрения пользователя
Описание слайда:
Программа с точки зрения пользователя

Слайд 157


Архитектура сегментной организации памяти Логический адрес ~ пара: , Таблица сегментов – служит для отображения логических адресов в физические;...
Описание слайда:
Архитектура сегментной организации памяти Логический адрес ~ пара: , Таблица сегментов – служит для отображения логических адресов в физические; каждый ее элемент содержит: base – начальный адрес сегмента в оперативной (физической) памяти. limit – длину сегмента. Базовый регистр таблицы сегментов - segment-table base register (STBR) срдержит адрес таблицы сегментов в памяти. Регистр длины таблицы сегментов - segment-table length register (STLR) содержит число сегментов, используемое программой; номер сегмента s корректен, если s < STLR.

Слайд 158


Аппаратная поддержка сегментного распределения памяти
Описание слайда:
Аппаратная поддержка сегментного распределения памяти

Слайд 159


Пример сегментной организации памяти
Описание слайда:
Пример сегментной организации памяти

Слайд 160


Совместное использование сегментов
Описание слайда:
Совместное использование сегментов

Слайд 161


Схема трансляции адресов в MULTICS
Описание слайда:
Схема трансляции адресов в MULTICS

Слайд 162


Трансляция адресов в Intel 386
Описание слайда:
Трансляция адресов в Intel 386

Слайд 163


Виртуальная память больше, чем физическая память
Описание слайда:
Виртуальная память больше, чем физическая память

Слайд 164


Преобразование страничной памяти в непрерывное дисковое пространство
Описание слайда:
Преобразование страничной памяти в непрерывное дисковое пространство

Слайд 165


Пример таблицы страниц, в которой не все страницы присутствуют в памяти
Описание слайда:
Пример таблицы страниц, в которой не все страницы присутствуют в памяти

Слайд 166


Этапы обработки ситуации отсутствия страницы в памяти
Описание слайда:
Этапы обработки ситуации отсутствия страницы в памяти

Слайд 167


Оценка производительности стратегии обработки страницы по требованию Коффициент отказов страниц (Page Fault Rate) 0  p  1.0 Если p = 0 – отсутствие...
Описание слайда:
Оценка производительности стратегии обработки страницы по требованию Коффициент отказов страниц (Page Fault Rate) 0  p  1.0 Если p = 0 – отсутствие отказов страниц Если p = 1, каждое обращение к странице приводит к отказу Эффективное время доступа (Effective Access Time - EAT) EAT = (1 – p) * время доступа к памяти + p * (время реакции на отказ + [время откачки страницы ] + время подкачки страницы + время рестарта)

Слайд 168


Файлы, отображаемые в память
Описание слайда:
Файлы, отображаемые в память

Слайд 169


Пример: замещение страниц
Описание слайда:
Пример: замещение страниц

Слайд 170


Замещение страниц
Описание слайда:
Замещение страниц

Слайд 171


График зависимости числа отказов страниц от числа фреймов
Описание слайда:
График зависимости числа отказов страниц от числа фреймов

Слайд 172


Алгоритм FIFO (First-in-First-Out) Наиболее простой алгоритм замещения страниц – в качестве жертвы всегда выбирается фрейм, первым из имеющихся...
Описание слайда:
Алгоритм FIFO (First-in-First-Out) Наиболее простой алгоритм замещения страниц – в качестве жертвы всегда выбирается фрейм, первым из имеющихся считанный в основную память. Строка запросов: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 3 фрейма (3 страницы могут быть одновременно в памяти для одного процесса) (1, 2, 3) (4, 1, 2) (5, 3, 4) 9 отказов страниц 4 фрейма (1, 2, 3, 4) (5, 1, 2, 3) (4, 5) 10 (!) отказов страниц FIFO – алгоритм замещения => аномалия Belady больше фреймов  меньше отказов страниц

Слайд 173


Пример замещения страниц по алгоритму FIFO
Описание слайда:
Пример замещения страниц по алгоритму FIFO

Слайд 174


Аномалия Belady при использовании алгоритма FIFO замещения страниц
Описание слайда:
Аномалия Belady при использовании алгоритма FIFO замещения страниц

Слайд 175


Алгоритм Least Recently Used (LRU) Замещается та страница, которая раньше всего использовалась. Строка запросов: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5...
Описание слайда:
Алгоритм Least Recently Used (LRU) Замещается та страница, которая раньше всего использовалась. Строка запросов: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 (1 2 3 4) 5 5 3 4 Реализация счетчиков: Каждый элемент таблицы страниц содержит счетчик; каждый раз при обращении к странице через некоторый элемент таблицы страниц содержимое часов (clock) копируется в его поле счетчика. Когда требуется изменение в конфигурации страниц, необходимо проанализировать поля счетчиков, чтобы определить, какую именно страницу заместить (ту, у которой содержимое поля счетчика меньше => требуется применить алгоритм поиска минимального элемента в массиве; сложность O(n), где n – длина таблицы страниц)

Слайд 176


Замещение страниц по алгоритму LRU
Описание слайда:
Замещение страниц по алгоритму LRU

Слайд 177


Использование стека для хранения информации о самых недавних обращениях к страницам
Описание слайда:
Использование стека для хранения информации о самых недавних обращениях к страницам

Слайд 178


Алгоритмы, близкие к LRU Имеется несколько алгоритмов, близких к алгоритму LRU, в которых реализованы различные идеи улучшений или упрощений,...
Описание слайда:
Алгоритмы, близкие к LRU Имеется несколько алгоритмов, близких к алгоритму LRU, в которых реализованы различные идеи улучшений или упрощений, направленные на то, чтобы уменьшить недостатки LRU. Бит ссылки (reference bit).В данном алгоритме с каждой страницей связывается бит, первоначально равный 0. При обращении к странице бит устанавливается в 1. Далее, при необходимости замещения страниц, заменяется та страница, у которой бит равен 0 (если такая существует), т.е. страница, к которой не было обращений. Данная версия алгоритма позволяет избежать поиска по таблице страниц. Однако она, очевидно, менее оптимальна, чем LRU. Второй шанс (second chance).В данной версии алгоритма используются ссылочный бит и показания часов, которые хранятся в каждом элементе таблицы страниц. Замещение страниц основано на показаниях часов. Если страница, которую следует заместить (по показаниям часов), имеет ссылочный бит, равный 1, то выполняются следующие действия: Установить ссылочный бит в 0; Оставить страницу в памяти; Заместить следующую страницу (по показаниям часов), по тем же самым правилам.

Слайд 179


Алгоритм второго шанса
Описание слайда:
Алгоритм второго шанса

Слайд 180


Фиксированное выделение Равномерное распределение – например, если имеется 100 фреймов и 5 процессов, каждому выделяется по 20 страниц....
Описание слайда:
Фиксированное выделение Равномерное распределение – например, если имеется 100 фреймов и 5 процессов, каждому выделяется по 20 страниц. Пропорциональное распределение – выделять фреймы в соответствии со следующим принципом:если общее число фреймов m, размер процесса – s, а общий размер всех процессов – S, то общее число фреймов, выделенных процессу, равно:a = m * (s / S).

Слайд 181


Thrashing
Описание слайда:
Thrashing

Слайд 182


Модель рабочего множества thrashing происходит, если сумма размеров локальных потребностей процессов в основной памяти больше общего размера...
Описание слайда:
Модель рабочего множества thrashing происходит, если сумма размеров локальных потребностей процессов в основной памяти больше общего размера памяти.Для борьбы с подобными явлениями в операционных системах для распределения фреймов используется модельрабочего множества.   рабочее множество  фиксированное число обращений к страницам WSSi (рабочее множество процесса Pi) = общее число обращений к страницам в самой недавней  (меняется в зависимости от времени) если  очень мало, не рассматриваем полную локальную потребность. Если  слишком велико, рассматриваем несколько локальных потребностей. Если  =   рассматриваем всю программу. D =  WSSi  общий объем требований фреймов Если D > m  Thrashing (m - общий размер памяти) Политика ОС: если D > m, приостановить один из процессов.

Слайд 183


Модель рабочего множества
Описание слайда:
Модель рабочего множества

Слайд 184


Атрибуты файлов Имя (Name) – информация в символьной форме, воспринимаемая человеком. Тип (Type) – необходим для систем, которые поддерживают...
Описание слайда:
Атрибуты файлов Имя (Name) – информация в символьной форме, воспринимаемая человеком. Тип (Type) – необходим для систем, которые поддерживают различные типы файлов (Эльбрус: тип файла – число; 0 – данные, 2 – код, 3 – текст и т.д.). В MS DOS, Windows, UNIX тип файла приняно кодировать расширением имени. Размещение (Location) – указатель на размещение файла на устройстве. Размер (Size) – текущий размер файла. Защита (Protection) – управляющая информация о том, кто может читать, изменять и исполнять файл. Время, дата, идентификация пользователя. Информация о файлах хранится в структуре директорий.

Слайд 185


Операции над файлом Создание - Create Запись - Write Чтение - Read Поиск позиции внутри файла - Seek Удаление - Delete Сокращение - Truncate Open(Fi)...
Описание слайда:
Операции над файлом Создание - Create Запись - Write Чтение - Read Поиск позиции внутри файла - Seek Удаление - Delete Сокращение - Truncate Open(Fi) – поиск в структуре директорий на диске элемента Fi, и перемещение содержимого элемента в память. Close (Fi) – переместить содержимое элемента Fi из памяти в структуру директорий на диске.

Слайд 186


Типы файлов – имя и расширение
Описание слайда:
Типы файлов – имя и расширение

Слайд 187


Методы доступа к файлам Последовательный доступ read next write next reset rewrite Прямой доступ read n write n position to n read next write next...
Описание слайда:
Методы доступа к файлам Последовательный доступ read next write next reset rewrite Прямой доступ read n write n position to n read next write next rewrite n n = относительный номер блока

Слайд 188


Файл последовательного доступа
Описание слайда:
Файл последовательного доступа

Слайд 189


Моделирование последовательного доступа для файла с прямым доступом
Описание слайда:
Моделирование последовательного доступа для файла с прямым доступом

Слайд 190


Пример индексного файла и файла, представляющего отношение (relative file)
Описание слайда:
Пример индексного файла и файла, представляющего отношение (relative file)

Слайд 191


Типичная организация файловой системы
Описание слайда:
Типичная организация файловой системы

Слайд 192


Одноуровневая организация для всех пользователей – проблемы с группировкой и именованием
Описание слайда:
Одноуровневая организация для всех пользователей – проблемы с группировкой и именованием

Слайд 193


Двухуровневая организация
Описание слайда:
Двухуровневая организация

Слайд 194


Древовидная структура директорий
Описание слайда:
Древовидная структура директорий

Слайд 195


Структура директорий в виде ациклического графа (с разделяемыми директориями и файлами)
Описание слайда:
Структура директорий в виде ациклического графа (с разделяемыми директориями и файлами)

Слайд 196


Структура директорий в виде произвольного графа
Описание слайда:
Структура директорий в виде произвольного графа

Слайд 197


Дерево смонтированных систем (а) и еще не смонтированная файловая система (b)
Описание слайда:
Дерево смонтированных систем (а) и еще не смонтированная файловая система (b)

Слайд 198


Точка монтирования
Описание слайда:
Точка монтирования

Слайд 199


Защита (protection) Создатель файла должен иметь возможность управлять: Списком допустимых операций над файлом Списком пользователей, которым они...
Описание слайда:
Защита (protection) Создатель файла должен иметь возможность управлять: Списком допустимых операций над файлом Списком пользователей, которым они разрешены Типы доступа: Read Write Execute Append Delete List

Слайд 200


Списки доступа и группы (UNIX) Режимы доступа: read, write, execute Три класса пользователей: RWX a) owner access 7  1 1 1 RWX b) group access 6  1...
Описание слайда:
Списки доступа и группы (UNIX) Режимы доступа: read, write, execute Три класса пользователей: RWX a) owner access 7  1 1 1 RWX b) group access 6  1 1 0 RWX c) public access 1  0 0 1 Системный администратор создает группу (например, JAVA) и включает в нее нескольких пользователей. Для конкретного файла (например, game) или поддиректории определяются соответствующие полномочия доступа Для директории “X” означает возможность входа в нее (cd)

Слайд 201


Типичная структура блока управления файлом
Описание слайда:
Типичная структура блока управления файлом

Слайд 202


Схема организации виртуальной файловой системы
Описание слайда:
Схема организации виртуальной файловой системы

Слайд 203


Смежное размещение файла на диске
Описание слайда:
Смежное размещение файла на диске

Слайд 204


Ссылочное размещение файла
Описание слайда:
Ссылочное размещение файла

Слайд 205


File Allocation Table (FAT)
Описание слайда:
File Allocation Table (FAT)

Слайд 206


Пример индексируемого размещения
Описание слайда:
Пример индексируемого размещения

Слайд 207


Управление свободной памятью Битовый вектор (n блоков)
Описание слайда:
Управление свободной памятью Битовый вектор (n блоков)

Слайд 208


Управление свободной памятью (прод.) Битовые шкалы требуют дополнительной памяти. Пример: размер блока = 212 байтов размер диска = 230 байтов (1 GB)...
Описание слайда:
Управление свободной памятью (прод.) Битовые шкалы требуют дополнительной памяти. Пример: размер блока = 212 байтов размер диска = 230 байтов (1 GB) n = 230/212 = 218 битов (или 32 KB) Легко получать смежно расположенные файлы Связанный список (свободной памяти): Невозможно легко получить смежную область памяти Нет лишнего расходования памяти

Слайд 209


Связанный список свободной дисковой памяти
Описание слайда:
Связанный список свободной дисковой памяти

Слайд 210


Различные методы размещения кэша для диска
Описание слайда:
Различные методы размещения кэша для диска

Слайд 211


Ввод-вывод без унифицированной буферной кэш-памяти
Описание слайда:
Ввод-вывод без унифицированной буферной кэш-памяти

Слайд 212


Ввод-вывод с использованием унифицированной буферной кэш-памяти
Описание слайда:
Ввод-вывод с использованием унифицированной буферной кэш-памяти

Слайд 213


Три независимых файловых системы
Описание слайда:
Три независимых файловых системы

Слайд 214


Типовая структура шины ПК
Описание слайда:
Типовая структура шины ПК

Слайд 215


Расположение портов для устройств на ПК (частично)
Описание слайда:
Расположение портов для устройств на ПК (частично)

Слайд 216


Опрос устройств (polling) Определяет состояние устройства command-ready – готово к выполнению команд; busy – занято; error – ошибка. Цикл busy-wait...
Описание слайда:
Опрос устройств (polling) Определяет состояние устройства command-ready – готово к выполнению команд; busy – занято; error – ошибка. Цикл busy-wait ожидания ввода-вывода с устройством Прерывания Линия запросов на прерывания (interrupt request – IRQ) переключается устройством ввода-вывода, которое сигнализирует с помощью запроса на прерывание о начале или окончании ввода-вывода. Обработчик прерываний получает сигнал о прерывании. Сигнал может бытьзамаскирован (maskable), чтобы игнорировать или задержать прерывание – например, если прерывание произошло в обработчике другого прерывания.

Слайд 217


Цикл ввода-вывода, управляемого прерываниями
Описание слайда:
Цикл ввода-вывода, управляемого прерываниями

Слайд 218


Вектор прерываний (событий) в процессоре Intel Pentium
Описание слайда:
Вектор прерываний (событий) в процессоре Intel Pentium

Слайд 219


Процесс выполнения DMA (Direct Memory Access)
Описание слайда:
Процесс выполнения DMA (Direct Memory Access)

Слайд 220


Структура модулей ввода-вывода в ядре
Описание слайда:
Структура модулей ввода-вывода в ядре

Слайд 221


Характеристики устройств ввода-вывода
Описание слайда:
Характеристики устройств ввода-вывода

Слайд 222


Структура модулей ввода-вывода в ядре UNIX
Описание слайда:
Структура модулей ввода-вывода в ядре UNIX

Слайд 223


Жизненный цикл запроса на ввод-вывод
Описание слайда:
Жизненный цикл запроса на ввод-вывод

Слайд 224


Взаимодействие между компьютерами
Описание слайда:
Взаимодействие между компьютерами

Слайд 225


Структура STREAMS
Описание слайда:
Структура STREAMS

Скачать

Похожие презентации
Mypresentation.ru
Загрузить презентацию