Динамические структуры данных

Эл. однонаправленного списка	Эл. двунаправленного списка	Эл. бинарного дерева
struct Node1 { double data; struct Node1 *next;};	struct Node2 { int num; struct Node2 *next; struct Node2 *prev;};	struct NodeTree {char name[10]; struct Node2 *llink; struct Node2 *rlink;};

Библиотечные функции для динамического выделения и освобождения памяти:

#include <stdlib.h>

void *malloc (size_t size); - Выделяет указанное аргументом size число байтов

void *calloc(size_t nelem, size_t elsize); - выделяет память для указанного аргументом nelem числа объектов, размер которых elsize.

void free(void *ptr); - освобождает ранее выделенную память, указатель на которую передается через аргумент ptr.

8. Принципы построения ОС. Архитектура ОС.

ОС – это комплекс программ, обеспечивающий контроль за существованием, распределением и использованием ресурсов ВС.

Основные принципы построения ОС:

1) модульность

2) особого режима работы

3) виртуализации

4) мобильности (переносимости)

5) совместимости

6) генерируемости

7) открытости (расширяемости)

8) обеспечения безопасности вычислений

Архитектура ОС

Ядро – модули, выполняющие основные внутрисистемные функции ОС и постоянно находящиеся в ОП. Эти функции недоступны для приложений. Другой класс функций ядра служит для поддержки приложений, создавая для них прикладную программную среду (API).

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

см. Лекцию №7 «Основные структуры ОС»

9. Управление процессами. Понятие процесса. Типы процессов. Жизненный цикл процесса.

10. Управление процессами. Понятие процесса. Контекст процесса.

«Программа» - упорядоченная последовательность действий в виде машинных команд.

«Задание» - совокупность программы, набора команд языка управления заданиями, необходимых для ее выполнения, и входных данных.

Процесс (или по-другому, задача) – абстракция, описывающая выполняющуюся программу.

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

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

Выводы:

1) все, что выполняется в ВС (даже определенные части ОС), организовано как набор процессов;

2) на однопроцессорной компьютерной системе в каждый момент времени может исполняться только один процесс;

3) во всех современных ВС поддерживается режим мультипрограммирования, при котором на одном процессоре попеременно выполняется сразу несколько программ (пока один процесс выполняется, остальные ждут своей очереди на получение процессора);

4) в МВС псевдопараллельная обработка нескольких процессоров достигается с помощью переключения процессора с одного процесса на другой.

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

Контекст процесса

Контекст процесса делиться на 3 части: 1) пользовательский контекст; 2) Регистровый контекст; 3)Контекст системного уровня.

1) – это содержимое пользовательского адресного пространства (т.е. содержимое сегментов программного кода, данных, стека, разделяемых сегментов и файлов, отображаемых в виртуальную память).

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

3) – это структуры данных ядра ОС, связанные с этим процессом.

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

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

Некоторые типы процессов.

«Полновесные процессы» (процессы) - это процессы, выполняющиеся внутри защищенных участков памяти операционной системы, то есть имеющие собственные виртуальные адресные пространства для статических и динамических данных.

«Легковесные процессы» (нити или потоки – thread). Нити существуют в рамках одного процесса и выполняются в квазиапараллельном режиме. Все нити одного процесса всегда решают общую задачу одного пользователя. Таким образом, аппарат нитей используется для более быстрого решения задачи путем ее распараллеливания.

Обобщая сказанное, отметим, что понятие процесса в любой ОС включает в себя:

· исполняемый код

· собственное виртуальное адресное пространство

· совокупность ресурсов, выделенных данному процессу

· хотя бы одну исполняемую нить

Жизненный цикл процесса

ЖЦП в ВС – время с момента создания до момента завершения выполнения процесса.

Основные состояния процесса:

1. Рождение – состояние процесса, когда он уже создан, но не готов к запуску, при этом создаются контекст и дескриптор; загружается кодовый сегмент процесса в оперативную память или в область свопинга, процесс помещается в очередь готовых пр.

2. Исполнение – активное состояние процесса, во время которого процесс обладает всеми необходимыми ресурсами и непосредственно выполняется процессором;

3. Ожидание – пассивное состояние процесса, процесс заблокирован, он не может выполняться по своим внутренним причинам, т.е. он ждет осуществления некоторого события, например, завершения операции ввода-вывода, получения сообщения от другого процесса, освобождения какого-либо необходимого ему ресурса;

4. Готовность – также пассивное состояние процесса: процесс имеет все требуемые для него ресурсы, он готов выполняться, однако процессор занят выполнением другого процесса;

5. Завершение – конечное состояние в ЖЦП, процесс выгружается из памяти и разрушаются все структуры данных, связанные с ним.

11. Взаимодействующие процессы. Методы реализации взаимного исключения.

12. Планирование процессов. Цели и задачи. Классификация алгоритмов.

Планирование процессов:

Основные задачи:

· определение момента времени для смены выполняемого процесса

· выбор процесса на выполнение из очереди готовых процессов

· переключение контекстов «старого» и «нового» процессов

Цели планирования:

1) Справедливость

2) Эффективность

3) Сокращение времени выполнения

4) Сокращение времени ожидания

5) Сокращение времени пребывания

Часть ОС, которая занимается планированием процессов – планировщик, а используемые алгоритмы – алгоритмы планирования.

Алгоритмы планирования зависят от типа ВС

Категории ВС:

в пакетных системах

в интерактивных системах

в системах реального времени

Свойства:

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

2. минимальные накладные расходы

3. сбалансированная загрузка ресурсов ВС

4. масштабируемость: алгоритмы должны сохранять работоспособность при увеличении нагрузки

Классификация алгоритмов:

1) Вытесняющие

2) Не вытесняющие

В не вытесняющих АП переключение происходит по инициативе самой задачи, в вытесняющих – по прошествии выделенного кванта времени по инициативе ОС.

Бес приоритетные АП: запускается процесс и выполняется до тех пор, пока не заблокируется либо добровольно не освободит ЦП

Приоритетные АП: запускается процесс и выполняется до истечения заданного времени.

13. Планирование процессов. Планирование в пакетных системах

1) Первым пришел-первым обслужен

2) Сначала самое короткое задание

3) Приоритет наименьшему времени выполнения

Первым пришел-первым обслужен или First Come First Served (FCFS):

Не вытесняющее планирование, задачи обслуживаются «в порядке очереди», в порядке их появления. Те задачи, которые были заблокированы, после перехода в состояние готовности ставятся в очередь.

Здесь 2 варианта:

1) ставить разблокированную задачу в конец очереди готовых задач

2) использовать две очереди: очередь новых задач, очередь разблокированных задач.

Преимущество: простота реализации

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

Сначала самое короткое задание или Shortest-Job-First (SJF)

Предполагается, что время выполнения каждого задания известно заранее

Недостаток: Задания, которым требовалось немного времени для своего завершения, вынуждены ожидать процессор наравне с длительными работами.

Приоритет наименьшему времени выполнения или Shortes Remainin Time (SRT)

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

Дисциплины FCFS, SJN, SRT относятся к не вытесняющим.

13. Планирование процессов. Планирование в интерактивных системах.

Цель: обеспечить приемлемое время реакции системы и равенство в обслуживании

1) Циклическое планирование

2) Приоритетное планирование

3) Выбор следующим самого короткого процесса

4) Гарантированное планирование

5) Лотерейное планирование

6) Справедливое планирование

Циклическое планирование или Round Robin (RR)

Каждая задача получает процессорное время порциями или квантами времени (time slice) q. По истечении кванта задача снимается с процессора и ставится в конец очереди задач, готовых к выполнению.

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

Приоритетное планирование

Каждому процессу присваивается приоритет. Запускается тот процесс, который находится в состоянии готовности и имеет самый высокий приоритет.

Реализация приоритетного обслуживания делается за счет организации нескольких очередей.

Выбор следующим самого короткого процесса.

Подход – аналог подхода SJF в пакетных системах. Но в интерактивных системах проблема: как определить какое задание самое короткое? Используется не само значение времени выполнения, а его оценка.

Гарантированное планирование

Если в системе имеется n процессов, каждому из них гарантируется 1/n часть времени ЦП.

Лотерейное планирование

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

Справедливое планирование:

Понятие справедливости. К примеру, ресурс предоставляется не процессу, а пользователю. Каждый из n пользователей должен получить 1/n часть времени ресурса независимо от количества процессов.

15. Планирование процессов. Планирование в системах реального времени.

16. Понятие процесса в ОС UNIX. Типы процессов. Контекст процесса.

В ОС UNIX процесс можно определить, с одной стороны, как единицу управления и потребления ресурсов, с другой стороны – как объект, зарегистрированный в таблице процессов ядра UNIX.

Типы процессов: а) системные процессы; б) демоны; в) прикладные процессы.

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

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

К прикладным процессам относятся все остальные процессы, выполняющиеся в системе.

Это процессы, порожденные в рамках пользовательского сеанса работы. Время жизни ограничено сеансом работы пользователя.

Каждому процессу в UNIX сопоставлено целое число – идентификатор процесса (PID), число в диапазоне от 0 до N, характеризующего максимально возможное количество одновременно существующих процессов. PID = 0 ассоциируется я ядром ОС, PID = 1 – процесс init.

Контекст процесса

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

С точки зрения логической структуры контекст процесса в UNIX состоит из:

· пользовательской составляющей или тела процесса (пользовательский контекст)

· аппаратной составляющей (аппаратный контекст)

· системной составляющей (системный контекст)

Объединение аппаратной составляющей и системной составляющей – общесистемная составляющая контекста.

17. Аппарат системных вызовов в ОС UNIX. Порождение новых процессов.

Для порождения новых процессов в UNIX существует единая схема, с помощью которой создаются все процессы, кроме процессов с PID=0 и PID=1.

Для создания нового процесса в ОС UNIX используется системный вызов fork().

#include <sys/types.h>

#include <unistd.h>

pid_t fork(void);

При этом в таблицу процессов заносится новая запись, и порожденный процесс получает свой PID.

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

Не наследуется порожденным процессом:

· PID

· PPID

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

Каждый из процессов – родительский и порожденный – получив управление, продолжат выполнение с одной и той же инструкции одной и той же программы, а именно с той точки, где происходит возврат из системного вызова fork().

Вызов fork() в случае удачного завершения возращает сыновнему процессу значение 0, а родительскому PID порожденного процесса.

18. Аппарат системных вызовов в ОС UNIX. Механизм замены тела процесса.

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

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

19. Аппарат системных вызовов в ОС UNIX. Использование схемы fork()-exec().

механизм fork-and-exec переключает старые команды на новые, пока окружение, в котором выполняется новая программа остается таким же, в том числе конфигурация устройств ввода/вывода, переменные окружения и приоритет. Этот механизм используется для создания всех процессов UNIX. Даже первый процесс, init, с процессорным ID 1, порождается во время загрузки в так называемой процедуре bootstrapping (начальной загрузки).

Эта схема иллюстрирует механизм fork-and-exec. ID процесса изменяется после процедуры порождения:

20.Аппарат системных вызовов в OC UNIX. Завершение процесса.

Когда процесс завершается нормально (его не завершили или иным способом неожиданно не прервали), программа возвращает его exit status (статус выхода) родителю. Этот exit status является числом, возвращаемым программой, предоставившей результаты своего выполнения. Система передачи информации об исполненной работе берет свое начало с языка программирования Си, на котором был написан UNIX.

Коды возврата могут быть интерпретированы родителем или скриптами. Значения кодов возврата специфичны для программ. Эту информацию обычно можно найти в man-страницах указанной программы, например команда grep возвращает -1, если не найдено совпадений, при этом в строке может быть выведено сообщение: "Нет найденных файлов". Другим примером является встроенная команда Bash true, которая не делает ничего, кроме возвращения статуса выхода 0, что означает успех.

21. Управление процессами. Жизненный цикл процесса в OС UNIX.

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

После выполнения системного вызова fork новый процесс обычно запускает новую программу с помощью одного из системных вызовов семейства exec. Все вызовы семейства exec производят приблизительно одинаковые действия: они замещают сегмент кода процесса и устанавливают сегменты данных и стека в исходное состояние. Формы вызовов exec отличаются только способами указания аргументов командной строки и переменных среды, передаваемых новой программе.

Программа init играет и другую важную роль в управлении процессами. Когда процесс завершается, он вызывает функцию _exit(), чтобы уведомить ядро о своей готовности прекратить работу. В качестве параметра функции _exit() передается код завершения — целое число, указывающее на причину останова процесса. По соглашению нулевой код завершения означает, что процесс окончился успешно.

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

22. Взаимодействие процессов в ОС UNIX. Классификация методов.

Сигналы – асинхронное уведомление процесса о каком-либо событии. Когда сигнал послан процессу, ОС прерывает выполнение процесса. Если процесс установил собственный обработчик сигнала, ОС запускает этот обработчик, передав ему информацию о сигнале. Если процесс не установил обработчик, то выполняется обработчик по умолчанию.

Каналы – псевдофайл, в который один процесс пишет, а другой читает

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

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

Разделяемая память – В обычной ситуации обмен информацией между процессами проходит через ядро. Техника разделяемой памяти позволяет осуществить обмен информацией не через ядро, а используя некоторую часть виртуального адресного пространства, куда помещаются и откуда считываются данные. После создания разделяемого сегмента памяти любой из пользовательских процессов может подсоединить его к своему собственному виртуальному пространству и работать с ним, как с обычным сегментом памяти. Недостатком такого обмена является отсутствие каких бы то ни было средств синхронизации.

Семафоры – переменные для подсчета сигналов запуска, сохраняемых на будущее.

23. Взаимодействие процессов в ОС UNIX. Неименованные каналы.

24. Взаимодействие процессов в ОС UNIX. Именованные каналы.

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

Например, можно создать канал и настроить gzip на сжатие того, что туда попадает:

mkfile pipe

gzip -9 –c <pipe >out

Параллельно, в другом процессе можно выполнить:
cat file > pipe

Что приведет к сжатию передаваемых данных gzip-ом.

25. Взаимодействие процессов в ОС UNIX. Сигналы, надежные сигналы.

Сигнал - асинхронное уведомление процесса о каком-либо событии. Когда сигнал послан процессу, операционная система прерывает выполнение процесса. Если процесс установил собственный обработчик сигнала, операционная система запускает этот обработчик, передав ему информацию о сигнале. Если процесс не установил обработчик, то выполняется обработчик по умолчанию.

Названия сигналов «SIG…» являются числовыми константами (макроопределениями Си) со значениями, определяемыми в заголовочном файле signal.h. Числовые значения сигналов могут меняться от системы к системе, хотя основная их часть имеет в разных системах одни и те же значения. Утилита kill позволяет задавать сигнал как числом, так и символьным обозначением.

Сигналы посылаются:

§ с терминала, нажатием специальных клавиш или комбинаций (например, нажатие Ctrl-C генерирует SIGINT, а Ctrl-Z SIGTSTP);

§ ядром системы:

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

§ ошибочных системных вызовах;

§ для информирования о событиях ввода-вывода;

§ одним процессом другому (или самому себе), с помощью системного вызоваkill(), в том числе:

§ из шелла, утилитой /bin/kill.

Сигналы не могут быть посланы завершившемуся процессу, находящемуся в состоянии «зомби».

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

26. Взаимодействие процессов в ОС UNIX. System V IPC.

- Разделяемая память

- Семафоры

- Очереди сообщений

get() – используется для создания средства IPC, возвращает идентификатор средства.

ctl() – Определяет состояние, устанавливает различные опции и права доступа или удаляет идентификатор IPC

op() – Выполняет операции над средством IPC

Общие свойства средств IPC:

- Средства могут быть созданы за любое время до их использования

- В момент создания для средства IPC устанавливаются собственность и права доступа, которые могут позднее быть изменены.

- Содержимое средства IPC может сохраняться после того, как все использовавшие его процессы завершились.

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

- Средства IPC теряются при перезагрузке системы.

get() – основные сведения: Создатель задает IPC_CREAT и права доступа в параметре flg; можно дополнительно задать IPC_EXCL; IPC_PRIVATE предоставляет приватный ключ

ctl – основные сведения: IPC_STAT – информация о состоянии; IPC_SET – изменяет хозяина и права доступа; IPC_RMID – удаляет средство.

ipcs() – Состояние всех существующих в данный момент средств IPC.

ipcrm() – удаление средства IPC.

Очереди сообщений:

msgget – создать очередь или получить доступ к ней

msgctl – определить состояние очереди; изменить хозяина или права доступа; изменить максимальный размер очереди или удалить ее

msgop – послать (msgsnd) или получить (msgrcv) сообщение

Семафоры:

Разделяемое короткое без знаковое целое значение.

Используется для: блокировки; управление доступом к ресурсам; подсчета; разделения небольшого без знакового значения между процессами.

Разделяемая память

shmget – создать или получить доступ к сегменту памяти

shmctl – определить состояние сегмента; изменить хозяина/группу сегмента и права доступа; удалить сегмент

shmop – присоединить (shmat) сегмент к области данных процесса, или отсоединить его (shmdt)

27. Взаимодействие процессов в ОС UNIX. Сокеты, определение, основные типы. Системные вызовы.

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

socket() – создание сокета

connect() – его привязка к адресу и порту, установка соединения

write() – посылка запроса

read() – прием ответа

close() – закрытие сокета.

bind() – привязка сокета к адресу

listen() – перевод сокета в пассивный режим

accept() – прием полностью установленного соединения

int socket(int domain, int type, int protocol); domain – определяет семейство протоколов. type – тип сокета; protocol – протокол для данного типа сокета.

int connect(int sockfd, struct sockaddr *serv_addr, socklen_t addrlen); sockfd – дескриптор сокета; *serv_addr – указатель на структуру, содержащую инфу о сокете; addrlen – размер этой структуры.

Структура sockaddr:

struct sockaddr{

unsigned short sa_family;

char sa_data[14];

};

int close(int sockfd); - Закрывает дескриптор сокет, тем самым, завершая соединение.

28. Взаимодействие процессов в ОС UNIX. Сокеты. Общая схема работы с сокетами без предварительного установления соединения.

29. Взаимодействие процессов в ОС UNIX. Сокеты. Общая схема работы с сокетами c предварительным установлением соединения.

30. Взаимодействие процессов в ОС UNIX. Среда MPI, индивидуальные и коллективные коммуникации.