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

машин

1000 /* или другое конкретное значение */
typedef struct {

while (1) { /* бесконечный цикл */
while (((in +

(1) { /* бесконечный цикл */
while (in == out)

механизм в Java-технологии, аналогичный RPC
RMI позволяет Java-приложению на одной

активности
P1 24
P2 3
P3 3
Пусть порядок процессов таков: P1

Время ожидания для P1 = 0; P2 = 24; P3 = 27
Среднее время ожидания: (0 + 24 + 27)/3 = 17

P1 .
Диаграмма Ганта для их распределения:
Время ожидания: P1 = 6;

(с опережением)




Среднее время ожидания = (9 + 1 + 0

с использованием длин предыдущих периодов активности, используя экспоненциальное усреднение

τn+1 = tn
Учитывается только фактическая длина последнего периода активности.
Если обобщить

= 20
Процес Время активности
P1 53
P2 17
P3 68
P4 24
Диаграмма Ганта:
Обычно

Q1) и пакетными процессами по стратегии FCFS (очередь Q2). Первоначально

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

(времени разрешения конфликтов и собственно времени диспетчеризации) и времени исп критич проц реального времени.

сгенерированные элементы, процесс-потребитель использует и удаляет использованные элементы. Добавим в

do nothing */
buffer[in] = nextProduced;
in = (in + 1) %

do nothing */
nextConsumed = buffer[out];
out = (out + 1) %

как: register1 = counter
register1 = register1 + 1 counter = register1
Оператор “count—”

режиме (interleaving) приводит к следующему: producer: register1 = counter (register1

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

структура процесса Pi:
do {
entry section
critical section
exit section
remainder section
} while (1);
Процессы

i ⇒ процесс Pi может войти в критическую секцию
Процесс Pi

false.
flag [i] == true ⇒ Pi готов войти в критическую

Pi :
do {
flag [i]:= true; turn = j; while (flag [j] and

(американской) булочной, где каждому клиенту присваивается его номер в очереди.
Обозначения:

(number[0], number[1], …, number[n-1]) + 1;
choosing[i] = false;
for

атомарно выполняет считывание и запоминание значения переменной, затем изменяет его

Pi
do {
while (TestAndSet(lock)) ;
critical section
lock = false;
remainder section

решение для синхронизации – атомарная операция Swap, выполняющая перестановку значений двух

waiting[n];
Процесс Pi
do {
key = true;
while (key == true)
Swap(&lock, &key);
critical

(по Э. Дейкстре)
Семафо́р — объект, позволяющий войти

mutex = 1
Процесс Pi: do { wait(mutex);

целого значения и указателя на список ждущих процессов::
typedef struct {

добавить текущий процесс к S.L; block;
}
signal(S): S.value++;
if (S.value

только после того, как действие A исполнено в процессе Pi
Использовать

S2;
int C:
Инициализация:
S1 = 1
S2 = 0
C = начальное значение

{
signal(S1);
wait(S2);
}
signal(S1);

Операция signal:
wait(S1);
C ++;
if (C

циклического буфера ограниченной длины; производитель генерирует элементы информации и записывает

nextp к буферу
…
signal(mutex);
signal(full);
} while (1);

буфера в nextc
…
signal(mutex);
signal(empty);
…
использовать элемент из nextc
…
} while

процессов: читатели (которые могут только читать ресурс) и писатели (которые изменяют ресурс). В каждый

во-первых, должен увеличить значение readcount, причем обеспечить взаимное исключение для действий

…
wait(mutex);
readcount--;
if (readcount == 0){
signal(wrt);
signal(mutex):
}

семафоров chopstick, описывающий текущее состояние палочек:chopstick[i] закрыт, если палочка занята, открыт –

(впрочем, их число принципиального значения не имеет – для другого

области (critical regions) – более высокоуровневая и надежная конструкция для синхронизации,

n) { pool[in] = nextp; in:= (in+1) % n; count++; }
проверка переполнения буфера выполняется

buffer when (count > 0) { nextc = pool[out]; out = (out+1)

переменной x следующие переменные:
semaphore mutex, first-delay, second-delay; int first-count, second-count;
Взаимное

синхронизировать доступ к абстрактному типу данных.
monitor monitor-name
{
описания общих переменных
procedure body

переменные:
condition x, y;
Условные переменные могут использоваться только в операциях wait

поддержки многозадачности, многопоточности (включая потоки реального времени) и мультипроцессирования. Используются

(C) В.О. Сафонов, 2007

pickup(int i) // following slides
void putdown(int i)

= hungry;
test[i];
if (state[i] != eating)
self[i].wait();
}

void putdown(int i) {
state[i] = thinking;
//

+ 4) % 5] != eating) &&
(state[i] == hungry)

–для реализации очереди входа в монитор; переменную next-count – счетчик процессов в

0)
int x-count = 0;
Реализация операции x.wait:

x-count++;
if (next-count > 0)
signal(next);
else
signal(mutex);
wait(x-sem);
x-count--;

Таким образом, обеспечивается, что процесс, освобожденный из очереди к

подобных ситуаций введем формальную модель системы в общем виде. С

на два типа вершин:
P = {P1, P2, …, Pn}, множество

ресурса Rj


Pi удерживает экземпляр ресурса Rj

Pi
Pi

и четырьмя видами ресурсов: ресурсы видов 1 и 3 имеют

1, 2 и 3. Процесс 1 претендует на ресурс, которым

( имеется четыре процесса и два вида ресурсов. В цикле

тупиков нет;
Если граф распределения ресурсов содержит цикл, то возможно два

процессов.
Чтобы ограничить возможность взаимного исключения владения ресурсами (первое условие тупика),

информацией о процессе и его потребностях в ресурсах с момента

которое не приведет к появлению тупиков.
Общий принцип избежания тупиков состоит

к данному графу необходимо добавить информацию не только о фактических,

избежанием тупиков) был предложен Э. Дейкстрой и впервые реализован в

n, соответственно. Инициализация:
Work = Available
Finish [i] = false для i

процесса Pi. Если Requesti [j] = k , то процесс

C
P0 7 4 3
P1 1 2 2
P2 6

то есть, (1,0,2) ≤ (3,3,2) ⇒ true.
Allocation Need Available
A B C A B

wait-for граф
Вершины - процессы.
Pi → Pj , если Pi ожидает

Вектор длины m; указывает наличие ресурсов каждого типа.
Allocation: Матрица n

и n, соответственно.
1. Инициализация:
(a) Work = Available
(b) For i =

и три типа ресурсов
A (7 экземпляров), B

P0 0 0 0
P1 2 0 1
P2 0 0 1
P3 1 0 0

все заблокированные процессы и освободить занимаемые ими ресурсы. Для более

сист, д.б. размещ в памяти и оформл в виде проца

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

пространством, является одной из основных для управления памятью.
Логическим адресом называется адрес,

первом обращении к ней из пользовательской программы. Это весьма полезный

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

Типичный для ранних компьютеров и ОС пример программы с оверлейной структурой – двухпросмотровый ассемблер. 

системы по откачке (записи) образа неактивного процесса на диск или подкачке (считыванию) активного процесса

Файл откачки (backing store) - обл дисковой памяти, используемая операционной системой для хранения образов откачанных процессов. Файл откачки организ макс эффективно: обеспечивается прямой доступ ко всем образам процессов в памяти (например, через таблицу по номеру процесса).

на две смежных части (partitions), которые "растут" навстречу друг другу:

Наиболее простая и распространенная стратегия распределения памяти – смежное распределение памяти – распределение памяти для пользовательских процессов в одной смежной области памяти.

маленького размера. Фрагментация возникает после выполнения системой большого числа запросов

обозначают номер страницы, младшие – смещение внутри страницы. Номер страницы (p) 

Смещение внутри страницы (d) добавляется к ее базовому адресу. В результате формируется физический адрес, передаваемый в устройство управления памятью.

фреймы стр в осн памяти м.б. расп не смежно: логичстранице

область физической памяти. В системе имеется базовый регистр таблицы страниц (page

Пробла 2 обращ решается введением ассоц памяти (cache) страниц,называемой также буфер трансляции адресов(translation lookaside buffer – TLB.Ассоц
пам явл ассоци списком пар вида: (номер страницы, номер фрейма).Ее быстродействие значительно выше, чем у основной памяти и у регистров.

ε единиц времени
Предположим, что цикл памяти – 1 микросекунда
Hit ratio

организ возможно, что логич адрес сформирован неверно, и его номер

Элты 6 и 7 не соотв логич стран проца, поэтому в них биты valid-invalid устан взнач invalid. Поэтому при попытке обращения по логич адресу с номером стран 6 или 7 произойдет прерывание по неверной адресации.

В примере процесс имеет 6 логич стран с номерами от 0 до 5.

Табл стран имеет длину 8 (с элем от 0 до 7).

служит для отображения логических адресов в физические; каждый ее элемент

памяти

Fault Rate) 0 ≤ p ≤ 1.0
Если p = 0

жертвы всегда выбирается фрейм, первым из имеющихся считанный в основную

(LRU)
Замещается та страница, которая раньше всего

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

страницам

в которых реализованы различные идеи улучшений или упрощений, направленные на

дольше всего не исп, ей как бы дается второй шанс

5 процессов, каждому выделяется по 20 страниц.
Пропорциональное распределение – выделять

очень высок. Это приводит к тому, что процесс занят в

в основной памяти больше общего размера памяти.Для борьбы с подобными

(Type) – необходим для систем, которые поддерживают различные типы файлов

внутри файла - Seek
Удаление - Delete
Сокращение - Truncate
Open(Fi) – поиск

имя и расширение

n
position to n
read next
write next
rewrite n
n = относительный номер

именованием

поиск
Нет возможности группировки

файлами)

файлом
Списком пользователей, которым они разрешены
Типы доступа:
Read
Write
Execute
Append
Delete
List

пользователей:
RWX
a) owner access 7 ⇒ 1 1 1 RWX
b) group access 6 ⇒ 1

⇒ block[i] занят
Вычисление номера блока
(число битов в слове) *
(число нулевых

= 212 байтов
размер диска = 230 байтов (1 GB)
n =

корпуса компьютера через шлейфы внутренних жестких дисков, устройств CD – и DVD-ROM. 
В

занято;
error – ошибка.
Цикл busy-wait ожидания ввода-вывода с устройством
Прерывания
Линия запросов на прерывания (interrupt

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

устр-ва исп собст буф память, что приводит к необходимости двойной

скрывает различия между контроллерами ввода-вывода конкретных устройств от ядра ОС.
Устройства

ПО

Программный интерфейс ввода-вывода

из следующих этапов:
-Определяется устройство, на котором хранится файл;
-Выполняется трансляция имени

системе необходимо:
-Сократить число контекстных переключений;
-Сократить объем копирования данных;
-Сократить число прерываний,