Указания методические к выполнению контрольной работы №2 по предмету «Операционные системы» Министерство образования и науки Украины Криворожский государственный педагогический университет С.А. Семериков Методические указания к выполнению контрольной работы №2 по предмету «Операционные системы» Кривой Рог 2009 Содержание Вводные положения.................................................................. 3 Тематика курсовых работ по курсу «Системное программирование» 4 Рекомендуемая литература..................................................... 22 Пример оформления титульного листа................................. 24 Пример оформления содержания........................................... 25 Вводные положения 1. Название контрольной работы определяется содержанием ее первой (теоретической) части. 2. Структура работы: Титульный лист содержит название работы и сведения об авторе (объем – до 1 стр.). Содержание (объем – до 1 стр.). Введение содержит общую характеристику выполненной работы (объем – до 1 стр.). Первая часть сжато раскрывает сущность вопроса, теоретические положения иллюстрируются примерами их реализации в конкретных операционных системах (объем – до 10 стр.). Вторая часть содержит описание алгоритмов решения предложенных задач, краткую характеристику использованных нестандартных инструментальных средств и фрагменты диалога с пользователем (объем – до 5 стр.). Заключение содержит перечень полученных результатов, выводы по реферированному материалу первой части и авторским программам второй части (объем – до 1 стр.). Список литературы составляется из библиографических описаний использованных источников (объем – до 1 стр.). Приложение состоит из листингов описанных во второй части программ (объем – до 20 стр.). 3. Полный текст контрольной работы, исходные тексты программ и исполняемые файлы прилагаются на диске. Текст должен быть в формате документа OpenOffice со следующими параметрами форматирования: размер страницы – А5 (14,8 см х 21 см), ориентация – книжная, поля – верхнее – 1,8 см, нижнее – 1,8 см, слева – 2,1 см, справа – 1,8 см шрифт основного текста – пропорциональный, размер 11 пт, шрифт листингов – моноширинный, размер 10 пт. выравнивание текста – по ширине, отступ : слева – 0 см, справа – 0 см, интервал : перед – 0 см, после – 0 см, первая строка – отступ 0,7 см, межстрочный интервал – одинарный. Допускается плоский текст в кодировке KOI8-R, рисунки – в форматах ps, gif. Тематика контрольных работ по курсу «Операционные системы» № Название, задание первой части Задание второй части 1. Системная архитектура Windows 2000 1. Напишите программу, определяющую, возвращает ли fstat количество байт в FIFO в качестве поля st_size структуры stat. 2. Напишите программу, отсекающую n пробелов в начале каждой строки (или n первых любых символов). Учтите, что в файле могут быть строки короче n (например, пустые строки). 3. Составьте аналог команды dump. 4. Напишите программу, печатающую: свои аргументы, переменные окружения, информацию обо всех открытых ею файлах и используемых каналах. 5. Напишите программу для определения того, что возвращает функция select при проверке возможности записи в дескриптор канала, у которого закрыт второй конец. 6. Создайте программу получения записи файла паролей по имени пользователя. 7. Напишите программу, выдающую файл на экран порциями по 20 строк и ожидающую нажатия клавиши. Усложнения: – добавить клавишу для возврата к началу файла. – используя библиотеку termcap, очищать экран перед выдачей очередной порции текста. – напишите эту программу, используя библиотеку curses. – используя curses, напишите программу параллельного просмотра 2-х файлов в 2-х неперекрывающихся окнах. – то же в перекрывающихся окнах. 8. Создайте простейший командный интерпретатор. 9. Создайте программу эхо-сервера и тестовый клиент для нее. 10. Напишите программу, которая вставляет строки, введенные с клавиатуры, в список. Память под узлы списка выделяйте динамически с использованием malloc(3). Ввод завершается, когда в начале строки вводится точка (.). Затем все строки из списка выводятся на экран. Подсказка: Объявите массив символов размера, достаточного чтобы вместить самую длинную введенную строку. Используйте gets(3), чтобы прочитать строку, и strlen(3), чтобы определить ее длину. Помните, что strlen(3) не считает нулевой символ, завершающий строку. После определения длины строки, выделите блок памяти нужного размера и внесите новый указатель в список. 2. Архитектура традиционных UNIX-систем 1. Составьте программу, центрирующую строки файла относительно середины экрана, т.е. добавляющую в начало строки такое количество пробелов, чтобы середина строки печаталась в 40-ой позиции (считаем, что обычный экран имеет ширину 80 символов). 2. Составьте программу, вычисляющую значение командной строки, представляющей собой обратную польскую запись арифметического выражения. Например, 20 10 5 + * вычисляется как 20 * (10 + 5) . 3. Составьте аналог команды touch. 4. Напишите программу, выделяющую n-ое поле из каждой строки файла. Поля разделяются двоеточиями. Предусмотрите задание символа-разделителя из аргументов программы. Используйте эту программу для выделения поля "домашний каталог" из файла /etc/passwd. 5. Составьте аналог команды find. 6. Напишите программу, переносящую слишком длинные строки. Слова разбивать нельзя (неумещающееся слово следует перенести целиком). Ширину строки считать равной 60. 7. Составьте аналог команды echo. 8. Составьте аналог команды rm. 9. Портируйте приведенную в приложении к лабораторной работе netlab5 программу под платформу Win32. 10. Реализуйте кольцевую очередь фиксированной длины в разделяемой памяти. Программа-производитель читает с клавиатуры и помещает прочитанный текст в виде записи в конец очереди. Потребитель берет записи из начала очереди. При обнаружении некоторого условия окончания, производитель должен перед выходом поместить в очередь запись-ограничитель. Когда потребитель получит такую запись, он также завершится. Совет: Очередь должна представлять собой массив записей. Таким образом, размер каждой записи не может превосходить фиксированную максимальную величину. 3. Безопасность Windows 2000 1. Составьте аналог команды cat. 2. Составьте аналог команды tee. 3. Составьте аналог команды cp. 4. Составьте аналог команды cat. 5. Составьте аналог команды wc. 6. Составьте аналог команды kill. 7. Создайте программу, реализующую функциональность гостевой книги. 8. Создайте Web-интерфейс к команде ftp. 9. Используя Web-интерфейс к команде netstat, получите список активных подключений. 10. Вы должны смоделировать производственную линию, производящую Виджеты. Каждый Виджет состоит из Детали С и Модуля 1. Модуль 1 состоит из Детали A и Детали B. Изготовление Детали A требует 2 секунды, Детали B – 3 секунды и Детали C – 4 секунды. Подсказка: элементы производственной линии должны быть представлены процессами. Используйте набор семафоров, по одному для каждой детали и модуля. Как только деталь или модуль произведены, добавляйте единицу к соответствующему семафору. Когда объект используется в на следующем этапе, вычитайте из того же семафора 1. Используйте sleep(3) для моделирования частоты, с которой производятся детали. 4. Архитектура современных UNIX-систем 1. Используя системный вызов stat, напишите программу, определяющую тип файла: обычный файл, каталог, устройство, FIFO-файл. 2. Напишите программу, разбивающую файл на два по вертикали: в первый файл попадает левая половина исходного файла, во второй – правая. Ширину колонки задавайте из аргументов main(). Если же аргумент не указан – 40 позиций. 3. Составьте программу-калькулятор, которая производит операции сложения, вычитания, умножения, деления; операнды и знак арифметической операции являются строковыми аргументами функции main. 4. Составьте аналог команды dir. 5. Напишите программу, печатающую свои параметры и значение первых десяти переменных окружения. 6. Напишите функцию, сжимающую подряд идущие пробелы в табуляции. 7. Составьте программу выдачи перекрестных ссылок, т.е. программу, которая выводит список всех идентификаторов переменных, используемых в программе, и для каждого из идентификаторов выводит список номеров строк, в которые он входит. 8. Составьте аналог команды chgrp. 9. Создайте программу файлового сервера с функциями просмотра списка файлов, загрузки файла на сервер/с сервера и клиент для нее. 10. Написать программу, которая анализирует текстовый файл, созданный текстовым редактором, таким как ed(1) или vi(1). После запроса, который предлагает ввести номер строки, с использованием printf(3) программа печатает соответствующую строку текста. Ввод нулевого номера завершает работу программы. Используйте open(2), read(2), lseek(2) и close(2) для ввода/вывода. Постройте таблицу отступов в файле и длин строк для каждой строки файла. Как только эта таблица построена, позиционируйтесь на начало заданной строки и прочтите точную длину строки. Предполагайте, что файл не длиннее сотни строк. Подсказка: Выберите или создайте текстовый файл с короткими строками. Помните, что первая строка начинается с нулевого отступа в файле. Найдите каждый символ перевода строки, запишите его позицию; в программе следует использовать вызов lseek(fd, 0L, 1). Для отладки распечатайте эту таблицу и сравните с таблицей, полученной вручную. Как только таблицы начнут совпадать, можно приступать к запросу номера строки. 5. Управление процессами в UNIX SVR4 1. Напишите функцию, расширяющую табуляции в подряд идущие пробелы. 2. Разработайте простую версию препроцессора для обработки операторов #include. 3. Составьте аналог команды dd. 4. Составьте программу, укорачивающую строки исходного файла до заданной величины и помещающую результат в указанный файл. 5. Разработайте простую версию препроцессора для обработки операторов #define. 6. Разработайте программу, укорачивающую строки входного файла до 60 символов без обрубания слов. 7. Напишите программу, обрабатывающую определения #ifdef, #else, #endif. Учтите, что эти директивы могут быть вложенными. 8. Составьте аналог команды mkdir. 9. Добавьте в программу счетчика посещений из лабораторной работы netlab6 возможность отслеживания различных страниц. Для этого можно использовать уникальный для каждой страницы файл. 10. Написать программу, которая анализирует текстовый файл, созданный текстовым редактором, таким как ed(1) или vi(1). После запроса, который предлагает ввести номер строки, с использованием printf(3) программа печатает соответствующую строку текста. Пользователю отводится 5 секунд на ввод номера строки. Если пользователь не успевает, программа должна распечатать все содержимое файла и завершиться. Если же пользователь успел в течение пяти секунд ввести номер строки, то программа должна работать дальше. Ввод нулевого номера завершает работу программы. Используйте open(2), read(2), lseek(2) и close(2) для ввода/вывода. Постройте таблицу отступов в файле и длин строк для каждой строки файла. Как только эта таблица построена, позиционируйтесь на начало заданной строки и прочтите точную длину строки. Предполагайте, что файл не длиннее сотни строк. Подсказка: Выберите или создайте текстовый файл с короткими строками. Помните, что первая строка начинается с нулевого отступа в файле. Найдите каждый символ перевода строки, запишите его позицию; в программе следует использовать вызов lseek(fd, 0L, 1). Для отладки распечатайте эту таблицу и сравните с таблицей, полученной вручную. Как только таблицы начнут совпадать, можно приступать к запросу номера строки. 6. Архитектура многопроцессорных операционных систем 1. Напишите упрощенный аналог команды ls, распечатывающий содержимое текущего каталога (файла с именем ".") без сортировки имен по алфавиту. Предусмотрите чтение каталога, чье имя задается как аргумент программы. Имена "." и ".." не выдавать. 2. Разработайте архитектуру и систему команд учебной машины и напишите интерпретатор учебного ассемблера, отрабатывающего по крайней мере такие команды: mov пересылка (:=) add сложение sub вычитание cmp сравнение и выработка признака jmp переход jeq переход, если == jlt переход, если < jle переход, если <= neg изменение знака not инвертирование признака 3. Напишите программу удаления файлов и каталогов, заданных в командной строке. Программа должна удалять каталоги рекурсивно и отказываться удалять файлы устройств. 4. Отсортируйте массив строк по лексикографическому убыванию, игнорируя различия между строчными и прописными буквами. 5. Составьте аналог команды date. 6. Составьте программу моделирования простейшего калькулятора, который считывает в каждой строчке по одному числу (возможно со знаком) или по одной операции сложения или умножения, осуществляет операцию и выдает результат. 7. Напишите программу, копирующую бинарный файл в обратном порядке байт. 8. Составьте программу кодировки и раскодировки файлов по заданному ключу (строке символов). 9. В программе чата из лабораторной работы netlab6 после нажатия кнопки «Войти в чат» введенный пароль виден в адресной строке – это хороший способ просмотреть чужой пароль. Избавьтесь от этого, изменив метод GET на метод POST. 10. Написать программу, которая анализирует текстовый файл, созданный текстовым редактором, таким как ed(1) или vi(1). После запроса, который предлагает ввести номер строки, с использованием printf(3) программа печатает соответствующую строку текста. Ввод нулевого номера завершает работу программы. Используйте open(2) и отображение файла в память взамен использования read(2), lseek(2) и write(2). Постройте таблицу отступов в файле и длин строк для каждой строки файла. Как только эта таблица построена, позиционируйтесь на начало заданной строки и прочтите точную длину строки. Предполагайте, что файл не длиннее сотни строк. Подсказка: Выберите или создайте текстовый файл с короткими строками. Помните, что первая строка начинается с нулевого отступа в файле. Найдите каждый символ перевода строки, запишите его позицию. Для отладки распечатайте эту таблицу и сравните с таблицей, полученной вручную. Как только таблицы начнут совпадать, можно приступать к запросу номера строки. 7. Микроядерные системы 1. Составьте аналог команды chmod. 2. Простейший строковый редактор. Программа вызывается «tsed s/old/new/ имя_файла», читая указанный текстовый файл и сканируя каждую строку на первое вхождение подстроки old. При совпадении выполняется замена old на new. Отредактированная строка пишется на стандартный вывод. 3. Пользуясь прямым доступом в видеопамять, напишите функции для сохранения прямоугольной области экрана в массив и обратно. 4. Составьте аналог команды cut. 5. Составьте программу дихотомического поиска в отсортированном массиве строк (методом деления пополам). 6. Составьте аналог команды cmp. 7. Составьте программу, которая будет удалять в конце (и в начале) каждой строки файла пробелы и табуляции, а также удалять строки, целиком состоящие из пробелов и табуляций. 8. Составьте программу удаления из программы на языке Си всех комментариев. Обратите внимание на особые случаи со строками в кавычках и символьными константами; так строка char s[] = "/*"; не является началом комментария! Комментарии записывайте в отдельный файл. 9. Добавьте в чат из лабораторной работы netlab6 возможности выхода и регистрации под другим именем без загрузки нового окна браузера. 10. Напишите программу, которая создает подпроцесс. Этот подпроцесс должен исполнить cat(1) длинного файла. Родитель должен вызвать printf(3) и распечатать какой-либо текст. После выполнения первой части задания модифицируйте программу так, чтобы последняя строка, распечатанная родителем, выводилась после завершения порожденного процесса. Используйте wait(2), waitid(2) или waitpid(3). 8. Конкуренция процессов в Windows 2000 1. Напишите функцию рекурсивного обхода дерева подкаталогов и печати имен всех файлов в нем с выдачей атрибутов в форме команды ls -l. 2. Используя вызов ioctl, составить программу «осыпающиеся буквы». 3. Создайте программу chmodr, рекурсивно изменяющую права доступа для всех файлов каталога и вложенных в него подкаталогов. Имя каталога и права указываются в командной строке. 4. Используя канал между родителем (клиентом) и потомком (сервером), создайте программу, в которой клиент считывает имя файла из стандартного ввода и записывает в канал. Если файл существует, сервер считывает его и записывает в канал, в противном случае возвращает клиенту сообщение об ошибке. 5. Напишем функцию, которая преобразует строку так, что при ее печати буквы в ней будут подчеркнуты, а цифры - выделены жирно. 6. Напишите примитивный интерпретатор команд, распознающий построчно команды вида: CMD ARG1 ... ARGn <FILE >FILE >>FILE >&FILE >>&FILE 7. Составьте функцию expand(s1, s2), которая расширяет сокращенные обозначения вида a-z строки s1 в эквивалентный полный список abcd...xyz в строке s2. Допускаются сокращения для строчных и прописных букв и цифр. Учтите случаи типа a-b-c, a-z0-9 и -a-g (соглашение состоит в том, что символ "-", стоящий в начале или в конце, воспринимается буквально). 8. Создайте 2 процесса (клиент и сервер), обменивающиеся данными через FIFO. 9. Добавьте в программу регистрации в чате из лабораторной работы netlab6 возможность игнорирования непустого, но состоящего из пробельных символов имени пользователя. 10. Напишите две программы: отправитель и получатель. Отправитель принимает текст с клавиатуры и рассылает сообщения нескольким копиям программы-получателя. Получатель сообщения распечатывает свое имя программы (argv[0]) и содержимое сообщения. Отправитель продолжает работу, пока не встретит конец файла. Тогда он рассылает всем получателям сообщение-ограничитель. Как только получатель заканчивает свою очередь сообщений, он отправляет сообщение отправителю. После получения такого подтверждения от всех получателей, отправитель удаляет очередь. 9. Механизмы параллельных вычислений в UNIX 1. Напишите программу, читающую слова из файла и размещающую их в виде двунаправленного списка слов, отсортированного по алфавиту. В конце работы распечатайте список дважды: в прямом и в обратном порядке. Не хранить в списке дубликаты; вместо этого вместе со словом хранить счетчик количества его вхождений в текст. 2. Составьте программу, преобразующую текст, состоящий только из строчных букв в текст, состоящий из прописных и строчных букв. Первая буква и буква после каждой точки – прописные, остальные – строчные. 3. Напишите программу, совмещающая команды mv и cp (в зависимости от своего названия). 4. Напишите программу, которая печатает слова из своего файла ввода, расположенные в порядке убывания частоты их появления. Перед каждым словом напечатайте число частоты его появления. 5. Напишите программу копирования ввода на вывод таким образом, чтобы из каждой группы последовательно одинаковых строк выводилась только одна строка. Это аналог программы uniq в системе UNIX. 6. Составьте аналог команды banner. 7. Напишите программу удаления каталога, которая удаляет все файлы в нем и, рекурсивно, все его подкаталоги. 8. Составьте программу, которая запрашивает анкетные данные типа фамилии, имени, отчества, даты рождения и формирует файл. Программа должна отлавливать ошибки ввода несимвольной и нецифровой информации, выхода составляющих даты рождения за допустимые границы с выдачей сообщений об ошибках. Программа должна давать возможность корректировать вводимые данные. Все данные об одном человеке записываются в одну строку файла через пробел. 9. Создайте Web-интерфейс с функциями просмотра списка файлов на сервере и загрузки файла с него. Для типов файлов, поддерживаемых браузером, разрешите отображение его средствами. 10. Напишите две программы, общающиеся через очередь. Одна из программ – мастер – будет получать сообщения, генерируемые другими программами – отправителями. Эти сообщения могут изображать состояние или степень готовности отправителя. При получении, мастер распечатывает сообщение и какую-либо идентификацию его отправителя. Перед завершением, каждый отправитель посылает сообщение-ограничитель. После получения таких ограничителей от всех отправителей, мастер удаляет очередь и завершается. 10. Управление памятью в современных операционных системах 1. Используя popen(), создайте канал между who и more. 2. Составьте аналог команды clear. 3. Разработайте программу, заполняющую промежутки между словами строки дополнительными пробелами таким образом, чтобы длина строки была равна 60 символам. 4. Составьте аналог команды ln. 5. Создайте демон, каждые 5 минут опрашивающий содержимое каталога, установленного при его запуске. При появлении изменений выводить их в системный журнал. 6. Напишите программу, вызывающую pthread_mutexattr_init и pthread_condattr_init в бесконечном цикле. Следите за использованием эти процессом памятью с помощью ps. Что происходит? теперь добавьте вызовы pthread_mutexattr_destroy и pthread_condattr_destroy и убедитесь, что утечки памяти нет. 7. Составьте вариант программы подсчета служебных слов языка Си, не учитывающий появление этих слов, заключенных в кавычки. 8. Составьте программу, распечатывающая слова в строках файла в обратном порядке. 9. Напишите программу, которая генерирует сортированный список из ста случайных чисел в диапазоне от 0 до 99. Распечатайте числа по десять в строке. Используйте popen(3), чтобы запустить sort(1) и rand(3) и srand(3) для генерации случайных чисел. 10. Используя фреймбуфер, составьте программу, которая строит график функции sin(x) на отрезке от 0 до 2*пи. 11. Управление памятью в Linux 1. Напишите программу, читающую файл построчно и печатающую слова в каждой строке в обратном порядке. 2. Используя 2 FIFO, создайте независимые программы клиента и сервера. Клиент считывает имя файла из стандартного ввода и записывает в первый FIFO. Если файл существует, сервер считывает его и записывает во второй FIFO, в противном случае возвращает клиенту сообщение об ошибке. 3. Составьте программу сохранения содержимого экрана (видеопамяти) в текстовом режиме в файл и обратно. 4. Напишите программу рекурсивного копирования поддерева каталогов. 5. Напишите программу, удаляющую из файла выделения. 6. Организуйте базу данных в файле как список записей. В каждой записи вместо ключа должен храниться номер очередной записи (ссылка). Напишите функции: поиска данных в списке (по значению), добавления данных в список в алфавитном порядке, (они просто приписываются к концу файла, но в нужных местах переставляются ссылки), распечатки списка в порядке ссылок, удалению элементов из списка (из самого файла они не удаляются!). Ссылка (номер) первой записи (головы списка) хранится в первых двух байтах файла, рассматриваемых как short. Введите оптимизацию: напишите функцию для сортировки файла (превращению перемешанного списка в линейный) и вычеркивания из него удаленных записей. При этом файл будет перезаписан. Если файл отсортирован, то поиск в нем можно производить более эффективно, чем прослеживание цепочки ссылок: просто линейным просмотром. Третий байт файла используйте как признак: 1 – файл был отсортирован, 0 – после сортировки в него было что-то добавлено и линейный порядок нарушен. 7. Используя системный вызов sysinfo, создайте программу для получения системной статистики. 8. Напишите 2 программы, обменивающиеся сообщениями через очередь сообщений. 9. Используя системный вызов sendfile, создайте программу для быстрого копирования файлов. 10. Напишите две программы, Производитель и Потребитель, такие что Производитель заполняет буфер в разделяемой памяти, а Потребитель читает его. Производитель должен помещать новые данные в буфер только после того, как Потребитель прочитает его. Совет: Для синхронизации можно использовать два семафора (эффективнее всего – набор из двух семафоров). Один из семафоров нужно ассоциировать с записью новых данных в буфер. Другой должен быть ассоциирован с чтением данных Потребителем. 12. Планирование времени в однопроцессорных системах 1. Напишите функцию canon(), канонизирующую имя файла, т.е. превращающую его в полное имя (от корневого каталога), не содержащее компонент "." и "..", а также лишних символов слэш '/'. 2. Используя библиотеку curses, напишите программу, реализующую клеточный автомат Конвея "Жизнь". Правила: есть прямоугольное поле (вообще говоря бесконечное, но принято в конечной модели замыкать края в кольцо), в котором живут "клетки" некоторого организма. Каждая имеет 8 соседних полей. Следующее поколение "клеток" образуется по таким правилам: если "клетка" имеет 2 или 3 соседей - она выживает. если "клетка" имеет меньше 2 или больше 3 соседей - она погибает. в пустом поле, имеющем ровно 3х живых соседей, рождается новая "клетка". Предусмотрите: редактирование поля, случайное заполнение поля, останов при смерти всех "клеток", останов при стабилизации колонии. 3. Напишите 2 клиента и сервер, взаимодействующий индивидуально с каждым клиентом через единую очередь сообщений. 4. Напишите 2 программы, взаимодействующих двунаправленно (т.е. каждый процесс может читать и писать) и синхронизирующихся с помощью семафоров. 5. Составьте функцию поиска подстроки в строке. Используя ее, напишите программу поиска подстроки в текстовом файле. Программа должна выводить строки (либо номера строк) файла, в которых встретилась данная подстрока. Подстрока задается в качестве аргумента функции main(). 6. Напишите программу, выдающую гистограмму длин строк файла (т.е. таблицу: строк длины 0 столько-то, длины 1 - столько-то, и.т.п., причем таблицу можно изобразить графически). 7. Создайте 2 процесса (клиент и сервер), обменивающиеся данными через разделяемую память. Используйте семафоры для синхронизации и уведомления каждого процесса о выполнении операций чтения и записи памяти. 8. При помощи curses напишите экранный редактор кодов доступа к файлу (в форме rwxrwxrwx). 9. Напишите программу pwd, определяющую полное имя текущего рабочего каталога. 10. Напишите две программы, одна из которых шлет сообщения другой. Получатель распечатывает содержимое сообщения, тип и значение, возвращенное msgrcv(2). Напишите программы так, чтобы они не исполнялись родственными процессами. Сделайте программы как можно проще. Для этого упражнения вам не нужна никакая проверка ошибок. Используйте численную форму вашего идентификатора пользователя в качестве ключа. Если позволит время, вы можете установить права доступа для очереди так, чтобы ваши одногруппники, зная ключ очереди, могли читать из нее или писать в нее. К обоим программам должен быть добавлен цикл, чтобы иметь дело с многими сообщениями. Если вы будете разделять идентификатор очереди с другими пользователями, вы должны сказать друг другу ваши идентификаторы пользователя и использовать их как типы сообщений. Замечание: ipcs -q распечатывает количество сообщений в очереди и их общий размер. 13. Планирование времени в многопроцессорных системах 1. Используя алгоритм обхода дерева каталогов, напишите аналог команды find, который будет позволять находить все файлы, чьи имена удовлетворяют заданному шаблону. 2. Напишите программу печати на принтере листинга Си-программ. Ключевые слова языка выделяйте двойной надпечаткой. Для выдачи на терминал напишите программу, подчеркивающую ключевые слова (подчеркивание - в следующей строке). 4. Создайте упрощенную версию команды ср, копирующую один файл в другой с отображением файла на память. 5. Создайте программу, помещающую сообщение в очередь и считывающую сообщения из очереди. 6. Напишите несколько функций для работы с упрощенной базой данных. Запись в базе данных содержит ключ - целое, и строку фиксированной длины: struct data { int b_key; /* ключ */ char b_data[ DATALEN ]; /* информация */ }; Напишите: добавление записи уничтожение по ключу поиск по ключу (и печать строки) обновление по ключу. Файл организован как несортированный массив записей без дубликатов (т.е. ключи не могут повторяться). Поиск производить линейно. Используйте функции fread, fwrite, fseek. Последняя функция позволяет вам позиционироваться к n-ой записи файла: fseek( fp, (long) n * sizeof(struct data), 0 ); Перепишите эту программу, объявив ключ как строку, например char b_key[ KEYLEN ]; Если строка-ключ короче KEYLEN символов, она должна оканчиваться '\0', иначе используются все KEYLEN букв и '\0' на конце отсутствует (так же устроено поле d_name в каталогах файловой системы). Усовершенствуйте алгоритм доступа, используя хеширование по ключу (hash - перемешивание, см. пример в приложении). Вынесите ключи в отдельный файл. Этот файл ключей состоит из структур struct record_header { int b_key ; /* ключ */ long b_offset; /* адрес записи в файле данных */ int b_length; /* длина записи (необязательно) */ }; то есть организован аналогично нашей первой базе данных. Сначала вы ищете нужный ключ в файле ключей. Поле b_offset у найденного ключа задает адрес данного в другом файле. Чтобы прочитать его, надо сделать fseek на расстояние b_offset в файле данных и прочесть b_length байт. 7. Используя фреймбуфер, напишите функцию, рисующую прямую линию из точки (x1,y1) в (x2,y2). Указание: используйте алгоритм Брезенхема (минимального отклонения). Ответ: пусть функция putpixel(x,y,color) рисует точку в координатах (x,y) цветом color. 8. Напишите программу, узнающую у системы и распечатывающую: номер процесса, номер и имя своего владельца, номер группы, название и тип терминала, на котором она работает. 9. Напишите при помощи curses "электронные часы", отображающие текущее время большими цифрами (например, размером 8x8 обычных символов) каждые 5 секунд. Используйте alarm(), pause(). 10. Напишите программу, которая создает два подпроцесса, взаимодействующих через программный канал. Используйте стандартные библиотечные функции popen(3) и pclose(3). Первый процесс выдает в канал текст, состоящий из символов верхнего и нижнего регистров. Второй процесс переводит все символы в верхний регистр, и выводит полученный текст на терминал. Подсказка: см. toupper(3). 14. Планирование времени в системах реального времени 1. Напишите программу, печатающую n последних строк файла. Имя файла и количество строк задаются в командной строке (по умолчанию – 5 последних строк). 2. Создайте программу, выводящую содержимое символической ссылки, а затем – целевого файла, на который она указывает. 3. Напишите программу, печатающую строки файла, в которых есть заданное в командной строке слово. 4. Напишите программу, печатающую файлы, переданные ей в качестве аргументов, останавливающуюся и ожидающую нажатия клавиши через каждые 20 строк. 5. Создайте аналог команды ps –aux. 6. Напишите диалоговую программу удаления одного или всех файлов в текущем каталоге. После вывода имени каждого файла программа должна спрашивать у пользователя, удалить его или оставить. 7. Напишите программу, измеряющую в миллисекундах время выполнения другой программы, переданной ей в качестве параметра командной строки 8. Используя popen, создайте канал между командой who и more. 9. Напишите программу, выводящую отсортированный по алфавиту список каталогов. 10. Напишите программу, которая входит в бесконечный цикл и издает звуковой сигнал на вашем терминале каждый раз, когда вы нажимаете DELETE. При получении SIGQUIT, она должна вывести сообщение, говорящее, сколько раз прозвучал сигнал, и завершиться. 15. Дисковое планирование 1. Напишите функцию, рисующую на экране прямоугольную рамку. Используйте ее для рисования рамки окна. 2. Напишите функцию, переводящую год, месяц, день, часы, минуты и секунды в число секунд, прошедшее до указанного момента с 00 часов 00 минут 00 секунд 1 Января 1970 года. 3. Напишите программу, печатающую тексты Си-программ на принтере. Выделяйте ключевые слова языка жирным шрифтом, строки "строка", символы 'c' и комментарии - курсивом. 4. Напишите аналог команды ls -l. 5. Напишите "часы", выдающие текущее время каждые 3 секунды. 6. Напишите программу, которая ожидает ввода с клавиатуры в течение 10 секунд. Если ничего не введено - печатает "Нет ввода", иначе - печатает "Спасибо". 7. Напишите программу, читающую файл построчно и размещающую строки в отсортированное двоичное дерево. По концу файла - распечатайте это дерево. Указание: используйте динамическую память и рекурсию. 8. Используя ioctl, создайте программу для выезда компакт-диска из привода. 9. Напишите программу, выборочно выводящую значение переменных окружения и устанавливающую новые значения по желанию пользователя. 10. Напишите программу, которая создает два подпроцесса, взаимодействующих через программный канал. Первый процесс выдает в канал текст, состоящий из символов верхнего и нижнего регистров. Второй процесс переводит все символы в верхний регистр, и выводит полученный текст на терминал. Подсказка: см. toupper(3). 16. Управление вводом-выводом в Windows 2000 1. Напишите функцию mysleep(n), задерживающую выполнение программы на n секунд. Воспользуйтесь системным вызовом alarm(n) (будильник) и вызовом pause(), который задерживает программу до получения любого сигнала. Предусмотрите рестарт при получении во время ожидания другого сигнала, нежели SIGALRM. Сохраняйте заказ alarm, сделанный до вызова sleep (alarm выдает число секунд, оставшееся до завершения предыдущего заказа). 2. Составьте программу вывода строк файла в инверсном отображении, причем порядок символов в строках также следует инвертировать. 3. Используя файловую систему /proc, получите информацию о типе, версии и дате выпуска операционной системы. 4. Используя интерфейс TCP-сокетов, создайте параллельный эхо-сервер и клиент для него. 5. Создайте аналог команды df. 6. Используя файловую систему /proc, получите информацию о процессоре (vendor_id, cpu family, model, model name, stepping, cpu MHz, cache size, fdiv_bug, hlt_bug, sep_bug, f00f_bug, coma_bug, fpu, fpu_exception, cpuid level, wp, flags, bogomips). 7. Напишите программу создания и записи образов дискет. 8. На curses напишите функцию редактирования текста в окне. Функция должна возвращать массив строк с обрезанными концевыми пробелами. Вариант: возвращать одну строку, в которой строки окна разделяются символами '\n'. 9. Напишите функции включения и выключения режима эхо-отображения набираемых на клавиатуре символов. 10. Напишите программу, которая подсчитывает пустые строки в файле, используя команду wc(1). 17. Подсистема управления файлами в UNIX SVR4 1. Напишите аналог команды ls -l, выдающий имена файлов каталога и их коды доступа в формате rwxrw-r--. 2. Напишите программу, которая построчно считывает небольшой файл в память и печатает строки в обратном порядке. 3. Используя библиотеку termcap напишите функции для: очистки экрана, позиционирования курсора, включения/выключения режима выделения текста инверсией. 4. Используя системный вызов stat, получите полную информацию о файле, имя которого передается в качестве аргумента командной строки. 5. Составьте программу вывода набора файлов на печать, начинающую каждый очередной файл с новой страницы и печатающую перед каждым файлом заголовок и номер текущей страницы. 6. Напишите программу, которая каждые 2 секунды проверяет, не изменилось ли содержимое текущего каталога. 7. Напишите программу, выдающую на экран файл /etc/termcap. Перехватывайте сигнал SIGINT, при получении сигнала запрашивайте "Продолжать?". По ответу 'y' - продолжить выдачу; по 'n' - завершить программу; по 'r' - начать выдавать файл с начала. 8. Напишите программу, которая приглашает пользователя ввести шаблон имени файла, аналогичный тому, который используется в shell. Синтаксис шаблона таков: * соответствует последовательности любых символов кроме /, имеющей любую длину; возможно – пустой последовательности, ? соответствует любому одному символу, / не может встречаться, любой другой символ соответствует самому себе. Символы * и ? в шаблоне могут встречаться в любом количестве и в любом порядке. Совет: используйте readdir, чтобы считать все имена файлов в текущем каталоге, и выберите из них соответствующие шаблону. Затем программа должна найти и распечатать имена всех файлов в текущем каталоге, соответствующих шаблону. Если таких файлов нет, программа должна распечатать сам шаблон. 9. Используя файловую систему /proc, получите информацию об используемой памяти. 10. Напишите программу, которая читает из нескольких файлов по очереди, т.е. после чтения строки из одного файла, читается строка из следующего и т.д. Если в течение TIME_OUT секунд ничего не было прочитано, берется следующий файл. Программа получает в качестве аргументов имена одного или нескольких файлов, из которых она будет читать. Обычно это терминальные файлы (т.е. /dev/ttynn), но могут быть файлы и других типов. (read(2) с нетерминального устройства может прочитать несколько строк, в зависимости от количества требуемых байтов и длины этих строк.) Если в одном из файлов достигнут конец файла, из него больше не читают. Когда конец файла достигнут во всех файлах, программа завершается. Проверьте вашу программу так: $ multiplex /dev/tty 'tty'. 18. Кластеры Beowulf и Linux 1. Напишите функцию печати текущего времени в формате ЧЧ:ММ:СС ДД-МЕС-ГГ. Используйте системный вызов time() и функцию localtime(). 2. Напишите программу, ищущую выход из лабиринта ("червяк в лабиринте"). Лабиринт загружается из файла .maze (не забудьте про расширение табуляций!). Алгоритм имеет рекурсивную природу и выглядит примерно так: #include <setjmp.h> jmp_buf jmp; int found = 0; maze(){ /* Это головная функция */ if( setjmp(jmp) == 0 ){ /* начало */ if( неСтенка(x_входа, y_входа)) GO( x_входа, y_входа); } } GO(x, y){ /* пойти в точку (x, y) */ if( этоВыход(x, y)){ found = 1; /* нашел выход */ пометить(x, y); longjmp(jmp, 1);} пометить(x, y); if( неСтенка(x-1,y)) GO(x-1, y); /* влево */ if( неСтенка(x,y-1)) GO(x, y-1); /* вверх */ if( неСтенка(x+1,y)) GO(x+1, y); /* вправо */ if( неСтенка(x,y+1)) GO(x, y+1); /* вниз */ снятьПометку(x, y); } #define пометить(x, y) лабиринт[y][x] = '*' #define снятьПометку(x, y) лабиринт[y][x] = ' ' #define этоВыход(x, y) (x == x_выхода && y == y_выхода) /* можно искать "золото": (лабиринт[y][x] == '$') */ неСтенка(x, y){ /* стенку изображайте символом @ или # */ if( координатыВнеПоля(x, y)) return 0; /*край лабиринта*/ return (лабиринт[y][x] == ' '); } Отобразите массив лабиринт на видеопамять (или воспользуйтесь curses). 3. Напишите рекурсивное решение задачи "ханойские башни" (перекладывание дисков: есть три стержня, на один из них надеты диски убывающего к вершине диаметра. Требуется переложить их на третий стержень, никогда не кладя диск большего диаметра поверх диска меньшего диаметра). Используйте пакет curses для изображения перекладывания дисков на экране терминала. 4. Напишите аналог команды ls -tm, выдающей список имен файлов текущего каталога, отсортированный по убыванию времени изменения. 5. Напишите программу печати текста в две колонки. Используйте буфер для формирования листа: файл читается построчно (слишком длинные строки обрубать), сначала заполняется левая половина листа (буфера), затем правая. Когда лист полностью заполнен или файл кончился - выдать лист построчно, расписать буфер пробелами (очистить лист) и повторить заполнение очередного листа. Указание: размеры листа должны передаваться как аргументы main(), для буфера используйте двумерный массив букв, память для него заказывайте динамически. Не обрубайте, а переносите слишком длинные строки (строка может потребовать даже переноса с листа на лист). 6. Напишите программу, которая читает файл, состоящий из "блоков" текста, разделенных пустыми строками. Размер "блока" ограничен. Программа готовит файл для печати на принтер так, чтобы ни один блок не разбивался на части. 7. Напишите программу, печатающую строки файла в обратном порядке. Не считывать файл целиком в память! 8. Создайте аналог команды find. 9. Создайте аналог команды head. 10. Напишите программу, которая приглашает пользователя ввести шаблон имени файла, аналогичный тому, который используется в shell. Синтаксис шаблона таков: * соответствует последовательности любых символов, имеющей любую длину; возможно – пустой последовательности, ? соответствует любому одному символу, любой другой символ соответствует самому себе. Символы * и ? в шаблоне могут встречаться в любом количестве и в любом порядке. Также в шаблоне могут встречаться символы /. При этом программа должна распечатывать все файлы, путевые имена которых соответствуют шаблону. Так, шаблону */* соответствуют все файлы во всех подкаталогах текущего каталога. Совет: используйте readdir, чтобы считать все имена файлов в текущем каталоге, и выберите из них соответствующие шаблону. Затем программа должна найти и распечатать имена всех файлов в текущем каталоге, соответствующих шаблону. Если таких файлов нет, программа должна распечатать сам шаблон. 19. Управление распределенными процессами 1. Создайте аналог команды kill. 2. Создайте аналог команды ln. 3. Создайте аналог команды mkfifo. 4. Создайте аналог команды mktemp. 5. Создайте аналог команды more. 6. Создайте аналог команды nice. 7. Создайте аналог команды sleep. 8. Создайте аналог команды tail. 9. Создайте аналог команды uname. 10. Напишите программу, которая запускает команду, заданную в качестве первого аргумента, в виде порожденного процесса. Все остальные аргументы программы передаются этой команде. Затем программа должна дождаться завершения порожденного процесса и распечатать его код завершения. 20. Зловредное программное обеспечение 1. Создайте аналог команды usleep. 2. Напишите программу, печатающую список всех файлов в текущем каталоге и во всех его подкаталогах. 3. Напишите программу, которая будет печатать слова из файла ввода, причем по одному на строку. 4. Напишите программу, сравнивающую два файла и печатающую строки, в которых они отличаются. 5. Используя файловую систему /proc, получите информацию об открытых всеми процессами файлах. 6. Создайте аналог команды hostname. 7. Напишите программу, которая печатает вопрос и требует односимвольного ответа. Измените атрибуты вашего терминала так, чтобы пользователю не нужно было вводить новую строку после ответа. 8. Напишите программу – аналог команды ls -ld. Для каждого своего аргумента эта команда должна распечатывать: 1) Биты состояния файла в воспринимаемой человеком форме: d если файл является каталогом, - если файл является обычным файлом, ? во всех остальных случаях. 2) Три группы символов, соответствующие правам доступа для хозяина, группы и всех остальных: r если файл доступен для чтения, иначе -, w если файл доступен для записи, иначе -, x если файл доступен для исполнения, иначе -. 3) Количество связей файла. 4) Имена владельца и группы файла (совет – используйте getpwuid и getgrgid). 5) Если файл является обычным файлом, его размер. Иначе оставьте это поле пустым. 6) Дату модификации файла (используйте ctime). 7) Имя файла (если было задано имя с путем, нужно распечатать только имя). 8) Желательно, чтобы поля имели постоянную ширину, т.е. чтобы листинг имел вид таблицы. Совет – используйте printf. 9. Напишите программу-производитель, которая помещает текст в буфер, размещенный в сегменте разделяемой памяти. Напишите программу-потребитель, которая будет читать из этого буфера. Может существовать несколько копий потребителя. Производитель может обновлять буфер только после того, как все потребители считали его содержимое. Совет: Для синхронизации можно использовать два семафора. Один из семафоров нужно ассоциировать с записью новых данных в буфер. Другой должен быть ассоциирован с чтением данных Потребителем. Значения семафоров будут меняться в диапазоне от 0 до количества потребителей. 10. Напишите функцию execvpe(), которая работает как execvp(2), но позволяет изменять среду исполнения, как execve(2). Совет: используйте внешнюю переменную environ. 21. Принципы проектирования операционных систем 1. Создайте программу, выводящую установленные для процесса ограничения. 2. Составьте аналог команды du. 3. Напишите программу сортировки строк в алфавитном порядке. 4. Составьте аналог команды vdir. 5. Составьте аналог команды cal. 6. Составьте аналог команды chown. 7. Составьте программу преобразования прописных букв из файла ввода в строчные, используя при этом функцию, в которой необходимо организовать анализ символа (действительно ли это буква). Строчные буквы выдавать без изменения. 8. Составьте аналог команды sync. 9. Модифицируйте тестовую систему из лабораторной работы netlab6 так, чтобы все вопросы выводились на одной странице. 10. Предположим, что исполняется n процессов. Часть из них читает, а остальные пишут в разделяемый сегмент памяти. Несколько читающих процессов могут работать с буфером одновременно. Если один из пишущих процессов выполняет запись, все остальные процессы должны ждать. Кроме того, если пишущий процесс хочет обновить данные, он должен ждать, пока все читающие процессы закончатся. Для обеспечения такого взаимного исключения надо использовать семафоры. Совет: Один из способов решения состоит в использовании набора из трех семафоров со следующими значениями: индекс 0 счетчик процессов, выполняющих чтение индекс 1 двоичный семафор, гарантирующий, что только один процесс может писать в буфер индекс 2 используется для блокировки чтения на время записи или ожидания записи. 22. Средства безопасности в операционных системах 1. Многие программы, принимающие ввод с терминала, позволяют редактировать строку перед использованием. Напишите программу, которая выключает эхо и каноническую обработку, таким образом выключив и обработку символа забоя. Ваша программа должна получать ввод с клавиатуры и показывать его на терминале в соответствии со следующими правилами: 1) Каждый введенный символ должен немедленно появляться на дисплее. 2) Когда вводится символ ERASE, стирается последний символ в текущей строке. 3) Когда вводится символ KILL, стираются все символы в текущей строке. 4) Когда вводится CTRL-W, стирается последнее слово в текущей строке, вместе со всеми следующими за ним пробелами. 5) Программа завершается, когда введен CTRL-D и курсор находится в начале строки. 6) Все непечатаемые символы, кроме перечисленных выше, должны издавать звуковой сигнал, выводя на терминал символ CTRL-G. 7) Длина строки ограничена 40 символами. Если какое-то слово пересекает 40-й столбец, это слово должно быть помещено в начало следующей строки. 2. Создайте программу, реализующую функциональность простого форума. 3. Портируйте команду mc на платформу Free Pascal для Linux. Рекомендуемая литература 1. Бах М. Архитектура операционной системы UNIX. – М.: Финансы и статистика, 1994. 2. Богатырев А. Хрестоматия по программированию на Си в Unix. 3. Голдт С., Ван дер Меер С., Буркетт С., Уэлш М. Руководство программиста для Linux. 4. Дегтярев Е.К. Введение в UNIX. – М., 1991. 5. Дюпуа Б., Габасси М. UNIX и TCP/IP: программирование на языке C. 6. Керниган Б.В., Пайк Р. UNIX – универсальная среда программирования. – М.: Финансы и статистика, 1992. 7. Олифер Н.А., Олифер В.Г. Компьютерные сети. 8. Олифер Н.А., Олифер В.Г. Сетевые операционные системы. – СПб.: Питер, 2001. 9. Рихтер Дж. Windows для профессионалов: создание эффективных WIN32-приложений с учетом специфики 64-разрядной версии Windows. 10. Симоненко В.П. Организация вычислительных процессов в ЭВМ, комплексах, сетях и системах. – К.: ТОО «Век+», 1997. 11. Соломон Д., Руссинович М. Внутреннее устройство Microsoft Windows 2000 (Мастер-класс) 12. Стивенс У.Р. UNIX: взаимодействие процессов. – СПб.: Питер, 2002. – 576 с. 13. Стивенс У.Р. UNIX: разработка сетевых приложений. 14. Столлингс В. Операционные системы. Внутреннее устройство и принципы проектирования. – М.: Вильямс, 2002. – 848 с. 15. Таненбаум Э. Современные операционные системы. 16. Таненбаум Э.С., Вудхалл А.С. Операционные системы. Разработка и реализация, 2005. – 576 с. 17. Фролов А.В., Фролов Г.В. Программирование для Windows NT. Часть 1, 2. – М.: Диалог-МИФИ, 1996. – 272 с. 18. Хэвиленд К., Грэй Д., Салама Б. Системное программирование в UNIX. Руководство программиста по разработке ПО. 19. Цикритзис Д., Бернстайн Ф. Операционные системы. – М.: Мир, 1977. 20. Ядро ОС Linux. Руководство программиста. Пример оформления титульного листа Министерство образования и науки Украины Криворожский государственный педагогический университет Контрольная работа №2 по предмету «Операционные системы» ЭВОЛЮЦИЯ ОПЕРАЦИОННЫХ СИСТЕМ Выполнил: студент III курса группы И-06 Н.Н. Неизвестный Руководитель: к.пед.н., доц. С.А. Семериков Кривой Рог 2009 Пример оформления содержания Содержание Введение...................................................................................... 3 1. Эволюция операционных систем........................................... 4 1.1. Первое поколение операционных систем....................... 4 1.2. Второе поколение операционных систем....................... 6 1.3. Третье поколение операционных систем....................... 8 1.4. Современные операционные системы.......................... 11 2................................................................................................. 14 2.1. Алгоритмы работы программ и примеры диалога Программа, печатающая свои аргументы, переменные окружения, информацию об открытых файлах и используемых каналах 14 2.2. Программа, разбивающая файл на два по вертикали.. 15 2.3. Программа, выделяющая n -ое поле из каждой строки файла 17 Заключение............................................................................... 18 Список литературы................................................................... 19 Приложения.............................................................................. 20 A. Листинг файла printenv.c........................................ 20 B. Листинг файла split.c................................................ 21 C. Листинг файла n-field.c........................................... 23 D. Дискета.................................................................................