Тема 15. Реализация некоторых подсистем ос Linux

Модель работы

• Основная сущность — процесс

• Один процесс — одна программа

• Порождение нового процесса — fork():

  • Создание копии вызывающего процесса (!)

  • Модификация PCB

  • Возврат управления в процессы

API работы с процессами

• fork()

• waitpid()

• execl(), execv(), execle(), execve()

• exit()

• kill()

Фоновый процесс — демон (daemon)

• Закрыть STDIN, STDOUT, STDERR

• Сбросить обработчики и маску сигналов

• Вызвать fork() (дочерний процесс №1)

• Отключиться от терминала (setsid())

• Ещё раз вызвать fork()

• Завершить дочерний процесс №1

• Подключить STDIN, STDOUT, STDERR к /dev/null

• Сменить umask на 0

• Сменить рабочий каталог на /

• Записать PID в файл

• Понизить привилегии

• Уведомить бывший родительский процесс об успешном запуске

• Завершить родительский процесс

Представление процессов в ядре

• Любой процесс или поток — task

• Все задачи объединены в двусвязный список структур task_struct

Потоки в Linux

• clone(function, stack_ptr, sharing_flags, arg)

• Linux-специфичный вызов

• Новый поток получает PID родителя

• Для различения потоков и процессов используется TID (Task ID)

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

• 3 класса потоков:

  • Реального времени невытесняемые — FIFO

  • Реального времени вытесняемые — RR

  • Разделения времени

• Приоритеты реального времени от 0 до 99

• Приоритеты разделения времени от 100 до 140

• Приоритет — nice (-20 — +19)

• Больше приоритет — больше квант (800/5)

• Динамический приоритет от -5 до +5 на основе эвристики

• По очереди выполнения на каждый процессор системы

• Поддерживается CPU affinity

• Скорость планировщика — О(1)

IPC в Linux

• Сигналы

• Неименованные каналы:

  • popen(), pclose()

  • pipe()

  • dup2()

• Именованные каналы:

  • mkfifo() / mknod()

• Семафоры:

  • semget()

  • semop()

  • semctl()

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

  • shmat()

  • shmdt()

  • shmctl()

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

  • msgget()

  • msgsnd(), msgrcv()

  • msgctl()

• Сокеты (UNIX — AF_UNIX, Berkeley — AF_INET):

  • socket(), socketpair()

  • setsockopt(), getsockopt()

  • send(), recv()

  • sendmsg(), recvmsg(), cmsg()

Алгоритмы планирования

1) FCFS

2) SJF

3) SRT

4) RR

5) HRRN

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

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

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

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

1) First Come First Served / FIFO

Задания выполняются в порядке их поступления в систему

+ Простота

+ Минимальные накладные расходы

2) Shortest Job First

Очередь строится на основе ожидаемого времени выполнения задания

(na+(n-1)b+(n-2)c+...)/n

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

- Необходимость вычисления длины задания

3) Shortest Remaining Time

Очередь строится на основе оставшегося до завершения задачи времени

+ Решение проблемы SJF с неодновременным поступлением процессов

- Необходимость регистрации времени работы процесса

- Увеличение накладных расходов

- Проблема «голодания»

4) Round Robin

FCFS с циклической очередью

Каждому процессу выделяется квант времени на работу

+ Оптимальность в системах разделения времени

- Проблема выбора кванта

5) Highest Response Ratio Next

Очередь строится на основе времени ожидания в очереди и ожидаемого времени выполнения

+ Баланс между быстрыми процессами и ожидающими долгими процессами

+ Нет проблемы «голодания»

- Высокие накладные расходы

Приоритет

Приоритет — искусственный коэффициент, влияющий на место процесса в очереди

Виды приоритетов:

Статические

Динамические

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

Несколько очередей

В каждой очереди находятся процессы одного приоритета

Проблема «голодания»

Схема снижения приоритета

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

Процессорное время гарантированно распределяется между процессами заранее известным образом

Требуется учёт использованного процессорного времени

Критерий построения очереди — соотношение потраченного и обещанного процессорного времени

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

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

Обмен билетами

+Позволяет приблизиться к достижению нужного разделения процессорного времени

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

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

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

Потоки в пространстве пользователя

Время выполнения потока больше кванта

Время выполнения потока меньше кванта

Потоки в пространстве ядра

Задачи ядра

Обработка прерываний

Управление процессами и потоками

Обеспечение межпроцессного взаимодействия

Управление памятью

Управление вводом-выводом

Обеспечение защиты