Как стать автором
Обновить

Xv6: учебная Unix-подобная ОС. Глава 1. Интерфейсы операционной системы

Уровень сложностиСредний
Время на прочтение14 мин
Количество просмотров12K
Автор оригинала: Russ Cox, Frans Kaashoek, Robert Morris

Примечание. Авторы рекомендуют читать книгу вместе с исходным текстом xv6. Авторы подготовили и лабораторные работы по xv6.

Xv6 работает на RISC-V, поэтому для его сборки нужны RISC-V версии инструментов: QEMU 5.1+, GDB 8.3+, GCC, и Binutils. Инструкция поможет поставить инструменты.

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

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

Эта книга рассказывает о принципах работы операционных систем на примере 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, которая передает один байт между двумя процессами туда и обратно по паре каналов. Оцените быстродействие программы в количестве передач за секунду.

Теги:
Хабы:
Всего голосов 15: ↑15 и ↓0+15
Комментарии6

Публикации

Истории

Работа

Программист С
30 вакансий

Ближайшие события