- •Введение
- •Требования к содержанию лекций
- •Организация лабораторного практикума
- •Программа лабораторного практикума
- •Лабораторная работа 1. Краткосрочное планирование задач
- •Лабораторная работа 2. Замещение областей памяти
- •Лабораторная работа 3. Синхронизация процессов/потоков
- •Лабораторная работа 5. Файловые системы
- •Основные понятия и определения
- •Литература
- •Распределение ресурса «центральный процессор»
- •Процесс и поток – типы ресурсов операционной системы
- •Классификация ОС по признаку поддержки процессов и потоков
- •1. Однозадачные ОС
- •2. Многозадачные ОС без поддержки многопоточности
- •3. Многозадачные ОС с поддержкой многопоточности
- •Реализация многопоточности внутри программы пользователя
- •Состояния потока
- •Дескрипторы процессов и потоков
- •Операции над процессами
- •1. Создание процесса
- •2. Завершение процесса
- •Операции над потоками
- •1. Создание потока
- •2. Завершение потока
- •Планирование
- •Модель поведения процесса с одним потоком
- •Критерии оценки алгоритмов планирования
- •Алгоритмы планирования в системах пакетной обработки данных
- •«Кратчайшая задача - первая» (Shortest Job First, SJF)
- •«Наименьшее оставшееся время выполнения»
- •Алгоритмы планирования в интерактивных системах
- •«Циклическое планирование» (Round Robin, RR)
- •«Приоритетное планирование»
- •«Самый короткий поток - следующий»
- •«Гарантированное планирование»
- •Лотерейное планирование
- •Планирование с использованием многоуровневых очередей
- •Алгоритм планирования Windows NT
- •Алгоритм планирования UNIX
- •Алгоритм планирования UNIX System V Release 4
- •Алгоритм планирования Linux (версия ядра 2.2 и ниже)
- •Заключение
- •Управление памятью
- •Архитектура оперативной памяти
- •Способ описания физической памяти
- •Алгоритм обеспечения пространственного мультиплексирования
- •Схема с фиксированными разделами
- •Оверлейная структура
- •Свопинг
- •Схема с переменными разделами
- •Общие вопросы управления страничной памятью
- •Алгоритмы замещения страниц
- •Оптимальный алгоритм
- •Алгоритм FIFO - Выталкивание первой пришедшей страницы
- •Алгоритм Second-Chance - Вторая попытка
- •Алгоритм «часы»
- •Заключение
- •Взаимодействие потоков – передача данных и синхронизация
- •Взаимодействие потоков
- •Критическая секция
- •Задача взаимного исключения
- •Семафоры
- •Тупики
- •Синхронизирующие объекты ОС
- •Сигналы
- •Обмен сообщениями (message passing) (Хоар, 1978 год)
- •Реализация взаимоисключений
- •Алгоритм Петерсона
- •Алгоритм булочной (Bakery algorithm)
- •Аппаратная поддержка взаимоисключений
- •Команда Test-and-Set (Проверить и присвоить 1)
- •Команда Swap (Обменять значения)
- •Классические задачи взаимодействия потоков
- •Задача "Производитель-потребитель"
- •Задача "Читатели-писатели"
- •Задача "Обедающие философы"
- •Проблема спящего брадобрея
- •Передача данных между взаимодействующими потоками
- •Архитектура файловой системы
- •Файлы с точки зрения пользователя
- •Типы объектов файловой системы
- •Имена объектов файловой системы
- •Операции над файлами
- •Директории – логическая структура файлового архива
- •Операции над директориями
- •Пользовательский интерфейс системы управления файлами
- •Виртуальная Файловая Система
- •Принцип работы
- •Структура VFS
- •Типы объектов в VFS
- •Символьные связи (мягкие ссылки)
- •Именованные конвейеры (именованные каналы)
- •Реализация VFS
- •Лабораторная работа 1. Краткосрочное планирование задач
- •Симулятор многозадачной системы
- •Модель эксперимента
- •Выполнение лабораторной работы
- •Архитектура программной лаборатории
- •Проведение эксперимента
- •Архитектура планировщика в Linux (Ядро 2.4.18)
- •Очередь процессов
- •Кванты времени центрального процессора
- •Выбор процесса на исполнение
- •Вычисление эффективного приоритета и размера кванта
- •Вытеснение процесса
- •Изменение алгоритма планирования
- •Компиляция и установка ядра Linux
- •Литература по лабораторной работе 1
- •Лабораторная работа 2. Замещение областей памяти
- •Симулятор многозадачной системы
- •Управление памятью в Linux (ядро 2.4.18)
- •Описание физической памяти в Linux
- •Узлы
- •Зоны
- •Отметки уровня воды (watermarks)
- •Страницы
- •Адресное пространство процесса
- •Страничные сбои
- •Выделение памяти по запросу
- •Подкачка по запросу
- •Демон выгрузки страниц (kswapd)
- •Кэш страниц
- •Добавление страниц в кэш страниц
- •Заполнения списка «холодных» страниц
- •Стратегия замещения страниц
- •Изменение стратегии замещения
- •Литература по лабораторной работе 2
- •Механизмы межпроцессного взаимодействия ОС UNIX
- •Семафоры.
- •Очереди сообщений.
- •Работа с разделяемой памятью.
- •Механизмы межпроцессного взаимодействия ОС Windows
- •Wait-функции
- •События
- •Ожидаемые таймеры
- •Семафоры
- •Мьютексы
- •Литература по лабораторным работам 3-4
- •Лабораторная работа 5. Файловые системы
- •Предлагаемые к реализации файловые системы
- •Файловая система 1
- •Файловая система 2
- •Файловая система 3
- •Симулятор работы с файловой системой
- •Постановка задачи
- •Операции над файлами
- •Операции над директориями
- •Требования к лабораторной работе
- •Архитектура программной лаборатории
- •Обзор архитектуры модуля поддержки файловой системы в Linux
- •Модули драйвера файловой системы Minix
- •Описание суперблока файловой системы
- •Описание индексного дескриптора (inode)
- •Основной файл заголовков
- •Исходные тексты функций работы с индексным дескриптором
- •Исходные тексты функций работы с объектами ФС разных типов
- •Другие модули
- •Реализация драйвера файловой системы
- •Литература по лабораторной работе 5
- •Литература
- •Дополнительная литература
Лабораторный практикум по курсу "Операционные системы"
Драйвер создается из следующих компонентов, принадлежащих каталогу исходных текстов файловой системы или каталогу исходных текстов VFS:
1.Описание суперблока файловой системы - include/linux/type_fs.h описывает информацию в том виде, в каком она хранится на диске, include/linux/type_fs_sb.h содержит описание структуры, которая добавляется к стандартной структуре ядра, описывающей суперблок.
2.Описание inode - include/linux/type_fs_i.h содержит описание структуры inode на диске и структуры, которая добавляется к стандартной структуре ядра, описывающей inode.
3.Основной include файл - include/linux/type_fs.h.
4.Исходные тексты функций работы с inode - fs/fstype/inode.c. Структура inode_operations
используется для операций c inode функциями VFS.
5.Исходные тексты функций работы с объектами файловой системы разных типов – файлами, каталогами, символьными ссылками и т.д. - fs/fstype/file.c, dir.c, symlink.c и т.д. Структуры типа struct file_operations используется для этих операций функциями VFS.
6.Операции, управляющие распределением и освобождением inode и блоков хранения данных - fs/fstype/bitmap.c
7.Операции с inode, связанные с именами, такие как создание и удаление имени, относящегося к inode, переименование и т.п.
Во время подключения файловой системы fstype_read_super заполняет структуру super_block информацией, полученной с поддерживаемого устройства. Поле s_op структуры содержит указатель на fstype_sops, используемый кодом VFS для выполнения операций над суперблоком.
Отключение происходит с помощью do_umount, включающем запуск fstype_put_super.
При доступе к файлу, fstype_read_inode заполняет общую системную inode структуру полями из fstype_inode. Поле inode.i_op заполняется указателями на реализации функций обработки inode для данной файловой системы.
Рассмотрение пунктов проще всего произвести на примере. Используем для этого файловую систему Minix.
Модули драйвера файловой системы Minix
Описание суперблока файловой системы
Формат хранения суперблока файловой системы на внешнем носителе содержится в файле include/linux/minix_fs.h. Суперблок содержит общую информацию о файловой системе – число файловых дескрипторов и т.д.
struct minix_super_block { __u16 s_ninodes; __u16 s_nzones; __u16 s_imap_blocks; __u16 s_zmap_blocks;
__u16 s_firstdatazone; __u16 s_log_zone_size; __u32 s_max_size;
Учебно-исследовательская лаборатория «Информационные технологии» 153
Лабораторный практикум по курсу "Операционные системы"
__u16 s_magic; __u16 s_state; __u32 s_zones;
};
При монтировании файловой системы в ядре создается суперблок VFS для управления файловой системой. Его формат определен в файле linux/fs.h
struct super_block { |
|
struct list_head |
s_list; |
kdev_t |
s_dev; |
unsigned long |
s_blocksize; |
unsigned char |
s_blocksize_bits; |
unsigned char |
s_dirt; |
… |
|
union { |
|
struct minix_sb_info struct ext2_sb_info struct ext3_sb_info struct msdos_sb_info
…
} u;
};
minix_sb; ext2_sb; ext3_sb; msdos_sb;
Одним из полей структуры является объединение (union u;), предназначенное для хранения информации, зависимой от конкретного типа файловой системы. Состав и формат этих данных определяются в файле include/linux/ minix_fs_sb.h
struct minix_sb_info {
unsigned long s_ninodes; unsigned long s_nzones; unsigned long s_imap_blocks; unsigned long s_zmap_blocks; unsigned long s_firstdatazone; unsigned long s_log_zone_size; unsigned long s_max_size;
int s_dirsize; int s_namelen; int s_link_max;
struct buffer_head ** s_imap; struct buffer_head ** s_zmap;
154 Учебно-исследовательская лаборатория «Информационные технологии»
Лабораторный практикум по курсу "Операционные системы"
struct buffer_head * s_sbh; struct minix_super_block * s_ms; unsigned short s_mount_state; unsigned short s_version;
};
Описание индексного дескриптора (inode)
Файл include/linux/minix_fs_i.h должен содержит описание структуры, которая добавляется к стандартной структуре ядра, описывающей индексный дескриптор.
struct minix_inode_info { union {
__u16 i1_data[16]; __u32 i2_data[16];
} u;
};
Основной файл заголовков
Основной файл заголовков include/linux/minix_fs.h содержит следующие элементы
-определения констант, используемых при работе с файловой системой;
-описание формата хранения индексного дескриптора на диске struct minix2_inode {
__u16 i_mode; |
// права доступа |
|
__u16 i_nlinks; |
// число жестких ссылок (имен) |
|
__u16 i_uid; |
// идентификатор владельца |
|
__u16 i_gid; |
//идентификатор группового владельца |
|
__u32 i_size; |
// размер |
|
__u32 |
i_atime; |
// время последнего доступа |
__u32 |
i_mtime; |
// время последнего изменения inode |
__u32 |
i_ctime; |
// время последнего изменения данных |
__u32 |
i_zone[10]; |
// описания расположения файла на ВН |
};
-описание формата хранения суперблока файловой системы на внешнем носителе (как мы уже сказали выше);
-описание формата хранения записи о дочернем объекта в директории (обратите внимание: в директории хранится только имя объекта файловой системы и номер его индексного дескриптора, все остальное хранится в индексном дескрипторе)
struct minix_dir_entry { __u16 inode;
Учебно-исследовательская лаборатория «Информационные технологии» 155
Лабораторный практикум по курсу "Операционные системы"
char name[0];
};
-прототипы всех функций работы с файловой системой, которые могут потребоваться подсистеме VFS;
-объявление структур, содержащих адреса функций работы с элементами файловой системы; эти структуры объявляются в файлах include/linux/file.c, include/linux/dir.c, include/linux/namei.c, используются при присвоении значений полям индексного дескриптора VFS: inode->i_op (операции над inode) и inode->f_op (операции над объектом файловой системы; впоследствии указанные поля используются подсистемой VFS для вызова функций чтения/записи файла и т.д.;
extern struct inode_operations minix_file_inode_operations; extern struct inode_operations minix_dir_inode_operations; extern struct file_operations minix_file_operations;
extern struct file_operations minix_dir_operations; extern struct dentry_operations minix_dentry_operations;
Исходные тексты функций работы с индексным дескриптором
Файл fs/minix/inode.c содержит определение функций работы с индексным дескриптором (создание, удаление, чтение, запись и т.д.), функции для работы с суперблоком и определение структуры, в которой эти функции регистрируются.
static struct super_operations minix_sops = { read_inode: minix_read_inode, write_inode: minix_write_inode, delete_inode: minix_delete_inode, put_super: minix_put_super, write_super: minix_write_super, statfs: minix_statfs, remount_fs: minix_remount,
};
Также в данном файле определены функции блочного ввода-вывода и структура с их перечислением.
static struct address_space_operations minix_aops = { readpage: minix_readpage,
writepage: minix_writepage, sync_page: block_sync_page, prepare_write: minix_prepare_write, commit_write: generic_commit_write, bmap: minix_bmap
};
156 Учебно-исследовательская лаборатория «Информационные технологии»
