Методичка ОС
.pdfvoid qsort(void*lineptr[], int left, int right, int (*соmр)(void*,void*)
);
В качестве своих аргументов функция qsort ожидает массив указателей, два целых значения и функцию с двумя аргументами типа указатель на void. Внутри тела функции qsort мы сможем работать с функцией соmр как с обычной переменной, использовав ее, например, в проверке условия if:
if((*соmр)(v[i],v[left])<0)/*перестановка*/ .
Как производится сборка программы из файлов. Перечислите основные стадии этого процесса.
Сборка программы из файлов осуществляется следующим образом. В первую очередь исходный код обрабатывается препроцессором, который включает нужные файлы и осуществляет макроподстановки. Полученный код компилируется в объектный файл. Заключительный этап проводится линковщиком, который устанавливает в объектном файле все внешние связи. Конечный результат зависит от типа создаваемой программы (библиотека, исполняемый файл и другие возможные варианты).
Также следует отменить, что проводить полную сборку из-за одного незначительного изменения было бы неэффективно, поэтому язык Си разбивает исходный код на единицы компиляции и при повторной сборке перекомпилирует только те единицы, которые изменились.
Как работает препроцессор языка Си, как исполняются директивы #include, #define, #ifdef (#ifndef).
Препроцессор языка Си работает на первом шаге компиляции и осуществляет:
1) Включение файла. Любая строка вида
#include "имя-файла"
или
#include <имя-файла>
заменяется содержимым файла с именем «имя-файла». 2) Макроподстановку.
#define имя замещающий текст
Во всех местах, где встречается лексема «имя», вместо нее будет
11
помещен замещающий текст. 3) Условную компиляцию.
#if !defined(HDR) #define HDR
/* здесь содержимое hdr.h */ #endif
Условная компиляция – это выборочное включение того или иного текста программы в зависимости от значения условия, вычисляемого во время компиляции (схоже с инструкциями if-else). Она позволяет управлять ходом препроцессирования.
Само препроцессирование проистекает в нескольких логически последовательных фазах (в отдельных реализациях некоторые фазы объединены):
1)Трехзнаковые последовательности заменяются их эквивалентами. Между строками вставляются символы новой строки, если того требует операционная система.
2)Выбрасываются пары символов, состоящие из обратной наклонной черты с последующим символом новой строки, тем самым осуществляется «склеивание» строк.
3)Комментарии заменяются единичными пробелами. Затем выполняются директивы препроцессора и макроподстановки.
4)Еsсаре-последовательности в символьных константах и
строковых литералах заменяются на символы, которые они обозначают. Соседние строковые литералы конкатенируются.
Результат препроцессирования транслируется в объектный код. Затем устанавливаются связи с другими программами и библиотеками посредством сбора необходимых программ и данных и соединения ссылок на внешние функции и объекты с их определениями.
3.Задачи на знание основ языка Си
1.Имеется переменная типа double. Напишите выражение для вычисления первой цифры справа от десятичной точки, считая, что значение переменной записано в формате с фиксированной точкой.
2.Имеется переменная типа double. Напишите выражение для вычисления второй цифры слева от десятичной точки в представлении значения этой переменной в формате с фиксированной точкой. Результат запишите в переменную типа
12
char. Если такой цифры в представлении числа нет, то присвойте переменной значение '_'.
3.Найдите все простые числа от 2 до 1000.
4.Найдите все простые делители числа в диапазоне от 2 до 1000.
5.Запишите код для вычисления произведения двух матриц.
6.Напишите функцию, вычисляющую максимальный элемент в массиве. Запишите различные способы передачи массива в функцию и доступа к элементам в самой функции.
7.Создайте в динамической памяти и заполните значением 1.0 нижнетреугольную матрицу размером 10х10, выделив память только под используемые элементы.
8.Напишите функцию, выполняющую сортировку произвольного массива. Критерий упорядочения элементов передать как параметр функции.
4. Задания к лабораторным работам №1-2
Цель лабораторных работ №№1-2: изучение синтаксиса языка Си. В лабораторной работе №1 реализуется алгоритм решения выбранной задачи. В лабораторной работе №2 решение оформляется в виде функций, выполняющих ввод данных пользователя с клавиатуры в консольном режиме, обработку данных согласно заданию и вывод результата.
Вариант №1. Дан двумерный целочисленный массив А(2,10). Известно, что среди его элементов два и только два равны между собой. Напечатать их индексы. Не брать для сравнения одну и ту же пару элементов дважды.
Вариант №2. Составить программу вывода всех трехзначных десятичных чисел, сумма цифр которых равна данному целому числу M.
Вариант №3. В массиве A(N) каждый элемент равен 0, 1 или 2. Переставить элементы массива так, чтобы сначала располагались все нули, затем все двойки и, наконец, все единицы.
Вариант №4. Напечатать все простые числа, не превосходящие заданное число M.
Вариант №5. В написанном выражении ((((1?2)?3)?4)?5)?6 вместо каждого знака «?» вставить знак одной из четырех арифметических операций +, –, *, / так, чтобы результат вычислений равнялся 35. При делении дробная часть в частном отбрасывается. Достаточно найти
13
одно решение.
Вариант №6. Дан одномерный массив. Все его элементы, не равные нулю, переписать, сохраняя их порядок в начало массива, а нулевые элементы – в конец массива.
Вариант №7. Натуральное число называется совершенным, если оно равно сумме всех своих собственных делителей, включая 1. Напечатать все совершенные числа, меньшие, чем заданное M.
Вариант №8. Заданы три числа D, M, Y, которые обозначают число, месяц и год. Найти номер N этого дня с начала года.
Вариант №9. Последовательность чисел определяется следующим образом: первое число – произвольное натуральное число, кратное 3; любое следующее число в последовательности равно сумме кубов всех цифр предыдущего числа. Любая такая последовательность становится постоянной, равной 153. Напишите программу, проверяющую это утверждение.
Вариант №10. Дан одномерный массив положительных вещественных чисел. Преобразовать этот массив следующим образом. Сначала обнуляется минимальный элемент. Затем максимальный элемент из оставшихся элементов. Далее минимальный из оставшихся и так до тех пор, пока не останется единственный элемент. Вывести на экран значение и индекс оставшегося элемента.
5. Задания к лабораторной работе №3
Цель лабораторной работы №3: изучение методов работы с динамической памятью средствами программного интерфейса Win32. В первой части работы пишется программа с функциями создания динамического массива требуемого размера, обработки его согласно заданию, вывода и очистки с использованием функций библиотеки времени исполнения C/C++. Во второй части работы вызовы библиотеки времени исполнения заменяются вызовами программного интерфейса Win32.
Вариант №1. Найти наибольший и наименьший элементы в динамическом массиве размерностью NxM.
Вариант №2. Необходимо каждый элемент строки разделить на сумму элементов строки в динамическом массиве размерностью
NxM.
Вариант №3. Необходимо каждый элемент строки разделить на
14
наибольший элемент строки в динамическом массиве размерностью NxM.
Вариант №4. По динамическому массиву из M вещественных чисел необходимо рассчитать выборочное среднее и выборочную дисперсию.
Вариант №5. Динамический массив размерности MxN необходимо дополнить (M+1)-й строкой и (N+1)-м столбцом, в которых записать суммы элементов соответствующих строк и столбцов. В элементе M+1,N+1 должна храниться сумма всех элементов массива.
Вариант №6. В динамическом массиве размерности MxN необходимо в каждой строке найти элемент с наименьшим значением, а затем среди этих чисел найти наибольшее. На экран вывести индексы этого элемента.
Вариант №7. Транспонировать матрицу, размещенную в динамическом массиве размерности NxN, не используя дополнительного массива.
Вариант №8. В динамическом массиве размерности MxN необходимо найти номер строки и номер столбца, в которых находится наименьший элемент.
Вариант №9. Создать динамический массив из M строк по N символов каждая. Необходимо вывести только те строки, которые являются палиндромами, то есть читаются одинаково слева направо и справа налево.
Вариант №10. Реализовать код для перемножения двух матриц, размещенных в динамических массивах размерности N.
6. Задание к лабораторным работам №4-8
Цель лабораторной работы №4: изучение методов работы с типами данных, определяемых пользователем на языке Си. Требуется реализовать в виде отдельной единицы компиляции (модуля) набор функций и объявлений данных, необходимых для работы с указанным в задании типом данных. В отдельном модуле пишется код для тестирования функций модуля.
Цель лабораторной работы №5: изучение функций ввода вывода в программном интерфейсе Win32. Интерфейс модуля для работы с заданной структурой данных из задания №4 расширяется функциями для сохранения структуры данных на диске целиком и
15
восстановления структуры данных из сохраненного файла.
Цель лабораторной работы №6: изучение методов работы с динамически подключаемыми библиотеками в программном интерфейсе Win32. Из модуля для работы с заданным типом данных, реализованным в задании №5, строится динамически подключаемая библиотека. Тестирующий код выполняет подключение библиотеки с использованием явного (парой вызовов LoadLibrary/GetProcAddress) и неявного (конфигурированием проекта) связывания.
Цель лабораторной работы №7: изучение методов написания многопоточных приложений и синхронизации потоков в программном интерфейсе Win32. В библиотеку функций для работы с заданной структурой данных, реализованную в задании №5 или №6, добавляется следующая функциональность. Вызов функции для добавления элемента в структуру выполняется в одном потоке, обработка вызова с действительным помещением элементов в нее – в другом потоке. Передача аргументов вызова осуществляется через буфер в памяти, доступ к которому синхронизируется. При каждом добавлении элемента в структуру данных происходит ее сохранение на диск целиком, как в задании №5. Тестирующая программа демонстрирует корректность записи элементов путем чтения файла на диске и печати его содержимого по окончании добавления.
Цель лабораторной работы №8: изучение методов работы с процессами в программном интерфейсе Win32. Задание выполняется по схеме задания №7 за исключением того, что поток, осуществляющий фактическое добавление элементов в структуру данных, реализуется в дочернем процессе.
В заданиях рассматриваются следующие абстрактные типы данных.
Ассоциативный массив (словарь) — абстрактный тип данных (интерфейс к хранилищу данных), позволяющий хранить пары вида (ключ, значение) и поддерживающий операции добавления пары, а также поиска и удаления пары по ключу.
Очередь - структура данных с дисциплиной доступа к элементам «первый пришёл - первый вышел». Добавление элемента возможно лишь в конец очереди, выборка - только из начала очереди, при этом выбранный элемент из очереди удаляется.
16
Стек - структура данных, в которой доступ к элементам организован по принципу «последним пришёл - первым вышел». Добавление элемента возможно только в вершину стека. Удаление элемента тоже возможно только из вершины стека, при этом второй сверху элемент становится верхним.
Дэк - двусвязная (двухсторонняя) очередь, «очередь с двумя концами» - структура данных, в которой элементы можно добавлять и удалять как в начало, так и в конец.
Связный список -структура данных, состоящая из узлов, каждый из которых содержит как собственные данные, так и одну или две ссылки на следующий и/или предыдущий узел списка.
Хэш-таблица – структура данных, реализующая ассоциативный массив. При реализации по методу цепочек представляет собой массив указателей на списки. Индекс массива – это хэш-код ключа из пары (ключ, значение). Список, соответствующий элементу массива состоит из элементов (ключ, значение), имеющих одинаковый хэшкод, равный значению индекса этого списка в массиве.
Вариант №1. Требуется реализовать структуру данных «ассоциативный массив» используя динамический массив.
Вариант №2. Требуется реализовать структуру данных «ассоциативный массив» используя связный список.
Вариант №3. Требуется реализовать структуру данных «ассоциативный массив» используя бинарное дерево.
Вариант №4. Требуется реализовать структуру данных «ассоциативный массив» используя хэш-таблицу, построенную по методу цепочек.
Вариант №5. Реализовать очередь на основе связного списка. Вариант №6. Реализовать очередь на основе динамического
массива.
Вариант №7. Реализовать стек на основе связного списка. Вариант №8. Реализовать стек на основе динамического массива. Вариант №9. Реализовать дек на основе связного списка. Вариант №10. Реализовать дек на основе динамического массива.
7. Темы заданий с элементами исследования
Приведенные ниже темы заданий посвящены разработке системных средств автоматизации многопоточного, параллельного и распределенного программирования. Работа по темам заданий
17
выполняется в рамках проекта "ГрафПлюс" [4]. Средства автоматизации представляют собой надстройку над интегрированной средой программирования MS Visual Studio (или аналогичной). Их работа основана на использовании препроцессора и каркасной библиотеки (фреймворка), построенных в терминах специально разработанной модели программирования. Исследования связаны с проектированием компонент данной системы и ее применением. Подробная информация содержится на сайте проекта по адресу http://graphplus.ssau.ru/. В работе над заданиями используются сведения из следующих дисциплин: теория формальных грамматик, методы параллельных вычислений, численные методы, распределенные алгоритмы, методы защиты информации и др. Задания направлены на развитие навыков программирования на языках: С/С++, С#, Java, Objective C, JavaScript, PHP и др.; языках разметки: XML, HTML, CSS; с использованием API и библиотек: Win32, pthread, TBB, Concurrency Runtime и др.
Выполнение задания с элементами исследования включает в себя разработку технического задания по выбранной теме и согласование его с руководителем, проектирование и программную реализацию. По результатам разработки оформляется бумажный отчет и аннотированный листинг в электронном виде.
1.Реализация паттерна управления вычислениями «портфель задач». Рассмотреть, по выбору, высокопроизводительные системы с общей памятью, распределенной памятью и комбинированные архитектуры. Язык программирования
C/C++.
2.Реализация паттернов управления вычислениями для метода переменных направлений. Рассмотреть, по выбору, высокопроизводительные системы с общей памятью, распределенной памятью, вычисления на графических ускорителях и комбинированные архитектуры. Язык программирования C/C++.
3.Имитационное моделирование распределенного алгоритма метода переменных направлений. Требуется реализовать монитор дискретно-событийного моделирования для данного численного метода и провести эксперименты с моделью. Использовать язык программирования С++ для монитора моделирования и язык по выбору для подсистемы визуализации.
18
4.Разработка и исследование статических методов балансировки нагрузки для численных методов, основанных на паттерне «конвейер». Требуется реализовать монитор дискретно-событийного моделирования для данного численного метода и провести эксперименты с моделью. Язык программирования С++ для монитора моделирования и язык по выбору для подсистемы визуализации.
5.Реализация паттерна управления вычислениями «конвейер». Рассмотреть, по выбору, высокопроизводительные системы с общей памятью, распределенной памятью и комбинированные архитектуры. Язык программирования
C/C++.
6.Разработка SAX-парсера. Требуется написать библиотечный модуль SAX-парсера и тесты для него на языке C++. Необходимо изучить спецификацию XML, определить подмножество языка XML, достаточное для описания форматов языка системы, формализовать анализируемый язык методами теории формальных грамматик.
7.Сопряжение с системами программирования Java, .NET и API браузеров. Требуется изучить и документировать методы вызова исполняемого кода из перечисленных сред исполнения. Рассмотреть случаи вызова, как процессов, так и методов в подгружаемых динамических библиотеках. Язык программирования подключаемого кода – C++.
8.API графического редактора для браузера. Изучить имеющиеся библиотеки, адаптировать или разработать заново библиотеки для визуализации файлов системы в webбраузере. Языки реализации – HTML5 и JavaScript.
9.Перенос генератора кода на платформы Java, .NET, C (Objective-C). Требуется изучить API многопоточных вычислений в целевой системе программирования и механизм исполнения системы. Используется язык C++ и язык выбранной платформы.
10.Графический редактор IDE. Реализовать редактор файлов описания модулей языка в системе программирования по выбору.
11.Интеграция IDE с системами программирования. Рассмотреть методы интеграции с IDE Visual Studio, Eclipse и другими по выбору.
12.Сайт исследовательского проекта. Требуется выполнить
19
проектирование и рассмотреть возможности хостинга сайта. Цель сайта – организовать взаимодействие внутри группы разработчиков. Допускается интеграция с существующими порталами аналогичного назначения.
13.Система управления запуском заданий на суперкомпьютере. Цель разработки: автоматизация загрузки и выгрузки файлов проекта на суперкомпьютер, компиляция и запуск, наблюдение за статусом запущенного задания. Необходимо создать для пользователя иллюзию локального исполнения программы.
14.Разработка библиотеки паттернов для параллельных алгоритмов в общей памяти. Задание предусматривает нагрузочное тестирование, сравнение с библиотеками TBB и Concurrency Runtime.
15.Разработка и исследование алгоритмов планирования многопоточных вычислений для SMP-систем. Задание предусматривает нагрузочное тестирование, сравнение с библиотеками TBB и Concurrency Runtime. Требуется реализовать разные методы связывания потоков с процессами, рассмотреть методы оптимизации планировщика.
16.Распределенные объекты. Требуется реализовать взаимодействие между процессами через сокеты и MPI, продумать совмещение разрабатываемой системы с планировщиками потоков разных типов.
17.Разработка алгоритмов планирования для динамических сетей процессов. Требуется реализовать на языке C++ алгоритмы планирования, позволяющие перестраивать сеть взаимодействующих процессов в темпе вычислений для SMPсистем.
18.Разработка алгоритмов планирования для систем с распределенной памятью и стационарных сетей взаимодействующих процессов. Для программ, в которых конфигурация сети процессов определяется перед запуском вычислений, требуется прозрачно для пользователя реализовать исполнение в распределенных кластерных архитектурах. Язык программирования C++.
19.Разработка алгоритмов балансировки для стационарных сетей процессов и гетерогенных систем с распределенной памятью. Реализовать имитационную модель алгоритма
20