1625914892-87304ba273974eff372da046ba2bc5da (843828), страница 5

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 5)

за счет сравнения такихбитов). В подобной реализации, при каждом обращении к строке кэша меняется "возраст" всехостальных строк.25) Описать алгоритм планирования запросов к жесткому диску SSTF.Как мы убедились, достаточно разумным является первоочередное обслуживание запросов, данные для которых лежат рядом с текущей позицией головок, а уж затем далеко отстоящих.

Алгоритм Short Seek Time First (SSTF) – короткое время поиска первым – как раз и исходит из этойпозиции. Для очередного обслуживания будем выбирать запрос, данные для которого лежатнаиболее близко к текущему положению магнитных головок. Естественно, что при наличии равноудаленных запросов решение о выборе между ними может приниматься исходя из различныхсоображений, например по алгоритму FCFS. Для предыдущего примера алгоритм даст такую последовательность положений головок:63675531231410784и всего головки переместятся на 141 цилиндр.

Заметим, что наш алгоритм похож на алгоритмSJF планирования процессов, если за аналог оценки времени очередного CPU burst процесса выбирать расстояние между текущим положением головки и положением, необходимым для удовлетворения запроса. И точно так же, как алгоритм SJF, он может приводить к длительному откладыванию выполнения какого-либо запроса. Необходимо вспомнить, что запросы в очередимогут появляться в любой момент времени. Если у нас все запросы, кроме одного, постоянногруппируются в области с большими номерами цилиндров, то этот один запрос может находиться в очереди неопределенно долго.26) Описать алгоритмы планирования запросов к жесткому диску LOOK, C-LOOK.В простейшем из алгоритмов сканирования – SCAN – головки постоянно перемещаются отодного края диска до другого, по ходу дела обслуживая все встречающиеся запросы.

По достижении другого края направление движения меняется, и все повторяется снова. Пусть впредыдущем примере в начальный момент времени головки двигаются в направленииуменьшения номеров цилиндров. Тогда мы и получим порядок обслуживания запросов, подсмотренный в конце предыдущего раздела. Последовательность перемещения головок выглядит следующим образом:635531231410706784и всего головки переместятся на 147 цилиндров.Если мы знаем, что обслужили последний попутный запрос в направлении движения головок,то мы можем не доходить до края диска, а сразу изменить направление движения на обратное:63553123141076784и всего головки переместятся на 133 цилиндра.

Полученная модификация алгоритма SCANполучила название LOOK.Допустим, что к моменту изменения направления движения головки в алгоритме SCAN, т. е.когда головка достигла одного из краев диска, у этого края накопилось большое количествоновых запросов, на обслуживание которых будет потрачено достаточно много времени (незабываем, что надо не только перемещать головку, но еще и передавать прочитанные данные!). Тогда запросы, относящиеся к другому краю диска и поступившие раньше, будутждать обслуживания несправедливо долго. Для сокращения времени ожидания запросовприменяется другая модификация алгоритма SCAN – циклическое сканирование.

Когда головка достигает одного из краев диска, она без чтения попутных запросов (иногда существенно быстрее, чем при выполнении обычного поиска цилиндра) перемещается на другойкрай, откуда вновь начинает движение в прежнем направлении. Для этого алгоритма, получившего название C-SCAN, последовательность перемещений будет выглядеть так:63553123141070998467По аналогии с алгоритмом LOOK для алгоритма SCAN можно предложить и алгоритм CLOOK для алгоритма C-SCAN:63553123141078467Существуют и другие разновидности алгоритмов сканирования, и совсем другие алгоритмы,но мы на этом закончим, ибо было сказано: "И еще раз говорю: никто не обнимет необъятного".27) Лекция №5.

Управление вводом-выводом1) Логическая организация локальной магистрали компьютера.В простейшем случае процессор, память и многочисленные внешние устройства связаны большим количеством электрических соединений – линий, которые в совокупности принято называть локальной магистралью компьютера.Внутри локальной магистрали линии, служащие для передачи сходных сигналов и предназначенные для выполнения сходных функций, принято группировать в шины. (шина данных, адресная шина, шина управления)2) Принцип передачи данных по локальной магистрали компьютера.Внешние устройства разнесены пространственно и могут подключаться к локальной магистралив одной точке или множестве точек, получивших название портов ввода-вывода.Что именно должны делать устройства, приняв информацию через свой порт, и каким именнообразом они должны поставлять информацию для чтения из порта, определяется электроннымисхемами устройств, которые называются контроллерами.3) Назначение контроллера устройства.Что именно должны делать устройства, приняв информацию через свой порт, и каким именнообразом они должны поставлять информацию для чтения из порта, определяется электроннымисхемами устройств, которые называются контроллерами.Контроллеры устройств ввода-вывода весьма различны как по своему внутреннему строению,так и по исполнению (от одной микросхемы до специализированной вычислительной системы сосвоим процессором, памятью и т.

д.), поскольку им приходится управлять совершенно разнымиприборами.4) Перечислить и указать назначение регистров контроллера устройства. Регистр состояния (бит занятости, бит готовности данных, бит ошибки); Регистр управления (бит готовности команды); Регистр входных данных; Регистр выходных данных.Регистры контроллера задают порт (который должен быть использован), направление переносаданных (чтение/запись), единицу переноса (побайтно/пословно), число байтов, которое следуетперенести.5) Алгоритм взаимодействия между процессором и контроллером.Процессор и основная память находятся на большой плате, которая называется материнской.Для подключения к ней периферийных устройств (дисководов, манипуляторов типа мыши,принтеров и т.д.) служат специальные платы - контроллеры.

Они вставляются в разъемы (слоты) на материнской плате, а к их концу (порту), выходящему наружу компьютера, подключаетсядополнительное устройство. Таким образом, периферийные устройства подключаются к системной магистрали не непосредственно, а через специальные устройства - контроллеры.Магистраль можно сравнить с телефонным кабелем, к которому параллельно подключены абоненты - блоки компьютера.

"Обращение" процессора к внешнему устройству похоже на вызовабонента. Все устройства пронумерованы. Когда нужно обратиться к какому-нибудь из них, вмагистраль посылается его адрес. Как и телефон, устройство может быть свободно или занято.Приняв сигнал "свободно", процессор посылает ему информацию. Контроллер внешнего устройства можно сравнить с телефонным аппаратом, который принимает сигнал от процессора и дешифрует его. Например, контроллер экрана, приняв от процессора сигнал 01000001 (код буквы"А"), преобразует его в указание электронно-лучевой трубке изобразить на экране букву "А".Построив модель контроллера и представляя себе, что скрывается за словами "прочитать информацию из порта" и "записать информацию в порт", мы готовы к рассмотрению процессавзаимодействия устройства и процессора.

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

Если бит занятости установлен, то это означает, что устройство еще не завершило предыдущую операцию, и процессор уходит на новую итерациюцикла. Если бит занятости сброшен, то устройство готово к выполнению новой операции, и процессор переходит на следующий шаг.2. Процессор записывает код команды вывода в порт регистра управления.3. Процессор записывает данные в порт регистра входных данных.4. Процессор устанавливает бит готовности команды. В следующих шагах процессор незадействован.5. Когда контроллер замечает, что бит готовности команды установлен, он устанавливает бит занятости.6. Контроллер анализирует код команды в регистре управления и обнаруживает, что этокоманда вывода.

Он берет данные из регистра входных данных и инициирует выполнение команды.7. После завершения операции контроллер обнуляет бит готовности команды.8. При успешном завершении операции контроллер обнуляет бит ошибки врегистре состояния, при неудачном завершении команды – устанавливает его.9. Контроллер сбрасывает бит занятости.6) Принцип работы прерываний.Для того чтобы процессор не дожидался состояния готовности устройства ввода-вывода в цикле,а мог выполнять в это время другую работу, необходимо, чтобы устройство само умело сигнализировать процессору о своей готовности. Технический механизм, который позволяет внешнимустройствам оповещать процессор о завершении команды вывода или команды ввода, получилназвание механизма прерываний.7) Назначение и принцип работы контроллера прерываний.В большинстве современных компьютеров устройства сообщают о своей готовности процессоруне напрямую, а через специальный контроллер прерываний, который дополнительно использует: шину прерываний; таблицу прерываний; векторы прерываний; приоритеты прерываний.В большинстве современных компьютеров процессор стараются полностью освободить отнеобходимости опроса внешних устройств, в том числе и от определения с помощью опросаустройства, сгенерировавшего сигналпрерывания.

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

Характеристики

Список файлов лекций