5.7 Лабораторная работа № 6 Оптимизация работы с внешним накопителем

Цель работы: Исследовать алгоритмы обслуживания заявок на доступ к дисковому накопителю.

Содержание работы: Имеется накопитель на жестком диске, содержащий С цилиндров, H головок чтения/записи, S секторов на на одной дорожке. Время подвода головок tпг зависит линейно от номера цилиндра Nc: tпг = a * Nc. Также известны значения времени оборота диска to и времени считывания одного сектора t1. Требуется написать программу, моделирующую управление считыванием m блоков информации с диска, и продемонстрировать ее работу на тестовом примере. Каждый из блоков состоит из n секторов, располагающихся на одной и той же дорожке, но необязательно друг за другом. Первоначально программа генерирует всю последовательность m запросов на блоки, при этом каждый запрос состоит из следующих случайным образом сформированных величин: Nc и n номеров секторов. Затем программа выбирает длину очереди обслуживания k =2, 4, 8, …, 512 обслуживает поочередно всю последовательность и подсчитывает время доступа. Значения параметров: С=2048, Н=1 (для упрощения задачи рассматривается только одна поверхность одной пластины накопителя), S=63; a=0,01 мс/цил, to=6 мс, t1=0,1 мс; m=1024, v=9. Конечный результат: График зависимости среднего времени доступа (мс) от параметра k для стратегии, заданной в варианте.

Варианты заданий:

1. Стратегия FCFS (обслуживание первого в очереди), n=1.

2. Стратегия SSTF (обслуживание по наикратчайшему времени доступа), n=1.

3. Стратегия SCAN (обслуживание сканированием), n=1.

4. Стратегия C-SCAN (обслуживание циклическим сканированием), n=1.

5. Стратегия Nstep-SCAN (обслуживание N-шаговым сканированием), n=1.

6. Стратегия FCFS (обслуживание первого в очереди), n=32.

7. Стратегия SSTF (обслуживание по наикратчайшему времени доступа), n=32.

8. Стратегия SCAN (обслуживание сканированием), n=32.

9. Стратегия C-SCAN (обслуживание циклическим сканированием), n=32.

10. Стратегия Nstep-SCAN (обслуживание N-шаговым сканированием), n=32.

5.8 Лабораторная работа № 7. Связь программ на языке высокого уровня и языке ассемблера.

Цель работы: Изучить методы связывания модулей, написанных на разных языках программирования, Способы передачи параметров в подпрограммы.

Содержание работы: Написать на ассемблере процедуру сортировки массива. Массив передается в подпрограмму из основной программы в виде параметра. Вызвать эту процедуру из программы на языке высокого уровня (PascalилиC).

Варианты заданий:

А.Количество элементов массива четко задано:

1. "Пузырек" (обменная сортировка). Если два элемента расположены не по порядку, то они меняются местами. Процесс повторяется до тех пор, пока все элементы не будут упорядочены.

2. Сортировка вставками. Элементы проссматриваются по одному, и каждый новый элемент вставляется в подходящее место среди ранее упорядоченных элементов.

3. Сортировка методом деления пополам. Сортировка вставками, нопоиск места вставки осуществляется методом деления последовательности пополам.

4. Сортировка посредством выбора. Сначала выбирается наименьший (или наибольший) элемент и каким-либо образом отделяется от остальных, затем выбирается наименьший (наибольший) из оставшихся, и т.д.

5. Сортировка подсчетом. Каждый элемент сравнивается со всеми остальными; окончательное положение элемента определяется подсчетом числа меньших элементов.

6. Сортировка Шелла (сортировка с убывающим шагом). Сначала упорядочиваются элементы n div 2 пар, затем n div 4 и т.д.

7. Улучшенный "пузырек" (обменная сортировка). При реализации "пузырька" учитывается, были ли перестановки или нет. Если нет работа программы заканчиваются.

8. "Шейкерная" сортировка. "Пузырек", но направление просмотра меняется на каждом шаге.

9. Обменная сортировка со слиянием (параллельная сортировка Бэтчета).

10. Обменная сортировка с разделением ("быстрая сортировка" Хоара).

В. Количество элементов массива заранее не известно:

11. "Пузырек" (обменная сортировка). Если два элемента расположены не по порядку, то они меняются местами. Процесс повторяется до тех пор, пока все элементы не будут упорядочены.

12. Сортировка вставками. Элементы проссматриваются по одному, и каждый новый элемент вставляется в подходящее место среди ранее упорядоченных элементов.

13. Сортировка методом деления пополам. Сортировка вставками, нопоиск места вставки осуществляется методом деления последовательности пополам.

14. Сортировка посредством выбора. Сначала выбирается наименьший (или наибольший) элемент и каким-либо образом отделяется от остальных, затем выбирается наименьший (наибольший) из оставшихся, и т.д.

15. Сортировка подсчетом. Каждый элемент сравнивается со всеми остальными; окончательное положение элемента определяется подсчетом числа меньших элементов.

16. Сортировка Шелла (сортировка с убывающим шагом). Сначала упорядочиваются элементы n div 2 пар, затем n div 4 и т.д.

17. Улучшенный "пузырек" (обменная сортировка). При реализации "пузырька" учитывается, были ли перестановки или нет. Если нет работа программы заканчиваются.

18. "Шейкерная" сортировка. "Пузырек", но направление просмотра меняется на каждом шаге.

19. Обменная сортировка со слиянием (параллельная сортировка Бэтчета).

20. Обменная сортировка с разделением ("быстрая сортировка" Хоара).