19. Опишите алгоритм замещения страниц ws.

Набор страниц, который процесс использует в данный момент, известен как рабочий набор. Если в памяти находится весь рабочий набор, процесс будет работать, не вызывая многочисленных ошибок отсутствия страниц до начала выполнения. Если объем доступной памяти слишком мал, процесс вызовет множество ошибок отсутствия страниц и будет работать медленно. О программе, вызывающей ошибку отсутствия страницы через каждые несколько команд, говорят, что она пробуксовывает. В многозадачных системах процессы довольно часто сбрасываются на диск (все их страницы удаляются из памяти), чтобы дать возможность другим процессам воспользоваться своей очередью доступа к ЦП. Возникает вопрос: что делать, когда процесс возобновляет свою работу? Процесс просто будет вызывать ошибки отсутствия страниц до тех пор, пока не будет загружен его рабочий набор. Многие системы замещения страниц пытаются отслеживать рабочий набор каждого процесса и обеспечивать его присутствие в памяти, перед тем как позволить процессу возобновить работу. Модель рабочего набора была разработана для сокращения количества ошибок отсутствия страниц. Загрузка страниц до того, как процессу будет позволено возобновить работу, называется также опережающей подкачкой страниц. Рассмотрим работу алгоритма. Аппаратура устанавливает биты R и M, а периодические прерывания от таймера запускают программу, очищающую бит обращения R. При каждой ошибке отсутствия страницы происходит сканирование таблицы страниц с целью найти страницу, пригодную для удаления. При каждой обработке записи проверяется состояние бита R. Если его значение равно 1, текущее виртуальное время записывается в поле времени последнего использования таблицы страниц, показывая, что страница была использована при возникновении ошибки отсутствия страницы. Если обращение к странице происходит в течение текущего такта времени, становится понятно, что она принадлежит рабочему набору и не является кандидатом на удаление. Если значение R равно 0, значит, за текущий такт времени обращений к странице не было, и она может быть кандидатом на удаление. Чтобы понять, должна ли она быть удалена или нет, вычисляется ее возраст (текущее виртуальное время за вычетом времени последнего использования), который сравнивается со значением t. Если возраст превышает значение t, то страница уже не относится к рабочему набору и заменяется новой страницей. Сканирование продолжается, и происходит обновление всех остальных записей. Но если значение R равно 0, но возраст меньше или равен t, то страница все еще относится к рабочему набору. Страница временно избегает удаления, но страница с наибольшим возрастом (наименьшим значением времени последнего использования) берется на заметку. Если будет просканирована вся таблица страниц и не будет найден кандидат на удаление, значит, к рабочему набору относятся все страницы. В таком случае, если найдена одна и более страниц с R = 0, удаляется одна из них, имеющая наибольший возраст. В худшем случае в течение текущего такта было обращение ко всем страницам (и поэтому у всех страниц R = 1), поэтому для удаления одна из них выбирается случайным образом, при этом предпочтение отдается неизмененной странице, если таковая имеется.

25. Опишите алгоритм замещения страниц fifo

Наиболее простой и низкозатратный алгоритм замещения страниц. Операционная система ведет список всех страниц, находящихся на данный момент в памяти, причем совсем недавно поступившие находятся в хвосте, поступившие раньше всех — в голове списка. При возникновении ошибки отсутствия страницы удаляется страница, находящаяся в голове списка, а к его хвосту добавляется новая страница. К сожалению, эта стратегия с достаточной вероятностью будет приводить к замещению активно используемых страниц. Поэтому принцип FIFO в чистом виде используется довольно редко.

26. Опишите алгоритм диспетчеризации процессов rr

Планирование по принципу RR предполагает диспетчирование процессов по принципу FIFO, но каждый процесс получает временной квант, в течение которого он может использовать ресурсы ЦП. Если завершения процесса не происходит по истечении кванта времени, то этот процесс переводится в конец списка готовых к выполнению процессов, а ресурсы ЦП предоставляются следующему процессу из списка. Такой алгоритм планирования подходит, например, для работы с разделением времени, когда система должна гарантировать приемлемые времена ответа для всех интерактивных пользователей. Очевидно, что для данного алгоритма планирования основной вопрос заключается в определении размера кванта времени, и следует ли делать его фиксированным или переменным. Очевидно, если квант времени выбирается слишком большим, то система RR фактически вырождается в FIFO, т.к. каждому процессу выделяется достаточно времени для завершения. Если же квант времени выбирается слишком малым, то контекстные переключения начинают играть доминирующую роль, что в итоге ухудшает характеристики системы.

27. Опишите алгоритм диспетчеризации процессов srtf

Если приходит новый процесс, время активности которого меньше, чем оставшееся время активного процесса, - прервать активный процесс. Эта схема известна под названием Shortest-Remaining-Time-First (SRTF).

В данном случае принцип прерывания процесса в момент поступления в систему более короткого процесса применяется несколько раз:

• в момент 2 прерывается процесс 1 и начинает исполняться более короткий процесс 2;

• в момент 4 прерывается процесс 2 и начинает исполняться более короткий процесс 3.

Из диаграммы видно, что, вследствие применения принципа прерывания процессов, периоды непрерывного выполнения процесса на процессоре могут быть не смежными и перемежаться с периодами выполнения других процессов. В данном случае среднее время ожидания = (9 + 1 + 0 +2)/4 = 3, т.е. оно, как и следовало предполагать, оказалось меньше, чем без применения принципа прерывания процессов.

28. Опишите алгоритм диспетчеризации процессов fcfs

Стратегия First-Come-First-Served (обслуживание в порядке поступления) – наиболее простая стратегия диспетчеризации, при которой ресурсы процессора предоставляются процессам в порядке их поступления (ввода) в систему, независимо от потребляемых ими ресурсов, в частности, от заявленного процессом времени, требуемого для его выполнения. Задания, по мере их поступления помещаются в очередь. При блокировке выполняемого процесса, следующим запускается процесс, стоящий первый в очереди. Когда заблокированный процесс переходит в состояние готовности – он помещается, подобно только что поступившему заданию, в конец очереди.

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

29. Опишите алгоритм диспетчеризации процессов sjf

Стратегия Shortest Job First (SJF, обслуживание самого короткого задания первым) – стратегия диспетчеризации процессора, при которой процессор предоставляется в первую очередь наиболее короткому процессу из имеющихся в системе. В данном случае с каждым процессом связывается длина его очередного периода активности. Эта длина используется для того, чтобы первым обслужить самый короткий процесс.

Возможны две схемы применения данной стратегии:

1. Без прерывания процессов – пока процессу предоставляется процессор, он не может быть прерван, пока не истечет его квант времени.

2. С прерыванием (SRTF).

Стратегия SJF оптимальна, в том смысле, что она обеспечивает минимальное среднее время ожидания для заданного набора процессов. Пусть набор процессов, времен их появления в системе и времени их активности следующие:

В данном случае среднее время ожидания = (0 + 6 + 3 + 7)/4 = 4.

30. Перечислите основные команды языка сценариев BASH

    BASH — Bourne-Again Shell, самый популярный командный интерпретатор в юниксоподобных системах, в особенности в GNU/Linux. 

    Любой bash-скрипт должен начинаться со строки: #!/bin/bash

break — выход из цикла for, while или until;

continue — выполнение следующей итерации цикла for, while или until;

echo — вывод аргументов, разделенных пробелами, на стандартное устройство вывода ($ echo Hello World) ;

cd — позволяет перейти в новый каталог;

exit — выход из оболочки;

export — отмечает аргументы как переменные для передачи в дочерние процессы в среде;

hash — запоминает полные имена путей команд, указанных в качестве аргументов, чтобы не искать их при следующем обращении;

kill — посылает сигнал завершения процессу;

pwd — выводит текущий рабочий каталог;

read — читает строку из ввода оболочки и использует ее для присвоения значений указанным переменным;

return — заставляет функцию оболочки выйти с указанным значением;

shift — перемещает позиционные параметры налево;

test — вычисляет условное выражение;

times — выводит имя пользователя и системное время, использованное оболочкой и ее потомками;

trap — указывает команды, которые должны выполняться при получении оболочкой сигнала;

unset — вызывает уничтожение переменных оболочки;

wait — ждет выхода из дочернего процесса и сообщает выходное состояние;

man — отображает руководства по командам;

cat — считывает файл, переданный как аргумент, и выводит его содержимое по стандартному каналу вывода:

$ cat users.txt

user:student password:123

user:teacher password:321

less — позволяет перемещаться по переданному файлу или куску текста, причём в обоих направлениях;

$? — переменная, которая содержит выходной статус последней запущенной команды:

$ true

$ echo $?

0

$ false

$ echo $?

1

grep — занимается поиском переданной строки в указанном файле;

history — выводит историю командной строки. Обычно её используют вместе с командой grep для поиска конкретной команды. Например, следующий код найдёт все команды, содержащие строку g++:

$ history | grep g++

155 g++ file1.txt

159 g++ file2.txt

ping — тестирует сетевое подключение.

31. Перечислите основные команды языка сценариев bat

Batch является языком программирования, используется для создания файлов сценарий которые можно выполнять на операционной системе Windows.

BREAK      Включение/выключение режима обработки комбинации клавиш

CALL          Вызов одного пакетного файла из другого.

CD               Вывод имени либо смена текущей папки.

CHKDSK    Проверка диска и вывод статистики.

CLS              Очистка экрана. RD         Удаление папки.

CMD            Запуск еще одного интерпретатора командных строк Windows.

COMP          Сравнение содержимого двух файлов или двух наборов файлов.

COPY    Копирование одного или нескольких файлов в другое место.

DATE    Вывод либо установка текущей даты.

DEL       Удаление одного или нескольких файлов.

DIR        Вывод списка файлов и подпапок из указанной папки.

DISKCOMP    Сравнение содержимого двух гибких дисков.

DISKCOPY     Копирование содержимого одного гибкого диска на другой.

ECHO              Вывод сообщений и переключение режима отображения команд на экране.

EXIT     Завершение работы программы CMD.EXE (интерпретатора командных строк).

FIND             Поиск текстовой строки в одном или нескольких файлах.

FOR              Запуск указанной команды для каждого из файлов в наборе.

GOTO    Передача управления в отмеченную строку пакетного файла.

IF           Оператор условного выполнения команд в пакетном файле.

LABEL Создание, изменение и удаление меток тома для дисков.

MD        Создание папки. VER       Вывод сведений о версии Windows.

MOVE Перемещение одного или нескольких файлов из одной папки в другую.

PATH    Вывод либо установка пути поиска исполняемых файлов.

PAUSE Приостановка выполнения пакетного файла и вывод сообщения.

PRINT          Вывод на печать содержимого текстовых файлов.

REM     Помещение комментариев в пакетные файлы и файл CONFIG.SYS.

RENAME    Переименование файлов и папок.

REPLACE   Замещение файлов SORT     Сортировка ввода.

SET        Вывод, установка и удаление переменных среды Windows.

SHIFT    Изменение содержимого (сдвиг) подставляемых параметров для пакетного файла.

START   Запуск программы или команды в отдельном окне.

TIME     Вывод и установка системного времени.

TREE     Графическое отображение структуры папок заданного диска или заданной папки. TYPE     Вывод на экран содержимого текстовых файлов.

XCOPY Копирование файлов и дерева папок.

32. Решите задачу производителя/потребителя через sleep и wakeup

Рассмотрим некоторые примитивы взаимодействия процессов, которые блокируют работу, пока им не разрешается входить в критическую область. Представителями простейшей пары таких примитивов являются sleep и wakeup. Системный вызов sleep блокирует вызывающий его процесс, который приостанавливается до тех пор, пока его не активизирует другой процесс. Активизирующий вызов wakeup использует один аргумент — активизируемый процесс. Дополнительно и sleep и wakeup используют еще один аргумент — адрес памяти, используемой для соотнесения вызовов sleep с вызовами wakeup.

В качестве примера применения этих примитивов рассмотрим задачу производителя и потребителя (задачу ограниченного буфера). Два процесса используют общий буфер фиксированного размера. Один из них, производитель, помещает информацию в буфер, а другой, потребитель, извлекает ее оттуда. (Можно также расширить проблему до m производителей и n потребителей, но мы будем рассматривать только случай с одним производителем и одним потребителем, поскольку такое допущение упрощает решение.) Проблемы возникаю, когда производителю требуется поместить новую запись в уже заполненный буфер. Решение заключается в блокировании производителя до тех пор, пока потребитель не извлечет как минимум одну запись. Также, если потребителю нужно извлечь запись из буфера и видит, что буфер пуст, он блокируется до тех пор, пока производитель не поместит что-нибудь в буфер и не активизирует этого потребителя. На первый взгляд этот подход выглядит довольно простым, но он приводит к разновидности состязательной ситуации. Для отслеживания количества записей в буфере нам потребуется переменная count. Если максимальное количество записей, которое может содержаться в буфере, равно N, то программа производителя должна сначала проверить, не имеет ли count значение N. Если переменная имеет такое значение, производитель должен заблокировать свое выполнение, а если не имеет — добавить запись и увеличить показание счетчика count. Программа потребителя работает схожим образом: сначала проверяет, не является ли значение count нулевым. Если оно равно нулю, процесс блокирует свое выполнение, а если не равно нулю, он извлекает запись и уменьшает значение счетчика. Каждый из процессов также проверяет, не нужно ли активизировать другой процесс, и если нужно, проводит эту активизацию. Вызовы sleep и wakeup в виде вызовов библиотечных процедур.

#define N 100 /* количество мест для записей в буфере */

int count = 0; /* количество записей в буфере */

void producer(void) {

int item;

while (TRUE) { /* бесконечное повторение */

item = produce_item( ); /* генерация новой записи */

if (count == N) sleep( ); /* если буфер полон, заблокироваться */

insert_item(item); /* помещение записи в буфер */

count = count + 1; /* увеличение счетчика записей в буфере */

if (count == 1) wakeup(consumer); /* был ли буфер пуст? */ } }

void consumer(void) {

int item; while (TRUE) { /* бесконечное повторение */

if (count == 0) sleep(); /* если буфер пуст, заблокироваться */

item = remove_item( ); /* извлечь запись из буфера */

count = count− 1; /* уменьшение счетчика записей в буфере */

if (count == N − 1) wakeup(producer); /* был ли буфер полон? */

consume_item(item); /* распечатка записи */ } }