Добавлен: 29.10.2018
Просмотров: 48184
Скачиваний: 190
486
Глава 5. Ввод и вывод информации
Один из способов вывода символа на растровый экран состоит в копировании его
из таблицы шрифтов с помощью процедуры BitBlt. Предположим, что в каком-то
шрифте используются символы размером 16 × 24 пиксела в истинных цветах RGB.
1. Сколько места займет каждый символ в таблице шрифта?
2. Если копирование одного байта занимает 100 нс, включая издержки, чему равна
скорость вывода в символах в секунду?
46. Если предположить, что копирование байта занимает 10 нс, сколько времени
понадобится для полной перерисовки отображаемого на адресное пространство
памяти экрана из 80 символов по 25 строк, работающего в текстовом режиме?
Сколько времени понадобится для графического экрана разрешением 1024 × 768
и глубиной цвета 24 бита?
47. В листинге 5.2 показан класс RegisterClass. В соответствующем коде X Window,
показанном в листинге 5.1, нет ни такого вызова, ни чего-либо ему подобного.
Почему?
48. В тексте был приведен пример вывода на экран прямоугольника с помощью ин-
терфейса Windows GDI
Rectangle(hdc, xleft, ytop, xright, ybottom);
Нужен ли здесь первый параметр (hdc), и если да, то зачем? Ведь координаты
прямоугольника задаются явным образом в виде параметров.
49. Терминал тонкого клиента используется для отображения веб-страницы, со-
стоящей из мультфильма размером 400 × 160 пикселов, демонстрирующегося
с частотой 10 кадров в секунду. Какую часть потока данных в сети Fast Ethernet
со скоростью передачи данных 100 Мбит/с займет демонстрация мультфильма?
50. Подмечено, что система тонкого клиента хорошо работает в тестовом режиме
с сетью со скоростью передачи данных 1 Мбит/с. Ожидаются ли какие-нибудь
проблемы в многопользовательском режиме работы?
Подсказка
: рассмотрите вариант с большим количеством пользователей, просма-
тривающих телепередачу, и таким же количеством пользователей, просматриваю-
щих информацию в Интернете.
51. Какие два преимущества и два недостатка свойственны вычислениям с использо-
ванием тонких клиентов?
52. Если максимальное напряжение питания центрального процессора V снижено до
значения V/n, его энергопотребление падает до 1/n
2
от первоначального значения,
а тактовая частота снижается до 1/n от первоначального значения. Предположим,
что пользователь вводит данные со скоростью 1 символ в секунду, а центральному
процессору для обработки каждого символа требуется 100 мс. Каким будет опти-
мальное значение n и сколько будет сэкономлено энергии по сравнению с работой
без снижения напряжения питания? Предположим, что простаивающий централь-
ный процессор вообще не потребляет электроэнергии.
53. Ноутбук настроен на режим максимального энергосбережения с отключением
дисплея и жесткого диска после определенного периода бездействия. Пользо-
ватель иногда запускает UNIX-программы в текстовом режиме, а все остальное
время использует X Window System. У него вызвало удивление то, что ноутбук
работал от аккумуляторной батареи значительно дольше, когда он пользовался
Вопросы
487
программами, работающими исключительно в текстовом режиме. Почему так
произошло?
54. Напишите программу, которая имитирует стабильное хранилище данных. Вос-
пользуйтесь двумя большими файлами фиксированного размера на вашем диске
для имитации двух дисков.
55. Напишите программу, реализующую три алгоритма перемещения блока головок.
Напишите программу драйвера, генерирующую обращения к произвольным
цилиндрам с номерами в диапазоне от 0 до 999, запустите все три алгоритма для
этой последовательности обращений и распечатайте суммарное расстояние пере-
мещений (в количестве цилиндров), которое необходимо преодолеть при исполь-
зовании этих трех алгоритмов.
56. Напишите программу, реализующую несколько таймеров при использовании
одних часов. Входные данные этой программы должны включать последователь-
ность из четырех типов команд (S <int>, T, E <int>, P): команда S <int> устанав-
ливает текущее время, соответствующее параметру <int>; команда T — это такт
часов; команда E <int> планирует сигнал, подаваемый во время <int>; команда P
выводит на печать значение текущего времени, следующего сигнала и заголовка
таймера. Ваша программа должна также выводить на печать отчет о каждом сроке
выдачи сигнала.
Гл а в а 6
.
Взаимоблокировка
В компьютерных системах множество ресурсов, которые одновременно могут исполь-
зоваться только одним процессом. Стоит лишь вспомнить принтеры, накопители на
магнитной ленте для резервного копирования данных компаний и элементы во вну-
тренних системных таблицах. Если два процесса одновременно выводят информацию
на принтер, то получается полная тарабарщина. Если два процесса будут использовать
один и тот же элемент таблицы файловой системы, то эта система непременно будет
повреждена. Поэтому все операционные системы способны временно предоставлять
процессу исключительные права доступа к конкретным ресурсам.
При работе многих приложений процессу нужен исключительный доступ не к одному,
а сразу к нескольким ресурсам. Предположим, к примеру, что каждый из двух процес-
сов захотел записать отсканированный документ на Blu-ray-диск. Процесс A запраши-
вает разрешение на использование сканера и получает его. Процесс B запрограмми-
рован по-другому: сначала он запрашивает разрешение на использование пишущего
привода Blu-ray-дисков и также получает это разрешение. Теперь A запрашивает разре-
шение на использование пишущего привода Blu-ray-дисков, но запрос отклоняется до
тех пор, пока это устройство не будет освобождено процессом B. К сожалению, вместо
того чтобы освободить привод, B запрашивает разрешение на использование сканера.
И в этот момент оба процесса оказываются заблокированными навсегда. Такая ситуа-
ция называется тупиковой ситуацией (тупиком), или взаимоблокировкой (deadlock).
Взаимоблокировки могут случаться и между машинами. К примеру, многие офисы
оборудованы локальной сетью, к которой подключено множество компьютеров. До-
вольно часто такие устройства, как сканеры, пишущие приводы Blu-ray-дисков и DVD,
принтеры и приводы накопителей на магнитной ленте, подключены к сети в качестве
ресурсов общего пользования, доступных любому пользователю на любой машине.
Если эти устройства могут быть дистанционно зарезервированы (например, с домаш-
него компьютера пользователя), то может возникнуть взаимоблокировка, похожая на
только что рассмотренную. При более сложных обстоятельствах во взаимоблокировку
могут быть вовлечены три, четыре и более устройств и пользователей.
Взаимоблокировки могут возникать и при массе других обстоятельств. К примеру,
в системах управления базами данных, во избежание попадания в состояние состяза-
ния программе может понадобиться блокировка нескольких используемых ею запи-
сей. Если процесс A блокирует запись R1, а процесс B блокирует запись R2, а затем
каждый процесс пытается заблокировать запись другого процесса, то получается та же
взаимоблокировка. Таким образом, взаимоблокировки могут появляться при работе
как с аппаратными, так и с программными ресурсами.
В данной главе будут рассмотрены разновидности взаимоблокировок, условия их воз-
никновения, а также некоторые пути предотвращения взаимоблокировок или уклоне-
ния от их возникновения. Хотя этот материал касается взаимоблокировок в контексте
6.1. Ресурсы
489
операционных систем, они также случаются в системах управления базами данных и во
многих других компьютерных областях, поэтому приводимые здесь сведения приме-
нимы к широкому спектру многозадачных систем. На тему взаимоблокировок суще-
ствует множество научных трудов. Библиографии по этой теме дважды публиковались
в Operating Systems Review, и на них стоит обратить внимание в качестве источников
справочной информации (Newton, 1979; Zobel, 1983). Хотя этим библиографиям уже
много лет, основная часть работ по взаимоблокировкам была завершена до 1980 года,
поэтому они все еще не утратили своей актуальности.
6.1. Ресурсы
Основная часть взаимоблокировок связана с ресурсами, к которым некоторым про-
цессам были предоставлены исключительные права доступа. К их числу относятся
устройства, записи данных, файлы и т. д. Чтобы придать рассмотрению взаимобло-
кировок как можно более универсальный характер, мы будем называть объекты,
к которым предоставляется доступ, ресурсами. Ресурсами могут быть аппаратные
устройства (например, привод Blu-ray-дисков) или какая-то часть информации (на-
пример, запись базы данных). Обычно у компьютера может быть множество ресурсов,
которые могут быть предоставлены процессу. Некоторые ресурсы могут быть доступ-
ны в нескольких идентичных экземплярах, например три привода Blu-ray-дисков.
Когда доступны несколько копий ресурса, то для удовлетворения любого запроса
на ресурс может быть использован один из них. Короче говоря, под ресурсом по-
нимается все, что должно предоставляться, использоваться и через некоторое время
высвобождаться, поскольку в один и тот же момент времени может использоваться
только одним процессом.
6.1.1. Выгружаемые и невыгружаемые ресурсы
Ресурсы бывают двух видов: выгружаемые и невыгружаемые. К выгружаемым отно-
сятся такие ресурсы, которые могут быть безболезненно отобраны у процесса, который
ими обладает. Примером такого ресурса может послужить память. Рассмотрим систему,
имеющую 1 Гбайт пользовательской памяти, один принтер и два процесса по 1 Гбайт,
каждый из которых хочет что-то вывести на печать. Процесс A запрашивает и полу-
чает принтер, а затем начинает вычислять значение, предназначенное для вывода на
печать. Но до завершения вычисления истекает выделенный ему квант времени, и он
выгружается на диск.
Теперь запускается процесс B, безуспешно, как оказывается, пытаясь завладеть прин-
тером. Потенциально возникает ситуация взаимоблокировки, поскольку у процесса
A есть принтер, а у процесса B — память и ни один из них не может продолжить свою
работу без ресурса, удерживаемого другим процессом.
К счастью, есть возможность отобрать память у процесса B, выгрузив этот процесс на
диск, и загрузить оттуда процесс A. Теперь A может возобновить свою работу, выпол-
нить распечатку и высвободить принтер. И никакой взаимоблокировки не возникнет.
А вот невыгружаемый ресурс нельзя отобрать у его текущего владельца, не вызвав
потенциально сбоя в вычислениях. Если у процесса, который уже приступил к записи
на Blu-ray-диск, внезапно отобрать пишущий привод и отдать его другому процессу,
490
Глава 6. Взаимоблокировка
это приведет к порче Blu-ray-диска. Пишущие приводы Blu-ray-дисков нельзя отобрать
в произвольный момент.
Выгружаемость ресурса зависит от контекста. На стандартном персональном ком-
пьютере память является выгружаемым ресурсом, поскольку страницы всегда мо-
гут быть выгружены на диск, чтобы нужный объем свободной памяти был восста-
новлен. А на смартфоне, не поддерживающем свопинг или страничную организацию
памяти, простой выгрузкой взаимоблокировки из-за дефицита памяти избежать не
удастся.
Как правило, во взаимоблокировках фигурируют невыгружаемые ресурсы. Обычно
потенциальные взаимоблокировки с участием выгружаемых ресурсов могут быть
устранены путем перераспределения ресурсов от одного процесса к другому. Поэтому
наше внимание будет сконцентрировано на невыгружаемых ресурсах.
В наиболее общем виде при использовании ресурса происходит следующая последо-
вательность событий:
1. Запрос ресурса.
2. Использование ресурса.
3. Высвобождение ресурса.
Если во время запроса ресурс недоступен, запрашивающий процесс вынужден перей-
ти к ожиданию. В некоторых операционных системах при отказе в выделении за-
прошенного ресурса процесс автоматически блокируется, а когда ресурс становится
доступен — возобновляется. В других системах отказ в выделении запрашиваемого
ресурса сопровождается кодом ошибки, и принятие решения о том, что следует делать,
немного подождать или попытаться снова получить ресурс, возлагается на вызываю-
щий процесс.
Процесс, чей запрос на выделение ресурса был только что отклонен, обычно входит
в короткий цикл: запрос ресурса, затем приостановка, — после чего повторяет попытку.
Хотя этот процесс не заблокирован, но по всем показателям он является фактически
заблокированным, поскольку не может выполнять никакой полезной работы. При
дальнейшем рассмотрении вопроса мы будем предполагать, что при отказе в выделении
запрошенного ресурса процесс впадает в спячку.
Особенности запроса ресурса существенно зависят от используемой системы. В неко-
торых системах для запроса предоставляется системный вызов request, позволяющий
процессам запросить ресурс в явном виде. В других системах единственными ресур-
сами, о которых знает операционная система, являются специальные файлы, которые
в конкретный момент времени могут быть открыты только одним процессом. Они
открываются с использованием обычного вызова open. Если файл уже используется,
вызывающий процесс блокируется до тех пор, пока файл не будет закрыт текущим
владельцем.
6.1.2. Получение ресурса
Для некоторых видов ресурсов, таких как записи в базе данных, управление использо-
ванием ресурсов зависит от самих пользовательских процессов, а не от системы. Один
из способов, позволяющих ввести пользовательское управление ресурсами, заключа-
ется в присоединении семафора к каждому из ресурсов.