Филиал МГУ в г. Душанбе

Факультет прикладной математики и информатики

Операционные системы

Содержание


Программа курса "Операционные системы"


Лекции

  1. Устройство компьютера. Фон-Неймановская архитектура, основные регистры процессора. Аппаратный стек и соглашения о взаимодействии функций

    Процессор, оперативная память, шина, внешние устройства. Протокол работы шины и подключение новых внешних устройств. Фон-Неймановская архитектура и алгоритм работы компьютера. Регистры процессора. Регистры, играющие особую роль: счетчик команд (или указатель инструкции) PC (Program Counter), указатель стека SP (Stack Pointer), указатель кадра FP (Frame Pointer). Абстрактный стек, стековый вычислитель и обратная польская запись выражений. Аппаратный стек и его реализация. Использование аппаратного стека для сохранения состояния задачи, для хранения точек возврата при вызове функций. Размещение локальных переменных функции в аппаратном стеке. Соглашения о вызовах функций в языке C/C++: передача параметров через стек и использование регистра FP для относительной адресации параметров и локальных переменных. Классы памяти в языке C/C++: статическая, стековая, динамическая, правила их использования. Реализация рекурсии, примеры рекурсивных программ: простой и расширенный алгоритмы Евклида.


  2. Асинхронные и синхронные прерывания. Режимы работы процессора, кольца защиты, системные вызовы. Виртуальная память

    Новые соглашения о вызовах функций для 64-битового процессора x86-64: поскольку добавлено 8 новых регистров R8-R15, стало возможным передавать аргументы функции через регистры (в MS Windows первые 4 целочисленных аргумента передаются через регистры RCX, RDX, R8, R9, остальные через стек, в Linux первые 6 целочисленных аргумента через регистры RDI, RSI, RDX, RCX, R8, R9). Указатель кадра (регистр FP, или RBP для процессора x86-64) больше не используется, локальные переменные адресуются относительно указателя стека RSP.

    Уровни защиты (Protection rings) и их использование в операционных системах. Режим ядра (нулевое кольцо) и пользовательский режим (кольцо 3), почему необходимы такие уровни. Промежуточные уровни защиты 1 и 2 (используются редко).

    Прерывания: аппаратные (асинхронные) и программные (синхронные). Векторы прерываний и порядок обработки прерывания: сохранение состояния прерванной задачи в аппаратном стеке, переключение контекстов и вызов обработчика прерывания в операционной системе, восстановление контекста и продолжение исполнения прерванной задачи. Причины синхронных прерываний: ошибка в программе (деление на 0, обращение по несуществующему адресу и т.п.) или исполнение специальной команды прерывания, например, команды INT процессора Intel 80X86. Использование команды прерывания INT для вызова функций операционной системы (INT 21 в MS DOS, INT 80 в Linux).

    Виртуальная память, почему она необходима в многозадачных операционных системах. Два способа организации виртуальной памяти: устаревшая сегментная реализация (на примере процессора Intel 80286), современная страничная реализация виртуальной памяти. Таблица описателей страниц и алгоритм вычисления физического адреса по виртуальному. Вытеснение страниц виртуальной памяти на диск при нехватке физического пространства. Прерывание "Page fault" и своппинг.


  3. Основные функции операционной системы. Краткая история операционных систем

    Основные функции операционной системы:
    1) предоставление прикладным программам удобного интерфейса для работы с устройствами, файлами и т.п. и одновременное обеспечение независимости прикладных программ от конкретных устройств;
    2) управление процессами, исполняющимися на компьютере (обеспечение взаимной независимости, передача информации между процессами - IPC, распределение памяти и процессорного времени и т.п.).

    Краткая история операционных систем. Эпоха компьютеров без ОС - использование перфокарт и лент для ввода и выполнения программ. Пакетный (Batch) режим исполнения заданий. ЭВМ IBM 360/370 и их советский аналог ЕС ЭВМ, одновременная загрузка нескольких задач в память (с использованием позиционно-независимого кода или сегментных регистров). Первые мини-ЭВМ - PDP-11 фирмы DEC с 16-разрядной архитектурой и их операционные системы: однозадачная RT-11 с непрерывными файлами, многозадачная RSX-11. Первая 32-разрядная мини-ЭВМ VAX и многозадачная ОС с высокой степенью защиты VAX VMS. MS DOS как одна из первых ОС для персональных компьютеров, 16-разрядная MS Windows 3.1. Windows NT, созданная совместно фирмами Microsoft и IBM с использованием опыта разработки VAX VMS (разработчик Дейв Катлер из фирмы DEC) и API Win32. Понятие API (Application Program Interface) как центральное в области разработки программного обеспечения - контракт между создателями операционной системы и разработчиками прикладных программ.

    Возвращение к 16-разрядной операционной системе Windows 95 и причины этого. Новое в Windows 95: поддержка Internet-протоколов, удобный оконный интерфейс. Линия 16-разрядных ОС фирмы Microsoft - Windows 98, Millenium Edition. Обратное возвращение к Windows NT: Windows 2000, Windows XP, Vista, Windows 7/8 и 64-битные варианты этих систем.

    Операционная система Unix, ее краткая характеризация и история. Unix как первая переносимая операционная система, написанная почти целиком на языке высокого уровня C. Варианты Unix - System-V от Bell Labs и AT&T, системы, разработанные в университете Berkeley - FreeBSD (Berkeley Software Distribution), NetBSD, использования этих систем как серверов в Internet. Система Linux, созданная финским студентом Линусом Торвальдсом, и ее развитиев рамках проекта открытого программного обеспечения.

    Операционные системы компьютеров Apple Macintosh. Ранние версии сисмемы Mac OS и их особенности (отождествление файлов по двум целым числам вместо традиционных имен или путей к файлам, подпись Signature программ и файлов с документами, файлы, состоящие из двух частей - Data fork и Resource fork, оконный интерфейс как часть операционной системы).Современные системы Apple Macintos, начинающиеся с Mac OS X, ядро которой построено на основе FreeBSD-Unix с использованием микроядра Mach. Операционные системы Android и Chromium фирмы Google для планшетных компьютеров и смартфонов на основе Linux.


  4. Классификация операционных систем. Компоненты ОС и способы построения ядра системы

    Классификация ОС

    1. Однозадачные ОС (Single tasking). MS DOS - можно было запустить 2 задачи, фоновую background и фронтальную foreground; некоторые встроенные системы и т.п.
    2. Многозадачные ОС (multi tasking).
      В старых ОС использовалась кооперативная многозадачность (co-operative), при которой несколько задач загружены в память, но работает только одна задача, причем система ее не прерывает. Задача, проработав квант времени, сама должна вернуть управление операционной системе, и та активизирует другую задачу. Примеры подобных систем - старая MS Windows 3.1 (использовавшаяся до Windows NT), старая операционная система компьютеров Apple Macintosh до версии Mac OS-X; операционная система серверов Novell Netware.
      В современных ОС используется вытесняющая многозадачность (pre-emptive).
      Операционная система работает в режиме разделения времени (time sharing). Задача, проработав квант времени (например, 0.01 сек), по таймеру прерывается системой и приостанавливается. Управление передается ядру ОС, которое определяет следующую задачу, получающую очередной квант времени. Таковы все современные многозадачные ОС (все типы Unix, MS Windows, Mac OS X, Android и т.п.).
    3. ОС можно разделить на однопользовательские и многопользовательские. Типичный пример многопользовательской системы - Unix, в котором на компьютере могут одновременно работать сразу много пользователей, заходя с удаленных терминалов (или X-терминалов). Система MS Windows скорее однопользовательская, в ней в любой момент времени работает только 1 пользователь, поскольку она задумывалась как ОС для персонального компьютера (хотя в ней предусмотрена возможность работы с удаленного терминала). Однопользовательская система вполне может быть многозадачной (таковы все современные ОС для персональных компьютеров).
    4. Существуют операционные системы реального времени (real time systems), в которых обеспечивается гарантированное время отклика. Подобные системы используются для управления реальными процессами, где критично быстродействие запущенных задач: управление самолетами, ядерными реакторами, космическими кораблями и т.п. В подобных системах процессы разделяются на процессы реального времени и обычные пользовательские, первые имеют безусловный приоритет над вторыми (процесс низкого приоритета не может замедлить real time-процесс). Ядро (или микроядро) системы должно быть построено так, чтобы исключить операции с непредсказуемым временем исполнения (длительные итеративные циклы и т.п.). Таковы ОС QNX, некоторые виды систем типа Unix (например, real-time Linux), MS Windows CE (Compact Edition) и др.
    5. Можно рассматривать также серверные ОС (серверы Novell Netware, MS Windows Server и т.п.), хотя на серверах очень часто используют универсальные ОС. Пример - на WEB-серверах Internet очень популярны Unix-системы FreeBSD/NetBSD и Linux.
    6. Существуют распределенные и облачные ОС, в которых задача выполняется распределенно групой компьютеров, объединенных быстродействующей локальной сетью (кластер), либо работающих в глобальной сети (MS Windows Azurro).

    Компоненты операционной системы

    1. Система управления процессами и нитями, распределяющая между ними процессорное время (scheduling).
    2. Система поддержки виртуальной памяти.
    3. Поддержка взаимодействия между процессами (нитями) и ядром, а также между пользовательскими процессами (IPC - Inter-Process Communication, включает в себя обмен сообщениями и использование разделяемой памяти shared memory).
    4. Драйверы устройств.
    5. Файловые системы.
    6. Командный интерфейс - интерпретатор текстовых команд оперативной системы, различные оболочки и скрипты.
    7. Графический оконный интерфейс. Он может быть реализован как часть ядра операционной системы (эта часть называется GUI - Graphical User Interface), например, так реализована оконная система в MS Windows, или как один или несколько пользовательских процессов (система X-Window в ОС Unix).

    Способы построения ядра ОС

    1. Ядро ОС может быть монолитным (monolitic). Это означает, что ядро системы представляет собой единую большую программу, все части которой работают на максимальном уровне привелегий (в нулевом кольце защиты процессора). При этом в современных системах имеется механизм загрузки модулей, например, драйверов устройств; таким образом обеспечивается возможность модификации ядра системы без его перекомпиляции.
      Таковы, например, ОС Linux, FreeBSD, MS Windows.
    2. Операционная система может быть построена с использованием технологии микроядра (micro-kernel). В микроядро выносятся лишь наиболее важные, базовые функции системы: управление процессами, базовое IPC, управление виртуальной памятью. Лишь элементы микроядра работают с максимальным уровнем привелегий (в нулевом кольце защиты процессора). Остальные части ОС (драйверы устройств, файловые системы и т.п.) работают уже как пользовательские процессы (используется термин "серверы" - например, файловый сервер). Таким образом, обеспечивается более высокая надежность системы - например, ошибка в драйвере устройства не приводит к катастрофе, ядро системы продолжает функционировать.
      Наиболее известно микроядро Mach, разработанное в MIT (Massachusetts Institute of Technology). По объему оно совсем небольшое, всего около 6 тыс. строк на C. Это позволяет отладить и сертифицировать текст, исключив или сведя к минимуму вероятность ошибок. На базе микроядра построена система реального времени QNX, а также система Mac OS-X, объединяющая в себе использование микроядра Mach, а также исходные коды FreeBSD Unix.


  5. Процессы и нити. Объекты синхронизации

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

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

    1. Виртуальное адресное пространство и его отображение на физическую память.
    2. Множество открытых файловых дескрипторов.
    3. Набор нитей - threads, другие названия - потоки или легковесные процессы (light-weight processes). Каждая нить исполняет свою последовательность команд, выбираемых из памяти процесса. Нити исполняются параллельно или псевдопараллельно (в режиме разделения времени, в многоядерных архитектурах могут исполняться на разных процессорах). Все нити работают в одном и том же виртуальном адресном пространстве, поэтому у них общие статические переменные, а также динамическая память (куча). Однако каждой нити выделяется свой собственный стек - он расположен в общем адресном пространстве, однако значение регистра SP у каждой нити свое. Благодаря этому локальные переменные функции у каждой нити свои, и при переключении нитей и вызове одной и той же фукции из разных нитей ее локальные переменные не разрушаются. Таким образом, функции, использующие только локальные переменные, безопасны при использовании нитей (thread-safe). Напротив, использование статических переменных опасно, оно обязательно требует применения объектов синхронизации. Иначе возможна ситуация, когда нить, начавшая менять критические данные, прерывается системой и оставляет данные в некорректном состоянии, что вызывает ошибку при попытке их использования другой нитью.

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

    Обмен данными между процессами
    (IPC - Inter-Process Communication)

    Существуют следующие способы обмена данными между процессами.

    1. Разделяемая память (shared memory). Часть адресного пространства разных процессов отображается на одну и ту же физическую память, через которую процессы могут обмениваться информацией. Недостатком этого способа является зависимость от архитектуры компьютера и ОС, что приводит к трудностям при перенесении программ на другую архитектуру.
    2. Использование программного канала (pipe). Этот прием используется в основном в Unix. Программа открывает два файловых дескриптора, связанных между собой (pipe - труба), первый используется для чтения, второй - для записи:
          int fds[2];
          int res = pipe(fds);
      
      После успешного выполнения системного вызова pipe процесс выполняет вызов fork, создающий два одинаковых процесса, один из которых является родителем (parent), другой - ребенком (child). Допустим, данные нужно передавать от ребенка к родителю. Тогда родительский процесс закрывает второй файловый дескриптор, а процесс-ребенок - первый дескриптор. Ребенок пишет данные, используя второй дескриптор, родитель их читает, используя первый дескриптор:
          int pid = fork();
          if (pid != 0) {
              // This is the parent process
              close(fds[1]);
              len = read(fds[0], buffer, maxLen);
              . . .
          } else {
              // This is the child process
              close(fds[0]);
              res = write(fds[1], buffer, len);
              . . .
          }
      

      Таким способом реализуется односторонняя связь между процессом-ребенком и процессом-родителем (pipe - это труба, по которой данные текут лишь в одну сторону). Для двусторонней связи надо создать две трубы и четыре файловых дескриптора.

      В MS-Windows использование программных каналов (pipe) менее популярно, чем в Unix, поскольку отсутствует системный вызов fork.

    3. Процессы могут посылать друг другу сообщения, в различных ОС для этого используются разные механизмы. Например, в Win32 для этой цели можно использовать системные функции SendMessage, BroadcastSystemMessage и др.
    4. Наконец, наиболее универсальный способ обмена информацией между процессами - это обмен данными по сети. В любой сетевой архитектуре присутствует локальный (loopback) интерфейc, позволяющий обмениваться данными процессам, работающим на одном компьютере (в протоколах TCP/IP для этого используется IP-адрес 127.0.0.1 или символическое имя localhost). Обмен по сети делает возможным исполнение задачи параллельно независимо от того, работают ли участвующие в ней процессы на одном или на разных компьютерах.

    Программирование с использованием нитей (threads)

    В Unix работа с нитями описана в стандарте POSIX. Нить отождествляется с помощью переменной типа pthread_t. Для создания и старта нити используется системная функция pthread_create. Ей передается адрес функции, которую нить исполняет в процессе своей работы.

    #include <pthread.h>
    
    // Prototype of thread body function
    void* run(void* arg);
    
    int main() {
        pthread_t thread1, thread2;
    
        // Create the first thread
        int res = pthread_create(
            &thread1,   // Thread identifier
            NULL,       // Thread attributes: defaults
            &run,       // Thread start function
            (void *) heads // Parameter of thread function
        );
    
        . . .
    }
    
    void run(void* arg) {
        // Thread function
        . . .
    }
    
    Одна нить может ожидать завершения другой нити:
        pthread_join(thread1, NULL);
    
    Здесь нить, исполняющая эту команду, приостанавливается до тех пор, пока нить thread1 не завершит свою работу.

    В MS Windows нить, как и процесс, является объектом ядра системы и, как все объекты ядра, отождествляется значением типа HANDLE. Для создания нити используется системный вызов CreateThread. В приведенном ниже фрагменте программы создается нить, HANDLE которой помещается в переменную hThread1. Идентификатор нити (четырехбайтовое целое число) записывается в переменную threadID1. Нить исполняет функцию run.

    #include <windows.h>
    
    // Prototype of thread body function
    DWORD WINAPI run(void* arg);
    
    int main() {
        HANDLE hThread1, hThread2;
        DWORD threadID1, threadID2;
        const char *arg1 = "Heads";
        const char *arg2 = "Tails";
    
        // Create the first thread
        hThread1 = CreateThread(
            NULL,          // pointer to thread attributes
            0,             // stack size - default
            &run,          // thread starting function
            (void *) arg1, // parameter of thread function
            0,             // creation flags
            &threadID1     // pointer to threadID (out)
        );
        . . .
    }
    
    DWORD WINAPI run(void* arg) {
        // Thread function
        . . .
    }
    
    Для ожидания завершения нити используется системный вызов WaitForSingleObject:
        WaitForSingleObject(hThread1, INFINITE);
    
    После завершения работы нити надо обязательно закрыть ее HANDLE, иначе операционная система не освободит память, которая используется под структуры данных, связанные с нитью.
        CloseHandle(hThread1);
    

    Объекты синхронизации

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

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

    Наиболее часто используется объект синхронизации mutex, от слов MUTual EXclusive — взаимно исключающий. Он служит для защиты критических данных. Мьютекс может принадлежать лишь одному процессу или нити. Нить или процесс, прежде чем начать модификацию или чтение критических данных, пытается сначала захватить мьютекс. Если он свободен (или уже принадлежит данной нити), то мьютекс захватывается нитью и помечается занятым; в противном случае нить приостанавливается до тех пор, пока другая нить, которой принадлежит мьютекс в данный момент, не освободит его. После захвата мьютекса нить может работать с критическими данными. По окончании работы нить освобождает мьютекс. Таким образом, использование мьютекса исключает одновременную работу с критическими данными двух и более нитей.

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

    Чтобы проиллюстрировать понятие мьютекса, можно привести следующие примеры "из жизни". Мьютексом может служить ключ от комнаты, в которую может войти только один человек (туалет и т.п.). Еще один красивый пример можно увидеть в фильме BBC о железных дорогах в Англии XIX века. Они были в основном однопутными и использовались попеременно поездами, движущимися в разных направлениях. Чтобы исключить встречное столкновение поездов, использовался так называемый Token (жетон, опознавательный знак), представлявший собой большое металлическое кольцо с латунным знаком на нем. Машинист поезда не имел право выехать на перегон между станциями, пока он не получал в свои руки это кольцо (его передавал машинисту дежурный по станции, когда поезд проходил мимо станции на малом ходу). Проехав перегон, машинист оставлял это кольцо на следующей станции, и потом встречный поезд привозил его обратно. Таким образом, кольцо защищало перегон между станциями и делало невозможным выезд на перегон одновременно двух поездов.

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

    Использование объектов типа mutex для синхронизации процессов и нитей

    Мьютексы бывают именованные и неименованные. Первые можно использовать для синхронизации процессов и нитей, вторые — только для синхронизации нитей. Рассмотрим лишь второй случай.

    В OC Unix использование нитей и мьютексов описано в стандарте POSIX, программы, работающие с этими объектами, используют библиотеку pthread (первая буква "p" — от слова POSIX). Программы на C/C++ должны подключать стандартный заголовочный файл "pthread.h". Объект mutex имеет тип pthread_mutex_t, должен описываться как глобальный и размещаться в статической памяти. Для его инициализации используется специальная константа PTHREAD_MUTEX_INITIALIZER (для мьютексов, реализация которых может не быть рекурсивной) или PTHREAD_RECURSIVE_MUTEX_INITIALIZER_NP (для рекурсивных мьютексов). Например, в приведенном ниже фрагменте описан мьютекс, содержащийся в переменной mtx.

    #include <pthread.h>
    
    static pthread_mutex_t mtx =
        PTHREAD_RECURSIVE_MUTEX_INITIALIZER_NP;
    

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

        pthread_mutex_lock(&mtx);
        // Критические действия
        . . .
        pthread_mutex_unlock(&mtx);
    

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

        pthread_mutex_destroy(&mtx);
    

    (Отметим, что при статической инициализации мьютекса с помощью константы PTHREAD_MUTEX_INITIALIZER или PTHREAD_RECURSIVE_MUTEX_INITIALIZER_NP системный объект типа мьютекс на самом деле создается и инициализируется при первом обращении к нему в функции pthread_mutex_lock. Можно также явно создать и инициализировать мьютекс, используя функцию pthread_mutex_init.)

    В OC MS Windows (вернее, при использовании Win32 API) мьютекс, как и процесс, нить и т.п., является объектом ядра системы и отождествляется значением типа HANDLE. Мьютекс создается и инициализируется с помощью функции CreateMutex:

    #include <Windows.h>
    
    static HANDLE hMutex = NULL;
    
    int main() {
        . . .
        hMutex = CreateMutex(
            NULL,   // default security attributes
            FALSE,  // initially not owned
            NULL    // unnamed mutex
        );
        if (hMutex == NULL) {
            printf(
                "Cannot create a mutex: error %d\n",
                GetLastError()
            );
            exit(-1);
        }
        . . .
    }
    

    В Win32 все мьютексы рекурсивные. Для захвата мьютекса в MS Windows используется одна из двух универсальных функций ожидания, применимых ко всем объектам ядра системы, которые могут находиться в сигнальном и несигнальном состояниях. Это функции WaitForSingleObject и WaitForMultipleObjects. В первой функции задается лишь один объект и функция ожидает, когда он перейдет в сигнальное состояние (до этого момента исполнение нити приостанавливается). Во второй функции можно задать целый массив объектов, причем вызов ее имеет два варианта (которые задаются третьим параметром типа BOOL): в первом варианте (третий параметр FALSE) функция ждет, пока хотя бы один из указанных объектов перейдет в сигнальное состояние; во втором варианте (третий параметр TRUE) функция ждет до тех пор, пока все указанные объекты перейдут в сигнальное состояние. Последний аргумент функций ожидания задает таймаут в миллисекундах, специальная константа INFINITE используется для потенциально бесконечного ожидания.

    Считается, что свободный мьютекс находится в сигнальном состоянии, захваченный — в несигнальном. Захват мьютекса выполняется с помощью функции WaitForSingleObject, освобождение — с помощью функции ReleaseMutex.

        WaitForSingleObject(hMutex, INFINITE);
        // Критические действия
        . . .
        ReleaseMutex(hMutex);
    

    (Здесь для простоты мы опустили обработку статуса завершения функции WaitForSingleObject. Она может завершиться успешно и вернуть значение WAIT_OBJECT_0, при неудаче возвращается значение WAIT_FAILED, при завершении по таймауту — значение WAIT_TIMEOUT; если нить, владевшая мьютексом, завершилась аварийно, не освободив его — значение WAIT_ABANDONED.)

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

        CloseHandle(hMutex);
    

    Критические секции

    В теории программирования критической секцией с некоторым именем ("A", например) называется отмеченный данным именем участок кода, который в любой момент времени может исполняться только одной нитью или процессом. Если нить вошла в критическую секцию с именем "A", то любая другая нить при попытке войти в критическую секцию с тем же именем приостанавливается системой, пока первая нить не покинет критическую секцию. Одним и тем же именем могут быть помечены несколько участков кода, которые представляют одну и ту же критическую секцию.

    Очевидно, что критические секции могут быть смоделированы с помощью мьютексов: критической секции с данным именем соответствует мьютекс, который надо захватывать при входе в критичекую секцию и освобождать при выходе. Тем не менее в MS Windows (точнее, в Win32 API) имеется специальный объект типа CRITICAL_SECTION, который используется для моделирования критических секций. Работа с ним чуть проще, чем с мьютексом, поскольку критические секции, в отличие от мьютексов, используются только для синхронизации нитей одного процесса, а именованные мьютексы могут использоваться и нитями разных процессов. К тому же вход в критичекскую секцию, выполняемый функцией EnterCriticalSection, в отличие от захвата мьютекса (функция WaitForSingleObject) не требует анализа возвращаемого значения. Благодаря этому при программировании с использованием Win32 API критические секции используются даже чаще, чем мьютексы.

    Объект типа CRITICAL_SECTION описывается как глобальный в статической памяти. Перед первым использованием критическую секцию нужно инициализировать с помощью функци InitializeCriticalSection, а по окончании использования — удалить, использовав функцию DeleteCriticalSection:

    #include <Windows.h>
    
    static CRITICAL_SECTION critSect;
    . . .
    int main() {
        InitializeCriticalSection(&critSect);
        . . .
    
        DeleteCriticalSection(&critSect);
        return 0;
    }
    

    Вход в критическую секцию выполняется с помощью функции EnterCriticalSection; покидая критическую секцию, нить вызывает функцию LeaveCriticalSection:

        EnterCriticalSection(&critSect);
        // Критическая секция
        . . .
        LeaveCriticalSection(&critSect);
    

  6. Объекты синхронизации — продолжение.
    Проблемы, возникающие при параллельной работе. Задача об обедающих философах

    Семафоры

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

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

    Такой простейший семафор в компьютерах моделируется целочисленной переменной S, которая может принимать два значения: значение S=1 означает, что семафор открыт (сигнальное состояние); значение S=0 означает, что семафор закрыт. Нить, ждущая семафор, приостанавливается, если он не находится в сигнальном состоянии (т.е. если S=0). При переходе семафора в сигнальное состояние S=1 операционная система возобновляет работу нити, а значение семафора уменьшается на 1 (S снова становится равным нулю). Для перевода семафора в сигнальное состояние S=1 какая-нибудь нить должна выполнить специальную команду, увеличивающую значение S на единицу.

    В общем случае семафор — это целочисленная переменная S, принимающая неотрицательные значения. При этом считается, что семафор закрыт, если значение S=0, и открыт, если значение S>0. Обычно программа пишется таким образом, что семафор S не может принимать значений, превосходящих заранее заданное максимальное значение M. (В Win32 API при создании семафора указывается его максимальное значение.) Каждая нить при ожидании и прохождении семафора уменьшает его значение на единицу. Можно рассмотреть следующую аналогию: имеется музей, работающий в зимнее время, и при нем гардероб, в котором 100 номерков. Посетитель музея должен сначала сдать верхнюю одежду в гардероб и получить номерок. Если номерки закончились, т.е. в музее уже 100 посетителей, то очередной посетитель ждет в гардеробе, пока кто-нибудь из предыдущих посетителей не сдаст номерок в гардероб и не получит назад свою одежду; только тогда новый посетитель сможет пройти в музей. Здесь значением семафора является текущее количество свободных номерков в гардеробе (начальное значение 100); каждый посетитель, проходящий в музей, уменьшает это значение на единицу; посетитель, покидающий музей, увеличивает значение на единицу. Значение семафора никогда не может превысить начального значения 100.

    Семафоры в Unix

    В Unix'е для описания семафора используется тип sem_t. Семафор создается с помощью функции sem_init. Пример:

    #include <semaphore.h>
    
    static sem_t mySemaphore;
    . . .
    int main() {
        . . .
        sem_init(
            &mySemaphore,   // semaphore
            0,              // shared between processes: No
            1               // initial value: semaphore is open
        );
        . . .
    }
    
    Объект семафор чаще всего описывается как глобальный в статической памяти. При создании семафора указывается его начальное значение (1 в данном случае) и флаг, определяющий, является ли семафор разделяемым между разными процессами (в данном случае нет). Если семафор используется разными процессами, то он должен быть помещен в разделяемую память (shared memory). Если нет, то он используется для синхронизации нитей, принадлежащих одному и тому же процессу.

    По окончании использования семафор должен быть освобожден с помощью функции sem_destroy:

        sem_destroy(&mySemaphore);
    

    Нить увеличивает значение семафора на единицу с помощью функции sem_post:

        sem_post(&mySemaphore);
    
    Ожидание семафора выполняется с помощью функции sem_wait:
        sem_wait(&mySemaphore);
    
    Если значение семафора больше нуля, то оно уменьшается на единицу и нить продолжает работать. В противном случае нить переводится в состояние ожидания, потенциально бесконечного (вызов sem_wait в Unix'е не имеет таймаута). Нить пробуждается, когда какая-либо другая нить выполнит sem_post для данного семафора. Если блокировка нити в случае нулевого значения семафора нежелательна, то можно использовать функцию sem_trywait, которая завершается мгновенно, возвращая ненулевое значение, если семафор был ненулевым (в этом случае она уменьшает его значение на 1), или 0, если семафор нулевой.

    Файл "semExample.cpp" содержит пример программы, использующей семафоры для синхронизации нитей. Создаются две нити. Первая вводит строку с клавиатуры терминала и помещает ее в массив в статической памяти. После этого вторая нить инвертирует введенную строку и печатает перевернутую строку на экран. Эти действия повторяются в бесконечном цикле. Первая нить сообщает второй о том, что строка введена, с помощью семафора "inputReady". Вторая нить информирует первую о том, что она готова принять следующую строку, используя семафор "invertReady".

    Семафоры в MS Window

    В Win32 API, в отличие от Unix, при создании семафора указывается его максимальнное значение. Пример:

    static HANDLE hMySemaphore = NULL;
    
    int main() {
        . . .
        // Initialize the semaphore
        hMySemaphore = CreateSemaphore( 
            NULL,   // default security attributes
            8,      // initial count
            8,      // maximal count
            NULL    // unnamed semaphore
        );
        . . .
    }    
    
    Здесь создается семафор, допускающий одновременный доступ к критической информации не более восьми нитей (третий параметр функции). Семафор неименованный, т.е. он может использоваться только нитями одного процесса. Начальное значение семафора также равно 8. Возможен вариант, когда начальное значение нулевое (семафор закрыт), и можно его в подходящий момент открыть, увеличив его на произвольное число (конечно, так, чтобы не превысить заданный максимум). Пример:
        // Initialize the semaphore
        hMySemaphore = CreateSemaphore( 
            NULL,                                  
            0,      // initial count: closed!
            8,      // maximal count
            NULL                               
        );
        . . .
        ReleaseSemaphore( 
            hMySemaphore,   // handle to semaphore
            8,              // increase count by 8
            NULL            // do not need the previous count
        );
    

    Для ожидания семафора нить использует универсальную функцию WaitForSingleObject, применимую для всех объектов синхронизации. Пример:

        WaitForSingleObject(hMySemaphore, INFINITE);
    
    Второй параметр задает таймаут в миллисекундах, в данном случае он бесконечный.

    Для увеличения семафора используется функция ReleaseSemaphore; в отличие от Unix-функции sem_post, она может увеличить значение семафора на число, большее единицы — это число задается вторым параметром функции:

        ReleaseSemaphore( 
            hMySemaphore,   // handle to semaphore
            1,              // increase count by one
            NULL            // not interested in previous count
        );
    

    По окончании использования семафора мы закрываем его хендл:

        CloseHandle(hMySemaphore);
    

    Объекты синхронизации "События" (Events)

    При программировании под Win32 API гораздо чаще, чем семафоры, используются объекты синхронизации типа "Событие" (Event). По сути дела, события — это простейшие семафоры, принимающие только 2 значения: 0 и 1 (т.е. максимальное значение семафора ограничено единицей). Таким образом, объект типа событие может находиться лишь в двух состояниях: сигнальном (значение 1) и несигнальном (значение 0). Событие можно представлять себе как лампочку, которая может гореть (сигнальное состояние) или быть потушена (несигнальное). Можно представить себе кабинет врача в поликлинике и очередь пациентов, ожидающих приема. Когда врач освобождается и готов принять очередного пациента, он зажигает лампочку над дверью, что означает приглашение войти очередному пациенту. Потушенная лампочка означает, что врач занят.

    Объекты "события" в MS Windows бывают двух типов: manual-reset events (события, сбрасываемые вручную) и auto-reset events (события, сбрасывающиеся автоматически). Семафоры соответствуют автоматическим событиям. Тип auto-reset означает, что, когда некоторая нить, ждавшая перехода события в сигнальное состояние, активизируется операционной системой, то событие автоматически переходит в несигнальное состояние. (Аналогия: когда поезд проходит зеленый семафор, то семафор автоматически переключатся на красный.) Автоматически сбрасываемое событие при переходе в сигнальное состояние всегда пробуждает только одну нить: если несколько нитей ждали события, то активизируется лишь одна из них (причем нельзя сказать, какая именно, порядок очереди FIFO здесь не гарантируется).

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

    Для работы с событиями используются следующие функции. CreateEvent создает объект типа событие, возвращая его хендл. Пример:

        HANDLE hMyEvent;
        . . .
        hMyEvent = CreateEvent( 
            NULL,   // LPSECURITY_ATTRIBUTES - default                                
            FALSE,  // bManulReset is false => auto-reset
            FALSE,  // bInitialState - nonsignaled
            NULL    // pName is NULL => not named                           
        );
    
    Здесь создается событие, сбрасываемое автоматически (второй параметр FALSE), находящееся изначально в несигнальном состоянии (третий параметр) и не имеющее имени (четвертый параметр). Права доступа к созданному объекту определяются по умолчанию (первый параметр). Отсутствие имени у объекта означает, что он может использоваться только нитями одного процесса — того, который создал этот объект. Это общее правило касается всех объктов синхронизации (мьютексов, семафоров, событий и др.): если их нужно использовать нитями разных процессов, то они должны иметь глобальные имена, по которым процессы их могут находить и использовать. В частности, если именованный объект уже существует (создан другим процессом), то при вызове функции CreateEvent с указанием его имени объект не создается заново, а текущий процесс лишь открывает хендл для доступа к нему (для открытия уже существующего именованного события можно также использовать функцию OpenEvent).

    Событие переводится в сигнальное состояние с помощью функции SetEvent:

        SetEvent(hMyEvent); 
    
    Вызов функции SetEvent соответствует включению лампочки (в англоязычной литературе часто используется выражение "fire event", зажечь событие). Можно также использовать функцию PulseEvent, которая на мгновение переводит событие в сигнальное состояние и тут же его сбрасывает обратно в несигнальное, это соответствует однократному миганию лампочки. При этом в случае автоматического события пробуждается лишь одна нить из числа ждущих события, в случае события, сбрасываемого вручную — все нити.

    Функцию PulseEvent имеет смысл использовать лишь для события, сбрасываемого вручную (для автоматического события функции SetEvent и PulseEvent эквивалентны). Более того, Microsoft вообще не рекомендует больше использовать функцию PulseEvent (она оставлена в системе лишь для совместимости с предыдущими версиями), т.к. возможны некоторые ситуации, в которых она приводит к нежелательным последствиям (ждущая нить может не быть активизирована). Вместо этого рекомендуется для синхронизации использовать более новую технологию условных переменных (condition variables), которую мы здесь рассматривать не будем.

    Перевод события в несигнальное состояние выполняется с помощью функции ResetEvent:

        ResetEvent(hMyEvent); 
    
    (она, как правило, используется лишь для событий, сбасываемых вручную).

    Ситуация Deadlock. Задача Дийкстры об обедающих философах и ее возможные решения

    . . .


  7. Компьютерные сети

    . . .


  8. Файловые системы

    Зачем нужны файловые системы? У первых компьютеров их не было, данные непосредственно читались с диска (магнитной ленты, барабана и т.п.) в виде записей. Файловая система позволяет удобно огранизовать доступ к многообразным данным, расположенном на одном носителе. Файл — это набор данных, имеющий свое имя, с ним можно работать либо как с целостным объектом (создавать, удалять, перемещать, копировать, переименовывать и т.п.), либо читать или записывать его содержимое.

    Отметим, что файл может отождествляться не только именем. Примером является ранняя версия файловой системы HFS компьютеров Apple Macintosh, в которой файл определялся двумя числами (стандартные диалоги открытия файлов возвращали именно пару чисел для доступа к файлу).

    Прежде чем перейти к устройству файловых систем, рассмотрим, что представляет собой диск. У него есть пластины, у каждой пластины две поверхности и соответственно используются две считывающие головки. Информация записывается на дорожках, которые представляют собой концентрические окружности. Набор таких дорожек, расположенных друг над другом на разных пластинах и их поверхностях, обычно называют цилиндром. Каждая дорожка делится на сектора, стандартное число секторов 64 (они нумеруются с единицы, в отличие от цилиндров и головок). Чаще всего в одном секторе записывается 512 байтов. Сектор — минимальная единица записи и чтения для диска.

    Раньше для адресации секторов на диске использовалась схема CHS — Cylinder, Head, Sector: для указания сектора нужно было указать номера силиндра, головки и сектора на дорожке. В современных дисках она заменена на схему LBA: Logical Block Address. В этой схеме каждый сектор получает свой собственный уникальный номер, начиная с нуля. Сектора нумеруются последовательно по цилиндрам и головкам. С этой точки зрения диск можно рассматривать просто как массив секторов, т.е. блоков размером в 512 байтов. Все современные контроллеры дисков используют логическую адресацию секторов LBA, скрывая от операционной системы детали физического устройства диска.

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

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

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

    Файловая система FAT32

    . . .

    Файловые системы Linux: понятие виртуальной файловой системы, inodes, файловые системы EXT2 и EXT3

    . . .


Примеры программ

Журнал группы ПМиИ-3, 2015