Архитектура операционной системы UNIX

       

в программе debug будет отсутствовать


1. Что произойдет в том случае, если в программе debug будет отсутствовать вызов функции wait ()? (Намек: возможны два исхода.)
2. С помощью функции ptrace отладчик считывает данные из пространства трассируемого процесса по одному слову за одну операцию. Какие изменения следует произвести в ядре операционной системы для того, чтобы увеличить количество считываемых слов? Какие изменения при этом необходимо сделать в самой функции ptrace?
3. Расширьте область действия функции ptrace так, чтобы в качестве параметра pid можно было указывать идентификатор процесса, не являющегося потомком текущего процесса. Подумайте над вопросами, связанными с защитой информации: При каких обстоятельствах процессу может быть позволено читать данные из адресного пространства другого, произвольного процесса? При каких обстоятельствах разрешается вести запись в адресное пространство другого процесса?
4. Организуйте из функций работы с сообщениями библиотеку пользовательского уровня с использованием обычных файлов, поименованных каналов и элементов блокировки. Создавая очередь сообщений, откройте управляющий файл для записи в него информации о состоянии очереди; защитите файл с помощью средств захвата файлов и других удобных для вас механизмов. Посылая сообщение данного типа, создавайте поименованный канал для всех сообщений этого типа, если такого канала еще не было, и передавайте сообщение через него (с подсчетом переданных байт). Управляющий файл должен соотносить тип сообщения с именем поименованного канала. При чтении сообщений управляющий файл направляет процесс к соответствующему поименованному каналу. Сравните эту схему с механизмом, описанным в настоящей главе, по эффективности, сложности реализации и функциональным возможностям.
5. Какие действия пытается выполнить программа, представленная на ?
*6. Напишите программу, которая подключала бы область разделяемой памяти слишком близко к вершине стека задачи и позволяла бы стеку при увеличении пересекать границу разделяемой области. В какой момент произойдет фатальная ошибка памяти?


1. Решите проблему функционирования многопроцессорных систем таким образом, чтобы все процессоры в системе могли функционировать в режиме ядра, но не более одного одновременно. Такое решение будет отличаться от первой из предложенных в тексте схем, где только один процессор (главный) предназначен для реализации функций ядра. Как добиться того, чтобы в режиме ядра в каждый момент времени находился только один процессор? Какую стратегию обработки прерываний при этом можно считать приемлемой?
2. Используя системные функции работы с разделяемой областью памяти, протестируйте программу, реализующую семафорную блокировку (). Последовательности операций P-V над семафором могут независимо один от другого выполнять несколько процессов. Каким образом в программе следует реализовать индикацию и обработку ошибок?
3. Разработайте алгоритм выполнения операции CP (условный тип операции P), используя текст алгоритма операции P.
4. Объясните, зачем в алгоритмах операций P и V (Рисунки и ) нужна блокировка прерываний. В какие моменты ее следует осуществлять?
5. Почему при выполнении "циклической блокировки" вместо строки: while (! CP(семафор));
ядро не может использовать операцию P безусловного типа? (В качестве наводящего вопроса: что произойдет в том случае, если процесс запустит операцию P и приостановится?)


6. Обратимся к алгоритму getblk, приведенному в . Опишите реализацию алгоритма в многопроцессорной системе для случая, когда блок отсутствует в буферном кеше.
*7. Предположим, что при выполнении алгоритма выделения буфера возникла чрезвычайно сильная конкуренция за семафор, принадлежащий списку свободных буферов. Разработайте схему ослабления конкуренции за счет разбиения списка свободных буферов на два подсписка.
*8. Предположим, что у терминального драйвера имеется семафор, значение которого при инициализации сбрасывается в 0 и по которому процессы приостанавливают свою работу в случае переполнения буфера вывода на терминал. Когда терминал готов к приему следующей порции данных, он выводит из состояния ожидания все процессы, приостановленные по семафору. Разработайте схему возобновления процессов, использующую операции типа P и V. В случае необходимости введите дополнительные флаги и семафоры. Как должна вести себя схема в том случае, если процессы выводятся из состояния ожидания по прерыванию, но при этом текущий процессор не имеет возможности блокировать прерывания на других процессорах?
*9. Если точки входа в драйвер защищаются семафорами, должно соблюдаться условие освобождения семафора в случае перехода процесса в состояние приостанова. Как это реализуется на практике? Каким образом должна производиться обработка прерываний, поступающих в то время, пока семафор драйвера заблокирован?
10. Обратимся к системным функциям установки и контроля системного времени (). Разные процессоры могут иметь различную тактовую частоту. Как в этом случае указанные функции должны работать?
Comments:

Copyright ©


*1. Опишите реализацию системной функции exit в системе с периферийными процессорами. В чем разница между этим случаем и тем, когда процесс завершает свою работу по получении неперехваченного сигнала? Каким образом ядру следует сохранить дамп содержимого памяти?
2. Процессы не могут игнорировать сигналы типа SIGKILL; объясните, что происходит в периферийной системе, когда процесс получает такой сигнал.
*3. Опишите реализацию системной функции exec в системе с периферийными процессорами.
*4. Каким образом центральному процессору следует производить распределение процессов между периферийными процессорами с тем, чтобы сбалансировать общую нагрузку?
*5. Что произойдет в том случае, если у периферийного процессора не окажется достаточно памяти для размещения всех выгруженных на него процессов? Каким образом должны производиться выгрузка и подкачка процессов в сети?
6. Рассмотрим систему, в которой запросы к удаленному файловому серверу посылаются в случае обнаружения в имени файла специального префикса. Пусть процесс вызывает функцию execl("/../sftig/bin/sh","sh",0); Исполняемый модуль находится на удаленной машине, но должен выполняться в локальной системе. Объясните, каким образом удаленный модуль переносится в локальную систему.
7. Если администратору нужно добавить в существующую систему со связью типа Newcastle новые машины, то как об этом лучше всего проинформировать модули Си-библиотеки?
*8. Во время выполнения функции exec ядро затирает адресное пространство процесса, включая и библиотечные таблицы, используемые связью типа Newcastle для слежения за ссылками на удаленные файлы. После выполнения функции процесс должен сохранить возможность обращения к этим файлам по их старым дескрипторам. Опишите реализацию этого момента.
*9. Как показано в , вызов системной функции exit в системах со связью типа Newcastle приводит к посылке сообщения процессу-спутнику, заставляющего последний завершить свою работу. Это делается на уровне библиотечных подпрограмм. Что происходит, когда локальный процесс получает сигнал, побуждающий его завершить свою работу в режиме ядра?


1. Рассмотрим следующий набор команд: grep main a.c b.c c.c > grepout & wc -1 < grepout & rm grepout &
Амперсанд (символ "&") в конце каждой командной строки говорит командному процессору shell о том, что команду следует выполнить на фоне, при этом shell может выполнять все командные строки параллельно. Почему это не равноценно следующей командной строке? grep main a.c b.c c.c | wc -1
2. Рассмотрим пример программы, приведенный на Рисунке . Предположим, что в тот момент, когда при ее выполнении встретился комментарий, произошло переключение контекста и другой процесс убрал содержимое буфера из списка указателей с помощью следующих команд: remove(gp) struct queue *gp; { gp - > forp - > backp = gp - > backp; gp - > backp - > forp = gp - > forp; gp - > forp = gp - > backp = NULL; }
Рассмотрим три случая:

  • Процесс убирает из списка с указателями структуру bp1.
  • Процесс убирает из списка с указателями структуру, следующую после структуры bp1.
  • Процесс убирает из списка структуру, которая первоначально следовала за bp1 до того, как структура bp была наполовину включена в указанный список.

В каком состоянии будет список после того, как первый процесс завершит выполнение части программы, расположенной после комментариев?
3. Что произошло бы в том случае, если ядро попыталось бы возобновить выполнение всех процессов, приостановленных по событию, но в системе не было бы к этому моменту ни одного такого процесса?
Comments:

Copyright ©


1. Рассмотрим функцию хеширования применительно к Рисунку . Наилучшей функцией хеширования является та, которая единым образом распределяет блоки между хеш-очередями. Что Вы могли бы предложить в качестве оптимальной функции хеширования? Должна ли эта функция в своих расчетах использовать логический номер устройства?
2. В алгоритме getblk, если ядро удаляет буфер из списка свободных буферов, оно должно повысить приоритет прерывания работы процессора так, чтобы блокировать прерывания до проверки списка. Почему?
*3. В алгоритме getblk ядро должно повысить приоритет прерывания работы процессора так, чтобы блокировать прерывания до проверки занятости блока. (Это не показано в тексте.) Почему?
4. В алгоритме brelse ядро помещает буфер в "голову" списка свободных буферов, если содержимое буфера неверно. Если содержимое буфера неверно, должен ли буфер появиться в хеш-очереди?
5. Предположим, что ядро выполняет отложенную запись блока. Что произойдет, когда другой процесс выберет этот блок из его хеш-очереди? Из списка свободных буферов?
*6. Если несколько процессов оспаривают буфер, ядро гарантирует, что ни один из них не приостановится навсегда, но не гарантирует, что процесс не "зависнет" и дождется получения буфера. Переделайте алгоритм getblk так, чтобы процессу было в конечном итоге гарантировано получение буфера.
7. Переделайте алгоритмы getblk и brelse так, чтобы ядро следовало не схеме замещения буферов, к которым наиболее долго не было обращений, а схеме "первым пришел - первым вышел". Повторите то же самое со схемой замещения редко используемых буферов.
8. Опишите ситуацию в алгоритме bread, когда информация в буфере уже верна.
*9. Опишите различные ситуации, встречающиеся в алгоритме breada. Что произойдет в случае следующего выполнения алгоритма bread или breada, когда текущий блок прочитан с продвижением? В алгоритме breada, если первый или второй блок отсутствует в кеше, в дальнейшем при проверке правильности содержимого буфера предполагается, что блок мог быть в буферном пуле. Как это может быть?


1. В версии V системы UNIX разрешается использовать не более 14 символов на каждую компоненту имени пути поиска. Алгоритм namei отсекает лишние символы в компоненте. Что нужно сделать в файловой системе и в соответствующих алгоритмах, чтобы стали допустимыми имена компонент произвольной длины?
2. Предположим, что пользователь имеет закрытую версию системы UNIX, причем он внес в нее такие изменения, что имя компоненты теперь может состоять из 30 символов; закрытая версия системы обеспечивает тот же способ хранения записей каталогов, как и стандартная операционная система, за исключением того, что записи каталогов имеют длину 32 байта вместо 16. Если пользователь смонтирует закрытую файловую систему в стандартной операционной среде, что произойдет во время работы алгоритма namei, когда процесс обратится к файлу?
*3. Рассмотрим работу алгоритма namei по преобразованию имени пути поиска в идентификатор индекса. В течение всего просмотра ядро проверяет соответствие текущего рабочего индекса индексу каталога. Может ли другой процесс удалить (unlink) каталог? Каким образом ядро предупреждает такие действия? В следующей главе мы вернемся к этой проблеме.
*4. Разработайте структуру каталога, повышающую эффективность поиска имен файлов без использования линейного просмотра. Рассмотрите два способа: хеширование и n-арные деревья.
*5. Разработайте алгоритм сокращения количества просмотров каталога в поисках имени файла, используя запоминание часто употребляемых имен.
*6. В идеальном случае в файловой системе не должно быть свободных индексов с номерами, меньшими, чем номер "запомненного" индекса, используемый алгоритмом ialloc. Как случается, что это утверждение бывает ложным?
7. Суперблок является дисковым блоком и содержит кроме списка свободных блоков и другую информацию, как показано в данной главе. Поэтому список свободных блоков в суперблоке не может содержать больше номеров свободных блоков, чем может поместиться в одном дисковом блоке в связанном списке свободных дисковых блоков. Какое число номеров свободных блоков было бы оптимальным для хранения в одном блоке из связанного списка?
Comments:

Copyright ©


1. Рассмотрим программу, приведенную на . Какое значение возвращает каждая операция read и что при этом содержится в буфере? Опишите, что происходит в ядре во время выполнения каждого вызова read.
2. Вновь вернемся к программе на и предположим, что оператор lseek(fd,9000L,0); стоит перед первым обращением к функции read. Что ищет процесс и что при этом происходит в ядре?
3. Процесс может открыть файл для работы в режиме добавления записей в конец файла, при этом имеется в виду, что каждая операция записи располагает данные по адресу смещения, указывающего текущий конец файла. Таким образом, два процесса могут открыть файл для работы в режиме добавления записей в конец файла и вводить данные, не опасаясь затереть записи друг другу. Что произойдет, если процесс откроет файл в режиме добавления в конец, а записывающую головку установит на начало файла?
4. Библиотека стандартных подпрограмм ввода-вывода повышает эффективность выполнения пользователем операций чтения и записи благодаря буферизации данных в библиотеке и сохранению большого количества модулей обращения к операционной системе, необходимых пользователю. Как бы вы реализовали библиотечные функции fread и fwrite? Что должны делать библиотечные функции fopen и fclose?

#include <fcntl.h> main() { int fd; char buf[1024]; fd = creat("junk",0666); lseek(fd,2000L,2); /* ищется байт с номером 2000 */ write(fd,"hello",5); close(fd);
fd = open("junk",O_RDONLY); read(fd,buf,1024); /* читает нули */ read(fd,buf,1024); /* считывает нечто, отличное от 0 */ read(fd,buf,1024); }

Рисунок 5.35. Считывание нулей и конца файла
5. Если процесс читает данные из файла последовательно, ядро запоминает значение блока, прочитанного с продвижением, в индексе, хранящемся в памяти. Что произойдет, если несколько процессов будут одновременно вести последовательное считывание данных из одного и того же файла?


#include <fcntl.h> main() { int fd; char buf[256];
fd = open("/etc/passwd",O_RDONLY); if (read(fd,buf,1024) < 0) printf("чтение завершается неудачно\n"); }

1. Составьте алгоритм преобразования виртуальных адресов в физические, на входе которого задаются виртуальный адрес и адрес точки входа в частную таблицу областей.
2. В машинах AT&T 3B2 и NSC серии 32000 используется двухуровневая схема трансляции виртуальных адресов в физические (с сегментацией). То есть в системе поддерживается указатель на таблицу страниц, каждая запись которой может адресовать фиксированную часть адресного пространства процесса по смещению в таблице. Сравните алгоритм трансляции виртуальных адресов на этих машинах с алгоритмом, изложенным в тексте при обсуждении модели управления памятью. Подумайте над проблемами производительности и потребности в памяти для размещения вспомогательных таблиц.
3. В архитектуре системы VAX-11 поддерживаются два набора регистров защиты памяти, используемых машиной в процессе трансляции пользовательских адресов. Механизм трансляции используется тот же, что и в предыдущем пункте, за одним исключением: указателей на таблицу страниц здесь два. Если процесс располагает тремя областями - команд, данных и стека - то каким образом, используя два набора регистров, следует производить отображение областей на таблицы страниц? Увеличение стека в архитектуре системы VAX-11 идет в направлении младших виртуальных адресов. Какой тогда вид имела бы область стека? В будет рассмотрена область разделяемой памяти: как она может быть реализована в архитектуре системы VAX-11?
4. Составьте алгоритм выделения и освобождения страниц памяти и таблиц страниц. Какие структуры данных следует использовать, чтобы достичь наивысшей производительности или наибольшей простоты реализации алгоритма?
5. Устройство управления памятью MC68451 для семейства микропроцессоров Motorola 68000 допускает выделение сегментов памяти размером от 256 байт до 16 мегабайт. Каждое (физическое) устройство управления памятью поддерживает 32 дескриптора сегментов. Опишите эффективный метод выделения памяти для этого случая. Каким образом осуществлялась бы реализация областей?


1. Запустите с терминала программу, приведенную на . Переадресуйте стандартный вывод данных в файл и сравните результаты между собой.
main() { printf("hello\n"); if (fork() == 0) printf("world\n"); }

Рисунок 7.33. Пример модуля, содержащего вызов функции fork и обращение к стандартному выводу
2. Разберитесь в механизме работы программы, приведенной на , и сравните ее результаты с результатами программы на .
#include <fcntl.h> int fdrd,fdwt; char c;
main(argc,argv) int argc; char *argv[]; { if (argc != 3) exit(1); fork();
if ((fdrd = open(argv[1],O_RDONLY)) == -1) exit(1); if (((fdwt = creat(argv[2],0666)) == -1) && ((fdwt = open(argv[2],O_WRONLY)) == -1)) exit(1); rdwrt(); } rdwrt() { for (;;) { if (read(fdrd,&c,1) != 1) return; write(fdwt,&c,1); } }

Рисунок 7.34. Пример программы, в которой процесс-родитель и процесс-потомок не разделяют доступ к файлу
3. Еще раз обратимся к программе, приведенной на и показывающей, как два процесса обмениваются сообщениями, используя спаренные каналы. Что произойдет, если они попытаются вести обмен сообщениями, используя один канал?
4. Возможна ли потеря информации в случае, когда процесс получает несколько сигналов прежде чем ему предоставляется возможность отреагировать на них надлежащим образом? (Рассмотрите случай, когда процесс подсчитывает количество полученных сигналов о прерывании.) Есть ли необходимость в решении этой проблемы?
5. Опишите механизм работы системной функции kill.
6. Процесс в программе на принимает сигналы типа "гибель потомка" и устанавливает функцию обработки сигналов в исходное состояние. Что происходит при выполнении программы?
#include <signal.h> main() { extern catcher();
signal(SIGCLD,catcher); if (fork() == 0) exit(); /* пауза до момента получения сигнала */ pause(); }
catcher() { printf("процесс-родитель получил сигнал\n"); signal(SIGCLD,catcher); }

Рисунок 7.35. Программа, в которой процесс принимает сигналы типа "гибель потомка"


  • При переводе процессов в состояние приостанова ядро назначает процессу, ожидающему снятия блокировки с индекса, более высокий приоритет по сравнению с процессом, ожидающим освобождения буфера. Точно так же, процессы, ожидающие ввода с терминала, получают более высокий приоритет по сравнению с процессами, ожидающими возможности производить вывод на терминал. Объясните причины такого поведения ядра.
  • * В алгоритме обработки прерываний по таймеру предусмотрен пересчет приоритетов и перезапуск процессов на выполнение с интервалом в 1 секунду. Придумайте алгоритм, в котором интервал перезапуска динамически меняется в зависимости от степени загрузки системы. Перевесит ли выигрыш усилия по усложнению алгоритма?
  • В шестой редакции системы UNIX для расчета продолжительности ИЦП текущим процессом используется следующая формула: decay(ИЦП) = max (пороговый приоритет, ИЦП-10);
    а в седьмой редакции: decay(ИЦП) = .8 * ИЦП;

    Приоритет процесса в обеих редакциях вычисляется по формуле: приоритет = ИЦП/16 + (базовый уровень приоритета);

    Повторите пример на , используя приведенные формулы.
  • Проделайте еще раз пример на с семью процессами вместо трех, а затем измените частоту прерываний по таймеру с 60 на 100 прерываний в секунду. Прокомментируйте результат.
  • Разработайте схему, в которой система накладывает ограничение на продолжительность выполнения процесса, при превышении которого процесс завершается. Каким образом пользователь должен отличать такой процесс от процессов, для которых не должны существовать подобные ограничения? Каким образом должна работать схема, если единственным условием является ее запуск из shell'а?
  • Когда процесс выполняет системную функцию wait и обнаруживает прекратившего существование потомка, ядро приплюсовывает к его ИЦП значение поля ИЦП потомка. Чем объясняется такое "наказание" процесса-родителя?
  • Команда nice запускает последующую команду с передачей ей указанного значения, например: nice 6 nroff -mm big_memo > output
    Напишите на языке Си программу, реализующую команду nice.
  • Проследите на примере , каким образом будет осуществляться диспетчеризация процессов в том случае, если значение, передаваемое функцией nice для процесса A, равно 5 или -5.
  • Проведите эксперимент с системной функцией renice x y, где x - код идентификации процесса (активного), а y - новое значение nice для указанного процесса.
  • Вернемся к примеру, приведенному на . Предположим, что группе, в которую входит процесс A, выделяется 33% процессорного времени, а группе, в которую входит процесс B, - 66% процессорного времени. В какой последовательности будут исполняться процессы? Обобщите алгоритм вычисления приоритетов таким образом, чтобы значение группового ИЦП усреднялось.
  • Выполните команду date. Команда без аргументов выводит текущую дату:



    1. Набросайте схему реализации алгоритма mfree, который освобождает пространство памяти и возвращает его таблице свободного пространства.

    2. В утверждается, что система блокирует перемещаемый процесс, чтобы другие процессы не могли его трогать с места до момента окончания операции. Что произошло бы, если бы система не делала этого?

    3. Предположим, что в адресном пространстве процесса располагаются таблицы используемых процессом сегментов и страниц. Каким образом ядро может выгрузить это пространство из памяти?

    4. Если стек ядра находится внутри адресного пространства процесса, почему процесс не может выгружать себя сам? Какой на Ваш взгляд должна быть системная программа выгрузки процессов, как она должна запускаться?

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

    6. Рассмотрите еще раз пример, приведенный на , при условии, что в памяти есть место только для 1 процесса.

    7. Обратимся к примеру, приведенному на . Составьте подобный пример, в котором процессу постоянно требуется для работы центральный процессор. Существует ли какой-нибудь способ снятия подобной напряженности?
      main() { f(); g(); }
      f() { vfork(); }
      g() { int blast[100],i; for (i = 0; i < 100; i++) blast[i] = i; }

      Рисунок 9.29
      Что произойдет в результате выполнения программы, приведенной на , в системе BSD 4.2? Каким будет стек процесса-родителя?

    8. Почему после выполнения функции fork процесса-потомка предпочтительнее запускать впереди процесса-родителя, если на разделяемых страницах биты копирования при записи установлены? Каким образом ядро может заставить потомка запуститься первым?




      1. * Предположим, что в системе имеются два файла устройств с одними и теми же старшим и младшим номерами, при том, что оба устройства - символьного типа. Если два процесса желают одновременно открыть физическое устройство, не будет никакой разницы, открывают ли они один и тот же файл устройства или же разные файлы. Что произойдет, когда они станут закрывать устройство?

      2. * Вспомним из , что системной функции mknod требуется разрешение суперпользователя на создание нового специального файла устройства. Если доступ к устройству управляется правами доступа к файлу, почему функции mknod нужно разрешение суперпользователя?

      3. Напишите программу, которая проверяет, что файловые системы на диске не перекрываются. Этой программе потребовались бы два аргумента: файл устройства, представляющий дисковый том, и дескриптор файла, откуда берутся номера секторов и их размер для диска данного типа. Для проверки отсутствия перекрытий этой программе понадобилась бы информация из суперблоков. Будет ли такая программа всегда правильной?

      4. Программа mkfs инициализирует файловую систему на диске путем создания суперблока, выделения места для списка индексов, включения всех информационных блоков в связанный список и создания корневого каталога. Как бы вы написали программу mkfs? Как изменится эта программа при наличии таблицы содержимого тома? Каким образом следует инициализировать таблицу содержимого тома?

      5. Программы mkfs и fsck () являются программами пользовательского уровня, а не частью ядра. Прокомментируйте это.

      6. Предположим, что программисту нужно разработать базу данных, работающую в среде ОС UNIX. Программы базы данных выполняются на пользовательском уровне, а не в составе ядра. Как система управления базой данных будет взаимодействовать с диском? Подумайте над следующими вопросами:

        • Использование стандартного интерфейса файловой системы вместо непосредственной работы с неструктурированными данными на диске,
        • Потребность в быстродействии,
        • Необходимость знать, когда фактически данные располагаются на диске,
        • Размер базы данных: должна ли она помещаться в одной файловой системе, занимать собой весь дисковый том или же располагаться на нескольких дисковых томах?


        • Содержание раздела