Operating Systems

План лекции и ссылки

PDF

• Unix и *nix

  Unix - 1969 г.

• системные вызовы

  Стандартизован их формат - POSIX. POSIX-программу можно запустить под Windows, доставив библиотек.

  Стандартизованы библиотеки - ISO C/C++

• strace и ltrace

• Планировщики ЦПУ и ввода-вывода

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

Конспект

ОС - предоставляет среду для приложений, через набор библиотек и системные вызовы. Посмотреть в Linux как это происходит можно через strace (трассировка системных вызовов) и ltrace (трассировка библиотек).

Первый код - на 24:30 (ассемблер с системным вызовом write).

См. файл hello.s

Чтобы скомпилировать, нужно сначала построить объектный файл сначала:

nasm -f elf hello.s

Если команды nasm нет, то ее надо поставить:

sudo aptitude install nasm

Затем слинковать:

ld -s -o hello hello.o

Однако, линковщик ld дает следующие ошибки:

ld: i386 architecture of input file `hello.o' is incompatible with i386:x86-64 output
ld: warning: cannot find entry symbol _start; defaulting to 00000000004000b0

Первая из них:

ld: i386 architecture of input file `hello.o' is incompatible with i386:x86-64 output

Заключается в том, что ликовщик ждет 64-разрядный файл для архитектуры x86-64, а вызов команды

nasm -f elf hello.s

производит объектный файл для 32-разрядной архитектуры. Команда

nasm -hf

покажет доступные форматы вывода утилиты nasm:

valid output formats for -f are (`*' denotes default):

• bin flat-form binary files (e.g. DOS .COM, .SYS) ith Intel hex srec Motorola S-records aout Linux a.out object files aoutb NetBSD/FreeBSD a.out object files coff COFF (i386) object files (e.g. DJGPP for DOS) elf32 ELF32 (i386) object files (e.g. Linux) elf64 ELF64 (x86_64) object files (e.g. Linux) elfx32 ELFX32 (x86_64) object files (e.g. Linux) as86 Linux as86 (bin86 version 0.3) object files obj MS-DOS 16-bit/32-bit OMF object files win32 Microsoft Win32 (i386) object files win64 Microsoft Win64 (x86-64) object files rdf Relocatable Dynamic Object File Format v2.0 ieee IEEE-695 (LADsoft variant) object file format macho32 NeXTstep/OpenStep/Rhapsody/Darwin/MacOS X (i386) object files macho64 NeXTstep/OpenStep/Rhapsody/Darwin/MacOS X (x86_64) object files dbg Trace of all info passed to output stage elf ELF (short name for ELF32) macho MACHO (short name for MACHO32) win WIN (short name for WIN32)

Для 64-разрядной архитектуры, надо выбирать -f elf64:

nasm -f elf64 hello.s

Снова запустим линковшик:

ld -s -o hello hello.o

На выходе получим исполняемый файл hello, и предупреждение:

ld: warning: cannot find entry symbol _start; defaulting to 00000000004000b0

которое происходит из-за того, что линкер ищет точку входа со стандартным именем _start, которой в нашем файле нет. (К слову, файл hello на данный момент можно запустить и он корректно отработает.) Поэтому, чтобы это предупреждение не появлялось, нужно либо в файле hello.s переименовать global start в global _start, либо запустить линковщик с явным указанием точки входа:

ld -e start -s -o hello hello.o

Запустить:

./hello

Программа напечатает

Hello world!

Всю эту свистопляску с архитектурой x86-64 можно было бы решить и по-другому, запустив nasm как и прежде с опцией -f elf (которая на самом деле синоним elf32), но указав ликовщику, чтобы он сгенерировал 32-разрядный исполняемый файл:

nasm -f elf hello.s
ld -m elf_i386 -e start -s -o hello hello.o

Это правильнее, потому что файл hello.s содержит код на 32-разрядном ассемблере (i386), а не на x86-64.

Запустить получившуюся программу в отладчике:

gdb ./hello

В консоли отладчмка написать

break _start

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

Посмотреть дамп объектного файла:

objdump -d hello

то что выведется - это та последовательность байт, которая исполняется.

Что плохо в этом примере? На самом деле, пишут как файле hello.c, а там синтаксис ассемблера AT&T (в файле hello.s - Intel).

Отступление про init scripts. id:5:initdefant, про то, что иногда надо читать исходники ядра.

Pentium: int 80 - медленно. sysenter/sysexit. Вызов этих команд требует специального обрамления.

На самом деле, пишут как в файле hello2.c.

В стандарте POSIX написано, что нужно подключить заголовочный файл unistd.h, тогда будет определена функия write, write - название системного вызова, функция, которая есть в библиотеке языка C. Ну и системный вызов происходит в библиотеке языка C.

Как понять, что происходит при работе программы?

• strace
• ltrace

Написали hello.s, но под отладчиком не смогли выполнить, поскольку не помнили, где у нас входная точка и где поставить точку прерывания.

Как еще можно посмотреть? strace.

strace ./hello

strace показывает каждый системный вызов, который делает программа.

Мы видим, что наш hello вышел с кодом 1, т.к. мы не заботились о коде выхода.

А вызов write, который мы запрограммировали на ассемблере, strace представила как вызов библиотечной функции. Если бы надо было определить аргументы write, можно было бы использовать strace, но можно воспользоваться:

man 2 write

2 - это раздел man - руководство программиста Linux.

man strace

Можно, не имея исходников программы, посмотреть, что программа делает, и если она работает некорректно, то можно посмотреть в каком месте: не хватило прав доступа, нужного файла не оказалось на месте, или вы хотели бы знать, но не знаете, как называется ее конфигурационный файл. strace можно указать ключ -e - выражение для фильтрации тех вызовов, которые надо показать.

strace sh -c 'echo Hello world'

Но это тоже не все вызовы. strace не отследила процесс-потомок. Чтобы показала все, надо добавить ключ -f - follow forks.

strace -f sh -c 'echo Hello world'

Вызовов много, отфильтруем вызовы write:

strace -f -e write sh -c 'echo Hello world'

Для сисадминов обычно интересен вызов open - когда программа пытается что-то открыть.

strace -f -e open sh -c 'echo Hello world'

И оказывается, когда выполнялась эта программа, открывалось как минимум два файла:

open("/etc/ld.so.cache", O_RDONLY|O_CLOEXEC) = 3
# это кеш динамически подгружаемых библиотек

open("/lib/x86_64-linux-gnu/libc.so.6", O_RDONLY|O_CLOEXEC) = 3
# файл с библиотекой языка C

Все это динамически подгружалось этому процессу в память.

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

ltrace - какие библиотечные вызовы делала программа.

ltrace sh -c 'echo Hello world'

Тут мы тоже видим write, но это не системный вызов, а функция-обертка библиотеки языка C. Мы видим функции копирования памяти mempcpy, функцию освобождения памяти free, функцию выделения памяти malloc. Фукция сравнения строк - strcmp - здесь мы видим, как оболочка пыталась определить, что мы с ее помощью хотим запустить:

strcmp("echo", "jobs")                                               = -5
strcmp("echo", "continue")                                           = 2
strcmp("echo", "export")                                             = -21
strcmp("echo", "exec")                                               = -21
strcmp("echo", "eval")                                               = -19
strcmp("echo", "echo")                                               = 0

Интерпретатор команд *nix

Shell: /bin/*sh

Вот как он выглядит в псевдокоде:

while (1) {
    write(1, "$ ", 2);
    readcmd(cmd, args); // parse user input
    if ((pid == fork() == 0) {  // child?
        exec (cmd, args, 0);
    } else if (pid > 0) { // parent?
        wait(0); // wait for child to terminate
    } else {
        perror("fork");
    }
}

write(1, "$ ", 2) - печатает приглашение на экран 1 - это стандартный вывод "$ " - приглашение 2 - длина приглашения

readcmd(cmd, args) - внутренняя команда, читает аргументы,

А дальше - нужно выполнить процесс. делается это через fork() (Этого в частности не было в POSIX-подсистеме NT4).

Процесс в памяти разделяется на два экземпляра, и в каждом fork() вернет разные значения, т.е. в памяти оказываются 2 процесса, исполняющиеся в одной и той же точке, сразу после выхода из fork(). Если fork() вернул 0, то значит мы в дочернем процессе, а если не 0 - то это либо код ошибки (и дочерний процесс не был создан), либо это id дочернего процесса.

Дочерний процесс делает exec, а родительский ждет (системный вызов wait) - если удалось создать потомка. wait - ждет, пока завершится потомок, и возвращает код возврата потомка (в псевдокоде sh оно игнорируется).

Если произошла ошибка, процесс-родитель вызовет perror("fork") - это встроенная в библиотеку C функция.

см. слайды с соглашениями и с работой системного вызова fork() (видео 47:10).

Часто вместо fork используется clone и clone2. По классике, в Unix процесс - это единица исполнения. Если вам нужно что-то обрабатывать параллельно, то вы создаете еще один процесс. Но сейчас так экономят ресурсы, что создают дополнительную нить, и у процесса может быть несколько нитей. Когда нитей несколько, дочерний процесс будет иметь только одну. Это не всегда то, что мы хотим, поэтому придумали новый метод сlone, который в зависимости от своих параметров будет или сохранять все нити или вести себя как fork и оставлять только одну.

После fork, операционная система *nix делает exec. Потому что в памяти два совершенно идентичных процесса. Иногда это хорошо, как в случаях веб-сервера (не тратится время на ожидание). Но если мы исполняем команду, то она должна стать той программой на диске, которой и является. Например, команда ls:

strace -f -o ls.log sh -c 'ls'

И посмотреть, что получилось:

less ls.log

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

wait - ждет завершения одного из потомков. Что будет если потомок завершился, а wait для него не сделали? Будет зомби - запись в таблице процесов, но процесса уже нет, вся его память освобождена. Она содежит информацию о коде завершения процесса, потому нужна. На случай, если родитель "одумается". Если родитель умер, то процесс усыновляется главным процессом init, который может сделать wait, иначе зомби будет болтаться до перезагрузки.

fork/exec разделены еще по следующей причине. ls, когда выполняется, должна выдать список файлов в текущем каталоге. Наследует атрибуты (имя текущего каталога) и открытые файлы родителя. Таким образом вызовом fork происходит наследование всего и вся, а вызовом exec замещается код процесса, который должен исполняться.

В *nix реализована технология copy-on-write. Операция клонирования fork - она фактически память не копирует. Она одни и те же участки памяти, назначает двум процессам сразу, через механизм виртуальной памяти. Может оказаться, что в назначенном таким образом участке памяти лежит переменная, и совершенно не нужно, чтобы она поменялась в родительском процессе. Поэтому операционная система отслеживает вызов записи средствами процессора, и в этот момент дублирует страницу памяти (не по байтам дублирует, а сразу страницу - 4 кб).

read/write (видео 54:20) - аргументы:

• номер файла

• указатель на буфер, где строка, которую надо прочитать/записать

• число байтов, которые можно прочитать, или нужно записать

• возвращает число байтов

ОС делает абстракцию оборудования следующим образом (видео 54:44):

1. Виртуализовать ресурс - память и процессор. Процесс думает, что вся память в его распоряжении. Он спокойно пишет в любой адрес памяти, и это никак не затрагивает другие процессы, их память. Процесс не заботится о других процессах, чтобы они выполнялись, это делает ОС. Когда процесс делает системный вызов, он останавливается! Но если даже он их не делает, ОС все равно может остановить процесс.
2. Windows, *nix. Windows 3.1 требовала, чтобы приложения обязательно сами вызывали систему, и многозадачность была кооперативная.

Как правило, прерывание происходит просто по таймеру, и специальная нить в ядре - "планировщик" - решает, надо отобрать сейчас процессор у процесса, или нет. Когда процессу пришло управление обратно, для него это выглядит как просто скачок во времени. Посмотреть за всем этим происходящим можно следующим образом (видео 57:15)

vmstat

Если ей не давать аргументов, она выведет одну строчку. Столбец cs - это "переключений контекста в секунду". Это среднее значение с момента включения системы. Может быть неправдоподобно маленьким, если система спала.

vmstat 4 4

Выведет четыре отсчета по 4 секунды.

Команда

man vmstat

даст справку по остальным столбцам.

Служебная файловая система о процессах: /proc

Файлы внутри /proc - виртуальные, они нигде на диске не хранятся. Это представление в виде файлов информации о ядре.

Команда

cat /proc/1/status

выведет информацию о состоянии первого процесса (init). Интересны последние две строчки:

voluntary_ctxt_switches:    1289
nonvoluntary_ctxt_switches: 17772

добровольных переключений контекста / принудительных переключений контекста

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

Можно сослаться на самого себя:

сat /proc/self/maps

В данном примере, сat выведет информацию о своем (cat) процессе. proc/self/maps покажет, как в данном случае ядро распорядилось памятью процесса cat. Видно, что по адресам таким-то, в память спроецирован такой-то файл, и память доступна для чтения или исполнения. s в разрешениях значит, что это память shared, т.е. если другой процесс загрузит этот файл в память, она не будет дважды потребляться. Будут эти же адреса, просто спроецированные в адресное пространство другого процесса. Или stack процесса, который должен быть досупен по записи - у него будет буква w в разрешениях.

Команда ps

количество выводимой информации зависит от версии Linux

ps

покажет процессы этого терминала.

ps aux | head

Столбец STAT - состояние процесса. В man ps написано, какие состояния у процесса могут быть.

S - означает "спит". Байка перестроечного времени - масло и муж. Не все состояния на самом деле есть.

Виртуализация памяти

процессу доступно адресное пространство 2^32 и он им монопольно распоряжается. За счет того, что процессор может изолировать адресные пространства процессов. На самом деле, процессу доступно не 4 Гб, а меньше, потому что ядру надо хранить свои структуры данных там, чтобы при системных вызовах не происходило переключение контекста с сохранением флагов и т.п. Поэтому процессам доступно 2-3 Гб.

Виртуализация памяти (видео 1:03:00):

• на диск
• сегменты x86
• страничная организация

Вся физическая память бъется на блоки (страницы) размером 4 кб, а операционная система отслеживает, какой блок какому процессу привязан. Процесс думает что у него непрерывное адресное пространство. На самом деле оно состоит из этих разрозненных кусков, которые центральным процессором собираются в единую картину.

cat /proc/swaps

покажет файлы подкачки.

swapon -s

то же самое.

Команда

free

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

free -l

покажет что память адресуется по-разному, есть верхняя, есть нижняя (ее внутреннее устройство)

Подходы к построению систем

• монолитное (нельзя изменить конфигурацию после загрузки)
• гибридное (модульное)
• микроядро (minix) - все компоненты можно подгружать/выгружать
• экзоядро - программа имеет прямой доступ к оборудованию, часть функционала реализуют сами.

Многозадачность

• кооперативная
• вытесняющая (preemptive) - система умеет силой отбирать управление у процесса)

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

• Долгосрочная - batch, есть в Linux, контролируется загрузка процессора
• Среднесрочная - процесс убивается при нехватке памяти
• краткосрочная - планировщик в ядре

Про batch

Команды at, batch, atq - позволяют запланировать задачу на определенное время.

batch

В появившейся консоли batch надо ввести желаемую команду:

xclock -update 1

Но у него переменной не оказалось, и batch пожаловался:

mutt

"Не могу открыть дисплей (не знает какой)". Попробуем снова в консоли batch:

DISPLAY=:0
xclock -update 1

pgrep xclock

Так мы увидели, что часы он так и не запустил, однако на этот раз никаких сообщений об ошибках нет. Другой пример: в консоли batch пишем:

ls -lR > /tmp/ls-lR.1

Теперь посмотрим список задач:

atq

batch принимает решение, что сейчас запустить, раз в минуту. Поэтому задача может некоторое время висеть в очереди, и не быть выполненной. Запланируем еще задачу (консоль batch):

tar czf /tmp/etc.tgz /etc

Можно поотслеживать, появляются ли запланированные файлы, с помощью watch:

watch ls /tmp/*

По умолчанию watch перезапускает указанную команду каждые 2 секунды.

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

watch ls /tmp/(все что найдено до выполнения watch)

Чтобы это работало как надо, надо звездочку взять в кавычки, или использовать обратный слэш перед звездочкой.

man batch

тут написано, когда задача не будет выполняться: когда средняя загрузка падает ниже 1,5. Посмотреть текущую загрузку можно командой:

uptime

Средняя загрузка считается, исходя из количества процессов, находящихся в статусе Run:

ps aux | grep R

только R будет встречаться в разных местах, не только в статусах. R означает, что процесс готов выполнять процессорное время. Т.е. число дoad average - это число процессов в очереди. Три числа там потому, что средняя загрузка рассчитывается за 1 мин, 5 мин и 15 мин (см. man uptime).

Нагрузим систему:

sh -c `while true ; do true; done` &

посмотреть, что процессорное время потребляется, можно командой top. Можно укоротить запись:

sh -c `while : ; do : ; done` &

И сейчас в batch можно ставить задачи, и они не будут выполняться, пока загрузка больше 1,5. В batch можно положить сколько угодно задач, до максимального количества процессов. Если load average больше 100, система будет медленная, зависит от процессора и их количества. top сверху показывает процессы, которые больше всех потребляют процессорное время. Отстрелим процессы: нажать 'k' в top - это встроенная в top команда kill. kill - это системный вызов в ядре - он получает параметром номер процесса и номер сигнала. номер сигнала 15 - означает TERM - нормальное завершение процесса, он может такой сигнал обработать. 9 - означает KILL - у процесса нет шансов узнать, что его завершают, он завершится принудительно.

kill -9 20431

-9 - сигнал KILL, 20431 - номер процесса. Также нужно учитывать, от чьего имени запущен процесс. Только root может завершать чужие процессы, или процесс, наделенный специальными привилегиями.

Можно задать конкретный load average, при котором будут срабатывать задачи - это делается при вызове демона atd - который отвечает за запуск задач.

man atd

и увидим, что это ключ -l.

batch бывает полезен - можно отдать команду на reboot или shutdown удаленной системе, чтобы успеть отключиться. А если систем много, и перезагрузить нужно много машин, в цикле, чтобы цикл не зависал - ставят задачу перезагрузки в batch.

Алгоритмы планировщика CPU

• FIFO/FCFS - первый вошел-первый вышел. (first come - first served)
• SJF (shortest job first) - если планировщик может предсказать сколько времени нужно процессу. планировщики замеряют время, которое процесс проводит между его прерыванием планировщиком или системным вызовом.
• приоритетное планирование (ОСРВ) - когда у процесса жестко указан приоритет, и нить или процесс надо выполнять жестко с этим приоритетом. байка про ibm-систему, которую запустили в 70-х, а в 80-х выключили для обслуживания. там были процессы, запущенные в 70-х, но которые ни разу не исполнялись.
• round-robin - способ подписывать смертный приговор - подписи ставились по кругу, чтобы не было известно, кто первый подписал. планировщик обслуживает процессы по кругу.
• многоуровневые очереди с обратной связью (CFQ). многоуровневость заключается в том, что процессы классифицируется, по времени исполнения между прерываниями, и в заисимости от того, как быстро процесс возвращает управление, он попадает в ту или иную очередь. Дальше планировщик каждую очередь обрабатывает отдельно. У него есть дерево раскрашенное.

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

Память

• распределение. Процесс попросил - дай блок по такому-то адресу, и операционная система ответила, что я выделила тебе такой блок. Есть посредник в библиотеке языка C, который занимается управлением памятью. В конечном итоге, он вызывает операционную систему.
• защита - заключается в том, что не вся память должна быть доступна для записи. т.е. если процесс запустился, то он не должен писать в те свои области памяти, которые хранят инструкции, т.е. модифицировать свой код на ходу. Иногда это нужно, как правило нет. И адреса памяти могут быть помечены на чтение, запись, исполнение. В служебной файловой системе /proc/self/maps можно подсмотреть как ядро распорядилось памятью текущего процесса. Если процесс обратится к адресам, которые ему операционная система не выделяла, сработает защита, в ядре произойдет исключение, процесс будет прерван (segmentation fault). Ошибка шины (11 сигнал) или ошибка сегментации. (или мог попытаться записать что-то по адресу, куда запись запрещена).
• разделение
• логическая организация (сегменты) - в intel-процах неинтересна, сегменты каждый делается по 4 гб и указывают на одни и те же области памяти (это делается для того, чтобы задействовать весь объем памяти). Поэтому сегментация не ипользуется в современных Linux или Windows, используется плоская модель памяти.
• физическая организация (подкачка) - когда процесс обращается по какому-то адресу памяти - это не настоящий адрес, а адрес виртуальной памяти. Превращение в реальный адрес происходит через процессор, в котором есть таблица, где записано, какому виртуальному адресу какой физический соответствует (страница 4 кб).

Планирование ввода/вывода

В зависимости от сценария запуска Linux, можно выбрать планировщик (виртуалка - noop, бд - deadline)

• RSS - random - практически не встречается
• FIFO - не встречается
• LIFO - почти не используется
• SCAN - встречается в ядре Windows. Пытается прочитать данные по ходу движения головок туда-сюда. NCQ, AHCI - поэтому нет смысла оптимизировать это в планировщике ввода-вывода.
• NOOP - за нашим планировщиком есть еще планировщик, например RAID, или хост виртуальной машины
• Anticipator - должен угадывать, какие данные нам еще понадобятся. следующие данные за прочитанными могут понадобиться и прочитать чуть больше.
• Deadline - deadline - отдает весь ввод вывод одному процессу, а затем отнимает - и следующему - подходит для БД-сервера.
• CFQ - по умолчанию. следит, чтобы каждому процессу досталось равное количество времени работы с диском.

Эти планировщики можно указывать.

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

У ядра есть своя память.

• кеш-буфер - Всю незанятую память по умолчанию ядро использует для этого. Если какой-то блок однажды был с диска прочитан, он помещается в кеш-буфер. Вся физ. память таким образом будет израсходована, и только когда памяти не будет хватать, ядро будет уменьшать кеш-буфер, выбрасывая из него, по определенному алгоритму, ненужные (например, самые старые) данные.
• промахи страниц (жесткие, мягкие)
• Алгоритмы виртуальной памяти: LRU, опережающая подгрузка ...

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

Производительность в числах

Operation	Time (nsec)
L1 cache reference	0.5
Branch mispredict	5
L2 cache reference	7
Mutex lock/unlock	25
Main memory reference	100
System call overhead	400
Compress 1KB bytes with Zippy	3,000
Context switch between processes	3,000
Send 2K bytes over 1 Gbps network	20,000
fork() (statically-linked binary)	70,000
fork() (dynamically-linked binary)	160,000
Read 1MB sequentially from memory	250,000
Roundtrip within same datacenter	500,000
Disk seek	10,000,000
Read 1MB sequentially from disk	20,000,000
Send packet CA -> Netherlands -> CA	150,000,000

Дополнительные литература и вопросы

(видео 1:46:00)

• Курс на интуите intuit.ru - курс операционные системы.

• mit.edu - Operating System Engeneering (номер - 6282) не используется линукс, используется собственная операционка Xv6 - воспроизводит шестую редакцию Unix. Методичка к ней - PDF-файл, где перечислены все строки. Также - материалы курса, слайды и заметки. лицензия - CC. Автор курса смотрит на операционку не как пользователь, а как инженер, который может ее изменить. Автор занимается параллельными ОС - многоядерными (если ядро системы одно в многопроцессорной системе, оно становится узким местом со своим планировщииком).

• какой-то финский университет тоже предлагает курс, но непонятна лицензия

• оптимизация. malloc из BSD. замена int80 на sysenter. Планировщик BFS - работает в Андроид