«ОПЕРАЦИОНННЫЕ СИСТЕМЫ»
Тема курсовой работы: Исследование алгоритмов планирования многопоточных вычислительных процессов
Выполнила: студентка 273 (1) групы
___________________ Иванова А.А.
e-mail адрес: aaaaaa@mail.ru
Руководитель: доцент кафедры Математики и информатики ________________ Горелов С.В.
Москва 2011
Образец задания
РОССИЙСКИЙ ГОСУДАРСТВЕННЫЙ СОЦИАЛЬНЫЙ УНИВЕРСИТЕТ
Факультет Информационных технологий
Кафедра Математики и информатики
ЗАДАНИЕ
на курсовую работу студенту(ке) 173 группы Ивановой Лидии Александровне
Тема курсовой работы: "Исследование алгоритмов планирования многопоточных вычислительных процессов"
Целевая установка и исходные данные: На основе анализа предметной области разработать программу, моделирующую многопоточные вычислительные процессы с различными алгоритмами планирования.
Входящий поток - простейший, интенсивность потока - 100-1000 1/с. среднее время обслуживания потока - 10 мс (усеченное нормальное распределение), микропроцессор – двухядерный, алгоритмы планирования - FIFO, кратчайший - первым.
Основные вопросы, подлежащие разработке (исследованию):
1. Аначиз предметной области.
2. Постановка задачи моделирования.
3. Определение (уточнение) требований к исходной информации.
4. Определение параметров и переменных модели.
5. Выбор и обоснование показателей и критериев эффективности системы.
6. Разработка содержательного описания модели.
7. Разработка алгоритма модели системы.
8. Разработка программы модели системы.
9. Тестирование программы.
10. Проведение экспериментов с моделью и анапиз полученных результатов
11. Разработка пояснительной записки и презентации для представления результатов работы и их зашиты
Ожидаемые результаты и предполагаемая практическая реализация
1. Рекомендации по организации многопоточных вычислительных процессов
2. Предполагается реализовать в учебном процессе кафедры при изучении дисциплины «Операционные системы»
К защите представить (указать объем пояснительной записки, перечень чертежей, схем и т.д.)
1. Пояснительную записку. 15-25 с.
2. Распечатку исходных текстов программ с комментариями
(в приложении к Пояснительной записке).
3. Иллюстративный материал. 10-15 (слайдов)
4. Программу модели и презентацию на носителе информации
5. Другие материалы (по необходимости), например, об использовании выполненной работы на других кафедрах или в других вузах
Консультанты профессор Сидоров В. А. __________
Место выполнения курсовой работы Р ГСУ, факультет Информационных технологий
Руководитель доцент кафедры математики и информатики, кандидат технических наук, доцент __________________________________ А. В. Сергеев
Задание получил(а) студент(ка) 273 (1) группы Иванова JI.A.
Литература
1. Армстронг (мл.), Джеймс. Секреты Unix: 2-е изд.: Пер. с англ. - М.: Издательский дом «Вильяме», 2001 -1072 е.: ил. - Парал. тит. англ.
2. Брюс У, Туррот П., Черникофф Д. Microsoft Windows ХР. Средства повышения производительности. /Пер. с англ., - М.: Издательство «СП ЭКОМ», 2003. - 672с.: ил.
3. Гультяев А.К. Виртуальные машины: несколько компьютеров - в одном (+ CD). - СПб.: Питер, 2006. - 224 с.
4. Кэррие Б. Криминалистический анализ файловых систем. - СПб.: Питер, 2007. - 480с.: ил.
5. Мюллер Дж. Оптимизация Windows ХР. - СПб.: Питер, 2006. - 480 с.
6. Мюллер Дж., Чоудри И. Microsoft Windows 2000. Настройка и оптимизация производительности./ Пер. с англ.. - М.: Издательство ЭКОМ, 2001. - 512 с.
7. Назаров С.В. Администрирование локальных сетей Windows NT/2000/.NET. - М.: Финансы и статистика, 2003. - 480 с.
8. Назаров С.В. Операционные среды, системы и оболочки. Основы структурной и функциональной организации: Учеб. Пособие. - М.: КУДИЦ-ПРЕСС, 2007. - 504 с.
9. Негус Кристофер. Linux. Библия пользователя, 5-е издание.: Пер. с англ. - М.: ООО «И.Д. Вильяме», 2007. -704с.: ил. - Парал. тит. англ.
10. Прайс Д., Гандэрлой М. Visual C#.NET. Полное руководство.: Пер. с англ. - К.: ВЕК+, СПб.: КОРОНА принт, К.: НТИ, М.: Энтроп, 2004. - 960 с.
11. Рихтер Дж. Windows для профессионалов / Пер. с англ. - 4-е изд. - СПб: Питер; М.: Издательско-торговый дом «Русская редакция», 2003. - 752 с.
12. Русинович М„ Соломон Д. «Внутреннее устройство Microsoft Windows: Windows Server 2003, Windows ХР и Windows 2000. Мастер-класс. / Пер с англ. - 4-е изд. - М.: Издательство «Русская редакция»; СПб.: Питер, 2006. - 992 стр.: ил.
13. Синчак С. Windows ХР. Настройка и разгон (+ CD). - СПб.: Питер, 2006. - 352 с.
14. Смит Д., Наир Р. Архитектура виртуальных машин. - «Открытые системы», № 05- 06, 2005
15. Стахнов А.А. Сетевое администрирование Linux, — СПб.: БХВ-Петербург, 2004. - 480с.: ил.
16. Таненбаум Э. Современные операционные системы.: Пер. с англ. 2-е изд. - СПб.: Питер, 2002. - 1040 с.
17. Чекмарев А.Н., Вишневский А.В., Кокорева О.И. Microsoft Windows Server 2003. Русская версия / Под общ. Ред. А.Н. Чекмарева. - СПб.: БХВ-Петербург, 2005. - 1120 с.
18. Шалин П.А. Реестр Windows ХР. Специальный справочник. - СПб.: Питер, 2006. -
175 с.
19. Шрайбер С. Недокументированные возможности Windows 2000. Библиотека программиста / Пер. с англ. - СПб: Питер, 2002. - 544 с.
Темы курсовых работ
Вариант 1
Исследование алгоритмов (модель) стека
1. Исходные данные:
• стек векторной структуры;
• перечень операций со стеком: создание, включение элемента, выборка элемента, извлечение данных, уничтожение.
2. Результаты работы модели должны включать в себя:
• меню с перечнем всех операций над стеком;
• печать содержимого стека.
3. Литература: Л7 с. 76 - 78, Л9 с. 89 - 96.
Вариант 2
Исследование алгоритмов (модель) очереди
1. Исходные данные:
• очередь векторной структуры;
• перечень операций с очередью: создание и освобождение, включение в очередь нового элемента, выборка элемента из очереди;
• дисциплина очереди - FIFO (добавление в конец очереди, выборка из головы очереди;
2. Результаты работы модели должны включать в себя:
• меню с перечнем всех операций над очередью;
• печать содержимого очереди.
3. Литература: Л7 с. 499 - 503, Л9 с. 115 - 122.
Вариант 3
Исследование алгоритмов (модель) очереди
1. Исходные данные:
• очередь списковой структуры;
• перечень операций с очередью: создание и освобождение, включение в очередь нового элемента, выборка элемента из очереди;
• дисциплина очереди - FIFO (добавление в конец очереди, выборка из головы
очереди).
2. Результаты работы модели должны включать в себя:
• меню с перечнем всех операций над очередью;
• печать содержимого очереди
3.Литература: Л3 с. 106 - 107, Л7 с. 499 - 503, Л9 с. 115 - 122.
Вариант 4
Исследование алгоритмов (модель) очереди
1. Исходные данные:
• очередь векторной структуры с динамической памятью;
• перечень операций с очередью: создание и освобождение, включение в очередь нового элемента, выборка элемента из очереди;
• дисциплина очереди - FIFO (добавление в конец очереди, выборка из головы очереди).
2. Результаты работы модели должны включать в себя:
• меню с перечнем всех операций над очередью;
• печать содержимого очереди. Литература: Л7 с. 499 - 503, Л9 с. 115 - 122.
Вариант 5
Исследование алгоритмов (модель) решения проблемы блокировок для произвольного числа процессов
1. Исходные данные:
• в системе имеется М типов ресурсов;
• количество процессов, претендующих на ресурсы, также равно М;
• для работы процесса необходимо два определенных ресурса;
• проблема синхронизации представляется классической проблемой «обедающих философов».
2.Результаты работы модели должны показать:
• беступиковое выполнение процессов путем анализа программы;
• решение для текущего состояния (есть тупик или нет, запускать новый процесс или нет).
3.Литература: Л3 с. 150 - 153, Л6 с. 227 - 239, Л8 с. 150 - 153.
Вариант 6
Исследование алгоритмов (модель) решения проблемы блокировок при доступе к базе данных
1. Исходные данные:
• количество процессов, претендующих на ресурсы, равно М;
• разрешается одновременное чтение всем процессам;
• разрешается запись только для одного процесса;
• при записи доступ для остальных процессов должен быть прекращен;
• проблема синхронизации представляется классической проблемой «читателей и писателей».
2. Результаты работы модели должны показать:
• беступиковое выполнение процессов путем анализа программы;
• решение для текущего состояния (есть тупик или нет, запускать новый процесс или нет).
3. Литература: Л3 с. 150 - 153, Л6 с. 227 - 239, Л7 с. 273 - 278, Л8 с. 153 - 154.
Вариант 7
Исследование алгоритмов (модель) решения проблемы межпроцессного взаимодействия
1. Исходные данные:
• количество процессов, претендующих на обслуживание, произвольное;
• одновременно обслуживается только один процесс;
• число ожидающих процессов не более п;
• проблема синхронизации представляется классической проблемой «спящего брадобрея».
2. Результаты работы модели должны показать:
• бесконфликтное выполнение процессов путем анализа программы решаемой задачи в структурной организации операционной системы.
3. Литература: Л8 с. 155 - 157, Л6 с. 227 - 239.
Вариант 8
Исследование алгоритмов (модель) дискового планирования № 1
1. Исходные данные:
• количество цилиндров диска - 1024;
• стартовый цилиндр - 500;
• поступление запросов к дорожкам - случайное (генерировать датчиком случайных чисел);
• среднее время поиска цилиндра - 10 мс;
• скорость вращения - 7200 об/мин;
• дорожка имеет 500 секторов;
• производится чтение файла размером 1 Мбайт;
• дисциплина обслуживания запросов - FIFO.
2. Результаты работы модели должны включать в себя:
• график перемещения головок по цилиндрам;
• количество пересеченных дорожек;
• среднее время чтения файла;
• среднее время поиска файла.
3. Литература: Л7 с. 560 - 568, Л8 с. 357 - 360.
Вариант 9
Исследование алгоритмов (модель) дискового планирования № 2
1. Исходные данные:
• количество цилиндров диска - 1024;
• стартовый цилиндр - 500;
• поступление запросов к дорожкам - случайное (генерировать датчиком случайных чисел);
• среднее время поиска цилиндра - 10 мс;
• скорость вращения - 7200 об/мин;
• дорожка имеет 500 секторов;
• производится чтение файла размером 1 Мбайт;
• дисциплина обслуживания запросов - LIFO.
2. Результаты работы модели должны включать в себя:
• график перемещения головок по цилиндрам;
• количество пересеченных дорожек;
• среднее время чтения файла;
• средняя продолжительность поиска файла.
3. Литература: Л7 с. 560 - 568, Л8 с. 357 - 360.
Вариант 10
Исследование алгоритмов (модель) дискового планирования № 3
1. Исходные данные:
• количество цилиндров диска - 1024;
• стартовый цилиндр - 500;
• поступление запросов к дорожкам - случайное (генерировать датчиком случайных чисел);
• среднее время поиска цилиндра - 10 мс;
• скорость вращения - 7200 об/мин;
• дорожка имеет 500 секторов;
• производится чтение файла размером 1 Мбайт;
• дисциплина обслуживания запросов - RSS.
2. Результаты работы модели должны включать в себя:
• график перемещения головок по цилиндрам;
• количество пересеченных дорожек;
• среднее время чтения файла;
• среднее время поиска файла.
3. Литература: Л7 с. 560 - 568, Л8 с. 357 - 360.
Вариант 11
Исследование алгоритмов (модель) дискового планирования № 4
1. Исходные данные:
• количество цилиндров диска - 1024;
• стартовый цилиндр - 500;
• поступление запросов к дорожкам - случайное (генерировать датчиком случайных чисел);
• среднее время поиска цилиндра - 10 мс;
• скорость вращения - 7200 об/мин;
• дорожка имеет 500 секторов;
• производится чтение файла размером 1 Мбайт;
• дисциплина обслуживания запросов - PRI.
2. Результаты работы модели должны включать в себя:
• график перемещения головок по цилиндрам;
• количество пересеченных дорожек;
• среднее время чтения файла;
• среднее время поиска файла.
3. Литература: Л7 с. 560 - 568, Л8 с. 357 - 360.
Вариант 12
Исследование алгоритмов (модель) алгоритма замены страниц
1. Исходные данные:
• объем области замещения оперативной памяти (резидентное множество) - 4 страницы;
• количество различных страниц - 6;
• последовательность обращения к страницам - задана;
• алгоритм замены - «часовой с двумя стрелками».
2. Результаты работы модели должны включать в себя:
• состояние памяти после поступления очередной страницы;
• число страничных прерываний.
3. Литература: ЛЗ с. 178 - 196, Л7 с. 415 - 421,436 - 437, Л8 с. 245 - 257.
Вариант 13
Исследование алгоритмов (модель) взаимоисключения для двух процессов
1. Исходные данные:
• процессы имеют критические разделы;
• известно четыре варианта, не дающие полного решения проблемы;
• предлагается алгоритм Деккера.
2. Результаты работы модели должны включать в себя:
• доказательство правильности алгоритма Деккера.
3. Литература: Л7 с. 257 - 262, Л8 с. 127 - 132.
Вариант 14
Исследование алгоритмов (модель) взаимоисключения процессов
1. Исходные данные:
• процессы имеют критические разделы;
• известно четыре варианта, не дающие полного решения проблемы;
• предлагается алгоритм Петерсона.
2. Результаты работы модели должны включать в себя:
• доказательство правильности алгоритма Петерсона.
3. Литература: Л7 с. 262 - 263, Л8 с. 127 - 132.
Вариант 15
Анализ свойств и возможностей файловой системы типа FAT
1. Исходные данные:
• известны характеристики магнитных дисков (до 32 Мбайт, 33-64 Мбайт, 65-128Мбайт, 129-255Мбайт, 256-511 Мбайт, 512-1023 Мбайт, 1024-2047 Мбайт, 2048-8192 Мбайт, 8193-16 384 Мбайт, 16 385-32 768 Мбайт, более 32 Гбайт);
• известен минимальный размер кластера - 512 байт;
• характеристики FAT 16 и FAT32.
2. Результаты работы должны включать в себя:
• программу построения таблицы, содержащей для каждого типа диска количество возможных кластеров различного размера, объем адресной информации (абсолютный и в процентах к емкости диска), возможную величину внутренней фрагментации и другие данные по усмотрению исполнителя;
• анализ целесообразности использования FAT 16 или FAT32 в зависимости от ем кости диска.
3. Литература: Л3 с. 279 - 294, Л8 с. 486 - 493.
Вариант 16
Анализ свойств и возможностей файловой системы типа NTFS
1. Исходные данные:
• известны характеристики магнитных дисков (до 32 Мбайт, 33-64 Мбай 65-128 Мбайт, 129-255 Мбайт, 256-511 Мбайт, 512-1023 Мбайт, 1024-2047 Мбай 2048-8192 Мбайт, 8193-16 384 Мбайт, 16 385-32 768 Мбайт, более 32 Гбайт),
• известен минимальный размер кластера - 512 байт;
• характеристики NTFS и NTFS 5.0.
2. Результаты работы должны включать в себя:
• программу построения таблицы, содержащей для каждого типа диска количество возможных кластеров различного размера, объем адресной информации (абсолютный и в процентах к емкости диска), возможную величину внутренне фрагментации и другие данные по усмотрению исполнителя;
• анализ целесообразности использования NTFS и NTFS 5.0 в зависимости от емкости диска и других требований.
3. Литература: ЛЗ с. 299 - 307, Л7 с. 638 -642, Л8 с. 914 – 926
Вариант 17
Анализ свойств и возможностей файловой системы UNIX.
1. Исходные данные:
• известны характеристики магнитных дисков (до 32 Мбайт, 33-64 M6ai 65-128Мбайт, 129-255Мбайт, 256-511 Мбайт, 512-1023 Мбайт, 1024-2047 M6ai 2048-8192 Мбайт, 8193-16 384 Мбайт, 16 385-32 768 Мбайт, более 32 Гбайт);
• известен минимальный размер кластера - 512 байт;
• характеристики s5 и ufs.
2. Результаты работы должны включать в себя:
• программу построения таблицы, содержащей для каждого типа диска количество возможных кластеров различного размера, объем адресной информации (абсолютный и в процентах к емкости диска), возможную величину внутренней фрагментации и др. данные по усмотрению исполнителя;
• анализ целесообразности использования NTFS и NTFS 5.0 в зависимости от емкости диска и других требований.
3. Литература: ЛЗ с. 288 - 290, Л7 с. 634 -637, Л8 с. 493 - 496, 811 -818.
Вариант 18
Анализ свойств и возможностей кластерных систем
1. Исходные данные:
• известные методы кластеризации;
• общие принципы построения кластерных систем;
• архитектуры кластеров;
• Windows 2000 Cluster Server и Sun Cluster;
• параллельные вычисления в кластерах.
2. Результаты работы должны включать в себя:
• представление набора выполняемых процессов взвешенным графом;
• разрезание графа на подграфы с минимизацией сетевого трафика.
3. Литература: Л6 с. 400 - 440, Л7 с. 670 -682, Л8 с. 602 - 605.
Вариант 19
Анализ свойств и возможностей кластерных систем
1. Исходные данные:
• известные методы кластеризации;
• общие принципы построения кластерных систем;
• архитектуры кластеров;
• Windows 2000 Cluster Server и Sun Cluster;
• параллельные вычисления в кластерах.
2. Результаты работы должны включать в себя:
• представление набора выполняемых процессов взвешенным графом;
• разрезание графа на подграфы с равными суммами весов вершин.
3. Литература: Л6 с. 400 - 440, Л7 с. 670 -682, Л8 с. 602 - 605.