Танненбаум Е. Архітектура компютера [pdf]

Виртуальные команды ввода-вывода

47

В листинге 6.1 на языке Java показано решение задачи с производителем и по требителем.

Здесь используются три класса: m,produser и consumer. Класс т содержит неко торые константы, указатели буфера in и out и сам буфер, который в нашем пример вмещает 100 простых чисел (от buffer[O] до buffer[99]).

Для моделирования параллельных процессов в данном случае используютс потоки (threads). У нас есть классproducerи класс consumer, которым приписыва ются значения переменных р и с соответственно. Каждый из этих классов образу ется из базового класса Threadс процедурой run. Класс run содержит код для threa Когда вызывается процедура start для объекта, образованного из Thread, запуска ется новый поток.

Каждый поток похож на процесс. Единственным различием является то, чт все потоки в пределах одной программы на языкеJava работают в одном адресно пространстве. Это позволяет им разделять один общий буфер. Если в компьютер имеется два и более процессоров, каждый поток может выполняться на друго процессоре, поэтому в данном случае имеет место реальный параллелизм. Есл компьютер содержит только один процессор, потоки разделяются во времени н одном процессоре. Мы будем продолжать называть производителя и потребител процессами (поскольку нас в данный момент интересуют параллельные процес сы), хотя Java поддерживает только параллельные потоки, а не реальные парал лельные процессы.

Функция next позволяет увеличивать значения in и out, при этом не нужно каж дый раз записывать код, чтобы проверить условие циклического возврата. Есл параметр в next равен 98 или указывает на более низкое значение, то возвращаетс следующее по порядку целое число. Если параметр равен 99, это значит, что м наткнулись на конец буфера, поэтому возвращается 0.

Должен быть способ «усыплять» любой из процессов, если он не может про должаться. Для этого разработчики Java включили в класс Thread специальны процедуры suspend (отключение) и resume (возобновление). Они используютс

влистинге 6.1.

Атеперь рассмотрим саму программу для производителя и потребителя. Сна чала производитель порождает новое простое число (шаг Р1). Обратите внимани на строку m.MAX_PRIME. Префикс т. здесь указывает, что имеется в виду MAXPRIM определенный в классе т. По той же причине этот префикс нужен для in, out, buffe и next.

Затем производитель проверяет (шаг Р2), не находится ли in ниже out. Если д (например, ш=62 и out=63), то буфер заполнен и производитель вызывает проце дуру suspend в Р2. Если буфер не заполнен, туда помещается новое простое числ (шаг РЗ) и значение in увеличивается (шаг Р4). Если новое значение in на 1 боль ше значения out (шаг Р5) (например, ш=17, out=l6), значит, in и out были равн

4 7 4 Глава 6. Уровень операционной системы

Листинг 6 . 1 . Параллельная обработка с состоянием гонок

public class m {

final public static int BUF_SIZE = 100;

final public static long MAX_PRIME=100000000000L; public static int in = 0, out = 0.

public static long buffer[ ] - new long[BUF_SIZE];

public	static	producer	p.
public	static	consumer	c;
public	static void mam(Stnng args[ ]){
	p = new producer );

с= new consumer ), p startO:

сstartO .

//буфер от 0 до 99 //остановиться здесь

//указатели на данные //простые числа хранятся //имя производителя //имя потребителя

//основной класс //создание производителя //создание потребителя //запуск производителя //запуск потребителя

//Это утилита для циклического увеличения m и out
public	static int next(int k) { i f		(k < BUF_SIZE	- 1) return(k+l). else re
class producer extends Thread {				//класс производителя
public	void runO {			//код производителя
long prime = 2;				// временная переменная
while		(prime < m.MAX_PRIME)	{
	prime = next_pnme(pnme):			//шаг Р1
	if (m next(m.m) == m.out) suspendO:			//шаг Р2
	m	buffer[m. in] = prime;		//шаг	РЗ
	m in = m.next(m in).			//шаг	Р4
	if	(m next(m out) = m in)	m c.resumeO.	//шаг	Р5

private long next_pnme(long pnme){ ..}		//функция, вычисляющая сл
class consumer extends Thread {	//класс		потребителя
public void run() {	//	код	потребителя
long emirp = 2;	//	временная переменная
while (emirp < m MAX_PRIME) {
if (m in == m out) suspendO:			//шагС1
emirp = m buffer[m.out]:			//шагС2
m.out = m next(m out);			//шагСЗ
if (m.out — m.next(m next(m.in))) m	p.resumeO; //шагС4
System out print!n(emirp).			//шагС5

Программа потребителя по структуре очень проста. Сначала произво верка (шаг С1), чтобы узнать, пуст ли буфер. Если он пуст, то потребите не нужно делать, поэтому он отключается. Если буфер не пуст, то потреб

Виртуальныекомандыввода-вывода

4 7 5

К сожалению, такая программа содержит ошибку (рис. 6.23). Напомним, что эти два процесса работают асинхронно и с разными скоростями, которые, к тому же, могут меняться. Рассмотрим случай, когда в буфере осталось только одно число в элементе 21, и m=22, a out=2i (см. рис. 6.23, а). Производитель на шаге Р1 ищет простое число, а потребитель на шаге С5 печатает число из позиции 20. Потребитель заканчивает печатать число, совершает проверку на шаге С1 и забирает последнее число из буфера на шаге С2. Затем он увеличивает значение out. В этот момент и in и ом? равны 22. Потребитель печатает число, а затем переходит к шагу С1, на котором он вызывает in и out из памяти, чтобы сравнить их (рис. 6.23, б).

		Процесс-производитель
Процесс-производитель	Процесс-производитель	на шаге Р5 посылает
на шаге Р1	на шаге Р1	сигнал пробуждения
Процесс-потребитель	Процесс-потребитель	процессу-потребителю
на шаге С5	на шаге С5	на шаге С1
100	100	100

		In = 23
In = 22	In = Out = 22	Out = 22	Простое
Out = 21	Простое		число
	число
	1 число		1 число
			в буфере
	в буфере

Рис. 6.23. Ситуация, при которой механизм взаимодействия производителя wпотребителя не работает

Вэтот момент, после того как потребитель вызвал in и out, но еще до того как он сравнил их, производитель находит следующее простое число. Он помещает это простое число в буфер на шаге РЗ и увеличивает in на шаге Р4. Теперь щ=23,

аом£=22. На шаге Р5 производитель обнаруживает, что in=*next(out). Иными словами, in на единицу больше out, а это значит, что в буфере в данный момент находится один элемент.

Исходя из этого, производитель делает неверный вывод, что потребитель отключен, и вызывает процедуру resume (рис. 6.23, в). На самом деле потребитель все это время продолжал работать, поэтому вызов процедуры resume оказался ложным. Затем производитель начинает искать следующее простое число.

Вэтот момент потребитель продолжает работать. Он уже вызвал in и out из

4 7 6 Глава 6. Уровень операционной системы

Производитель продолжает цикл. В конце концов он заполняет буфер и ется. Теперь оба процесса отключены и будут находиться в таком сост скончаниявеков.

Сложность здесь в том, что между моментом, когда потребитель выз out, и моментом, когда он отключается, производитель, обнаружив, что in предположив, что потребитель отключен (хотя на самом деле он еще пр функционировать), вызывает процедуру resume, чего не нужно делать, п потребитель функционирует. Такая ситуация называется состоянием скольку успех процедуры зависит от того, кто выиграет гонку по проверк после того как значение out увеличилось.

Проблема состояния гонок хорошо известна. Она была настолько сер через несколько лет после появления Java компания Sun изменила кла и убрала вызовы процедур suspend и resume, поскольку они очень часто п к состоянию гонок. Предложенное решение было основано на изменен но поскольку мы изучаем операционные системы, мы обсудим другое которое используется во многих операционных системах, в том числе UN

Синхронизация процесса с использованием семафоров

Проблему состояния гонок можно разрешить по крайней мере двумя сп Первый способ — снабдить каждый процесс специальным битом ожида буждения. Если процесс, который функционирует в данный момент, пол нал «пробуждения», то этот бит устанавливается. Если процесс отключа момент, когда этот бит установлен, он немедленно перезапускается, а би вается. Данный бит сохраняет сигнал пробуждения для будущего испол

Этот метод решает проблему состояния гонок только в том случае, е есть всего 2 процесса. В общем случае при наличии п процессов он не Конечно, каждому процессу можно приписать п-1 таких битов ожидани дения, но это неудобно.

Дейкстра [31] предложил другое решение этой проблемы. Где-то в па ходятся две переменные, которые могут содержать неотрицательные цел Эти переменные называются семафорами. Операционная система пред два системных вызова, up и down, которые оперируют семафорами. Up пр 1 к семафору, a down отнимает 1 от семафора. Если операция down сов над семафором, значение которого больше 0, этот семафор уменьшается н цесс продолжается. Если значение семафора равно 0, то операция down завершиться. Тогда данный процесс отключается до тех пор, пока друго не выполнит операцию up над этим семафором.

Команда up проверяет, не равен ли семафор нулю. Если он равен 0 процесс находится в режиме ожидания, то семафор увеличивается на 1. П

Виртуальные команды ввода-вывода

4 7

другой процесс не может получить доступ к этому семафору до тех пор, пока пе вый не завершит выполнение команды или не будет приостановлен при попыт выполнить команду down над 0. В таблице 6.5 изложены важные свойства систе ных вызовов up и down.

Таблица 6.5. Результаты операций над семафором
Команда	Семафор = 0	Семафор > О
Up	Семафор = семафор + 1; если другой процесс пытается	Семафор = семафор +1
	совершить команду down над этим семафором, теперь
	он сможет это сделать и продолжить свою работу
Down	Процесс останавливается до тех пор, пока другой	Семафор = семафор -1
	процесс не выполнит операцию up над этим
	семафором

Как мы уже сказали, в языке Java предусмотрено свое решение проблемы с стояния гонок, но мы сейчас обсуждаем операционные системы. Следовательн нам нужно каким-либо образом выразить использование семафоров в языке Ja Мы предположим, что были написаны две процедуры, up и down, которые сове шают системные вызовы up и down соответственно. Используя в качестве пар метров обычные целые числа, мы сможем выразить применение семафоров в пр граммах на языке Java.

В листинге 6.2 показано, как можно устранить состояние гонок с помощью мафоров. В класс т добавляются два семафора: available, который изначально р вен 100 (это размер буфера), w.filled, который изначально равен 0. Производите начинает работус шага Р1, а потребитель — с шага С1. Выполнение процедуры do над семафором filled сразу же приостанавливает работу потребителя. Ког производитель находит первое простоечисло, он вызывает процедуруdown сavaila в качестве параметра, устанавливая available на 99. На шаге Р5 он вызывает пр цедуру up с параметромfilled, устанавливаяfilled на 1. Это действие освобожда потребителя, который теперь может завершить вызов процедуры down. После эт гоfilled принимает значение 0, и оба процесса продолжают работу.

А теперь давайте еще раз рассмотрим состояние гонок. В определенный моме ш=22, a out=2\, производитель находится на шаге Р1, а потребитель — на шаге С Потребитель завершает действие и переходит к шагу С1, который вызывает пр цедуру down, чтобы выполнить ее над семафором filled, который до вызова им значение 1, а после вызова принял значение 0. Затем потребитель берет последн число из буфера и выполняет процедуру up над available, после чего available пр нимает значение 100. Потребитель печатает это число и переходит к шагу С1.

Как раз перед тем, как потребитель может вызвать процедуру down, производ тель находит следующее простое число и быстро выполняет шаги Р2, РЗ и Р4.

В этот MOMemfilled=0. Производитель собирается выполнить над ним коман up, а потребитель собирается вызвать процедуру up. Если потребитель выполн

Ч/О	Глава Ь. Уровень операционной системы

Операции над семафорами неделимы. Если операция над семаф лась, то никакой другой процесс не может использовать этот сема пока первый процесс не завершит операцию или пока он не будет п Более того, при наличии семафоров сигналы пробуждения не пр операторы if в листинге 6.1 делимы. Между проверкой условия и нужного действия другой процесс может послать сигнал пробужде

Всущности, проблема синхронизации была устранена путем вв мых системных прерываний up и down. Чтобы эти операции был операционная система должна запретить двум и более процессам исп семафор одновременно. Если был сделан системный вызов up или другой код пользователя не будет запущен, пока данный вызов не за этого обычно во время выполнения операций над семафорами ввод прерывания.

Технология с использованием семафоров работает для произво ства процессов. Несколько процессов могут «спать», не завершив с зов down на одном и том же семафоре. Когда какой-нибудь другой п нит процедуру up на том же семафоре, один из ждущих процессов мо вызов down и продолжить работу. Семафор сохраняет значение 0, и сы продолжают ждать.

Поясним это на другом примере. Представьте себе 20 баскетбо Они играют 10 партий (процессов). Каждая игра происходит на о Имеется большая корзина (семафор) для баскетбольных мячей. К с только 7 мячей. В каждый момент в корзине находится от 0 до 7 м принимает значение от 0 до 7). Помещение мяча в корзину — это оп скольку она увеличивает значение семафора. Извлечение мяча из операция down, поскольку она уменьшает значение семафора.

Всамом начале один игрок от каждого поля посылается к кор Семерым из них удается получить мяч (завершить операцию dow трое вынуждены ждать мяч. Их игры временно приостановлены. В одна из партий заканчивается и мяч возвращается в корзину (выпо ция up). Эта операция позволяет одному из трех оставшихся игр мяч (закончить незавершенную операцию down) и продолжить игр две партии остаются приостановленными до тех пор, пока еще два тятся в корзину. Когда эти два мяча положат в корзину (то есть бу еще две операции up), можно будут продолжить последние две пар

Листинг 6.2. Параллельная обработка с использованием семафоров

public class m {
final	public	static int BUF_SIZE = 100.	//буфер от	0
final	public	static long MAX_PRIME=100000000000L.	//остановиться	зде
public static int in = 0. out = 0.			//указатели

	Примеры операционных систем			479
public static vend mainCStnng args[ ]) {	//основной		клласс
p = new producerO;	//создание		производителя
с = new consumerO;	//создание		потребителя
p.startO:	//запуск	производителя
с startO:	//запуск	потребителя

// Это утилита для циклического увеличения in и out

public static int nextdnt k) {if (k < BUF_SIZE - 1) return(k+l): else return(O).

class producer extends Thread {

native void updnt s); native void downdnt s); public void run() {

long prime - 2;

while (prime < m.MAX_PRIME) { prime = next_pnme(pnme): downtm.available);

m buffer[m in] = prime; m.in = m next(m.in); up(m.filled);

private long next_pnme(long pnme){ ...}

class consumer extends Thread {

native void updnt s); native void downdnt s); public void runC) {

long emirp = 2,

while (emirp < m MAX_PRIME) { down(m.filled),

emirp = m.buffer[m.out]; m.out = m next(m out); up(m. available): System.out.print!n(emirp);

//класс производителя //процедуры над семафорами //код производителя //временная переменная

//шагР1

//шагР2

//шагРЗ

//шагР4

//шагР5

//функция, которая выдает следующее число

//класс потребителя //процедуры над семафорами //код потребителя //временная переменная

//шагС1

//шагС2

//шагСЗ //шаг С4 //шагС5

Примеры операционных систем

В этом разделе мы продолжим обсуждать Pentium II и Ultra SPARC П. Мы рассмотрим операционные системы, которые используются на этих процессорах.

Для Pentium II мы возьмем Windows NT (для краткости мы будем называть

4 8 0 Глава 6. Уровень операционной системы

Введение

В этом разделе мы дадим краткий обзор двух операционных систем (UN При этом мы обратим особое внимание на историю, структуру и системны

UNIX

Операционная система UNIX была разработана в компании Bell Labs 70-х годов. Первая версия была написана Кеном Томпсоном (Ken Tho ассемблере для мини-компьютера PDP-7. Затем была написана втора для компьютера PDP-11, уже на языке С. Ее автором был Деннис Ритч Ritchie). В 1974 году Ритчи и Томпсон опубликовали очень важную раб теме UNIX [120]. За эту работу они были награждены престижной Тьюринга Ассоциации вычислительной техники (Ritchie, 1984; Thomps После публикации этой работы многие университеты попросили у Bel пию UNIX. Поскольку материнская компания Bell Labs, AT&T была в то регулируемой монополией и ей не разрешалось принимать участие в терном бизнесе, университеты смогли приобрести операционную систе за небольшую плату.

PDP-11 использовались практически во всех компьютерных научны университетов, и операционные системы, которые пришли туда вместе с не нравились ни профессорам, ни студентам. UNIX быстро заполнил Эта операционная система была снабжена исходными текстами, поэт могли до бесконечности исправлять ее.

Одним из первых университетов, которые приобрели систему UNIX лифорнийский университет в Беркли. Поскольку имелась в наличии п ходная программа, в Беркли сумели существенно преобразовать эту сист ди изменений было портирование этой системы на мини-компьютер VAX, виртуальной памяти со страничной организацией, расширение имен фа символов до 255, а также включение сетевого протокола TCP/IP, котор используется в Интернете (во многом благодря тому факту, что он был Berkeley UNIX).

Пока в Беркли производились все эти изменения, компания AT&T с тельно продолжала разработку UNIX, в результате чего в 1982 году п System III, а в 1984 — System V. В конце 80-х годов широко использов разные и совершенно несовместимые версии UNIX: Berkeley UNIX и Такое положение, да еще и отсутствие стандартов на форматы программ ном коде сильно препятствовало коммерческому успеху системы UNIX щики программного обеспечения не могли писать программы для UNI было никакой гарантии, что эти программы будут работать на любой верс (как было сделано с MS DOS). После долгих споров комиссия стандарт ституте инженеров по электротехнике и электронике выпустила станда (Portable Operating System-IX — интерфейс переносной операционной с

Примеры операционных систем

481

Стандарт POSIX разделен на несколько частей, каждая из которых покрывает отдельную область системы UNIX. Первая часть Р 1003.1 определяет системные вызовы; вторая часть Р1003.2 определяет основные обслуживающие программы и т. д. Стандарт Р1003.1 определяет около 60 системных вызовов, которыедолжны поддерживаться всеми соответствующими системами. Это вызовы для чтения и записи файлов, создания новых процессов и т. д. Сейчас практически все системы UNIX поддерживают системные вызовы Р1003.1. Однако многие системы UNIX поддерживают и дополнительные системные вызовы, в частности те, которые определены в System V или в Berkeley UNIX. Обычно к набору POSIX добавляется до 100 системных вызовов. Операционная система для машины UltraSPARC II основана на System V. Она называется Solaris. Она поддерживает и многие вызовы из системы Berkeley.

В табл. 6.6 приведены категории системных вызовов. Системные вызовы управления файлами и директориями — это самые большие и самые важные категории. Большинство из них относятся к стандарту Р1003.1. Остальные происходят из системы System V.

Таблица 6.6. Системные вызовы UNIX

Категория	Примеры
Управлениефайлами	Открытие, чтение, запись, закрытие и блокировка файлов
Управлениедиректориями	Создание и удалениедиректорий; перемещение файлов
	по директориям
Управление процессами	Порождение, завершение, отслеживание процессов
	ипередачасигналов
Управлениепамятью	Разделение общей памяти между процессами; защита страниц

Вызов/установкапараметров Идентификацияпользователя,группы,процесса;установка

	приоритетов
Даты и периодывремени	Указание на время доступа к файлам; использование датчика
	временных интервалов; рабочий профиль программы
Работа в сети	Установка/принятие соединения; отправка/получение
	сообщения
Прочее	Учет использования ресурсов; ограничение на доступный
	объем памяти; перезагрузка системы

Сфера использования сетей в большей степени относится к Berkeley UNIX, а не к System V. В Беркли было введено понятие сокет (конечный пункт сетевой связи). Четырехпроводные стенные розетки, к которым можно подсоединять телефоны, послужили в качестве модели этого понятия. Процесс в системе UNIX может создать сокет, присоединиться к нему и установить связь с сокетом на удаленном компьютере. По этой связи можно пересылать данные в обоих направлениях, обычносиспользованиемпротоколаTCP/IP. Посколькутехнологиясетевойсвязидесятилетиями применялась в системе UNIX, значительное число серверов в Интер-

4 8 2 Глава 6. Уровень операционной системы

из них. Внизу находятся драйверы устройств, которые защищают систе от аппаратного обеспечения. Изначально каждый драйвер устройства сан отдельно от всех других и представлял собой независимую единицу вело к многочисленным дублированиям, поскольку многиедрайверы дол дело с управлением потоками, исправлением ошибок, приоритетами, о данных от команд и т. д. По этой причине Деннис Ритчи изобрел стр названием поток для написания драйверов в модулях. При наличии пот установить двустороннюю связь между пользовательским процессом и ус аппаратного обеспечения и вставить между ними один или нескольк Пользовательский процесс передает данные в поток, а затем эти данные ваются или передаются дальше каждым модулем до тех пор, пока они не аппаратного обеспечения. При передаче данных от аппаратного обеспе исходит обратный процесс.

Оболочка	Пользовательская		Пользо
	программа
			р
Интерфейссистемныхвызовов
Система файлов	Управление процессами		Привил
	Межпроцессорная
Кэш блоков		Планирование	р
	связь
Драйверы устройств		Управление

Сигналы

памятью

Аппаратное обеспечение

Рис. 6.24. Структура типичной системы UNIX

Над драйверами устройств находится система управления файлами. ляет именами файлов, директориями, расположением блоков на диск и выполняет многие другие функции. В системе файлов имеется так на кэш блоков для хранения недавно считанных с диска блоков, на случа понадобятся еще раз. Некоторые системы файлов использовались на пр многих лет. Среди них можно назвать быструю файловую систему Berk журналирующие файловые системы [121].

Еще одна часть ядра системы UNIX — структура управления процес выполняет различные функции, в том числе управляет межпроцессорн которая позволяет разным процессам взаимодействовать друг с другом низирует работу процессов, чтобы избежать состояния гонок. Для этого ет ряд механизмов. Код управления процессами также управляет план