Примечание. Авторы рекомендуют читать книгу вместе с исходным текстом xv6. Авторы подготовили и лабораторные работы по xv6.
Операционная система делит компьютер между несколькими программами так, что программы выполняются одновременно. Операционная система абстрагирует работу с оборудованием - программу не заботит, с каким типом диска работает компьютер. Операционная система позволяет программам обмениваться данными и работать совместно.
Операционная система определяет интерфейс, с которым работают программы. Хороший интерфейс спроектировать трудно. Примитивный интерфейс проще реализовать, но часто программы хотят сложных функций. Интерфейс должен комбинировать примитивные механизмы для создания сложных функций.
Эта книга рассказывает о принципах работы операционных систем на примере xv6. Операционная система xv6 реализует базовый интерфейс, который Кен Томпсон и Деннис Ритчи предложили в операционной системе Unix, и подражает внутреннему устройству Unix. Комбинации простейших механизмов Unix дают удивительную свободу действий. Современные операционные системы признали успех Unix и реализуют похожие интерфейсы - BSD, Linux, macOS, Solaris, и даже Microsoft Windows. Изучение xv6 поможет понять работу и других операционных систем.
Ядро xv6 - специальная программа, что предоставляет службы операционной системы другим программам. Программа, когда работает, зовется процессом. Каждый процесс владеет собственной памятью, которая хранит инструкции, данные и стек процесса. Инструкции - вычисления, что выполняет программа. Данные - переменные, с которыми инструкции работают. Стек хранит вызовы процедур, которые программа выполняет. На компьютере работают несколько процессов, но только одно ядро.
Процесс выполняет системный вызов, чтобы воспользоваться услугами ядра. Системный вызов передает управление ядру, ядро работает и возвращает управление - так процесс переключается между пространствами пользователя и ядра.
Ядро защищает себя от процессов пользователя с помощью механизмов центрального процессора. Ядро работает с оборудованием, а пользовательские процессы - нет. Пользовательский процесс выполняет системный вызов, процессор повышает привилегии и выполняет код ядра.
Набор системных вызовов - интерфейс ядра, доступный пользовательским программам. Ядро xv6 предоставляет часть системных вызовов из тех, что предоставляет ядро Unix.
Системный вызов | Описание |
---|---|
int fork() | Создает новый процесс, возвращает PID дочернего процесса. |
int exit(int status) | Завершает текущий процесс, передает status вызову wait(), не возвращает управление программе. |
int wait(int *status) | Ожидает завершения дочернего процесса, пишет код завершения в *status, возвращает PID завершенного процесса. |
int kill(int pid) | Завершает процесс с указанным PID. Возвращает 0 в случае успеха и -1 в случае ошибки. |
int getpid() | Возвращает PID текущего процесса. |
int sleep(int n) | Приостанавливает процесс на n тактов процессора. |
int exec(char *file, char *argv[]) | Загружает программу из файла file и выполняет с аргументами argv. Возвращает управление только в случае ошибки. |
char *sbrk(int n) | Расширяет память процесса на n байтов. Возвращает адрес начала новой памяти. |
int open(char *file, int flags) | Открывает файл. flags означает разрешения на чтение и запись. Возвращает файловый дескриптор. |
int write(int fd, char *buf, int n) | Пишет n байтов из buf в файл с дескриптором fd. Возвращает число записанных байтов. |
int read(int fd, char *buf, int n) | Читает n байтов из файла в buf. Возвращает число прочитанных байтов или 0, если достигнут конец файла. |
int close(int fd) | Освобождает открытый файловый дескриптор fd. |
int dup(int fd) | Возвращает новый файловый дескриптор, что ссылается на тот же файл, что и fd. |
int pipe(int p[]) | Создает канал, помещает файловые дескрипторы чтения и записи в p[0] и p[1]. |
int chdir(char *dir) | Меняет текущую директорию. |
int mkdir(char *dir) | Создает новую директорию. |
int mknod(char *file, int, int) | Создает файл устройства. |
int fstat(int fd, struct stat *st) | Пишет информацию о файле в *st. |
int stat(char *file, struct stat *st) | Пишет информацию о файле в *st. |
int link(char *file1, char *file2) | Создает новое имя file2 для файла file1. |
int unlink(char *file) | Удаляет файл. |
Дальнейший текст описывает службы xv6 - процессы, память, дескрипторы файлов, каналы и файловую систему. Примеры кода показывают, как программа shell
пользуется службами ядра, и как тщательно спроектированы системные вызовы.
Программа shell
- интерфейс командной строки Unix. Shell
читает и выполняет команды пользователя. Shell
- пользовательская программа, а не часть ядра - в этом мощь системных вызовов. Shell
легко заменить другой программой - современные Unix-системы предлагают несколько таких программ с различным интерфейсом и возможностями автоматизации работы. Shell
в xv6 реализует базовые идеи Bourne shell. Код программы shell
- в user/sh.c
.
Процессы и память
Каждый процесс xv6 владеет памятью в пространстве пользователя. Память процесса состоит из кода, данных и стека. Ядро xv6 делит время работы процессоров между процессами. Xv6 сохраняет регистры процессора, пока процесс не выполняется, и восстанавливает регистры, когда приступит к выполнению процесса. Ядро назначает каждому процессу идентификатор PID и распоряжается состоянием каждого процесса.
Процесс запускает новый процесс вызовом fork
. Вызов fork
копирует память процесса - код, данные и стек - затем возвращает управление. Вызов fork
вернет исходному процессу PID нового процесса, а новому процессу - 0
. Исходный процесс называют родительским, а новый - дочерним.
int pid = fork();
if (0 < pid) {
printf("parent: child=%d\n", pid);
pid = wait((int *) 0);
printf("child %d is done\n", pid);
} else if (0 == pid) {
printf("child: exiting\n");
exit(0);
} else {
printf("fork error\n");
}
Системный вызов exit
останавливает текущий процесс и освобождает связанные с ним ресурсы, такие как память и открытые файлы. Аргумент exit
- код завершения - 0
в случае успеха и 1
в случае ошибки.
Системный вызов wait
возвращает текущему процессу PID завершенного дочернего процесса и пишет код завершения по переданному адресу. Вызов wait
разрешает передать 0
, если код завершения не нужен. Вызов wait
ожидает завершения дочернего процесса, если ни один дочерний процесс еще не завершился, и немедленно вернет -1
, если у текущего процесса нет дочерних.
Порядок вывода строк
parent: child=1234
child: exiting
зависит от того, какой из процессов первым вызовет printf
. После завершения дочернего процесса, wait
вернет управление родительскому и код напечатает
parent: child 1234 is done
Хотя после вызова fork
содержимое памяти обоих процессов одинаковое, один процесс не влияет на работу другого. Каждый процесс работает с собственными переменными и регистрами процессора. Например, переменная pid
дочернего процесса останется неизменной, когда родительский процесс выполнит
pid = wait((int *) 0);
Вызов exec
заменит образ памяти текущего процесса тем, что загрузит из файла. В случае успеха exec
не возвращает управление вызывающей программе, а начинает выполнение программы из файла. exec
принимает 2 аргумента: имя исполняемого файла и массив строк-аргументов программы.
Исполняемый файл - результат компиляции исходного текста программы. Формат исполняемого файла определяет, где код, данные, первую инструкцию программы и т.д. Xv6 использует формат ELF
, о котором подробно рассказывает Глава 3. Заголовок ELF-файла определяет точку входа в программу - адрес первой инструкции.
char* argv[3];
argv[0] = "echo";
argv[1] = "hello";
argv[2] = 0;
exec("/bin/echo", argv);
printf("exec error\n");
Этот фрагмент кода заменит текущую программу программой /bin/echo
, запущенной с аргументами "echo", "hello". Первый аргумент - имя программы.
Программа shell
в xv6 использует вызовы fork
и exec
, чтобы выполнять программы по просьбе пользователя. Цикл в main
получает строку от пользователя вызовом getcmd
, затем создает копию процесса shell
вызовом fork
. Родительский shell
вызывает wait
и ожидает завершения дочернего, а дочерний shell
выполняет команду, что ввел пользователь. Например, пользователь вводит "echo hello", parsecmd
разбирает ввод, а runcmd
выполняет команду вызовом exec
. Так shell
выполнит код echo
вместо дальнейшего кода runcmd
. Затем код echo вызовет exit
, после чего родительский shell
вернется из wait
в main
.
// Read and run input commands.
while(getcmd(buf, sizeof(buf)) >= 0){
if(buf[0] == 'c' && buf[1] == 'd' && buf[2] == ' '){
// Chdir must be called by the parent, not the child.
buf[strlen(buf)-1] = 0; // chop \n
if(chdir(buf+3) < 0)
fprintf(2, "cannot cd %s\n", buf+3);
continue;
}
if(fork1() == 0)
runcmd(parsecmd(buf));
wait(0);
}
Ценность отдельных вызовов fork
и exec
увидим позже, когда изучим код shell
, что перенаправляет ввод-вывод.
Операционная система оптимизирует код fork
и не копирует память, пока процессы в память не пишут. Копирование памяти - пустая трата времени, когда за fork
следует exec
, который снова память заменит.
Xv6 распределяет большинство памяти неявно - fork
запрашивает необходимую память для копирования процесса, а exec
- для загрузки программы из файла. Процесс вызывает sbrk
, когда требуется дополнительная память, чтобы расширить память на n байтов. Вызов sbrk
возвращает адрес новой памяти.
Ввод-вывод и дескрипторы файлов
Дескриптор файла - целое число, которое представляет объект в ядре, доступный процессу для чтения и записи. Процесс получает дескриптор файла, когда открывает файл, директорию, устройство, создает канал или копирует другой дескриптор. Дескриптор файла абстрагирует работу с этими объектами. Вместо "дескриптор файла" будем говорить "файл".
Ядро ведет таблицу открытых файлов каждого процесса, а дескриптор файла - индекс в этой таблице. Условились, что три дескриптора каждого процесса заранее определены:
0
- стандартный ввод илиstdin
1
- стандартный вывод илиstdout
2
- вывод ошибок илиstderr
Программа shell
следует этому соглашению, чтобы перенаправлять ввод-вывод и запускать конвейер команд. Код shell
гарантирует, что каждый процесс открывает эти дескрипторы сразу после запуска и связывает с терминалом.
// Ensure that three file descriptors are open.
while((fd = open("console", O_RDWR)) >= 0){
if(fd >= 3){
close(fd);
break;
}
}
Вызов read
читает байты из файла, связанного с дескриптором, а вызов write
- записывает байты в файл. read(fd, buf, n)
читает до n
байтов, записывает в buf
и возвращает число прочитанных байтов. Каждый дескриптор запоминает позицию в файле. Вызов read
читает байты от текущей позиции и сдвигает позицию на число прочитанных байтов. Следующий read
прочтет следующие байты файла. Вызов read вернет 0
, когда позиция достигнет конца файла.
Вызов write(fd, buf, n)
пишет n
байтов из buf
в файл и возвращает число записанных байтов. Возврат менее n
байтов означает ошибку записи. Вызов write
пишет от текущей позиции в файле и сдвигает позицию на число записанных байтов. Следующий write
продолжает запись там, где остановился предыдущий.
Вот так работает программа cat
- копирует байты со стандартного ввода в стандартный вывод:
char buf[512];
int n;
for (;;) {
n = read(0, buf, sizeof buf);
if (0 == n)
break;
if (n < 0) {
fprintf(2, "read error\n");
exit(1);
}
if (write(1, buf, n) != n) {
fprintf("write error\n");
exit(1);
}
}
Программа cat
не знает, читает ли ввод с терминала, из файла или канала. Так же cat
не знает, куда печатает вывод. Соглашение о файловых дескрипторах 0
, 1
и 2
упрощает код программы.
Вызов close
освобождает файловый дескриптор. Следующий вызов open
, pipe
, dup
использует этот дескриптор. Ядро выбирает наименьший свободный дескриптор среди тех, что принадлежат процессу.
Вызов fork
копирует и дескрипторы файлов процесса: дочерний процесс получает те же открытые файлы, которыми владеет родительский процесс. Вызов exec
перезаписывает память процесса, но не трогает дескрипторы файлов. Программа shell
пользуется этим, чтобы перенаправлять ввод-вывод команд: shell
вызывает fork
, закрывает и снова открывает дескрипторы файлов stdin
, stdout
, stderr
дочернего процесса, затем вызывает exec
и выполняет указанную программу. Вот как shell
могла бы выполнить команду cat < input.txt
:
char *argv[2];
argv[0] = "cat";
argv[1] = 0;
if (0 == fork()) {
close(0);
open("input.txt", O_RDONLY);
exec("cat", argv);
}
Вызов open
использует дескриптор 0
после close(0)
. Таким образом программа cat отработает со вводом из файла input.txt
. Дескрипторы файлов родительского процесса останутся нетронутыми.
Программа shell
перенаправляет ввод-вывод команд так же:
// Execute cmd. Never returns.
void runcmd(struct cmd *cmd) {
/*...*/
switch (cmd->type) {
/*...*/
case REDIR:
rcmd = (struct redircmd*)cmd;
close(rcmd->fd);
if (open(rcmd->file, rcmd->mode) < 0) {
fprintf(2, "open %s failed\n", rcmd->file);
exit(1);
}
runcmd(rcmd->cmd);
break;
Код уже вызвал fork
и код работает с дескрипторами файлов дочернего процесса.
Второй аргумент open - комбинация битовых флагов - определяет действие open. Файл kernel/fcntl.h
перечисляет доступные флаги:
O_RDONLY
- открыть файл только для чтенияO_WRONLY
- открыть файл только для записиO_RDWR
- открыть файл для чтения и записиO_CREATE
- создать файл, если не существуетO_TRUNC
- обрезать длину файла до 0 байтов
Между вызовами fork
и exec
программа shell
способна перенаправить ввод-вывод команды, а собственный ввод-вывод оставить прежним. Код станет сложнее, если вместо отдельных fork
и exec
объявить один forkexec
: программе shell придется перенаправлять собственные дескрипторы, выполнять команду, а затем восстанавливать дескрипторы или придется учить команды самостоятельно перенаправлять ввод-вывод.
Вызов fork
копирует дескрипторы файлов, но родительский и дочерний процессы используют одну позицию внутри файла.
if (0 == fork) {
write(1, "hello ", 6);
exit(0);
} else {
wait(0);
write(1, "world\n", 6);
}
Этот фрагмент кода напечатает "hello world" в stdout
. Процесс-родитель дождется завершения дочернего и продолжит печать. Такое поведение помогает получить последовательный вывод нескольких команд, например
(echo hello; echo world) >output.txt
Вызов dup
копирует файловый дескриптор - возвращает новый дескриптор, который связан с тем же объектом. Оба дескриптора ссылаются на одну и ту же позицию в файле. Вот еще один способ записать строку "hello world" в файл:
int fd = dup(1);
write(1, "hello ", 6);
write(fd, "world\n", 6);
А вот так bash
в Unix объединяет стандартный вывод и вывод ошибок:
ls existing-file non-existing-file > tmp1 2>&1
2>&1
говорит программе shell
, что дескриптор 2
- копия дескриптора 1
. Таким образом команда направит вывод ошибок туда же, куда и стандартный вывод. Shell
в xv6 не умеет перенаправлять вывод ошибок, но теперь ясно, как это реализовать.
Повторный вызов open
для того же имени файла вернет новый дескриптор, у которого позиция в файле не зависит от других дескрипторов. Этим open
отличается от dup
и fork
.
Дескрипторы файлов - полезная абстракция: процесс пишет в стандартный вывод и не заботится, куда вывод направлен - на терминал, в файл или на вход другого процесса.
Каналы
Канал - маленький буфер в ядре. Канал предоставляет процессам два файловых дескриптора: один для чтения, другой для записи. Один процесс пишет в канал, а другой читает.
Пример кода запускает программу wc
, которая читает из канала:
int p[2];
char *argv[2];
argv[0] = "wc";
argv[1] = 0;
pipe(p);
if (0 == fork()) {
close(0);
dup(p[0]);
close(p[0]);
close(p[1]);
exec("/bin/wc", argv);
} else {
close(p[0]);
write(p[1], "hello world\n");
close(p[1]);
}
Код создает канал вызовом pipe
и сохраняет дескрипторы чтения и записи канала в элементах массива p[0]
и p[1]
соответственно. Оба процесса - родительский и дочерний - владеют дескрипторами канала после вызова fork
.
Дочерний процесс вызывает close
и dup
, чтобы направить вывод канала в стандартный ввод - дескриптор 0
. Затем дочерний процесс закрывает ненужные дескрипторы в p
и запускает программу wc
. Теперь wc
читает из канала.
Родительский процесс закрывает ненужный дескриптор чтения канала, записывает строку "hello world\n" в канал и закрывает дескриптор записи канала.
Вызов read
заставит процесс ожидать записи в канал, если канал пуст. Вызов read
вернет 0
только когда код закроет последний дескриптор записи в канал, поэтому важно закрыть дескриптор записи канала в дочернем процессе прежде, чем читать канал. Программа wc
зависнет, если дескриптор не закрыть.
Программа shell
в xv6 реализует конвейеры команд с помощью каналов, например
grep fork sh.c | wc -l
Дочерний процесс создает канал, чтобы связать вывод левой команды со вводом правой. Затем процесс вызывает fork
и runcmd
для левой команды, вызывает fork
и runcmd
для правой команды и ждет, пока обе команды завершат работу. Правая команда - тоже конвейер, например
cat wordlist.txt | sort | uniq
________________ ___________
left right
Правая команда дважды вызовет fork
. Таким образом программа shell
строит дерево процессов. Листья дерева - команды, а узлы дерева - процессы, что ждут завершения левого и правого дочерних процессов.
Конвейер работает и с помощью временных файлов вместо каналов:
# pipe
echo hello world | wc
# temporary file
echo hello world >/tmp/xyz; wc </tmp/xyz
Каналы лучше временных файлов по трем причинам:
Каналы | Временные файлы |
---|---|
Каналы не оставляют следов - ядро автоматически уничтожает каналы после закрытия. | Файл остается на диске. |
Объем передаваемых данных не ограничен | Объем данных ограничен свободным местом на диске. |
Команды выполняются параллельно | Первая команда должна завершить работу прежде, чем начнет работу вторая |
Вторая команда ждет завершения первой прежде чем начать работу.
Файловая система
Файловая система xv6 хранит файлы и директории. Файл - произвольный массив байтов. Имя файла - ссылка на этот массив. Число имен файла не ограничено. Директории содержат имена файлов и вложенных директорий.
Файловая система xv6 - дерево директорий. Имя корневой директории /
. Путь /a/b/c
указывает на файл или директорию c
, что лежит в директории с именем b
, которая вложена в директорию с именем a
, которая вложена в корневую директорию /
.
Путь, что начинается в корневой директории /
- абсолютный. Относительный путь не начинается в /
. Поиск файла по относительному пути начинается в текущей директории процесса. Вызов chdir меняет текущую директорию процесса.
chdir("/a");
chdir("b");
// open using relative path
open("c", O_RDONLY);
// open using absolute path
open("/a/b/c", O_RDONLY);
Оба фрагмента кода открывают файл /a/b/c
. Первый фрагмент дважды меняет текущую директорию процесса и открывает файл по относительному пути. Второй фрагмент не меняет текущую директорию процесса и открывает файл по абсолютному пути.
Эти системные вызовы создают файлы и директории:
mkdir
создает новую директориюopen
с флагомO_CREATE
создает новый файл данныхmknod
создает новый файл устройства
mkdir("/dir");
fd = open("/dir/file", O_CREATE|O_WRONLY);
close(fd);
mknod("/console", 1, 1);
Ядро идентифицирует устройство по двум числам, что переданы mknod
. Процесс работает с файлом устройства, а ядро направляет вызовы read
и write
драйверу устройства.
Имя файла и сам файл - не одно и то же. Файл - блок данных, у которого одно или несколько имен. Имя файла - ссылка на файл. Файловая система хранит для каждого файла структуру inode
. Структура inode
хранит метаданные файла - тип, размер, расположение на диске и число ссылок на файл. Запись в директории - имя файла и ссылка на inode
.
Вызов fstat
заполняет структуру stat
информацией из inode
.
// kernel/stat.h
#define T_DIR 1 // Directory
#define T_FILE 2 // File
#define T_DEVICE 3 // Device
struct stat {
int dev; // File system's disk device
uint ino; // Inode number
short type; // Type of file
short nlink; // Number of links to file
uint64 size; // Size of file in bytes
};
Вызов link
создает имя файла, которое ссылается на тот же inode
, что и указанный файл.
open("a", O_CREATE|O_WRONLY);
link("a", "b");
Этот фрагмент кода создает один файл с двумя именами - a
и b
. Чтение или запись в a
- то же, что чтение или запись в b
.
Файловая система назначает каждому inode
идентификатор. Вызов fstat
запишет идентификатор inode
в поле ino
структуры stat
- так можно узнать, что имена a
и b
указывают на один и тот же файл. Поле nlink
хранит число имен, которые ссылаются на этот файл.
Вызов unlink
удалит имя файла. Ядро удалит inode
файла и освободит место на диске только когда счетчик ссылок на файл nlink
окажется равен 0
и ни один файловый дескриптор не ссылается на файл.
Код
open("a", O_CREATE|O_WRONLY);
link("a", "b");
unlink("a");
оставит файл доступным по имени b
.
Код
fd = open("/tmp/xyz", O_CREATE|O_RDWR);
unlink("/tmp/xyz");
создаст временный файл, который ядро удалит после закрытия дескриптора fd
или завершения процесса.
Unix реализует утилиты работы с файлами как пользовательские программы, которые может вызывать программа shell
- mkdir
, ln
, rm
и т.д. Пользователи добавляют новые программы и расширяют возможности shell
. Такое решение кажется очевидным, но другие системы - современники Unix - встраивали такие команды в shell
, а саму shell
- в ядро.
Единственное исключение - shell
сама реализует команду cd
. Команда cd
меняет текущую директорию процесса. Пользовательская программа работает в отдельном процессе после вызова fork
и не способна изменить текущую директорию процесса shell
.
Реальный мир
Стандартные файловые дескрипторы, каналы и синтаксис shell
для работы с ними - главное преимущество Unix - помогают писать общие программы, которые легко объединять для решения новых задач. Идеи Unix зародили культуру программ-инструментов и сделали Unix такой мощной и популярной. Shell
стал первым языком сценариев. Интерфейс системных вызовов Unix и по сей день остается в BSD, Linux и macOS.
Интерфейс системных вызовов Unix стал стандартом под названием Portable Operating System Interface или POSIX. Система xv6 не совместима с POSIX: xv6 реализует только часть системных вызовов POSIX и реализует не так, как требует стандарт. Авторы сделали xv6 простой и ясной, похожей на Unix.
Энтузиасты расширили xv6 - реализовали больше системных вызовов и библиотеку языка Си, чтобы запускать простые Unix-программы, но xv6 далеко до современных операционных систем. Такие системы поддерживают работу с сетью, графические оконные системы, пользовательские потоки, драйверы самых разных устройств и т.д. Современные системы быстро развиваются и предлагают больше, чем POSIX.
Unix унифицировал доступ к файлам, директориям и устройствам с помощью интерфейса доступа по именам и файловым дескрипторам. Система Plan 9 пошла дальше и применила эту идею к сетевым и графическим ресурсам, однако многие последователи Unix не пошли этим путем.
Multics - предшественник Unix - работал с файлами так же, как с оперативной памятью. Разработчики Unix вооружились идеями Multics, но упростили систему.
Unix позволяет нескольким пользователям одновременно работать в системе. Unix выполняет каждый процесс от имени конкретного пользователя. Xv6 же выполняет процессы от имени единственного пользователя.
Эта книга рассказывает как xv6 реализует Unix-подобный интерфейс, но идеи годятся не только для Unix. Операционная система одновременно выполняет несколько процессов на одном компьютере, защищает процессы друг от друга, но позволяет процессам взаимодействовать. Xv6 научит видеть эти идеи и в сложных операционных системах.
Упражнения
Напишите программу с использованием системных вызовов Unix, которая передает один байт между двумя процессами туда и обратно по паре каналов. Оцените быстродействие программы в количестве передач за секунду.