Модель ОС через CPS

Навигация

• Homepage
• Содержание курса
• Билеты к зачёту
• Домашние задания

• Квазиполезное

  • Модель ОС с первой лекции
  • Демонизация
  • Псевдотерминалы
  • Пример запуска poll(3)

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

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

Рассмотрим простейшую программу:

def main():
    name = read()
    s = "hello, " + name
    write(s)
    exit(0)

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

• что именно (какой системный вызов) должно для этого процесса сделать ядро;
• с какими параметрами этот системный вызов должен исполняться;
• что исполнять после системного вызова и как процесс получит результат.

Для наглядности нашей модели все эти вещи процесс будет сообщать ядру явно ¹. Для этого код программы должен выглядеть немного по-другому. Тут-то на сцену и выходит CPS (continuation passing style): передача кода-продолжения как аргумента чего-либо (на это еще можно смотреть как на callback).

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

• внутри себя делают только нерперывные вычисления и не взаимодействуют с ОС;
• завершаются, если хочется сделать системный вызов;
• при завершении указывают, что должно исполняться дальше.

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

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

• тэга системного вызова (READ_TAG, WRITE_TAG или EXIT_TAG);
• списка параметров системного вызова;
• функцию-продолжение процесса.

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

Тогда приведенный выше код программы будет выглядеть примерно так:

def main():
    return (READ_TAG, [], cont)

def cont(name):
    s = "hello, " + name
    return (WRITE_TAG, [s], cont2)

def cont2():
    return (EXIT_TAG, [0], None)

Это уже не очень похоже на программу, которую можно просто "взять и исполнить". Ей нужен интерпретатор, знающий о соглашениях, наложенных на представление этой программы: почему она в некоторых местах делает странные return и как их обрабатывать. Этим интерпретатором и является ядро.

Ядро

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

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

while True:
    (tag, syscall_args, cont) = process(args)
    if tag == READ_TAG:
        result = do_readline()
    elif tag == WRITE_TAG:
        do_writeline(syscall_args)
        result = None
    else:
        print("ERROR: No such syscall")
    process = cont
    args = result

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

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

while processes:
    (prog, args) = processes.pop()
    (tag, syscall_args, cont) = prog(*args)
    if tag == READ_TAG:
        result = do_readline()
        processes.append((cont, [result]))
    elif tag == WRITE_TAG:
        do_writeline(syscall_args)
        processes.append((cont, []))
    else:
        print("ERROR: No such syscall")

Создание новых процессов

Обрабатывать системные вызовы уже существующих процессов, конечно, полезно, но не несет особого смысла, если эти процессы некому создать. Традиционно в unix-like системах создание нового процесса происходит с помощью дублирования текущего процесса и всей сопутствующей ему информации. Это делается системным вызовом fork. Он дублирует процесс, инициировавший этот системный вызов, а полученным двум процессам-близнецам возвращает разные результаты, чтобы они могли понять, какой из процессов — новый, а какой — старый.³

flag = fork()
if flag:
    write("Old process")
else:
    write("New process")

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

flag = fork()
if not flag:
    exec("bash")
    write("This will never be printed")
else:
    exec("wrongbinaryname")
    write("exec() failed")

В ядре обработка этих системных вызовов выглядит достаточно очевидно:

    elif tag == FORK_TAG:
        processes.append((cont, [True]))
        processes.append((cont, [False]))
    elif tag == EXEC_TAG:
        new_cont = load_binary(syscall_args[0])
        processes.append((new_cont, syscall_args[1:]))

Надо заметить, что cont в приведенной обработке системного вызова exec() не используется, что хорошо согласуется с описанной семантикой этого системного вызова.

Завершение процесса

Завершение процессов происходит тоже с помощью системного вызова, который называется exit(). Его обработка в ядре тривиальна: нужно просто выкинуть процесс из списка процессов (и освободить соответствующие ему ресурсы):⁴

    elif tag == EXIT_TAG:
        # NB: no "processes.append((cont, ...))" here
        pass

TODO: возможно, здесь должно быть еще что-нибудь про kill

Блокирующие системные вызовы

TODO: наверное, это должно быть вообще не здесь, потому что в приведенной реализации этого нет

Реализация

У этой модели есть примитивная реализация на питоне, которую можно позапускать и посмотреть, как она себя ведет. Ее можно найти здесь.