Душанбе 2021
Операционные системы, черновики лекций
Операционные системы
http://mech.math.msu.su/~vvb/ (с 1991)
Экзамен в виде опроса (50 вопросов, проверяет компьютер).
Результат экзамены дает 30% окончательной оценки.
70% оценки составляет выполнение домашних заданий.
Программы мы будем писать на C/C++,
мы не будем использовать классы и библиотеки высокого уровня
языка C++. Программы мы будем реализовывать, используя
вызовы функций операционной системы.
Операционная система:
-- ее внутреннее устройство (Таннебаум. Операционные системы. Minix);
-- как использовать операционную систему максимально эффективно
при написании прикладных программ.
Самое важное понятие, связанное с операционными системами --
это API операционной системы
Application Program Interface
набор функций, как правило, на языке C
(хотя в старой Mac OS для компьютеров Apple/Mac
API был сформулирован на Pascal, до начала 2000-х годов,
с возвращением Стива Джобса и заменой старой OS на современную
Mac OS-X, которая является Unix-подобной системой, а Unix, конечно же,
основан на языке C).
Мы будем использовать MS Windows и писать программы, пользуясь API Windows --
оно называется Win32, было разработано в 1992 г. совместно фирмами Microsoft и
IBM, для разработки был приглашен Даве Каттлер из фирмы DEC (Digital Equipment
Corporation, сейчас это Hewlett Packard, впервых разработали 32-разрядный мини-
компьютер VAX 1980, операционная система VAX VMS), который разработал
ОС Windows NT + API Win32.
Для программирования можно использовать оболочку CodeBlocks
(используется компилятор MinGW -- Minimal GNU for Windows).
(В Unix имеется API POSIX -- начало 1980-х, намного более простой,
чем Win32. В пакете CygWIN используется компилятор gcc/g++ и API POSIX,
в MinGW -- тот же компилятор gcc/g++, но API Win32.)
===============================
1. Устройство компьютера
Фон-Неймановская архитектура:
программа и данные находятся в одной и той же оперативной памяти.
Данные могут интерпретироваться как программа и, обратно, программа
может создаваться и обрабатываться самим компьютером как данные.
Составные части компьютера.
2 части обязательны:
1) процессор -- основа, мозг компьютера, он выполняет команды;
2) оперативная память -- набор ячеек (байты, слова), в которых записаны
двоичные коды, их можно интерпретировать как целые числа, адреса
памяти, вещественные числа либо команды процессора.
Также у компьютера могут быть разные необязательные устройства:
монитор, клавиатура, дисковые накопители, графическая карта, сетевая карта,
устройста, подключаемая через USB -- принтер, флешка и т.п.
Важно, что все составные части компьютера взаимодействуют (обмениваются
данными) через общую шину (Bus), к которой они подключаются параллельно.
ПАРАЛЛЕЛЬНОЕ подключение позволяет избежать огромного количества проводов.
Правила обмена по шине определяются
ПРОТОКОЛОМ РАБОТЫ ШИНЫ.
С точки зрения процессора любое внешнее устройство выглядит как
набор из некольких ячеек памяти (порты, или регистры устройства),
в которые можно записывать информацию и из которых можно информацию считывать.
Каждая ячейка имеет свой собственный фиксированный номер, или адрес.
ПЕРЕРЫВ до 14:00 (время Душанбе)
У любого устройства имеется CSR-регистр
(Control-Status Register) и один или несколько
буферных регистров. У некоторых устройств может быть
собственная память (видеопамять графической карты) и
может быть отдельная шина для связи с процессором.
Имеется контроллер DMA (Direct Memory Access),
позволяющим внешним устройствам напрямую обращаться к памяти компьютера,
минуя процессор (читать память или писать в нее).
Например, так работает диск.
Устройство процессора:
процессор имеет свою внутреннюю память, которая называется
регистрами процессора. Все операции процессор выполняет с регистрами
(даже когда в команде один из операндов находится в памяти).
Регистры процессора бывают 2-х типов:
-- общие регистры хранят целые числа или адреса элементов памяти;
-- плавающие регистры хранят вещественные числа
в плавающем формате (64-разрядное или 80-разрядное число).
Общие регистры бывают у любого процессора, дешевые процессоры
могут не иметь поддержки вещественной арифметики и не иметь
плавающих регистров.
Пример:
Intel 8086, 80286 -- 16-разрядные процессоры
80386 -- 32-разрядный процессор
не имели поддержки веществ. арифметики.
Первый процессор Intel с поддержкой вещ. арифметики -- Inter 80486.
Ядро операционной системы, как правило, не использует
вещественную арифметику и плавающие процессоры.
Среди регистров общего назначения есть несколько регистров,
выполняющих специальные функции:
-- Program Counter (PC), в Intel 80x86 он называется
Instruction Pointer (IP), указатель команды,
он содержит адрес команды, которая будет выполняться
на следующем шаге;
-- Stack Pointer (SP), указатель стека, хранит адрес
вершины стека в оперативной памяти, стек растет в
сторону уменьшения адресов
push x === SP := SP - 4
m[SP] := x
pop x === x := m[SP]
SP := SP + 4
(в 32-разрядной архитектуре).
-- Frame Pointer (указатель кадра), хранит адрес
кадра локальных переменных функции, локальные
переменные хранятся в стеке, что позволяет выполнять
рекурсию, использовать распараллеливание с помощью
нитей (thread) и др.
Алгоритм работы компьютера:
цикл до бесконечности выполнять
| прочесть из памяти команду с адресом PC
| PC.увеличить на длину прочитанной команды
| выполнить прочитанную команду
конец цикла
Какие регистры есть у процессора Intel 80*86
CISC -- Complete Instruction Set Computer
RISC -- Reduced Instruction Set Computers
Inter, AMD --- NVIDIA CUDO
Apple MAC -- использовали процессоры Motorola 68000
(CISC, но самые лучшие),
затем они перешли на процессор PowePC --
хороший RISC-процессор.
И вдруг?????? Apple Mac перешел на Intel в 2006-м году
руководствуясь бизнес-соображениями.
16-разрядные регистры называются
AX, BX, CX, DX,
SI, DI, BP, SP
всего 8 регистров. Причем они изначально предназначались
для выполнения определенных ролей:
AX -- аккумулятор (в нем получаем результат арифм. операций),
AX, DX -- расширенный аккумулятор: например, в паре регистров
получается результат умножения 16-разрядных чисел
(32-разрядный), младшие биты в AX, старшие в DX.
При делении в AX получаем частное, в DX -- остаток
от деления чисел;
СX (counter) -- счетчик цикла;
SI (Source Index) -- адрес источника в командах обработки строк;
DI (Destination Index) -- адрес получателя;
BP (Base Pointer) -- указатель кадра (FP -- Frame Pointer);
SP (Stack Pointer) -- указатель вершины стека.
В процессоре обязательно имеется регистр флагов, обычно он обозначается
CC0 (Conditional Codes). В регистре флагов есть биты NZVC:
N -- Negative, устанавливается в 1, если результат последней команды < 0,
иначе устанавливается в 0;
Z -- Zero, устанавливается в 1, если результат нулевой,
V -- oVerflow, устанавливается в 1, если произошло переполнение,
С -- Сarry, устанавливается в 1, если произошел перенос из старшего
или младшего разряда.
Команды условного перехода -- осуществляют переход в зависимости
от комбинаций этих битов.
Пример: соманда CMP (Compare -- сравнить) как бы вычитает из первого аргумента
второй и результат никуда не помещает, просто устанавливает соответствующие
биты в регистре флагов. Есть аналогичная команда TST.
Вызов функций и захват/удаление кадра локальных
переменных функции
В современных компьютерах адрес возврата сохраняется в стеке.
Команда вызова функции
call f === push PC
PC := f
Команда возвращения из функции
return === pop PC
Соглашения о передаче параметров функциям.
В 32-разрядной архитектуре Intel 80*86 параметры функциям
передаются через стек:
res = f(111, 222);
Код транслируется в
push 222
push 111
call f
res := AX
Функция возвращает результат в нулевом регистре (в регистре AX для Intel).
Адресация локальных переменных:
Они адресуются относительно регистра FP (BP в случае Intel)
FP хранит адрес кадра локальных переменных, каждой переменной соответствует
смещение относительно FP, т.е. адрес переменной равен FP+смещение.
FP хранит адрес ячейки, в которой записывается старое значение FP
(для вызявающей функции).
int f(int x, int y) {
int z;
double a[10];
...
return 777;
}
В момент начала работы функции на вершине стека хранится адрес возврата.
Под вершиной стека хранится x, затем y
| адрес возврата | <-- SP
| x | SP + 4
| y | SP + 8
| . . . |
Первое действие -- сохранить старое значение FP
Затем определим новое значение FP как адрес вершины стека.
Дальше в стеке захватим место под локальные переменные
push FP
FP := SP
SP := SP - 84
| a . . | <-- SP
| . . . |
| . . . |
| z |
| старое FP | <-- FP
| адрес возврата |
| x | SP + 4
| y | SP + 8
| . . . |
Адрес y = FP + 12
y = FP + 8
z = FP - 4
a = FP - 84
Выход из функции:
SP := FP
pop FP
return
==============================================
2 Jun 2021
Устройство компьютера
Процессор, оперативная память RAM Random Access Memory,
шина (Bus), внешние устройства.
Процессор Intel 80x86, AMD, ARM (Risc-процессоры), на ARM
построены смартфоны, NVIDIA, Power PC, DEC Alpha, Motorola, MIP, ...
Регистры процессора -- его внутренняя память, все действия
процессор производит с регистрами. У процессора есть набор команд
(инструкций) для использования программистами, также обычно есть
микрокод, реализующий "внешние" команды процессора.
Регистры:
-- общие, хранят числа или адреса памяти;
-- плавающие, хранят вещественные числа в плавающем формате.
Обычно общие регистры называются R0, R1, R2, ...
В конкретных архитектурах регистры могут иметь другие названия.
Некоторые регистры предназначены для выполнения специальных функций:
PC (IP в Intel 80*86) -- содержит адрес команды, которая будет выполняться
SP -- содержит адрес вершины стека
(стек растет в сторону уменьшения адресов)
FP (BP в Untel) -- указатель кадра локальных переменных
Intel 80*86
16-разрядная версия, регистр хранит 2-байтовое слово
AX -- все слово, AL (Low) -- младший байт, АН (High) -- старший байт.
32-разрядная версия (начиная c процессора Intel 80386)
EAX (Extendent) -- регист содержит слово из 4-х байтов.
64-разрядная версия (AMD, Intel Itanium, ...)
RAX, RBX, RCX, RDX,
RSI, RDI, RSP, RBP.
В 64-разрядной версии добавлены еще 8 регистров (получается всего 16 регистров):
R8, R9, R10, ..., R15
В результате стало возможно держать промежуточные результаты вычислений
в регистрах, что серьезно увеличило скорость выполнения программы за счет
меньшего числа обращений к памяти для записи и чтения промежуточных
результатов вычисления. Кроме того, изменились соглашения о вызове
функций, теперь часть аргументов передается не через стек,
а через регистры.
Соглашения о вызове функций и размещении локальных переменных в стеке.
В 32-разрядной архитектуре все аргументы обычных (не системных) функций
передаются через стек (оперативную память):
аргументы кладутся в стек в обратном порядке
стек работает по дисциплине LIFO (Last In First Out)
в результате первый аргумент лежит на вершине стека, второй под ним, ...
a = f(x, y);
push y
push x
call f
Команда call f помещает на стек точку возврата (т.е. текущее значение PC)
и в регистр PC адрес функции f (т.е. осуществляет переход к
выполнению функции).
В момент входа в функцию на вершине стека лежит адрес возврата.
int f(int x, int y) {
int z;
double a[10];
. . .
return 777;
}
Начало кода функции:
push FP ; сохранить предыдущее значение FP
FP := SP ; FP указывает на ячейку, в которой хранится
; предыдущее значение FP
SP := SP - 84 ; захватить 84 байта под локальные перменные
После этого будут следующие адреса фактических параметров функции
и локальных переменных:
Стек:
| a | <-- SP
| . . . |
| z |
| старое FP | <-- FP
| адрес возврата |
| параметр x функции |
| параметр y функции |
| . . . |
Адреса переменных:
a == [FP - 84]
z == [FP - 4]
x == [FP + 8]
y == [FP + 12]
Локальные переменные имеют отрицательные смещения относительно FP
Аргументы функции имеют положительные смещения.
Завершение работы функции:
int f(int x, int y) {
int z;
double a[10];
. . .
return 777;
}
После . . . идет фрагмент:
R0 := 777 ; поместить возвращаемое значение в R0
SP := FP ; удалить кадр локальных переменных
pop FP ; восстановить предыдущее значение FP
return ; вернуться в вызывающую функцию (pop PC)
В 64-разрядной архитектуре соглашения о вызове функций другие,
причем они различные в Linux и в MS Windows:
в Linux первые 6 аргументов передаются через регистры
RDI, RSI, RDX, RCX, R8, R9
RBX, RSP, RBP, R12–R15 должны сохраняться
в MS Windows первые 4 аргумента передаются через регистры.
RCX, RDX, R8, R9
RAX, RCX, RDX, R8, R9, R10, R11 можно не сохранять
RBX, RBP, RDI, RSI, RSP, R12-R15 должны сохраняться.
ПЕРЕРЫВ до 14:00
Механизм прерываний
===================
Алгоритм работы компьютера:
цикл до бесконечности выполнять
| прочесть из памяти команду с адресом PC
| PC.увеличить на длину прочитанной команды
| выполнить прочитанную команду
конец цикла
Как работать с внешними устройствами?
Процессор должен определить, что произошло какое-то
событие (например, пользователь нажал клавишу), и среагировать
на него. Как это сделать?
1. Циклический опрос: процессор может читать контрольный регист клавиатуры
и, как только появляется код нажатой клафиши, считать его из буферного
регистра и обработать эту ситуацию.
Недостатки: трата впустую времени на опрос + запаздывание с
реакцией на событие.
2. Использовать механизм прерываний. На общей шине есть линии прерывания,
на которых выставляется сигнал прерывания, а также номер аппаратного прерывания
(0..15). Каждому номеру аппаратного прерывания соответствует
вектор прерывания:
он содержит адрес программы обработки прерывания и
слово состояния процессора (содержит уровень защиты,
0..3 для Intel, биты флагов, бит разрешения прерывания
и др. информацию, описывающую текущее состояние задачи).
В момент прерывания компьютер запоминает значение регистра PC
и текущее состояние в аппаратном стеке. После этого регистру PC
и регистру состояния процессора присваиваются значения,
прочитанные из вектора прерывания. Таким образом процессор переходит к
исполнению функции обработки прерывания, причем обработчику присваиваются
повышенные привелегии (например, кольцо защиты 0), записанные
в векторе прерывания. По окончанию обработчика прерывания
выполняется команда RTI (ReTurn from Interrupt): она из вершины аппаратного
стека извлекает старое слово состояния процессора (которое было до
прерывания) и старое значение регистра PC, в результате мы возвращаемся
к исполнению прерванной задачи.
Обработчик прерывания -- это, как правило, небольшая функция,
которая должна работать очень быстро (никаких долгих циклов
внутри нее не должно быть). Как правило, она работает в нулевом кольце
защиты (с максимальными привелегиями) и в процессе выполнения она
запрещает другие прерывания. По окончанию она вновь разрешае прерывания.
Пример: обработчик прерывания от клавиатуры: он считывает символ из
буферного регистра и добавляет его в очередь запросов от клавиатуры,
которая связана с любой работающей программой.
Прерывания бывают двух типов:
1) аппаратные, или асинхронные -- связаны с внешними устройствами;
2) синхронные, или программные, в свою очередь бывают 2-х типов
-- прерывания, связанные с некорректной командой: деление на ноль,
переполнение или исчезновение порядка при операциях
с вещественными числами, попытка прочесть/записать ячейку
памяти, защищенную от доступа, обращение к неправильному адресу;
-- имеются специальные команды прерывания, нужные для
а) для обращения к BIOS или для вызова функции API из ядра ОС
(int 21 MS DOC, int 80 в Linux);
b) прерывание int 3 используется отладчиками для установки
точки отладки.
======================================================
3 Jun 2021
Устройство компьютера.
Соглашения о вызове функций.
Ассемблер Intel 8086-64.
64-разрядная версия (AMD, Intel Itanium, ...)
RAX, RBX, RCX, RDX,
RSI, RDI, RSP, RBP.
В 64-разрядной версии добавлены еще 8 регистров (получается всего 16 регистров):
R8, R9, R10, ..., R15
Младших 4 байта регистра RAX называется EAX, аналогично для остальных регистров.
В 64-разрядной архитектуре соглашения о вызове функций другие,
причем они различные в Linux и в MS Windows:
в Linux первые 6 аргументов передаются через регистры
RDI, RSI, RDX, RCX, R8, R9
RBX, RSP, RBP, R12–R15 должны сохраняться
в MS Windows первые 4 аргумента передаются через регистры.
RCX, RDX, R8, R9
RAX, RCX, RDX, R8, R9, R10, R11 можно не сохранять
RBX, RBP, RDI, RSI, RSP, R12-R15 должны сохраняться.
В Linux имена функций в Ассемблере такие же,
как и втесте С-программы.
int f(int x, int y) {
. . .
}
.file "f.c"
.text
.globl f
.type f, @function
f:
В MS Window к именам функций языка C, возможно,
добавляется префикс _
.file "f.c"
.text
.globl _f
.type _f, @function
_f:
Передача параметров функции:
Для функции от 2-х аргументов оба аргумента передаются через
регистры:
в Linux, OS-X через регистры RDI, RSI
в MS Windows через регистры RCX, RDX
Давайте для примера напишем функцию max(a, b)
Проект состоит из двух файлов:
tstmax.c -- вводит исходные данные (числа a, b),
вызывает функцию max(a, b) и печатает результат.
max64.s -- реализация на Ассемблере "as" (не на MASM!!!)
функции int max(int a, int b);
Файл tstmax.c с программой на C:
#include <stdio.h>
#include <stdlib.h>
extern int max(int a, int b); /* Prototype of function */
int main(void) {
int a, b, m;
while (1) {
printf("a, b: ");
if (scanf("%d%d", &a, &b) < 2)
break;
m = max(a, b);
printf("max(a, b) = %d\n", m);
}
return 0;
}
Файл max64.s с программой на Ассемблере:
.file "max64.s"
.text
.globl max
.type max, @function
max: # int max(int a, int b)
pushq %rbp # save frame pointer in stack
movq %rsp, %rbp # new FP points to old FP in stack
movl %edi, %eax # ax := a
movl %esi, %edx # dx := b
cmpl %edx, %eax # cc0 := a - b
jge L0 # if result >= 0 goto L0 (greater or equals)
movl %edx, %eax # ax := b
L0:
movq %rbp, %rsp # top of stack := FP
popq %rbp # restore old FP
ret
Рассмотрим чуть более сложную программу:
найти сумму элементов целочисленного массива.
Массив задается адресом начала и числом элементов:
extern int sum(const int *a, int n);
Эта функция реализуется на Ассемблере.
Тестирующая функция реализуется на C.
Функция на Ассемблере, вариант для Linux, файл sum64.s
.file "sum64.s"
.text
.globl sum
sum: # int sum(const int *a, int n)
# a === %rdi, n === %rsi
pushq %rbp # save frame pointer in stack
movq %rsp, %rbp # new FP points to old FP in stack
movl $0, %eax # sum := 0
L0: # loop
cmpl $0, %esi # compare n with 0
jle L1 # if result <= 0 goto L1 ("le" == less or equal)
addl (%rdi), %eax # sum += *a
addq $4, %rdi # a += 4
subl $1, %esi # n -= 1
jmp L0 # goto L0
L1:
movq %rbp, %rsp # SP := FP
popq %rbp # restore old FP
ret
Замечание:
в варианте для MS Window первые 2 аргумента функции передаются
через регистры RCX, RDX. Поэтому в приведенной выше программе
надо всюду заменить RDI на RCX, RSI на RDX.
Возможно???, для MS Windows в Ассемблере имя функции надо заменить
на _sum:
.file "sum64.s"
.text
.globl _sum
.type _sum, @function
_sum: # int sum(const int *a, int n)
(Постараюсь это точно выяснить.)
Задачи по первой теме: устройство компьютера.
Написать маленький проект, включающий 2 файла,
файл *.c содержит тестирующую программу, которая вводит
длину массива, элементы массива, вызывает функцию, написанную
на Ассемблере (файл *.s) и печатает результат, который функция
возвращает. Функция на Ассемблере вычисляет результат от
массива заданной длины:
int sum(const int* a, int n);
Массив содержит целые 4-байтовые числа, длина массива -- это также
целое 4-байтовое число. Указатель начала массива содержит 8-байтовый
адрес его начала. Можно написать программу в варианте для
Linux/OS-X или для MS Windows.
Совет для пользователей MS Windows:
установите пакет CygWin
скачайте программу установки с сайта
http://cygwin.org/
setup-x86_64.exe
Запустите ее от имени администратора,
выберите, что устанавливать:
gcc, g++, as, make, wget (робот для скачивания сайта целиком).
Для редактирования текстов программ лучше всего использовать
notepad++
Список задач
1. Написать функцию, которая вычисляет максимальный элемент массива
целых чисел.
int arrayMax(const int *a, int n);
2. Написать функцию, которая вычисляет количество перемен знака в
массиве целых чисел.
int numSignChanges(const int *a, int n);
Мы считаем, что числа >= 0 положительны (знак +),
числа < 0 отрицательные (знак -).
a = [1, 2, 3, -4, -5, 6]
Число перемен знака = 2.
a = [-10, -20, -30, -40, -50, 60, 0, 1]
Число перемен знака = 1.
===========================================================
Прерывания, обработчики прерывания.
Зачем нужны прерывания?
1. Аппаратные (асинхронные) инициируются внешними устройствами
и сигнализирую процессору о некотором событии. В ответ процессор
прерывает свои занятия и вызывает функцию-обработчик данного прерывания.
2. Синхронные прерывания происходят в результате выполнения
определенных команд программы.
а) либо это некорректная команда, например, деление на 0 или
обращение по неправильному или запрещенному адресу памяти;
б) либо это специальная команда int N (от Interrupt),
инициирующая прерывание с номером N.
Как используется команда int ???
Для двух целей:
1) вызов каких либо сервисных функций BIOS
(используется инструкция int n, n может принимать
несколько значений), операционной системы
(INT 21H для MS DOS, int 80x для Linux).
Обычный вызов функции для системного сервиса невозможен,
поскольку ядро системы и пользовательская программа
могут использовать разные адресные пространства (при использовании
виртуальной памяти) или иметь разные привелегии (при
работе в защищенном режиме в современных операционных системах).
Долгое время прерывания были единственным способом
вызова функций ОС, т.к. при переходе к обработчику
прерывания слово состояния процессора считывается
из вектора прерывания, и таким образом пользовательская
программа может исполнить действия, требующие системных
привелегий (операционная система выступает в качестве
посредника);
2) для отладки пользовательской программы программа-отладчик
устанавлявает точку остановки (breakpoint) в пользовательской
программе, заменяя пользовательскую команду на команду
int 3
Когда программа доходит до этого места, выполняется команда
прерывания, обрабатывает которую отладчик.
Следующая лекция будет посвящена механизму виртуальной памяти.
Домашние задания присылайте на адрес
vladimir_borisen@mail.ru
Subject: Душанбе, домашнее задание 1 (2, 3, 4, ...)
========================================================
4 Jun 2021
Устройство компьютера: виртуальная память
Виртуальная память -- это механизм отображения виртуальных адресов
на физическую память
Используется в многозадачных операционных системах.
В программе могут использоваться абсолютные адреса.
Например, в ячейку памяти с адресом 1000 записываем число.
Или вызываем функцию по адресу 1000000.
При такой адресации две программы, использующие одни и те же
адреса памяти, будут конфликтовать.
Как разрешается подобная ситуация?
1. Использовать относительную адресацию: адрес вычисляется как
содержимое базового регистра + смещение.
В старых процессорах Intel8086 использовались сегментные
регистры CS Code Segment, DS Data Segment.
Тогда компьютеры IBM PC были 16-разрядными и имелы 640Kib памяти.
2^16 = 65536, всего адресуемо с помощью смещений 65K памяти.
Венгерская система обозначений, используемая в фирме Microsoft:
LPCSTR -- Long Pointer to Constant STRing
Различались длинные указатели (lp -- long pointer)
и короткие указатели (np -- near pointer)
Для изменения короткого указателя достаточно было увеличить одно слово
(16-разрядное). Для изменения длинного указателя надо было увеличить
2 слова: сегментный регистр (DS или CS) и смещение.
Главная проблема сегментной загрузки и сегментной адресации:
программа и ее данные занимают непрерывный участок памяти.
При завершении процесса его участок памяти освобождается, и остается
свободный сегмент. Но не факт, что в него можно загрузить другую
программу, потому что ей может быть необходим сегмент большего размера.
Реализация виртуальной памяти -- это была в свое время революция!
Она была одновременно с переходом на 32-разрядную адресацию.
Размер непосредственно адресуемой памяти при 32-разрядной адресации
равен 2^32 = 4,294,967,296
Первый 32-разрядный мини-компьютер -- это VAX фирмы DEC (Digital Equipment
Corporation --> Hewlett Packard), выпущенный в 1980 г. Второй 32-разрядный
мини-компьютер -- это Eclipse, или MV-8000
Виртуальная память -- это отображение виртуальных адресов на физические
адреса
f: Z+ --> Z+
Это осуществляется с помощью страничной организации виртуальной и
физической памяти.
Рассмотрим 32-разрядную архитектуру
Страница как виртуальной, так и физической памяти занимает
2^12 = 4096 байтов.
Как виртуальная, так и физическая память делится на страницы.
Часть операционной системы, которая называется MMU
(Memory Management Unit), управляет отображением виртуальных
страниц памяти на физические страницы.
Виртиальная память Физическая память
0 +-----------------+ +---------------------+
| |-----+ | |
4096|---------------- | | |---------------------|
| | | +-----> | |
8192|-----------------| | | |---------------------|
| | +--------> | |
|-----------------| | |---------------------|
| |--------+ | |
|-----------------| |---------------------|
| . . . | | . . . |
| | | |
| | | |
| | | |
При обращении к виртуальной памяти компьютер преобразует
обращение к виртуальной странице к соответствующей ей
физической странице. Смещение внутри страницы остается тем же самым.
Виртуальный адрес: 32 бита 31 30 29 . . .13 12 11 10 . . . 3 2 1 0
* * * . . .* * x x x ... x x x x
Номер страницы Биты смещения внутри
страницы
32-разрядный адрес делится на 2 части:
младшие 12 разрядов -- смещение внутри страницы (размера 4096=2^12)
старшие 20 разрядов -- это номер виртуальной страницы
При отображении виртуального адреса на физический смещение внутри
страницы (12 младших разрядов) остается неизменным, а номер
виртуальной страницы заменяется на номер физической страницы,
причем всё это реализовано внутри процессора на аппаратном уровне.
В оперативной памяти для каждого процесса хранится таблица описателей
страниц. Описатель страницы содержит адрес начала физической страницы,
для задания этого адреса достаточно хранить 20 битов. В остальных 12
битах записываются различные характеристики физической страницы:
защитить (разрешить) страницу от записи/чтения/выполнения,
признак того, что виртуальная страница отображена на физическую и др.
Имеется регистр, в котором содержится адрес таблицы описателей страниц
данного процесса.
Виртуальная страница может не быть отображена на физическую страницу,
имеется соответствующий бит в описателе страницы. При попытке доступа
к этой странице происходит синхронное прерывание "Page Fault", при этом
обработчик прерывания может выделить физическую страницу для данной
виртуальной страницы. Если же физическая память уже исчерпана, то
операционная система (MMU) может выкинуть их памяти на диск страницу
какого-либо другого процесса и выделить текущему процессу освобожденную
страницу. Это называется своппингом (swapping, от to swap -- обменивать).
Своппинг:
обращаемся к странице, которой нет в физической памяти.
Если есть свободная страница физической памяти, то выделяем ее
для данной виртуальной страницы.
При этом, если в эту страницу мы уже раньше что-то записали и
она была перемещена на диск, то надо ее прочитать обратно с
диска в физическую память.
Если нет свободной страницы, то надо выкинуть на диск какую-либо
другую страницу (другого или того же процесса) и использовать ее.
ПЕРЕРЫВ до 14:00
Особенности механизма виртуальной памяти
1. Таблица описателей виртуальных страниц хранится для каждого процесса
отдельно.
2. Таблица может быть многоуровневой.
Например, если у нас 32-разрядная архитектура, то под адрес
внутри страницы отводится 12 битов, под номер страницы 20 бита.
Таким образом, число описателей страниц (PTE Page Table Entry, одно слово =
4 байта) равно 2^20 = 1M * (размер описателя 4 байта) = 4M.
Это довольно много и не всегда необходимо для небольших программ. Поэтому
в Intel 80386 используется двухуровневая реализация таблицы страниц:
старшие 10 битов виртуального адреса (биты с 31 по 22)
используются как индекс в директории таблиц.
Директория таблиц содержит адреса не более чем 1024-х таблиц страниц.
Каждая таблица страниц содержит 1024 описателя страницы.
Десять битов виртуального адреса с 21 по 12 содержат индекс в таблице страниц,
уже соответствующий описателю конкретной страницы виртуальной памяти.
Наконец, младшие 12 битов (с 11 по 0) содержат смещение внутри страницы.
Виртуальный адрес
индекс в директории таблиц | индекс в таблице страниц | смещение внутри стр.
31 30 ... 22 | 21 20 19 ... 12 | 11 10 9 . . . 2 1 0
Директория таблиц содержит | Таблица страниц содержит |
адреса таблиц страниц | описатели страниц: |
| адрес страницы + допол- |
| нительные биты описателя|
10 битов | 10 битов | 12 битов
3. Некоторые страницы виртуальной памяти могут тождественно отображаться
на физическую память (это используется ядром системы).
Защишенный режим === механизм вирт. памяти включен
используется в прикладных программах
Реальный режим === используется ядром операционной системы,
в частности, блоком MMU
управления памятью.
4. Некоторые страницы защищены от своппинга. Страницы, содержащие
критический код, важный для функционирования системы, всегда остаются
в физической памяти (pinned pages, fixe pages ...).
5. Некоторые страницы включаются одновременно в виртуальное пространство
нескольких процессов (Shared memory, разделяемая память). Например, код программы
или код код разделяемой библиотеки хранится в физической памяти в одном
экземпляре, даже когда он используется несколькими разными программами
(процессами). Это разделямые библиотеки в Unix, файлы *.so, или
динамически подключаемые библиотеки *.dll (Dynamic Link Library)
в MS Windows.
6. В описателе страницы имеется бит Dirty, который означает, что
какое-то слова в странице изменились. Использование этого бита позволяет
избежать лишних операций чтения и записи на диск при своппинге.
===================================================================
Вернемся к Ассемблеру "as", входящему в оболочку gcc.
Имеются различия в соглашения об именах функций и
о передаче параметров функциям между:
1) 32-разрядной и 64-разрядной архитектурами;
2) между Linux+MAC OS-X и MS Windows.
Будем рассматривать только 64-разрядную архитектуру.
Различие 32/64:
В 32-разрядной архитектуре имена функций в Ассемблере
начинаются с символа подчеркивания:
функция языка C
int sum(const int *am int n);
в Ассемблере будет выглядеть как
.globl _sum
_sum:
код функции
. . .
Но 64-архитектуре имена функций функций в Ассемблере
точно такие же, как и C:
.globl sum
sum:
код функции
. . .
Напомним различие между соглашениями о передаче
параметров фунциям между Linux или MAC OS-X
и MS Windows:
в Linux первые 6 (целочиленных) аргументов функции
передаются через регистры
RDI, RSI, RDX, RCX, R8, R9.
Функция должна сохранять регистры
RBX, RSP, RBP, R12–R15
в MS Windows первые 4 аргумента передаются через регистры.
RCX, RDX, R8, R9
RAX, RCX, RDX, R8, R9, R10, R11 можно не сохранять,
RBX, RBP, RDI, RSI, RSP, R12-R15 должны сохраняться.
Регистры, которые безнаказанно можно портить = использовать
для промежуточных вычислений:
AX, DX, CX, R8, R9.
============================================================
07 Jun 2021
Повторим Ассемблер
На входе в любую функцию выполняется пара команд
f:
pushq %rbp # save frame pointer in stack
movq %rsp, %rbp # new FP points to old FP in stack
Старое значение указателя кадра (регистр FP) сохраняется в стеке.
Затем указатель стека копируется в регистр FP. В результате
FP будет содержать адрес ячейки, в которой записано его старое значение.
Дальше идет тело функции. Результат функции должен быть записан в регистр
RAX (нулевой регистр, он обычно носит название аккумулятор). После этого
восстанавлявается указатель стека и затем старое значение FP:
movq %rbp, %rsp # top of stack := FP
popq %rbp # restore old FP
Для выполнения двух этих действий в Intel имеется специальная команда
leave
(можно использовать ее). После этого на вершине стека будет лежать
адрес возврата, и выполняется команда возврата в вызывающую
функцию
ret
(от слова Return -- вернуться).
В MS Windows первые 2 аргумента передаются через регистры RCX, RDX.
В Linux, OS-X -- через регистры RDI, RSI.
Виртуальная память
Поддержка страничной организации виртуальной памяти
процессорами серии Intel 80x86 появилаcь в процеccоре
Intel Intel-80386 -- первый 32-разрядный процессор.
До этого использовались 16-разрядные процессора
Intel 8086
80186
80286
Типичный персональный компьютер IBM PC:
Процессор Interl-80286, 4MByte память, 40 MByte диск.
16-разрядный процессор, адресация с использованием
сегментного регистра (CS или DS).
Операционная система MS Dos или MS Windows 3.1
MS Dos -- однозадачная операционная система.
MS Windows -- многозадачная операционная система с
кооперативной многозадачностью.
Современные ОС используют вытесняющую (pre-emptive) многозадачность.
schedyield() -- дать возможность подышать другим.
Разработка процессора Intel-80386 -- настоящая революция,
которая положила конец эпохе детства для персональных
компьютеров. Intel-80386 поддерживает
1) виртуальную память;
2) защищенный или реальный режим выполнения.
Виртуальная память: для каждого процесса по отдельности
настраивается механизм отображения виртуальной памяти на
физическую. Виртуальный адрес делится на 2 части (рассмотрим
на 32-разрядной архитектуры)
** ********** ******** | ** **********
31 30 . . . | 11 . . . 3210
Старшие 20 битов |
задают номер виртуальной| Смещение внутри
страницы | страницы 0..4095
Размер страницы 2^12 = 4096|
Всего страниц может быть |
2^20 = примерно миллион |
Операционная система для процесса выделяет таблицу описателей страниц.
В этой таблице потенциально может быть 2^20 элементов.
Описатель страницы содержит 4 байта. Он состоит из адреса
физической страницы, деленного на 2^12=4096, получается 20 битов.
Остается еще 12 битов, которые используются для хранения дополнительной
информации о странице:
-- страница присутствует в памяти;
-- старница закрыта для записи/чтения/исполнения
-- страница грязная (Dirty)
после того. как она была прочитана с диска при своппинге,
в нее была произведена запись (страницы на диске и в памяти
отличаются);
-- . . .
Таблица описателей страниц имеет потенциальный размер 4MByte. Поэтому
может использоваться двухуровневая организация этой таблицы.
ПЕРЕРЫВ до 14:00
Виртуальный адрес делится на 2 части:
младшие 12 битов -- смещение внутри страницы;
старшие 20 битов -- номер виртуальной страницы.
Всего 2^20 == примерно миллион виртуальных страниц.
Таблица описателей страниц (PTE == Page Table Element)
должна содержать миллион описателей, каждый описатель имеет размер
4 байта (содержит 20 бит адреса страницы + 12 битов описателя страницы)
Размер таблицы страниц должен быть равен 4 MByte -- это очень много!
Допустим, у нас на компьютере работают 100 процессов x 4Mb = 400 Mb
нужно только для хранения таблиц страниц!
Поэтому одноуровневая организация виртуальной памяти никогда не используется!
Во всех реальных компьютерах используется многоуровневая организация
виртуальной памяти. Давайте для примера рассмотрим самую простую схему
двухуровневой виртуальной памяти.
В процессоре имеетря регистр PTBR -- Page Table Base Register.
Он содержит таблицу страниц нулевого уровня, ее размер 4K, т.е.
в ней 1024 ссылки на адреса таблиц первого уровня.
При обращении в виртуальному адресу 10 старших битов (биты 31--22)
используются как индекс в таблице страниц нулевого уровня
(ее называют еще директорией страниц, Pade Directory)/
PTE с данным индексом в таблице нулевого уровня содержит
адрес таблицы первого уровня, которая используется для нахождения физического
адреса страницы.
Каждая таблица первого уровня тоже совсем маленькая, она содержит
описателя 1024 физических страниц. В качестве индекса в таблице 1-го
уровня используются биты 21--12 виртуального адреса.
Наконец, младшие 12 битов задают смещение внутри физической страницы.
Преимущество:
мы не захватываем большой непрерывный фрагмент памяти для
хранения таблицы страниц. Каждая таблица нулевого и первого
уровней помещается в одной физической странице!
Недостаток: для нахождения физического адреса, на который отображается
виртуальный адрес, нужно 2 обращения к памяти:
1) сначала в таблице нулевого уровня читаем адрес таблицы первого уровня
(используем биты 31--22 виртуального адреса в качестве индекса
в таблице 0-го уровня);
2) затем в таблице первого уровня читаем адрес физической страницы
(используем биты 21--12 виртуального адреса в качестве индекса
в таблице 1-го уровня);
3) к полученному адресу физической страницы прибавляется смещение внутри
страницы, биты 11--0 виртуального адреса.
Обязательного для ускорения такого чтения используется специальная
кэш-память процессора, которая называется
TLB (Translation Lookaside Buffer).
При переключении процессов происходит переключение их контекстов,
в частности, изменяется значение регистра PTBR (Page Table Base Register),
и при этом TLB очищается. То есть после переключения контекстов
процесс опять начинает работать медленно, пока TLB-кэш не разогреется.
Это означает, что переключать процессы слишко часто очень накладно.
Реально операционная система переключает процессы 100 раз в секунду.
Для компьютера 1/100 секунды -- это почти что вечность.
Второе: гораздо выгоднее распараллеливать вычисления с помощью
нитей (Threads), а не с помощью процессов. Нити исполняются параллельно
или псевдопараллельно, но при этом используют общее виртуальное
адресное пространство. Поэтому при переключении нитей кэш TLB
не сбрасывается, и прогамма не теряет скорости работы.
====================================================================
Очень важно отметить, что при поддержке виртуальной памяти
нужно иметь по крайней мере 2 режима работы процессора.
Обычно их называют
1) реальный режим;
2) защищенный режим.
В реальном режиме процессор обращается непосредственно к
физическим адресам памяти, а механизм виртуальной памяти не используется.
в частности, часть MMU (Memory Management Unit) ядра системы,
обеспечивающая механизм виртуальной памяти для пользовательских
процессов, сама работает в реальном режиме.
В защищенном режиме работают пользовательские программы. Таким образом,
для пользовательской программы нет никакой возможности обращения к конкретным
физическим адресам. Для этого требуется написать драйвер (в MS Windows
для этого предоставляется пакет DDK -- Driver Developer Kit).
Драйверы устройств подсоединяются к ядру системы и работают в реальном
режиме.
В реальном режиме работает ядро операционной системы. Есть системы
с монолитным ядром (Linux, MS Windows) и с микроядром (MAC OS-X, QNX).
В системах с микроядром драйверы устройств работают в режиме пользовательского
процесса с некоторыми преимуществами.
В MS Windows или в Linux ошибка в драйвере устройства приведет
к падению всей системы. В MAC OS-X падение драйвера не приводит
к падению всей системы.
Последнее: если мы рассматриваем устройство "голого" компьютера
(без операционной системы или с максимально примитивной ОС),
то следует упомянуть важнейшее устройство -- таймер. Таймер имеет
кристалл (как в кварцевых часах), генерирующий импульсы со строго заданной
частотой. На каждом импульсе увеличивается на 1 счетчик импульсов (вариант --
он может уменьшаться на 1). Как только счетчик достигает заданного значения
(для установки этого значения используется другой регистр таймера,
который называется делителем частоты), происходит аппаратное прерывание.
Счетчик таймера может при этом сбрасываться на 0 (или перезагружаться
при использовании уменьшения на 1). Это дает возможность операционной системе
переключать задачи или нити.
Следующий раз: ядро системы, назначение, принципы работы ядра, его составные
части. Монолитное или микро-ядро.
==========================================
8 Jun2021
Система разработки Code::Blocks
Плюсы: свободная, достаточно хорошо продумана.
Минусы: иногда трудно контролировать команды компиляции и ключи компиляции.
Лучше установить CygWin и для редактирования программ Notepad++
Запускаете Terminal CygWin
Создайте в своей домашней директории /home/MyName/
поддиректорию для ваших программ
/home/MyName/bin
командой
mkdir bin
В начальный скрипт советую добавить
Отредактируйте файл .bashrc в домашней директории:
добавьте строки
mount c: /c/
PS1='$PWD>'
PATH=$PATH:~/bin
При установке CygWin:
1) скачиваем установщик
setup-x86_64.exe
(я обычно создаю директорию c:\cygwinDistrib,
а устанавливаю cygwin в директорию
c:\cygwin64
2) запускаем установщик с правами администратора;
3) он скачивает оглавление пакетов с сайта cygwin.org
4) выборите сервер, с которого будете производить установку
(лучше выбрать протокол http);
5) ВАЖНО!!! Надо выбрать пакеты, которые вы будете устанавливать:
gcc-g++
gdb
vim
zip
unzip
make
wget
ssh (openssh)
Тема сегодняшней лекции: ядро операционной системы
=================================================
Что такое операционная система?
Функции операционной системы:
компьютер -- страна,
операцмрнная система -- это как бы государство.
Что требуется от государства? Забота о гражданах,
включает
-- предоставление ряда услуг:
транспорт, почта, энергетика, водопровод, дороги и т.п.
-- соблюдение законности, защита от преступников, распределение ресурсов,
полиция, армия, ...
В этой аналогии в качестве граждан страны выступают прикладные программы,
которые в свою очередь обеспечивают сервисы для пользователей.
Операционная система состоит из
-- ядра системы;
-- утилит (полезных системных программ).
Ядро системы постоянно находится в памяти и работает постоянно.
Утилиты могут загружаться для выполнения отдельных задач. Это практически
прикладные программы, которые устанавливаются параллельно с ядром
системы. Помимо ядра, есть база пользователей, registry в MS Windows,
содержит конфигурацию всех программ на компьютере; имеются системные
сервисы (или демоны в Unix).
Ядро системы постоянно находится в памяти и работает в реальном
режиме.
Функции ядра:
-- создание и запуск пользовательских процессов и нитей;
-- управление виртуальной памятью (MMU);
ПЕРЕРЫВ до 14:00
-- взаимодействие между процессами IPC (Inter Process Communication)
-- управление внешними устройствами (через драйверы устройств).
В случае монолитного ядра драйверы являются его частью
(они либо компилируются вместе с ядром, либо при готовом ядре
подгружаются как бинарные модули). Если архитектура использует
микроядро, то драйверы уже не являются частью ядра, а при необходимости
запускаются как пользовательские процессы и работают в защищенном
режиме.
Операционные системы Linux и MS Windows используют монолитное ядро,
MAC Os-X использует микроядро (также операционная система реального
времени QNX построена на основе микроядра).
-- планирование исполнения процессов, распределение времени между процессами
и нитями (эта часть ядра называется планировщик или scheduler);
-- поддержка файловых систем;
-- ядро может иметь часть GUI, которая отвечает за графический и оконный
интерфейс (только в MS Windows; в Unix-системах графика поддерживается
отдельным пользовательским процессом: X-server в X-Window в Linux,
WayLand в современных Unix-системах, включая Linux; в MAC OS-X используется
графическая система Quartz).
При использовании микроядра в нем оставлены только самые основны возможности
ядра: управление процессами и нитями, управление виртуальной памятью (MMU),
взаимдействие между процессами (IPC). Микроядро очень простое и компактное
(ядро Mach, созданное в MIT, содержит всего около 5000 строчек кода на C),
сделатьошибку в коде почти невозможно => операционная система очень надежная.
Большинство обычных функций ОС в архитектуре с микроядром исполняются
процессами-серверами, работающими в защищенном режиме (как обычные полььзовательские
процессы).
Система QNX реального времени также построена на основе микроядра (Mach ?),
поскольку дя Real Time systems надежность и гарантированное время отклика
намного важнее, чем СРЕДНЕЕ время выполнения команды.
-- ядро может поддерживать работу с сетью полностью или частично, передавая
команды для конкретной сетевой архитектуры соответствующему стеку
сетевых протоколов, работающему в пользовательском режиме.
Мы будем знакомиться с функциями ядра системы с точки зрения прикладной программы.
Нас будет интересовать набор функций и объектов ядра, предоставляемых прикладным
программам.
Мы рассмотрим
1) процессы, их создание и обмен данными между ними;
2) распараллеливание, нити, объекты синхронизации;
3) сетевое программирование;
4) работа с файловыми системами (например, обойти все файлы во всех поддиректориях,
подсчитав что-то там, например, суммарное число строк во всех *.cpp и *.h-файлах);
5) . . .
Наибольшее внимание мы будем уделять объектам ядра системы и способам работы
с ними.
Важно понимать, что пользовательский процесс работает с низкими привелегиями:
есть так называемые кольца защиты, в процессорах типа Intel их 4:
кольцо 0 -- режим операционной системы (или суперпользователя), можно всё;
режим 3 -- пользовательский процесс, все опасные действия запрещены
(физическая адресация, обращение к внешним стройствам, обращение
к станицам памяти, защищенным от записи/чтения/выполнения).
кольцо 1 -- зарезервировано для драйверов (в MS Windows и в Linux не используется);
кольцо 2 -- аналогично.
========================================================
9 Jun 2021
CygWin -- реализация утилит Unix под MS Windows
Использует API для всех Unix-систем: POSIX (1988)
Использует CYGWIN32.dll и другие разделяемые библиотеки.
MinGW (Minimal GNU for Windows) -- компилятор GCC + полная поддержка
API Win32
Используются стандартные разделяемые
библиотеки dll из MS Windows
Тема лекции: процессы в операционной системе.
Процесс -- это примерно пользовательское приложение, задача, запущенная на компьютере.
Но не совсем точно, поскольку пользовательское приложение может исполняться
несколькими процессами, работающими совместно.
Процесс -- задача, работающая на компьютере. У процесса есть:
1) PID -- идентификатор процесса. У разныых процессов гарантировано разные PID;
2) процесс -- объект ядра системы. Все объекты отождествляются с помощью
переменной типа HANDLE. HANDLE хранит уникальный номер объекта, с помощью которого
можно получить доступ к объекту. Пользовательская программа для получения доступа
открывает объект и получает в ответ HANDLE.
HANDLE hProcess = OpenProcess(...);
. . .
CloseHandle(hProcess);
3) для каждого процесса поддерживается виртуальная память и набор регистров, отвечающих
за виртуальную память;
4) у каждого процесса имеется набор нитей, работающих параллельно или
псевдопараллельно (в режиме разделения времени Time Sharing). Все нити уиспользуют
одно и то же виртуальное адресное пространство процесса;
5) у процесса есть набор открытых файлов (файловых дескрипторов). В MS Windows
открытые файлы также являются объектами ядра системы и отождествляются с помощью
HANDLE'ов. Помимо них, файлы доступны через файловые дескрипторы: числа от 0 до 1024,
это просто индексы в таблице открытых фалов процесса. Файловый дескриптор 0
соответствует входному потоку (stdin в программах на C, std::cin на С++,
дескриптор 1 -- выходному потоку stdout, std::cout), дескриптор 2 -- stderr,
std::cerr).
Создание процесса
Имеются функции в стандартной библиотеке POSIX типа exec:
exece, execl, execp, ...
Идея: в Unix одна из самых популярных системных функций -- это fork()
int pid = fork();
Поцесс раздваивается, все открытые файли и сетевые сокеты дублируются,
получается два процесса-двойника. Процесс-отец получает идентификатор
ребенка, а ребенок получает 0.
int childID = fork();
if (childID != 0) {
// I ams father!
// Continue mi life...
. . .
} else {
// I am a child.
// Transform to another process
execl(pathToProcessFile, arg1, arg2, NULL);
}
В MS Windows функция fork() не реализовано.
ПЕРЕРЫВ до 14:00
Установите пакет MinGW-W64 (Minimal GNU for Windows)
Установочный пакет скачивается с сайта
http://mingw-w64.org/
Идем по ссылке downloads...
Выбираем в таблице строку MingW-W64-builds
Скачиваем установщик: mingw-w64-install.exe
Запускаем его,
выбираем Architecture: x86_64
Threads: win32
Нажимаем Next для продолжения инсталляции.
После этого запускаем из меню Windows
minGW-W64 -> Terminal
Пример на создание процесса-ребенка в Win32.
Для этого используется функция CreateProcess ил API Win32
STARTUPINFO si;
PROCESS_INFORMATION pi;
memset(&si, 0, sizeof(si));
si.cb = sizeof(si);
memset(&pi, 0, sizeof(pi));
BOOL ok = CreateProcess(
pathToExeFile,
commandArgs,
NULL, // Process handle not inheritable
NULL, // Thread handle not inheritable
FALSE, // Do not inherit handles
0, // CREATE_NEW_CONSOLE, // Creation flags
NULL, // Use parent's environment block
NULL, // Use parent's starting directory
&si, // Pointer to STARTUPINFO structure
&pi // Pointer to PROCESS_INFORMATION structure
);
. . .
// Обязательно надо закрыть хендлы созданного процесса и нити!!!
// Иначе эта информация будет вечно храниться в ядре системы.
CloseHandle(pi.hProcess);
CloseHandle(pi.hThread);
В качесве минимального примера совместной работы двух процессов
рассмотрим программу жеребьевки (draw): работают 2 процесса,
при этом первый процесс запускает второй.
Монета орел/решка
Heads / Tails
Процесс-родитель 10 раз печатает слово Heads, засыпая между печатями
на промежуток времени 0..2 сек; процесс-ребенок 10 раз печаает слово Tails.
Если процесс запущен без аргументовкомандной строки, то это процесс-родитель;
с непустыми аргументами -- ребенок.
Домашнее задание:
1) установить mingw-w64;
2) выполнить в терминале mingw-w64 программу winproc.cpp
(жеребьевка с помощью двух параллельных процессов).
==================================================
10 Jun 2021
MS Windows, Win32
Создание процессов. Взаимодействие процессов
IPC -- Inter Process Communication
Всё это было еще до изобретения нитей (Threads) и
выглядит неного устаревшим, но тем не менее распараллеливание
задачи с помощью нескольких процессов всё еще очень популярно.
Рассмотрим наиболее старый способ взаимодействия мжду процессами:
программный каналЮ или труба (pipe).
Системный вызов
int fds[2];
pipe(fds);
Pipe:
---------------------------------------------
fds[0] <<<--- <<< <<< <<<--- fds[1]
---------------------------------------------
чтение запись
Раздваиваем наш процесс с помощью fork().
После этого ребенок пишет во второй конец трубы fds[1],
а родитель эти данные (которые ему передает ребенок) из первого
конца трубы:
int pid = fork();
if (pid != 0) {
// This is the parent process
close(fds[1]);
len = read(fds[0], buffer, maxLen);
. . .
} else {
// This is the child process
close(fds[0]);
res = write(fds[1], buffer, len);
. . .
}
В MS Windows не реализован системный вызов fork.
Поэтому в Windows для рааботы с трубой мы используем
создание процесса-ребенка с помощью функции CreateProcess.
При этом мы предварительно в процессе-родителе создаем трубу и
при создании ребенка просим, чтобы ребенок унаследовал
хендлы файлов, описывающих концы трубы. Для этого системный
вызов CreateProcess структуру STARTUP_INFORMATION, в которой,
в частности, задаются наследуемые хендлы входного потока.
Имеется проект winpipe, состоящий из двух файлов и, соответственно,
двух выполняемых программ:
winpipe.cpp -- процесс-родитель, используется как интерфейс к
к процессу-ребенку. Все, что мы вводим с клавиатуры,
передается по трубе процессу-ребенку. Процесс-ребенок
воспринимает это как чтение с клавиатуры (более точно,
из входного потока).
В процессе-родителе создаются две трубы: по одной данные текут от
родителя к ребенку, по второй -- от ребенка к родителю.
rcalc.cpp -- калькулятор формул, вычисляющий значение формулы.
ПЕРЕРЫВ до 14:00
Проект "WinPipe + Calculator": winpipe.cpp, rcalc.cpp.
Надо сделать задачу, подменив child-процесс на процесс,
который выполняет нужную обработку входной строки
(которую он получает от процесса-родителя).
1. Перевернуть фразу, изменив порядок слов на обратный (фраза на английском языке).
Hello, my baby!
baby! my Hello,
2. Получив текстовую запись (цифрами) однозначного или двузначного числа,
отослать обратно запись этого числа на английском языке:
10
ten
17
seventeen
--------------------------------------------------------------------------
Новая тема: параллельное программирование с помощью нитей (Threads)
Нити были изобретены совсем недавно, в начале 80-х годов,
насколько я представляю, фирмой Sun Microsystems (впервые были
использованы в Unix-системах фирмы Sun: Solaris & Sun Unix;
Silicon Graphics использовала Sun Unix для графических станций.
Идея OpenGL принадлежит Silicon Graphics).
Вместо того, чтобы распараллеливать нашу задачу с помощью процессов,
мы запускаем несколько нитей (облегченных процессов, light-weight process,
иногда говорят "потоков исполнения"), которые разделяют общее виртуальное адресное
пространство.
Преимущества:
-- переключение контектов при переключении нитей происходит
на порядок быстрее, чем при переключении процессов; кеш виртуальной памяти TLB
не сбраасывается;
-- т.к. нити используют общее адресное пространство, они могут совместно работать
над одними и теми же данными, обмен данными между нитями максимально
удобный.
Недостатки:
-- используется лишь один компьютер, невозможно распараллелить задачу между
разными компьютерами, например, в облаке.
Ускорение вычислений достигается, когда в компьютере есть несколько ядер.
Но, даже если речь не идет об ускорении программы, нити всё равно нужны
чисто логически. Например, любая графическая (оконная) программа должна делать
параллельно по крайней мере 2 действия:
1) обрабатывать оконные сообщения о действиях пользователя;
2) производить длительные вычисления, обмен данными по сети,
принимать пакеты по радио или от радара и т.п.
Для работы с нитями существует много интерфейсов. Наиболее интерфейс POSIX,
сейчас поддержка нитей включена в стандартную библиотеку STL языка C++.
Мы пока что будем пользоваться поддержкой нитей в Win32.
ВАЖНО!!!
Все нити используют одно и то же адресное пространство,
но у каждой нити свой собственный стек (участок виртуальной памяти,
на который ссылается регистр SP процессора). Поскольку локальные
переменные функции распогаются в стеке, они безопасны с точки
зрения нитей. Одна и та же функция может вызываться из разных нитей,
но при этом она работает с разными наборами локальных переменных.
Для доступа к общим (статическимЮ глобальным) данным со стороны разных
нитей приходится использовать объекты синхронизации.
Рассмотрим пример проекта "Жеребьевка", реализованного не с помощью процессов,
а с помощью нитей. Для конкурентного доступа к консоли при печати
используется объект типа mutex (MUtual EXcusive), под MS Windows можно
использовать объект "Критическая секция".
=========================================================
14 Jun 2021
Параллельное программирование с помощью нитей
Несколько нитей работают в рамках одного процесса и разделяют
общую виртуальную память, но у каждой нити свой стек. Благодаря этому
нити безопасны при использовании локальных переменных.
Если же необходимо совместное использование глоюальных (статических)
переменных разнимы нитями, то необходимо для доступа к этим переменным
использовать объекты синхронзации (мьютексы, критические секции, семафоры,
события, условные переменные).
Самый прстой объект синхронизации -- это mutex, от MUTual EXclusive
(взаимно исключающий). Это некоторый символический объект, который нужен для
доступа к критическим данным (говорят, что данные защищены мьютексом).
Другое название мьютекса -- lock (замок).
Жлезные дороги в Англии XIX века были однопутными. Машинист мог выехать на перегон,
только если у него в руках специальный token -- латунное кольцо с биркой на нем,
которое машинист забирал из рук дежурного по станции, когда он проезжал станцию.
На следующей станции машинист отдавал токен дежурному по другой станции, встречный поезд
привозил токен назад.
Это кольцо служило мьютексом, защищающим перегон.
В MS Windows, помимо мьютексов, имеется объект "Критическая секция",
более удобный, чем мьютекст, для синхронизации нитей одного процесса.
У критической секции имеется имя.
В теории программирования критической секцией с данным именем называется
участок кода программы, в который может войти только одна нить.
Если другая нить также пытается войти в него, то она приостанавлиается
до тех пор, пока первая нить не выйдет из критической секции.
Одним и тем же именем критической секции могут быть отмечены
несколько разных участков кода программы.
код программы
код программы
код программы
код программы
войти в критическую секцию с именем "A" <-- Нить 2 (ждет, пока нить 1 не выйдет
код программы из критической секции)
код программы
код программы
выйти из критической секции с именем "A"
код программы
код программы
код программы
код программы
код программы
войти в критическую секцию с именем "A"
код программы <-- Нить 1 (вошла в крит. секцию)
код программы
код программы
выйти из критической секции с именем "A"
код программы
код программы
Для примера распараллеливания вычислительной задачи
напишем вычисление интеграла от заданной функции по
отрезку [a, b]. Пусть мы запускаем k нитей:
i-я нить вычисляет интеграл по отрезку
[a + i*dx, a + (i+1)*dx]
где
dx = (b - a)/k
Для вычисления интеграла нитью по ее отрезку
мы будем использовать квадратурную формулу Симпсона:
Для маленького отрезка [x0, x1] интеграл приблизительно равен
(f(x0) + 4*f((x0 + x1)/2) + f(x1))/6 * (x1 - x0)
Она точна для многочленов степени <= 3.
ПЕРЕРЫВ до 14:00 Душанбе
Функция, вычисляющая интеграл по формуле Симпсона (без параллельности):
double simpson(double (*f)(double), double a, double b, int n) {
assert(n > 0);
double h = (b - a)/n;
double s1 = (*f)(a) + (*f)(b);
double s2 = 0.;
double x = a + h;
for (int i = 0; i < n - 1; ++i) {
s2 += (*f)(x);
x += h;
}
double s4 = 0.;
x = a + h/2.;
for (int i = 0; i < n; ++i) {
s4 += (*f)(x);
x += h;
}
return (s1 + 2.*s2 + 4.*s4)*h/6.;
}
Объяснение
Рассмотрим маленький отрезок [x0, x2], h = x2 - x0,
и обозначим середину отрезка через x1 = (x0 + x2)/2.
Пусть функция принимаает в этих точкаах значения y0, y1, y2:
y0 = f(x0), y1 = f(x1), y2 = f(x2).
Приблизим функцию на отрезке параболой по трем точкам.
Тогда нетрудно доказать, что интеграл от параболы равен
((y0 + 4*y1 + y2)/6)*h
Значения функции в крайних точках берутся с весовыми коэффициентами 1,
в средней точке -- с коэффициентом 4, сумма делится на 6 (нормируется)
и умножается на длину отрезка интегрирования. Формула легко запоминается,
и она является точной для многочленов степени не выше 3.
Когда мы разбиваем большой отрезок [a, b] на n маленьких и суммируем интергралы по
маленьким отрезкам, вычисленные по формуле Симпсона, то значения функции
в крайних точках a, b входят в общую сумму с весовыми коэффициентами 1,
в серединах маленьких отрезков -- с коэффициентами 4, в концах маленьких
отрезков -- с коэффициентами 2 (исключая точки a, b). Именно так и реализована
приведенная выше функция simpson(f, a, b, n).
При запуске нитей мы передаем каждой указатель на блок аргументов:
class ArgBlock {
public:
double (*f)(double); // Function to integrate
double a; // Beginning of line segment
double b; // End of line segment
int n; // Number of sub-segments
double integral; // Result should be written here
};
Он содержит указатель на интегрируемую функцию, пределы интегрирования,
число отрезков разбиения, а также поле integral, куда нить должна записать
результат своей работы, т.е. интеграл по отрезку [a, b] от функции f(x).
Функция работы нити у всех нитей одна и та же:
DWORD WINAPI computeIntegral(void* threadArgs) {
ArgBlock* args = (ArgBlock*) threadArgs;
double s = simpson(args->f, args->a, args->b, args->n);
args->integral = s;
return 0;
}
Нити создаются в цикле в функции main():
int k = n/numThreads;
if (k < 1)
k = 1;
double dx = (b - a)/numThreads;
for (int i = 0; i < numThreads; ++i) {
// Define arguments of i-th thread
threadArg[i].a = a + i*dx;
threadArg[i].b = threadArg[i].a + dx;
threadArg[i].n = k;
threadArg[i].f = &f;
// Create i-th thread
hThread[i] = CreateThread(
NULL, // lpThreadAttributes
0, // dwStackSize - default
&computeIntegral, // thread starting function
(void *) &(threadArg[i]), // parameter of thread starting function
0, // dwCreationFlags
&(threadID[i])
);
}
После этого основная нить программы дожидается завершения всех
нитей, вычисляющих интегралы по k сегментам, на которые разбит отрезок [a, b]:
// Wait until all threads finish.
WaitForMultipleObjects(
(DWORD) numThreads, // Number of threads
hThread, // Array of thread handles
TRUE, // Wait for all
INFINITE // Wait timeout: infinite
);
И после этого суммируются интегралы по отрезкам разбиения, которые
вычислены отдельными нитями:
// Compute the integral as a sum of integrals by all segments
double s = 0.;
for (int i = 0; i < numThreads; ++i) {
s += threadArg[i].integral;
}
Посл измерения скорости работы программы мы получили лучший
результат для 6 нитей.
Завтра: параллельные алгоритмы для работы с матрицами.
====================================================================
15 Jun 2021
Параллельные вычисления с помощью нитей
Идея: у нас имеется пул нитей, между которыми мы распределем вычисления;
нити работают параллельно, за счет этого вычисления ускоряются.
Мы не создаем заново нити на каждом этапе работы, а нити существуют на всем
протяжении основной задачи. Каждая нить выполняет свою часть работы, когда
мы ее об этом попросим. Завершив работу, она не заканчивает свое существование,
а продолжает ждать, когда мы попросим ее совершить новое задание.
И только когда мы попросим нить совершить самоубийство,
она завершает свое существование (делает себе харакири).
Для примера рассмотрим алгоритм Гаусса приведения матрицы к ступенчатому виду.
Здесь распараллеливается обнуление столбца матрицы путем вычитания из строки
другой строки, в которой находится разрешающий элемент.
Каждой рабочей нити дается задание обнулить часть столбца, начиная с заданной строки
и указав количество строк, которые нить должна обработать.
Каким образом осуществляетсясвязь между основной нитью и работающими нитями?
Для этого мы используем объект синхронзации типа Event.
Объект Event (Событие) может находиться в двух состояниях
(лампочки потушена/зажжена).
Сигнальное состояние (лампочка горит)
для включения используется функция
SetEvent(hEvent);
Для выключения (перевода в несигнальное состояние) используется функция
ResetEvent(hEvent);
Для ожидания перехода события в сигнальное состояние (включения лампочки)
используются сандартные функции ожидания:
WaitForSingleObject(hEvent, timeout);
WaitForMultipleObjects(numObjects, objectArray, TRUE, timeout) -- ждём всех
WaitForMultipleObjects(numObjects, objectArray, FALSE, timeout) -- ждём хотя бы одного
ВАЖНО:
в MS Windows события бывают двух типов:
1) manual reset event;
2) auto reset event.
Событие первого типа надо выключать вручную:
ResetEvent(hEvent);
Событие второго типа (с автоматическим выключением) переходит в несигнальное
состояние при завершении функции ожидания этого события.
Автоматически сбрасываемые события, по моему опыту программирования,
удобнее и используются чаще. Мы будем использовать автоматически
сбрасываемые события (Auto Rest Events). Для них функцция
ResetEvent(hEvent)
не нужна.
-----------------------------
Рассмотрим метод Гаусса.
Матрицу размера m строк на n столбцов мы представляем в виде
линейного массива, в котором элементы матрицы расположеня по строкам:
сначала 0-я строка, затем 1-я строка, ..., в конце m-1-я строка.
j
+-----------------------------------+
0 |*********| | m строк
1 | ****+-------------------------|
2 | |???????????????????????? | i
...| 0 |? |
| |? |
| |? |
m-1| |? |
+-----------------------------------+
0 1 2 3 ... n столбцов n-1
Элемент матрицы с индексами i, j -- это элемент линейного массива
a[i*n + j]
ПЕРЕРЫВ до 14:00 (Душанбе)
Распределяем работу между нитями. Допустим, у нас 5 нитей,
и надо обработать 13 строк. 13 не делится на 5. Мы распределяем работу
следующим образом:
одной нити выдаетсядля обработки не больше 3 строк.
Нити обрабатывают
3, 3, 3, 3, 1
(последняя нить может обрабатывать меньшее количество строк).
Для распараллеливания вычислительных задач с помощью нитей
обычно используют пакет OpenMP (Multiple Processing)
========================================================
16 Jun 2021
Параллельные вычисления с матрицами
Точное измерение интервалов времени в Win32
Сначала определяем частоту системного таймера:
LARGE_INTEGER frequency;
QueryPerformanceFrequency(&frequency);
printf("Timer frequency = %lld\n", frequency);
Далее измеряем время начала вычислений:
LARGE_INTEGER start;
QueryPerformanceCounter(&start);
После завершения вычислений измеряем время окончания:
LARGE_INTEGER end;
QueryPerformanceCounter(&end);
И дальше вычисляем интервал времени в секундах:
double interval =
double(end.QuadPart - start.QuadPart) / double(frequency.QuadPart);
Печатаем результат:
printf("Computation interval: %.6f s\n", interval);
Результат вычислительного эксперимента:
на входе у нас невырожденная матрица размера 20*20
При одной нити время вычисления ступенчатой матрицы
равно
Computation interval: 0.254260 s
Computation interval: 0.224036 s
Computation interval: 0.044739 s
Computation interval: 0.160770 s
При двух нитях время вычисления
Computation interval: 0.139312 s
Computation interval: 0.172168 s
Computation interval: 0.215276 s
Computation interval: 0.115769 s
При 4-х нитях время
Computation interval: 0.167057 s
Computation interval: 0.072556 s
Computation interval: 0.184135 s
Computation interval: 0.105568 s
(Работает Zoom-конференция, которая отнимает гигантское время CPU
порядка 50%, это искажает результаты экспериментов.)
Домашнее задание, 2 варианта:
1) вычислить обратную матрицу;
2) решить систему линейных уравнений с невырожденной матрицей.
Для меня был шок, когда задача на вычисение обратной матрицы решалась
некоторыми студентами с помощью вычисления алгебраических дополнений
и детерминанта.
Даже если мы вычисляем определители миноров с помощью метода Гаусса,
то определитель вычисляется за время O(n^3), всего в матрице n^2 элементов,
получаем общее время вычисления обратной матрицы O(n^5).
ТАК ДЕЛАТЬ НЕЛЬЗЯ!!!
Обратная матрица вычисляется с помощью метода Гаусса:
к исходной матрице мы приписываем справа единичную матрицу:
* * * * * * * * | 1 0 0 0
* * * * --> * * * * | 0 1 0 0
* * * * * * * * | 0 0 1 0
* * * * * * * * | 0 0 0 1
Полученную матрицу приводим методом Гаусса к ступенчатому виду:
* * * * | * * * *
0 * * * | * * * *
0 0 * * | * * * *
0 0 0 * | * * * *
Домножаем строки этой матрицы на элементы, обратные к диагональным,
так, чтобы на диагонали стояли единицы:
1 * * * | * * * *
0 1 * * | * * * *
0 0 1 * | * * * *
0 0 0 1 | * * * *
Делаем обратный проход, аналогичный методу Гаусса, так, чтобы элементы
в столбца над диагональными элементами стали нулевыми. Из каждой строки над
разрешающей строкой вычитаем разрешающую строку, умноженную на соответствующий
элемент столбца.
Сначала обрабатываем последний столбец, потом предпоследний и т.д.
1 * * 0 | * * * *
0 1 * 0 | * * * *
0 0 1 0 | * * * *
0 0 0 1 | * * * *
предпоследний
1 * 0 0 | * * * *
0 1 0 0 | * * * *
0 0 1 0 | * * * *
0 0 0 1 | * * * *
. . .
в конце-концов получаем слева единичную матрицу
1 0 0 0 | * * * *
0 1 0 0 | * * * *
0 0 1 0 | * * * *
0 0 0 1 | * * * *
в правой части будет обратная матрица.
Аналогично решается линейная система
A*X = B
где A -- невырожденная матрица системы, B -- столбец свободных членов,
X -- столбец неизвестных.
Сначала формируем расширенную матрицу системы:
* * * * * * * * | b0
* * * * --> * * * * | b1
* * * * * * * * | b2
* * * * * * * * | b3
Приводим расширенную матрицу методом Гаусса к ступенчатому виду:
* * * * | *
0 * * * | *
0 0 * * | *
0 0 0 * | *
Домножаем строки этой матрицы на элементы, обратные к диагональным,
так, чтобы на диагонали стояли единицы:
1 * * * | *
0 1 * * | *
0 0 1 * | *
0 0 0 1 | *
Выполняем обратный проход, аналогичный методу Гаусса, так, чтобы слева
получилась единичная матрица.
Сначала обрабатываем последний столбец, потом предпоследний и т.д.
1 * * 0 | *
0 1 * 0 | *
0 0 1 0 | *
0 0 0 1 | *
предпоследний
1 * 0 0 | *
0 1 0 0 | *
0 0 1 0 | *
0 0 0 1 | *
. . .
в конце-концов получаем слева единичную матрицу
1 0 0 0 | *
0 1 0 0 | *
0 0 1 0 | *
0 0 0 1 | *
Последний столбец расширенной матрицы будет содержать решение
исходной системы линейных уравнений.
Напишем программу, вычисляющую обратную матрицу и решающую систему
линейных уравнений в непараллельном варианте. Вашей задачей будет
написать параллельные варианты этих программ.
ПЕРЕРЫВ до 14:00
Напишем программы вычисления обратной матрицы и решения
линейной системы СЛАУ для непараллельного случая.
Файл "matrix.cpp"
Задание на дом: распараллелить эти алгоритмы.
2 варианта, студенты с нечетными номерами делают 1-ю задачу,
с четными -- 2-ю.
1. Вычислить обратную матрицу (для невырожденной квадратной матрицы).
2. Решить систему линейных уравнений с невырожденной квадратной матрицей.
Deadline -- понедельник 21 июня.
На следующем занятии: Dead lock (клинч) и как его избежать.
=================================================================
17 June 2021
Объекты синхронизации
Семафоры, мьютексы, критические секции, события (частный случай семафоров),
атомарные переменные (счетчики), условные переменные.
Семафор целочисленная переменная, принимающая значения >= 0.
Она регулирует доступ к общим объектам со стороны нескольких
процессов или нитей. Пусть начальное значение семафора равно m.
Идея в том, чтобы ограничить доступ к критическим объектам
не более чем m участникам. Тот, кто хочет получить доступ,
выполняем функцию
sem_wait(&s)
Если при этом значение семафора
больше нуля, то оно уменьшается на 1 и участник получаеет доступ к критическим
объектам (нить продолжает работать). Если же в этот момент значние семафора
равно нулю, то нить приостанавливается и ждем, пока значение семафора не
станет положителльным, после чего операционная система возобновляет
исполнение нити/процесса.
Аналогия:
имеется музей, в который можно пропускать не больше 50 человек
одновременно. Зима. Имеется гардероб, в котором 50 номерков,
каждый входящий в музей должен сдать верхнюю одежду в гардероб.
Он при этом забирает номерок, а при выходе возвращает номерок и
получает обратно свою верхнюю одежду. Количество свободных
номерков в гардеробе выполняет роль семафора.
Освобождение семафора выполняется с помощью функции
sem_post(&s);
Этот вызов увеличивает значение семафора на 1.
В Win32 также есть семафоры. Создание семафора выполняется функцией
hMySemaphore = CreateSemaphore(
NULL, // default security attributes
8, // initial count
8, // maximal count
NULL // unnamed semaphore
);
Ожидание семафора выполняется обычной для Windows функцией
WaitForSingleObject(hMySemaphore, INFINITE);
Освобождение семафора выполняется командой
ReleaseSemaphore(
hMySemaphore, // handle to semaphore
1, // increase count by 1
NULL // do not need the previous count
);
В отличие от Unix, в Win32 семафор можно увеличить на число, большее единицы.
Событие Event -- это простейший семафор, значение которого не может быть
больше 1.
SetEvent(hEvent) --
присвоить семафору значение 1.
WaitForSingleObject(hEvent, timeout)
WaitForMultipleObjects(count, hEvents, waitAll, timeout)
уменьшает значение семафора на 1 (т.е. он становится равным нулю)
для auto-reset events. Для manual-reset events для выключения события
надо явно вызвать функцию ResetEvent(hEvent).
Мьютекс (mutex от MUTual EXclusive -- взаимно исключающий) -- это объект,
который может принадлежать только одной нити/процессу. Мьютекст бывает
свободным и захваченным. При попытке захвата мьютекса,который кому-то уже принадлежит,
нить приостанавливается до тех пор, пока мьютекс не будет освобожден
другой нитью. Другое название мьютекса -- Lock (замок).
Ситуация Deadlock (мертвый захват, клинч) -- когда несколько участников
не дают работать друг другу, и из этой ситуации нет выхода.
В случае мьтекса -- допустим, что нить уже захватила мьютекст и пытаюсь
захватить его повторно. Операционная система приостанавливает эту нить.
Но только нить, которая захватила мьютекс, может его освободить.
Получается Deadlock.
Как быть? В POSIX испльзуются мьютексы трех типов: обычные, с проверкой ошибки
(при попытке повторного захвата мьютекса происходит ошибка), и
РЕКУРСИВНЫЕ мьютексы (очень советую всегда использовать только рекурсивные мьютексы).
При захвате рекурсивного мьютекса счетчик числа захватов увеличивается на 1,
а при освобождении мьютекса он реально не освобождается, а просто счетчик
захватов уменьшается на 1. Реально он освобождается, только когда счетчик становится
равным нулю.
void f() {
pthread_mutex_lock(&m);
. . .
g();
. . .
pthread_mutex_unlock(&m);
}
void g() {
pthread_mutex_lock(&m);
. . .
pthread_mutex_unlock(&m);
}
В случае рекурсивного мьютекса такая программа не приводит к Deadlock.
В Win32 все мьютексы рекурсивные, и Deadlock не возникает при повторном
захвате мьютекса.
В Unix надо инициализировать мьютекст при статической инициализации
следующим образом:
static pthread_mutex_t mtx =
PTHREAD_RECURSIVE_MUTEX_INITIALIZER_NP;
При статической инициализации реально мьютекс как объект ядра системы
создается при первом обращении к нему.
Типичная ситуация, когда необходим мьютекс:
для изменения критических данных нужно сделать несколько действий.
Если прервать эти действия в середине, то данные будут находиться
в некорректном состоянии, и попытка их использования другой нитью
или процессом приведет к катастрофе.
Перед изменениями нить захватывает мьютекс, по завершанию изменений
его освобождает. Тот, кто хочет использовать данные, также должен
захватить мьютекс и по окончанию использования данных его освободить.
Отличие мьютекса от семафора: семафор никому не принадлежит,
мьютекс после захвата принадлежит ровно одной нити/процессу,
и только эта нить может его освободить.
Критические секции -- в WIn32 они более популярны, чем мьютексы.
В критическую секцию кода программы с данным именем может войти только одна нить.
EnterCriticalSection(&s);
код критической секции
LeaveCriticalSection(&s);
ПЕРЕРЫВ до 14:00
Проблема с возниковением ситуации Deadlock
Имеются разделяемые ресурсы и несколько процессов или нитей,
которые с ними работают. При этом при захвате ресурса одним
участником другие участники использовать его не могут,
пока участник, им владеющий, не освободит его. В процессе
такой работы может возникнуть ситуация, когда все участники
ждут освобождения ресурсов и не могут ничего
сделать. Это возникает при циклическом ожидании.
Например, есть 3 участника A, B, C.
A ждет, когда B освободит какой-то ресурс.
В ждет, когда C освободит другой ресурс.
С ждет, когда A освободит еще один ресурс.
Возникает Deadlock.
Дейкстра, 1965, задача для студентов.
За круглым столом сидят 5 обедающих философов, между ними лежат 5 вилок.
В середине стола блюдо со спагетти, для еды нужны 2 вилки.
Каждый философ думает какое-то время, потом, когда проголодается,
берет сначала левую вилку, если она свободна, затем правую вилку,
если она свободна, затем ест какое-то время, после чего кладет
обе вилки на стол, освобождая их.
Каждый философ выпоняет такие действия независимо от остальных.
Оказывается, при этом может возникнуть deadlock, когда все философы
взяли левую вилку и ждут, когда освободится правая.
Напишем программу, которая моделирует такую ситуацию.
Каждому философу соответствует нить,которая исполняет его алгоритм:
цикл 50 раз выполнить
| подождать случайное время <= макс. время размышления
| захватить левую вилку
| подождать случайное время <= макс. время между захватами вилок
| захватить правую вилку
| поесть случайное время <= макс. время еды
| освободить левую вилку
| освободить правую вилку
конец цикла
Каждой вилке соответствует мьютекс.
Захвату вилки соответствует команда
WaitForSingleObject(hMutex, INFINITE);
Освобождению вилки соответствует функция
ReleaseMutex(hMutex);
Случайные промежутки времени, в течение которых философ думает,
ест, промежуток между захватом левой вилки и попыткой захватить праву вилку
моделируются с помощью функции
Sleep(milliseconds);
Как философам избежать клинча (deadlock)? Можно ли каким-либо
образом изменить порядок действий каждого отдельного философа за столом,
чтобы deadlock не возникал?
Оказывается, можно, и такой алгоритм был предложен Dijkstra (Дайкстра,
как правильно произносится его фамилия по-голландски, или Дейкстра,
как обычно пишут его фамилию в русскоязычной литературе).
Основная причина возникновения deadlock состоит в циклицеском
ожидании:
A ждёт B,
B ждёт C,
C ждёт D,
D ждёт A.
Дейкстра предложил перенумеровать все общие ресурсы
и захватывать их только в порядке возрастания номеров.
Если одна нить хочет захватить более одного ресурса, то она должна
захватывать их всегда в порядке возрастания номеров.
Например, пусть нить захватиа ресурс с номером 17 и хочет захватить
ресурс с номером 5. Это запрещено! Она должна сначала освободить
ресурс 17, затем захватить ресурс 5 и только после этого снова захватить
ресурс 17.
Теорема Дейкстры.
Пусть все ресурсы частично упорядочены.
( a < b и b < c => a < c
При этом могут быть несравнимые элементы:
неверно, что a < b или b < a. )
Тогда deadlock не может возникнуть, если
1) каждая нить/процесс может одновременно захватывать только
ресурсы, которые сравнимы между собой;
2) захватывать ресурсы можно только в порядке их возрастания.
Следствие для задачи об обедающих фиософах.
Deadlock не возникнет, если каждый философ сначала будет брать
вилку с меньшим номером и затем вилку с большим номером.
То есть из 5-ти философов, сидящих за столом, философы с номерами 0, 1, 2, 3
сначала берут левую вилку и затем правую, и только философ 4 сначала берет
правую вилку и затем левую.
Для философов n = 0, 1, 2, 3 левая вилка имеет номер n, правая n+1;
для философа n = 4 левая вилка имеет номер 4, правая номер 0.
Задача на дом: переделать программу обедающих философов
diningPhil.cpp
в соответствии с алгоритмом Дейкстры и проверить, что deadlock
больше не возникает.
==============================
21 Jun 2021
Условные переменные. Интерфейс нитей, независимый от операционной
системы:
std::thread
std::mutex
std::unique_lock
std::lock_quard
std::condition_variable
Условные переменные -- всегда были в POSIX, не были реализованы
в первых версиях Win32. Например, Windows XP не реализует
CONDITION_VARIABLE.
Что такое условная переменная? Это объединение бинарного семафора
(или события в терминах Windows) и мьютекса.
Пусть мы ждем какого-то события, связанного с критическими
данными, и при этом по наступлению события хотим сразу получить
исключительный доступ к этим данным.
Пример: мы хотим купить через Интернет билет на чемпионат Европы
по футболу. Я открыл браузер и жду, когда появятся свободные билеты.
Мне приходит сообщение, что есть свободные билеты. Я пытаюсь купить
билет, но меня опережают, билет уже куплен кем-то другим.
Хотелось бы, чтобы по получению уведомления о наличие свободного билета
я получил бы сразу исключительноый доступ к базе так, чтобы никто другой,
кроме меня, не мог бы купить свободный билет, пока я этого не сделаю либо
не откажусь от покупки.
критические данные (база билетов)
мьютекс, который защищает эту базу.
захватить мьютекс
если усть свободные билеты
то купить билет
иначе
условная_переменная.ждать, пока появится свободный билет
купить билет
конец если
освободить мьютекс
Кто-то другой, кто изменит базу так, что появятся свободные билеты
выполнит команду
условная_переменная.оповестить о наличии билетов
Во время ожидания на условной переменной мьютекс временно
освобождается. После того, как кто-то другой выполнит оповещение
на условной переменной (о том, что база изменилась), ожидание
заканчивается и я снова получаю мьютекст, передающий базу в
мое полное распоряжение.
std::mutex m;
std::conditional_variable condVar;
{
std::unique_lock<std::mutex> lock(m);
while (в базе нет свободных билетов) {
condVar.wait();
}
купить билет; (в этот момент мы владеем мьютексом!)
}
Другая нить должна изменить базу так, чтобы появились свободные билеты.
{
std::lock_guard<std::mutex> lock(m);
изменяем базу так, чтобы в ней появились свободные билеты
}
condVar.notify_one(); // Оповестить одного
Оповестить всех
condVar.notify_all();
В стандартной библиотеке не реализованы семафоры (и события как их
частный случай): считается, что условных переменных достаточно для
программирования любых параллельных программ.
Простейший пример на использование условных переменных:
схема producer-consumer.
producer содает (получает по сети, вводит с клавиатуры и т.п.)
какие-то объекты и передает их consumur'у на обработку.
consumer обрабатывает полученные объекты, показывает результат
и т.п.
ПЕРЕРЫВ до 11:30
Пример простой программы, использующей условные переменные и ожидание
на условных переменных
Работают две нити: producerThread и consumerThread
producerThread вводит с клавиатуры строку, добавляет ее в буфер и
передает ее consumerThread.
consumerThread получает строку от producerThread, обрабатывает ее
(в нашем случае переворачивает), печатает на консоли и ждет следующей строки.
Консоль является общей и используется попеременно двумя нитями.
Программа использует STL языка C++11, в которой добавлена поддержка нитей.
Файл prodCons.cpp
Условные переменные в Win32:
Могут использовать либо мьютекс,
либо критическую секцию
CRITICAL_SECTION CritSection;
CONDITION_VARIABLE ConditionVar;
void PerformOperationOnSharedData()
{
EnterCriticalSection(&CritSection);
// Wait until the predicate is TRUE
while( TestPredicate() == FALSE )
{
SleepConditionVariableCS(&ConditionVar, &CritSection, INFINITE);
}
// The data can be changed safely because we own the critical
// section and the predicate is TRUE
ChangeSharedData();
LeaveCriticalSection(&CritSection);
// If necessary, signal the condition variable by calling
// WakeConditionVariable or WakeAllConditionVariable so other
// threads can wake
}
Совет:
лучше использовать не функции Win32 или POSIX, а нити и объекты синхронизаци
из стандартной библиотеки STL или, как вариант, из Qt. Это и намного проще,
и меньше возможностей совершить фатальную ошибку.
========================================================
22 Jun 2021
Компьютерные сети
Сеть Internet (Arpanet) была основана в середине 1970-х
Сначала название проекта было DARPA (Defence Advanced Researche Project...?)
Сначала это был государственный военный проект в США, но потом от него отказались
и его стали поддерживать как открытый проект. В начал 80-х сеть была
одной из глобальных сетей (не самой большой), другие сети: DECNet, USENet, FIDO, ...
В конце 90-х получилось так, что сначала все глобальные сети получили из сети
Internet доступ к ним, а кончилось тем, что просто стали частью сети Interner
и растворились в ней.
internet с маленькой буквы -- это объединение разных сетей в одну межсеть.
Internet большой буквы -- это название конкретной глобальной сети.
Сейчас уже в сознании обывателей слова Интернет и сеть означают одно и то же,
люди даже не понимают разницу между локальными и глобальными сетями.
Еще: в сознании современных людей отождествляются понятия
"сеть Intenet" и "Всемирная паутина". На самом деле, Всемирная паутина
(WWW -- World Wide Web) -- это просто один из сервисов в Интернете,
который был основан в 1989, почти на 20 лет позже, чем сеть Интернет.
Он был основан в Церне физиками для облегчения и ускорения обмена научной
информацией.
Классификация сетей:
-- локальные и глобальные сети;
-- одноранговые сети (peer-to-peer) и сети типа клиент-сервер;
-- класcификация по ипользуемым протоколам.
Например, фирма Microsoft в течение почти 15 лет не признавала сущесствования
Интернета, т.е. стек протоколов Интернета не был реализован в MS DOS и MS Windows 3.1.
Microsoft пытались поддерживать свой (и IBM) стек протоколов NETBIOS (или
в современной версии NETBEUI???). Впервые поддержка Internet-протоколов появилась
в Windows NT (1992), окончательно в пользовательских системах она укоренилась c
входом MS Windows-95 (ОС с 16-разрядным ядром); ... Windows Millenium Edition;
всё это извращение в прошлое закончилось версией Millenium Edition, после чего
Microsoft вернулась полностью к линии Windows NT, начиная с WIndows 2000 (особо
подчеркивалось, что в ней хорошо реализования все сетевые протоколы).
Windows XP, Windows Vista, Windows 7, Windows 8, Windows 10, --> Win 11.
(WSL Windows service for Linux ???).
Башня (стек) сетевых протоколов:
NETBIOS (NETBEUI)
TCP/IP (Unix, Internet)
IPX/SPX (Novel NETWARE)
AppleTalk,
ISO/OSI,
. . .
Уровневая модель описания и реализации сетевых протоколов
=========================================================
Модель ISO/OSI
Internetaion Standard Organization / Open System Interconnection
Взаимодействие Открытых Систем (ВОС).
ISO/OSI была задумана как конкретная башня протоколов, задуманная для
замены всех существующих на тот момент разнообразных башен протоколов
(как в некотором смысле Вавилонская башня в области сетей). К сожалению
(или к счастью?), проект оказался крайне неудачным, этот стандарт был
придуман и даже кем-то реализован, но никто не стал им пользоваться,
поскольлко сам по себе стандарт оказался неудачным (был принят ряд неудачных
решений). В результате проект ISO/OSI остася лишь как некоторый общий взгляд
на реальные стеки протоколов -- способ их классификации, позволяющий
лучше понять местокаждого протокола в конкретном стеке протоколов.
Главная идея: уровневое (layer -- слой), или слоеное описание протоколов.
При описании сложного протокола мы разбиваем его на слои. Протокол каждого
слоя описывается строго в терминах команд протокола слоя на единицу меньше.
В модели ISO/OSI выделяются следующие уровни (или слои, layer) протоколов:
Стек ISO/OSI Стек TCP/IP
Прикладной Application
Представления данных Presentation
Сессионный (сеансовый) Session
Транспортный Transport
Сетевой <--------> Network
Канальный V- - - - ^ Channel
Физический V- - - - ^ Physical
ПЕРЕРЫВ до 14:00
Физический уровень -- описывает формы сигналов и среду передачи
Канальный уровень -- описывает передачу пакетов от компьютера на физический уровень.
Важный подуровень MAC (Media Access Control) -- описывает алгоритм получения
доступа к среде
Сетевой уровень -- описывает прохождение пакетов интерсети через маршрутизаторы,
хабы, switch'и т.п. сетевые устройства
Транспортный -- описывает формат адресов и формат пакетов интерсети. На этом уровне
мы как бы не знаем о существовании сети, сегментов сети, маршрутизаторов
и т.п. Мы передаем пакет в сеть, указывая адрес назначения, а сеть
сама, без нашего участия,продвигает пакет к узлу назначения.
Пример: протокол IP или протокол UDP из Internet-стека.
Сессионный уровень -- с моей точки зрения это уровень виртуального соединения
между двумя участниками передачи. На этом уровне передаются уже не
пакеты, а сообщения произвольной длины. А разрезании дллинного сообщения
на пакеты, переповторе передачи пакетов в случае их потери или
искажения нам заботиться не надо, за нас это всё делают драйверы
протоколов. Пример протокла из стека Internet -- протокол TCP
Представление данных -- описываются форматы передаваемых данных
Прикладной уровень -- описываются конкретные прикладные протоколы:
протокол электронной почты SMTP (Simple Message Tansfer Protocol),
порт 25;
протокол передачи гипертекста всемирной паутины HTTP
(Hyper Text Transfer Protocol), 80;
протокол передачи файлов FTP (File Transfer Protocol), 21;
протокол удаленного терминала Telnet, 23;
безопасный протокол удаленного терминала ssh (Secure SHell), 22;
Протокол -- это набор соглашений о взаимодействии.
Протокол переговоров между авиадиспетчером и пилотом самолета.
Ascend / descent
Climb
Протоколы описываются в открытых документах, принятых как международный стандарт.
Рассмотрим конкретный стек протоколов Internet.
Он называется TCP/IP по названиям двух самых важных протоколов:
IP (Internet Protocol) -- базовый протокол для большинства остальных;
не может быть напрямую использован прикладной программой.
TCP (Transfer Control Protocol) -- протокол управляемой передачи. Основан
на установке виртуального соединения между двумя участниками передачи,
по котором данные передаются в обе стороны (full-duplex connection).
Данные любой длины передаются гарантировано, происходит проверка
контрольных сумм пакетов и их переповтор при искажении / потере
пакета.
Другие Интернет-протоколы:
UDP (Used Datagram Protocol) -- протокол передачи и приема дейтаграмм.
DATAGRAM -- это пакет, который мы передаем в сеть и про который мы не можем сказать,
дошел ли он до адресата, исказился ли он при передаче, был ли он потерян.
Как бумажное письмо -- мы его опускаем в почтовый ящик и больше ничего
не знаем о его судьбе.
Пример: видео или аудио-информация может передаваться по протоколу UDP. Он также
может использоваться при групповом широковещании.
ARP -- Address Resolution Protocol -- протокол сетевого/канального уровня.
-------------------------------------------
Пакет -- это небольшая порция данных ограниченного размера, которая передается
по сети как единое целое. Пакет состоит из друх частей:
-- служебная часть пакета (заголовок, header);
-- содержательная часть, та информация, которая передается по сети.
Служебная часть пакета зависит от используемого протокола, но она, как правило,
влючает:
-- адрес назначения (destination address),
-- адрес отправителя (source address),
-- длина пакета,
номер протокола,
порядковый номер сегмента данных,
. . .
контрольная сумма (вернее, CRC -- cyclic redundancy check)
Аналогия -- это как бы конверт,в который завернуто само письмо.
Circuit switching (коммутация каналов), данные передаюся сплошным потоком,
обмен данными требует предварительной установки соединения.
Packet switching (обмен пакетами), данные передаются в виде пакетов. Для передачи
не требуется процедура предваритеьной установки соединения.
Аналогия -- классическая телефонная сеть и почтовая сеть.
Адреса в протоколах Internet
Существуют две версии протоколов:
1) классическая версия IPv4;
2) современная версия IPv6.
Рассмотрим классическую версию протоколов.
Адрес состоит из двух частей:
-- IP-номер, состоит из 4-х байтов, 158.250.33.65 компьютер mech.math.msu.su
-- порт -- целое 2-байтовой число от 1..65535
Аналогия: IP-адрес, это как бы номер дома;
порт, это как бы номер квартиры в доме.
Пару (IP, Port) иногда называют сокетом (слово сокет перегружено и в разных
контекстах может означать совершенно разные вещи).
Хотя чаще всего сокетом называю конечную точку взаимодействия
(как бы трубка телефона, в которую можно говорить и которую можно слушать).
Соглашение: в Интернете известные сервисы имеют фиксированные номера портов.
Например, чтобы обратиться к демону всемирной паутины (httpd), подсоединимся к нему
с помощью программы telnet или, если telnet не усстановлен в Windows,
помощью нашей учебной программы unicli. Цель -- скачать интернет-страницу
C:\home\vvb\Dush\Projects\CodeBlock\Net\Unicli>.\unicli mech.math.msu.su 80
peer addr = 158.250.33.65, port 80
Connected!
GET http://mech.math.msu.su/~vvb/index.html HTTP/1.1
Host: mech.math.msu.su
HTTP/1.1 200 OK
Date: Tue, 22 Jun 2021 14:34:41 GMT
Server: Apache/2.2.16 (Fedora)
Last-Modified: Tue, 18 May 2021 08:10:56 GMT
ETag: "17c1d17-17f8-5c2963fe125ce"
Accept-Ranges: bytes
Content-Length: 6136
Connection: close
Content-Type: text/html
X-Pad: avoid browser bug
<!DOCTYPE html>
<html>
<head>
<meta http-equiv='Content-Type' content='text/html; charset=koi8-r'>
<title>Vladimir Borisenko home page
</title>
</head>
<body>
<h2>
Home Page of Vladimir Borisenko
</h2>
. . .
</body>
</html>
Здесь устанавливается соединение с сервером mech.math.msu.su на порту 80,
и затем, после выдачи "Connected!", мы вводим с клавиатуры команды протокола HTTP.
Текст запроса
GET http://mech.math.msu.su/~vvb/index.html HTTP/1.1
Host: mech.math.msu.su
заканчивается передачей пустой строки. В протоколе HTTP пустая строка
отделяет заголовок HTTP-запроса от тела запроса, но для запроса GET
тело запроса должно быть пустым. Дальше программа unicli распечатывает
текст ответа сервера. Ответ состоит также из заголовка, потом идет пустая строка
и затем тело ответа. Если запрос выполнен успешно, то тело ответа содержит
текст скачиваемой Internet-траницы. В данном случае заголовок ответа состоит
из строк
HTTP/1.1 200 OK
Date: Tue, 22 Jun 2021 14:34:41 GMT
Server: Apache/2.2.16 (Fedora)
Last-Modified: Tue, 18 May 2021 08:10:56 GMT
ETag: "17c1d17-17f8-5c2963fe125ce"
Accept-Ranges: bytes
Content-Length: 6136
Connection: close
Content-Type: text/html
X-Pad: avoid browser bug
включая пустую строку в конце, а тело ответа -- это текст скачиваемой страницы:
<!DOCTYPE html>
<html>
<head>
<meta http-equiv='Content-Type' content='text/html; charset=koi8-r'>
<title>Vladimir Borisenko home page
</title>
</head>
<body>
<h2>
Home Page of Vladimir Borisenko
</h2>
. . .
</body>
</html>
Первая строка заголовка представляет собой статус завершения команды:
HTTP/1.1 200 OK
Код 200 означает успешное завершение (коды 300-399 говорят о перенаправлении
запроса, коды 400-499 об ошибке). Дальше выдается разнообразная информация о
странице. Самая главная строка -- это
Content-Length: 6136
она выдает количество байтов в теле ответа, т.е. размер выдаваемой страницы.
Когда принимающая программа заканчивает чтение заголовка (завершающегося пустой строкой),
она согласно этой информации уже знает, сколько байтов следует принять, чтобы полностью
считать тело ответа.
=================================================================
23 Jun 2021
Программирование сетевых приложений с использованием интерфейса
BSDI-Sockets
Система адресов в Internet: классический вариант IPv4
Адрес состоит из двух частей:
1) IP-номер, например, 158.250.33.65
состоит из 4 байтов, записанных в BigEndian-формате
(старший байт слова имеет младший адрес, байты нумеруются
слева направо).
Big Endian. Число 259 = 256 + 3. В двоичном виде записывается как
0000...0000100000011
Разобьем на байты
00000000,00000000,00000001,00000011
В формате BigEndian байты слова нумеруются слева направо:
0 1 2 3
Если 259 было бы IP-номером, то оно было бы записано как
0.0.1.3
Формат BigEndian был популярен, когда создавали Internet,
т.е. в конце 1960-х -- начале 1970-х годов.
BigEndian компьютеры -- это IBM 360-370, советские ЕС ЭВМ,
процессоры Motorola (Ранние Apple-сомпьютеры, графические станции),
процессор PowerPC (Apple MAC до 2006 г.).
Но гораздо правильнее нумеровать байты справа налево, так, что младшие
биты слова записывались в байте с младшим адресом. Таково большинство
современных процессоров.
Little Endian компьютеры & процессоры:
все компьютеры фирмы Digital Equipment Corporation
PDP-11, советские Электроника, VAX, Alpha, процессоры Intel 80*86,
Intel/AMD 86_64, ...
2) номер порта -- неотрицательное двухбайтовое число в диапазоне 1..65534,
также записанное в Big Endian формате.
IP-номер -- это как бы адрес компьютера в Интернете (более точно,
адрес сетего интерфейса в компьютере, поскольку в одном компьютере
может быть несколько сетевых интерфейсов, когда компьютер выполняет роль
шлюза/маршрутизатора, соединяющего несколько локальных сетей).
Порт -- это как бы адрес внутри компьютера (как у многоквартирного дома
номер дома и номера квартир внутри дома).
Пара (IP, Port) называется сокетом.
(Слова сокет имеет много разных значений!)
Порты с номерами 1..1023 являются привелегированными и недоступны для
пользовательских программ (нужны привелегии администратора).
Например, обчный пользователь не может запустить Web-сервер,
поскольку тот использует порт 80 для приема приходящих
соединений. Имеется для Web-сервера альтернативный непривелегированный
порт 8080.
Давайте мы в учебных программах будем по умолчанию использовать порт 1234
(он больше 1023, т.е. непривелегированный).
Для человека IP-номера не очень удобны, их трудно запоминать.
Например, компьютер mail.ru имеет IP-номер 94.100.180.201
(на самом деле, он использует 4 IP-номера!). Имеется отображение
символических имен на IP-номера, которое называется DNS
Domain Name Service.
DNS не только отображает символические имена на IP-номера, но и
организует адреса компьютеров в некоторую иерархическую
структуру.
Интпернет разбивается на зоны, зоны на подзоны, подзоны на по-подзоны и т.д.
Когда Интернет только создавалась (в 1970-е годы), в ней было только 8 зон
верхнего уровня:
edu, com, org, net, gov, arpa, ... все они были в США
Пример: зона edu объединяет университеты и другие учебные институты на
территории США
Имеется name server, который отвечает за зону edu
Это полностью его ответственность. Права на зону edu делегированы ему.
В этой зоне имеется Michigan State University, ему выделена подзона
msu.edu
За эту подзону (msu внутри edu) также отвечает name server.
А этот сервер уже знает про конкретные узлы в его зоне. Например,
математический факультет имеет имя math, полное его имя
math.msu.edu
В программе на языке C/C++ для получения IP-номера по доменному имени
используется функция gethostbyname
Сетевые программы, использующие Интернет-протоколы, используют
обычно один из двух протоколов:
1) протокол TCP используется большинством программ;
2) некоторые программы используют протокол UDP.
Разница:
-- протокол TCP требует предварительной установки (виртуального) соединения;
при установенном соединении осуществляется гарантированная передача и
прием сообщений произвольной длины;
-- протокол UDP не требует установки соединения, но он не гарантирует
доставку сообщений. В нем передаются дейтаграммы, т.е. короткие сообщения
ограниченной длины; скорее всего, всегда можно передавать сообщения
длины <= 1024. Пакет с сообщением просто передается в сеть, а принял его
кто-нибудь или нет, узнать невозможно.
ACK -- positive acknolegement (положительное уведомление о доставке пакета)
NAC -- negative acknolegement (пакет исказился или вообще не дошел до адресата,
адресат посылает NAC отправителю).
ПЕРЕРЫВ до 14:00
Программирование сетевых приложений с использванием
интерфейса BSDI-сокетов
Основная идея интерфейса сокетов -- работать с сетью так же,
как и с файлом.
В Unix открытый файл отождествляется файловым дескриптором,
который есть просто целое число (индекс вв таблице открытых
файлов процесса). Когда процесс стартует, у него открыты 3 файла:
стандартный входной поток stdin, файловый дескриптор 0,
стандартный выходной поток stdout, файловый дескриптор 1,
стандартный выходной поток ошибок stderr файловый дескриптор 2.
Открытие файла на чтение:
int fd = open("input.txt", O_RDONLY);
На запись O_WRONLY, на чтение и запись O_RDWR.
И после этого можно читать из файла:
ssize_t res = read(fd, buffer, numBytes);
Команда возвращает количество прочитанных байтов или (-1) в случае ошибки.
Для записи в файл используется команда
ssize_t res = write(fd, buffer, numBytes);
Команда возвращает количество записанных байтов, теоретически оно может
быть меньше, чем numBytes, хотя на практике эти числа всегда равны, если
только не произошло ошибки записи.
Идея интерфеса сокетов:
после того, как установлено соединение,
мы работаем с сетью точно так же, как и с файлом,
в Unix'е даже используются те же самые команды read и write,
в качестве файлового дескритора указывается номер сокета,
это также просто целое число.
Сокет -- это что-то типа файла, имитация файла для работы с сетью.
В Unix'е помимо функций read и write можно также использовать
функции recv и send, это аналог функция чтения и записи для сокетов.
ssize_t res = read(fd, buffer, numBytes);
ssize_t res = recv(fd, buffer, numBytes, 0);
Последний аргмент -- это флаги.
Флаг 0 означает, что не обязательно ждать всех numBytes байтов,
можно завершить функцию, когда по сети придет первая порция байтов.
Если надо дождаться получения всех numBytes байтов, то используется флаг
int res = recv(fd, buffer, numBytes, MSG_WAITALL);
Фукции send и recv блокирующие, пока они не завершатся, программа висит.
В Unix асинхронная работа фактически не реализована (в отличие от Windows).
Зато есть функция select, которая позволяет проверить, по каким сокетам
пришли данные. Обычно в программах read или accept выполняется только тогда,
когда перед этим была выполнена функция select, которая вернула результат,
сообщающий, что по сети пришли данные.
ОЧЕНЬ ВАЖНО!!!
Интерфейс сокетов используется в Unix не только для сети Internet,
но и вообще для любых сетевых архитектур. Отсюда следует, что функции
открытия сокетов и установки соединения испоьзуют адреса общего вида
struct socaddr
и и указатели на адреса Internet надо приводить к указателям на
адреса общего вида:
struct socaddr_in peerAddr;
. . .
int res = connect(s, &peerAddr, sizeof(peerAddr)); // ОШИБКА!!!
Надо писать
int res = connect(s, (struct socaddr*) &peerAddr, sizeof(peerAddr)); // правильно
Создание сокета -- рассмотрим вариант Internet-сокета:
int s0 = socket(AF_INET, SOCK_STREAM, IPPROTO_TCP);
AF_INET Addres Family Internet -- сокет для Интернет-соединений
SOCK_STREAM (потоковый) означает, что используется протокол TCP (а не UDP),
т.е. протокол, основанный на установке соединения
IPPROTO_TCP эта константа равна нулю -- номер семейства протоколов для данной сетевой
архитектуры, для Internet этот параметр
не используется (всегда 0).
Создается сокет, пока что ни с кем не соединенный и не имеющий адреса.
При установке соединения роли несимметричны. Например, при установке
телефонного соединения один участник звонит другому, другой принимает звонок.
После того, как соединение установлено, роли участников абсолютно одинаковы
(полностью симметричны): оба могут говорить в телефон и оба могут слушать,
в случае компьютера записывать данные в сокет и читать данные из сокета.
Тот, кто звонит, должен знать номер того, кому он звонит, а собственный номер
при этом знать совершенно не обязательно!
Аналогично в интерфейсе сокетов клиент (это тот, кто инициирует соединение,
т.е. "звонит по телефону") не задает адрес сокета, это за него автоматически
делает система в момент соединения, т.е. сокету присваиватся
конкретный номер порта.
Сервер (этот тот, кто принимает соединение), в отличие от клиента, должен
указать номер порта, по которому будут приниматься соединения, т.е.
связать сокет с конкретным адресом. Это делается с помощью функции bind:
// Create a socket
int s0 = socket(AF_INET, SOCK_STREAM, IPPROTO_TCP);
// Bind the socket with address
//-------------------------------------------
struct sockaddr_in myaddr; // Структура, описывающая адрес для приема соединений
memset(&myaddr, 0, sizeof(struct sockaddr_in)); // Почистить ее!
unsigned short listenPort = 1234;
myaddr.sin_family = AF_INET; // Семейство адресов Internet
myaddr.sin_port = htons(listenPort); // Порт для приема соединений
myaddr.sin_addr.s_addr = htonl(INADDR_ANY); // Принимаем соединения от ВСЕХ!!!
Функция (точнее, макроопределение) htons означает "Host TO Network Short" делает
перестановку байтов от порядка порядка байтов на данном компьютере (host)
к Big Endian формату, который используется в Internet (Network),
s (Short) означает, что переставляем байты в 16-разрядном слове.
myaddr.sin_addr.s_addr = htonl(INADDR_ANY);
означает взять 4-байтовое число INADDR_ANY, означающее Inet-адрес для всех,
htonl Host TO Network Long -- переставить байты 4-байтового слова в порядке
от нашего компьютера в Big Endian формат.
sin_addr.s_addr означает трактовку адреса как единого 4-байтового целого числа,
а не как массива из 4-х байтов.
// Bind a socket to the address
int res = bind(s0, (struct sockaddr*) &myaddr, sizeof(myaddr));
И после этого выполняем команду listen (слушать), которая отмечает сокет s0
как сокет, используемый НЕ ДЛЯ ОБМЕНА ДАННЫМИ,
а только ДЛЯ ПРИЁМА ПРИХОДЯЩИХ СОЕДИНЕНИЙ.
Сокет s0 -- это как бы секретарша (receptionist), которая только принимает клиентов
и направляет их к специалистам (сама ничего не умеет).
Два типа сокетов и Inet-архитектуре:
-- клиентский сокет, по которому можно отсылать и принимать данные,
используя функции send и recv. Соединение устанавливается
с помощь функции connect;
-- серверный сокет, по которому можно только принимать соединения от клиентов.
Использует функцию listen (она помечает сокет как серверный) и функцию
accept для приема приходящих соединений.
res = listen(s0, 5); // "5" is the maximal length of the queue
ПЕРЕРЫВ до 15:40 (10 минут)
Установка соединения, схема
Клиент
int s = socket(...)
struct sockaddr_in serverAddr;
// Заполняет адрес сервера
// ... gethostbyname(...)
int res = connect(s, (struct socaddr*) &serverAddr, sizeof(serverAddr));
char buffer[128];
char send_buffer[128];
while (true) {
ssize_t numBytes = recv(s, buffer, 1, 0);
if (numBytes <= 0)
break;
. . .
send(s, send_buffer, len);
. . .
}
closesocket(s0); // Закрываем сокет
WSACleanup(); // Завершаем работу с библиотеков winsock2, файл libws2_32.lib
Сервер:
int s0 = socket(...);
struct sockaddr_in myaddr;
. . . // Заполняем собственный адрес сервера
myaddr.sin_port = htons(listenPort); // ГЛАВНОЕ!!! Указываем порт, по которому
. . . // будем принимать соединения
// Bind a socket to the address
int res = bind(s0, (struct sockaddr*) &myaddr, sizeof(myaddr));
res = listen(s0, 5); // Указываем, что сокет будет использоваться только
// для приема соединений
struct sockaddr_in clientAddr;
int peeraddr_len = sizeof(clientAddr);
// Принять соединение от клиента и создать новый сокет s1 для обмена данными
int s1 = accept(s0, (struct sockaddr*) &peeraddr, &peeraddr_len);
// Функция accept блокирующая, если никто не подсоединяется, то она будет
// ждать потенциально бесконечно долго.
closesocket(s0); // если больше принимать соединения не нужно
while (true) {
send(s1, "Hello!\r\n", 8, 0);
char buffer[128];
ssize n = recv(s1, buffer, 1, 0);
if (n <= 0)
break;
. . .
}
closesocket(s1);
WSACleanup(); // Завершаем работу с библиотеков winsock2, файл libws2_32.lib
====================================================================
24 Jun 2021
Интерфейс сокетов, продолжние
В протоколе TCP одной команде send может соответствовать несколько команд recv
send 200 байтов ----------> recv 50
recv 50
recv 80
recv 20
Функции send и recv работают с потоком данных.
В протоколах желательно заранее передавать длину данных, которые пересылаются.
Рассмотрим протокол HTTP (Hyper Text Transfer Protocol, 1989).
Протокол очень простой, легко понимаемый и реализуемый. Некоторые возможности,
которых не было в первых версиях протокола, были позже добавлены:
HTTP/1.0
HTTP/1.1 (широко используется сейчас)
HTTP/2.0 (наше ближайшее будущее)
Главная ккоманда -- получить страницу *.html
Программа telnet (другое название Терминал):
подсоединяемся к партнеру по протоколу TCP;
всё, что мы печатаем на клавиатуре, пересылается по сети партнеру по сессии;
всё, что выводит на экран партнер, на самом деле не выводится на его экран,
а пересылается нам и мы распечатываем эти данные на своем экране.
Программа telnet, в частности, позволяет работать на удаленном компьютере
(для этого на удаленном компьютере должен работать telnet-демон),
позволяет беседовать с любым демоном. Всегда, в течение 40 лет в Windows
была программа telnet, но Microsoft посчитали, что все дополнительные возможности
из MS Windows следует убрать. По умолчанию telnet не установлена.
Рассмотрим замену: учебное приложение "Универсальный клиент" unicli.cpp
В этой программе создается отдельная нить, которая только читает данные по сокету,
а основная нить читает, что человек набирает на клавиатуре, и пересылает
введенные строки партнеру.
Классические протколы, как правило, основаны на обмене текстовыми строками
(или блоками из строк). Каждая строка заканчивается двумя символами,
теми же, какими в MS DOC или в MS Windows разделяются строки (или, по мнению
MS Windows, абзацы) в текстовых файлах:
CR LF Carrige Return, Line Feed
'\r' '\n' Return, New_line
В Unix строки разделяются одним символом '\n',
в Apple MAC строки разделяются также одним символом, но это '\r'
Если вы открываете файл в языке C/C++ как текстовый, то при вводе и выводе
происходит преобразование текста: пара "\r\n" преобразуется в один символ '\n',
при выводе происходит обратное преобразование "\n" --> "\r\n".
Давайте поговорим с демоном всемирной паутины, используя unicli.
/c/home/vvb/Dush/Projects/CodeBlock/Net>./unicli.exe mech.math.msu.su 80
Server IP number = 158.250.33.65, port 80
Connected!
GET http://mech.math.msu.su/~vvb/index.html HTTP/1.1
Host: mech
Connection: keep-alive
HTTP/1.1 200 OK
Date: Thu, 24 Jun 2021 07:26:51 GMT
Server: Apache/2.2.16 (Fedora)
Last-Modified: Tue, 18 May 2021 08:10:56 GMT
ETag: "17c1d17-17f8-5c2963fe125ce"
Accept-Ranges: bytes
Content-Length: 6136
Connection: close
Content-Type: text/html
X-Pad: avoid browser bug
<!DOCTYPE html>
<html>
<head>
<meta http-equiv='Content-Type' content='text/html; charset=koi8-r'>
<title>Vladimir Borisenko home page
</title>
</head>
<body>
<h2>
Home Page of Vladimir Borisenko
</h2>
. . .
</body>
</html>
Давайте рассмотрим устройство программы unicli.cpp
Unix -- имеется функция select, которая для заданного множества
файловых дескрипторов и сокетов позволяет проверить, пришли ли данные
по ним, и понять, по каким файлам пришли данные.
В MS Windows функция select тоже есть, но она работает немного по-другому,
в ней можно проверять только (сетевые) сокеты и нельзя смешивать,
например, входней поток (клавиатура) и сокеты.
Поэтому мы выбираем другое решение: выполнть чтение в отдельной нити.
Диалог с человеком осуществлятся при этом в основной нити.
Задача по сети, вариант 1 (для нечетных номеров по журналу):
написать программу, которая скачивает html-страницу из интернета.
downloadPage
Командная не используется. Программа должна попросить человека
ввести URL (Universe Resource Locator -- адрес Интернет-страницы)
скачать страницу из Интернета и записать результат в файл
output.html
в текущей директории.
Заголовок ответа сервера записывать в файл не нужно!!!
Только сам текст страницы.
Страница должна быть сохранена в файле OSDrafts2021.html в текущей директории.
Указание: берем программу client.cpp, она должна реализовать следующий диалог:
После установки соединения переслать демону команды
GET http://mech.math.msu.su/~vvb/Dush/OSDrafts2021.html HTTP/1.1
Host: mech.math.msu.su
пууустаая стттттроооока!!!
Пустая строка также передается в конце запроса.
Получаем ответ от сервера:
HTTP/1.1 200 OK
. . .
Content-Length: 6136
. . .
X-Pad: avoid browser bug
Тест html-страницы
(ОН ИДЁТ ПОСЛЕ ПУСТОЙ СТРОКИ, КОТОРОЙ ЗАКАНЧИВАЕТСЯ ЗАГОЛОВОК),
длина страницы указана в строке заголовка Content-Length.
ПЕРЕРЫВ до 14:00
Указание:
Удобне реализовать функцию "Прочесть строку из сокета"
Прототип функции:
bool receiveLine(int s, char* line, int maxLen, int& len);
s -- номер открытого сокета, из которого мы читаем данные;
line -- указатель на начало массива, в который мы записываем
прочитанную строку
maxlen -- максимальная длина строки
len -- выходной параметр, длина прочитанной строки
Функция возвращает true, когда всё нормально, и false,
когда соединение разорвано.
Идея реализации: читаем данные по одному байту, пока не встретим
символ '\n', который означает конец строки. Этот мы выбрасываем
из конца строки, а также при необходимости выбрасываем предыдущий
символ '\r'
Например, сервер передает нам
Hello!\r\n
Функция записывает в массив line
Hello!
а в переменную len число 6.
bool receiveLine(int s, char* line, int maxLen, int& len) {
char buffer[4];
int n = 0;
while (n < maxLen) {
int res = recv(s, buffer, 1, 0);
if (res <= 0) {
return false;
}
if (buffer[0] == '\n')
break;
line[n] = buffer[0];
++n;
}
if (n > 0 && line[n-1] == '\r') {
// Remove CR at the end of line
--n;
}
line[n] = 0;
len = n;
return true;
}
Мы на нескольких простых примерах познакомились с программированием
обмена по протоколу TCP. Давайте рассмотрим пример на программирование
протокола UDP. Здесь мы передаем на поток данных, а отдельные дейтаграмы,
т.е. сообщения ограниченной длины, которые, ак правило, помещаются
внутри одного пакета физического уровня (для TCP/IP надежно использовать
сообщения длиной меньше 1024).
Протокол UDP не требует предварительной установки соединения.
В нем можно сразу передавать и принимать сообщения.
Программа "Групповой чат".
Имеется общий чат-сервер, который принимает сообщение от одного участника
и рассылает это сообщение всем остальным участникам.
Каждый участник, желающий присоединиться к обмену сообщениями, присылает
сообщение серверу, и сервер регистрирует его.
Задача для четных номеров:
Написать программу-клиента для группового чата на основе протокола UDP.
В чате надо посылать все сообщения серверу, а сервер будет пересылать
ваши сообщения остальным участникам.
Чат-клиент должен сначала спросить у человека адрес и порт сервера,
затем какой порт он сам будет использовать. Ну и затем надо
вводить сообщение с клавиатуры, посылать его серверу, а затем принимать
от сервера сообщения, которые он присылает каждому клиенту, в том числе и нам.
Указания:
В чат-клиенте должна быть отдельная нить, которая занимается только
чтением строк из сети (эти строки ей пересылает чат-сервер). Прочитанные строки
добавляются в очередь принятых строк
std::deque<std::string> stringBuffer;
Чат-клиент сначал вводит строку для отсылки серверу:
std::string lineToSend;
std::getline(lineToSend);
res = sendto(
s, lineToSend.data(), int(lineToSend.size()), 0,
(sockaddr*) &serverAddr, sizeof(serverAddr)
);
EnterCriticalSection(&critSect);
while (!stringBuffer.empty()) {
// Печатаем все принятые строки
std::string s = stringBuffer.front();
stringBuffer.pop_front();
std::cout << s << std::endl;
}
LeaveCriticalSection(&critSect);
Строки принимаются и складываются в очередь stringBuffer в отдельной нити:
DWORD WINAPI run(void*) {
char buffer[LINE_MAXLEN + 4];
// cout << "Receiving thread starts..." << endl;
while (!finished) {
sockaddr_in clientAddr;
int addLen = sizeof(clientAddr);
int res = recvfrom(
s, buffer, LINE_MAXLEN, 0,
(sockaddr*) &clientAddr, &addLen
);
// cout << "recvfrom: res = " << res << endl;
buffer[LINE_MAXLEN - 1] = 0;
if (res < 0) {
cout << "Cannot receive: err=" <<
WSAGetLastError() << endl;
break;
}
if (res > 0) {
buffer[res] =0;
// cout << "Received: " << buffer << endl;
// Add a new line to the queue
EnterCriticalSection(&critSect);
std::string s = buffer;
stringBuffer.push_back(s);
LeaveCriticalSection(&critSect);
}
}
cout << "Receive thread is ended" << endl;
return 0;
}