Теория вычислительных систем — это то, что позволяет нам программировать. Однако, можно писать программы и без представления о концепциях, скрывающихся за вычислительными процессами. Не то, чтобы это было плохо — когда мы программируем, то работаем на намного более высоком уровне абстракции.
В конце концов, когда мы ведём машину, то концентрируемся только на двух или трёх педалях, переключателе передач и руле. Для повседневной неспешной езды этого более чем достаточно. Однако, если мы хотим управлять автомобилем на пределе его возможностей, то тут нужно знать гораздо больше, чем просто три педали, КПП и руль.
Такой подход справедлив и в программировании. Большая часть повседневной мирской работы может быть выполнена при минимальном знании теории вычислительных систем или даже вообще без него. Не нужно понимать теорию категорий, чтобы накидать форму «Контакты» в PHP. Тем не менее, если вы планируете писать код, требующий серьёзных вычислений, то тут уж придётся разобраться с тем, что у этих самых вычислений под капотом.
Основные этапы развития архитектуры микропроцессоров
Цель этой статьи — представить некоторые фундаментальные основы вычислений. Если это окажется интересным, то в дальнейшем я могу написать более продвинутый топик на эту тему, но прямо сейчас я хочу просто рассмотреть логику простейшего абстрактного вычислительного устройства — машины с конечным числом состояний (finite state machine).
Машина с конечным числом состояний
Машина с конечным числом состояний (finite state machine, FSM), или конечный автомат (finite automaton) — это математическая абстракция, используемая при проектировании алгоритмов. Говоря простым языком, машина с конечным числом состояний умеет считывать последовательности входных данных. Когда она считывает входной сигнал, то переключается в новое состояние. Куда именно переключится, получив данный сигнал, — заложено в её текущем состоянии. Звучит запутанно, но на самом деле всё очень просто.
Представим устройство, которое читает длинную бумажную ленту. На каждом дюйме этой ленты напечатана буква — a или b.
Как только устройство считывает букву, оно меняет своё состояние. Вот очень простой граф переходов для такой машины:
Кружки — это состояния, в которых машина может быть. Стрелочки — переходы между ними. Так что, если вы находитесь в состоянии s и считываете a, то вам необходимо перейти в состояние q. А если b, то просто остаётесь на месте.
Итак, если изначально мы находимся в состоянии s и начинаем читать ленту из первого рисунка слева направо, то сначала будет прочитана a, и мы переместимся в состояние q, затем b — вернёмся обратно в s. Следующая b оставит нас на месте, а a вновь переместит в q. Элементарно, но какой в этом смысл?
Оказывается, если пропустить ленту с буквами через FSM, то по её итоговому состоянию можно сделать некоторые выводы о последовательности букв. Для приведённго выше простого конечного автомата финальное состояние s означает, что лента закончилась буквой b. Если же мы закончили в состоянии q, то последней на ленте была буква a.
Основы информатики и вычислительной техники. Алгоритмы плюс робот (1987)
Это может показаться бессмысленным, но существует масса задач, которые можно решить с помощью такого подхода. Простейший пример: определить, содержит ли HTML-страница следующие теги в заданном порядке:
Машина с конечным числом состояний может перейти в новой состояние, считав , потом зациклиться до считывания , зациклиться до считывания и т.д. Если она успешно придёт к финальному состоянию, то заданные тэги стоят в правильном порядке.
Также конечный автомат может использоваться для представления механизмов парковочного счётчика, автомата с газировкой, автоматизированного газового насоса и тому подобных штук.
Детерминированная машина с конечным числом состояний (Deterministic Finite State Machine)
Машины с конечным числом состояний, которые мы рассматривали выше, являются детерминированными. У них из любого состояния существует только один переход для любого разрешённого входного сигнала. Другими словами, не существует двух различных путей из данного состояния, когда вы считываете, допустим, букву a. На первый взгляд такое ограничение кажется глупым.
Что хорошего в наборе решений, если один и тот же сигнал на входе может переместить вас более, чем в одно состояние? Вы же не можете сказать компьютеру: если x == true , то выполни doSomethingBig() или doSomethingSmall(), не так ли?
Ну, вообще-то, с помощью машины с конечным числом состояний можно провернуть что-то в этом роде. Выход конечного автомата — его финальное состояние. Сначала он проведёт все вычисления, затем прочтёт последнее состояние, и только тогда совершится какое-то действие. А в процессе переходов от состояния к состоянию не будет делаться ровным счётом ничего.
FSM обрабатывает поступившие данные, и только дойдя до конца и считав конечное состояние, совершает ожидаемое от неё действие (например, наливает газировку). Этот принцип особенно важен, когда дело доходит до недетерминированных машин с конечным числом состояний.
Недетерминированная машина с конечным числом состояний (Nondeterministic Finite State Machine)
Недетерминированные машины с конечным числом состояний, или недетерминированные конечные автоматы (nondeterministic finite automaton, NFA) — это конечные автоматы, у которых входной сигнал для данного состояния может вести более чем в одно последующее состояние. Допустим, например, что мы хотим построить FSM, которая способна распознавать строки букв, начинающиеся с буквы a, за которой следует нуль или более букв b или нуль или более букв c. Условие останова — следующая буква алфавита на входе. Допустимыми строками будут:
Итак, надо распознать букву a с последующим нулём или более одинаковых букв b или c и с замыкающей следующей буквой алфавита. Самый простой способ отобразить этот алгоритм с помощью машины с конечным числом состояний представлен ниже. Финальное состояние t означает, что строка была принята целиком и соответствует шаблону.
Видите проблему? Находясь в начальной точке s мы понятия не имеем, какой из путей выбрать. Если мы прочли только букву a, то мы ещё не знаем, идти нам в q или в r. Существует несколько способов решить эту задачу. Первый из них — откат.
Вы просто перебираете все возможные пути и игнорируете или возвращаетесь назад по тем из них, где решение заходит в тупик.
На этом принципе основан алгоритм большинства шахматных программ. Они просматривают все возможности всех возможных ходов на данном этапе и выбирают ту стратегию, которая в данный момент даёт максимальное преимущество над противником.
Другой путь — это преобразовать недетерминированную машину с конечным числом состояний в детерминированную. Существование алгоритма преобразования любой недетерминированного автомата в детерминированный является одним из интереснейших атрибутов NFA. Однако, часто это весьма сложный процесс. К счастью для нас, пример выше достаточно прост. Фактически, всё преобразование можно провести в уме, не прибегая к помощи формального алгоритма.
Машина ниже — детерминированная версия недетерминированной машины на предыдущем рисунке. Здесь конечные состояния t или v достижимы для любой принятой машиной строки.
Недетерминированная модель имеет четыре состояния и шесть переходов. Детерминированная модель — шесть состояний, десять переходов и два возможных завершения. Разница невелика, однако мы знаем, что сложность имеет свойство расти по экспоненте. И адекватных размеров недетерминированная машина способна вырасти в просто огромную детерминированную.
Регулярные выражения
Если вы когда-нибудь занимались любым видом программирования, то вы почти наверняка сталкивались с регулярными выражениями (regular expressions). Регулярные выражения и машины с конечным числом состояний функционально эквивалентны. Всё, что можно допустить для (или связать с) регулярным выражением, можно допустить для (или связать с) конечным автоматом. Например, шаблон, который мы разбирали выше, можно связать с
Регулярные выражения и машины с конечным числом состояний также имеют и одинаковые ограничения. Точнее, они могут принимать или связывать шаблоны, для обработки которых требуется конечный размер памяти. Так какие же типы шаблонов для них недопустимы? Предположим, что мы хотим найти только строки, состоящие из a и b, где за каким-то количеством букв a следует такое же число букв b. Другими словами, за n a следует n b, где n — какое-то число. Примером могут послужить строки:
- ab
- aabb
- aaaaaabbbbbb
- aaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbb
На первый взгляд это выглядит детской задачей для машины с конечным числом состояний. Проблема в том, что вы или быстро выйдете за пределы заданного числа состояний, или вам придётся допустить бесконечное их количество — и в этот момент ваше устройство перестаёт быть машиной с конечным числом состояний.
Допустим, вы создаёте конечный автомат, который может принять двадцать a и следующие за ними двадцать b. Он будет прекрасно работать до те пор, пока на вход не придёт строка из двадцати одной a и двадцати одной b. И тогда вам придётся переписывать вашу машину для обработки более длинных строк. Для любой строки, которую вы можете распознать, всегда есть ещё одна, которая будет лишь немного длиннее, но которую ваша машина уже не способна обработать, не выходя за пределы памяти.
Это положение известно как лемма о накачке для регулярных языков. Её основная мысль: если ваш шаблон имеет блок, который может быть повторён более, чем один раз, то этот шаблон не является регулярным. Другими словами, ни регулярные выражения, ни машины с конечным числом состояний не могут быть сконструированы так, чтобы распознавать все строки, которые можно связать с шаблоном.
Если вы посмотрите внимательнее, то заметите, что тип шаблона, в котором каждая a связана с b, выглядит очень похоже на HTML, где внутри любой пары тэгов можно заключить произвольное количество других пар тэгов. Вот почему вы можете использовать регулярное выражение или машину с конечным числом состояний для распознавания, содержит ли HTML-страница конкретные html , head и body элементы в правильном порядке, но не можете использовать регулярное выражение, чтобы сказать, является ли HTML-страница целиком корректной или нет. HTML — не регулярный шаблон.
Машина Тьюринга
Так как же нам распознавать нерегулярные шаблоны? Существует теоретическое устройство, подобное конечному автомату и называемое машиной Тьюринга (Turing Machine). Как и у машины с конечным числом состояний, у него имеется бумажная лента, с которой оно считывает информацию. Однако, машина Тьюринга также способна записывать и стирать данные на ленте. Полное объяснение принципов этого устройства займёт больше места, чем у нас здесь имеется, поэтому я обозначу лишь несколько важных моментов, относящихся к нашей дискуссии о машинах с конечным числом состояний и регулярных выражениях.
Машина Тьюринга вычислительно полна, и всё, что в принципе может быть вычислено, может быть вычислено с помощью машины Тьюринга. А благодаря способности записывать данные на ленту с такой же лёгкостью, как и считывать их с ленты, она не ограничена конечным числом состояний. Бумажную ленту можно представить, как имеющую бесконечную длину. Очевидно, что современные компьютеры не обладают бесконечным количеством памяти, однако, они имеют её достаточно, чтобы вы не вышли за предел для тех типов задач, которые они способны обработать.
Машина Тьюринга предоставляет нам воображаемое механическое устройство, позволяющее визуализировать и понять, как работает вычислительный процесс. Это особенно полезно для понимания пределов вычислений. Если это интересно, то в будущем я могу написать отдельную статью о машине Тьюринга.
Почему это имеет значение?
Так какой во всём этом смысл? Как вышесказанное способно помочь вам при создании очередной PHP-формы? Несмотря на все их ограничения, машины с конечным числом состояний — одна из центральных концепций теории вычислений.
В частности, тот факт, что из любого недетермированного конечного автомата, который вы можете спроектировать, возможно получить детерминированный конечный автомат, делающий то же самое. Это ключевой момент, потому что подразумевает, что вы можете спроектировать свой алгоритм, в котором каждый шаг будет наиболее очевидным. А уже имея надлежащий алгоритм, вы сможете легко конвертировать его в ту форму, в которой он будет наиболее эффективен.
Понимание, что машины с конечным числом состояний и регулярные выражения функционально эквивалентны, открывает невероятно интересные способы применения движков регэкспов. Особенно, когда дело доходит до создания бизнес-правил, которые могут быть изменены без перекомпиляции всей системы.
Знание основ теории вычислительных систем позволяет вам брать проблему X, которую вы понятия не имеете как решать, и применять к ней подход: «Я не знаю, как решить X, но я знаю, как решить Y и как привести решение для Y к решению для X. Вот почему теперь я знаю, как решить X».
- state machine
- finite state machine
- finite automaton
- машина конечных состояний
- конечный автомат
Источник: habr.com
Вычислительная система. Системное и прикладное программное обеспечение. Классификация. Назначение. Схема. (Тема 1.2.3)
Все программное обеспечение, имеющееся на компьютере, принято
делить на 2 большие части — базовое программное обеспечение (его
еще могут называть системным программным обеспечением) и
прикладное программное обеспечение.
Базовое программное обеспечение — это набор программ,
которые отвечают за взаимодействие с аппаратными средствами
(компонентами, составляющими базовую конфигурацию
вычислительной техники).
В состав базового (системного) программного обеспечения входят:
•операционные системы;
•сервисные программы (оболочки операционных систем, утилиты,
интерфейсные программы);
•инструментальные программы (трансляторы, загрузчики, средства
отладки);
•программы технического обслуживания (наладочные,
диагностические, тестовые).
3.
Операционная система — это обязательная часть базового программного
обеспечения компьютера. Обеспечивает эффективное функционирование
компьютера, организует выполнение других программ, установленных на
компьютере, а также взаимодействие пользователя и внешних устройств с
компьютером.
Сервисные программы — это программы, которые дополняют и расширяют
возможности операционной системы, предоставляя пользователю компьютера
дополнительные возможности.
Инструментальные программы — это программы, которые предназначены
для эффективной разработки и отладки программного обеспечения.
Используются обычно высококвалифицированными пользователями —
программистами.
Программы технического обслуживания компьютера — это программы,
которые предназначены для диагностики, тестирования технических средств
и поиска неисправностей в компьютере. Благодаря использованию этих
программ повышается надежность и достоверность обработки информации
на компьютере.
4.
В состав прикладного программного обеспечения входят
различные программы, предназначенные для решения задач
пользователя, например:
•текстовые редакторы;
•гипертекстовые редакторы;
•редакторы электронных таблиц;
•графические редакторы;
•экспертные системы;
•издательские системы;
•программы для бухгалтеров;
•программы для банковских сотрудников;
•программы для маркетологов;
•программы для сотрудников страховых компаний и т.д.
5.
На рис. 12.2 представлена принципиальная схема конфигурации программного обеспечения компьютера.
6.
Задачи и функции операционной системы (ОС)
Если рассматривать ОС как некий механизм, управляющий всеми частями вычислительной
машины, то одной из основных задач ОС является управление вычислительными ресурсами.
К вычислительным ресурсам относят процессорное время, оперативную и постоянную память,
мультимедиа-компоненты, телекоммуникационное и периферийное оборудование.
Управление ресурсами включает решение двух общих, не зависящих от типа ресурса задач —
планирование ресурса и отслеживание его состояния.
Второй основной задачей операционной системы является предоставление пользователю некоей
абстрактной машины, с чьей помощью он может решать различные задачи.
Под абстрактной машиной в данном случае понимается машина, которая состоит из стандартных
блоков, каждый из которых управляется стандартным образом.
Исходя из такой постановки задач, можно определить следующие функции операционной
системы:
эффективное управление вычислительными ресурсами для повышения эффективности работы
вычислительной машины
и обеспечение необходимого уровня прозрачности оборудования для пользователей.
7.
Виды операционных систем
Наиболее распространенными из классификаций операционных систем
являются следующие две — по функциональным возможностям и по
областям применения.
По функциональным возможностям выделяют:
•однозадачные и многозадачные — многозадачные ОС делятся на ОС
с вытесняющей и невытесняющей многозадачностью. При вытесняющей
многозадачности контроль за работой программ лежит на операционной
системе, в противном же случае ход вычислений контролируется каждой
программой самостоятельно;
•однопользовательские и многопользовательские;
•однопроцессорные и многопроцессорные — многопроцессорные ОС
делятся на симметричные и асимметричные. Асимметричные
многопроцессорные операционные системы отличаются от симметричных
тем, что первая монополизирует для работы операционной системы один или
более процессоров, в то время как вторая использует часть процессорного
времени каждого процессора.
•однонитевые и многонитевые операционные системы
8.
•По областям применения выделяют операционные
системы:
•мейнфреймов,
•кластеров,
•серверов,
•рабочих станций,
•карманных компьютеров,
•мобильные и встраиваемые операционные системы.
В зависимости от области применения различаются и
функциональные возможности каждого класса
операционных систем.
9.
Свойства операционных систем
Свойства, которыми обладают операционные системы, делятся
на две группы — машинно независимые и машинно
зависимые.
Машинно независимые свойства характеризуют
возможности операционной системы по управлению
вычислительными ресурсами и особенности организации
вычислительных процессов, а также способы организации
файловых структур.
К машинно зависимым свойствам современных
операционных систем относят многозадачность, возможность
одновременной работы нескольких пользователей,
возможность многопроцессорной обработки данных,
возможность распараллеливания вычислений и многие другие.
10.
Управление ресурсами
Врамках проблемы управления вычислительными ресурсами необходимо решать две задачи:
1) планирование ресурса — определение, кому, когда и в каком количестве необходимо
выделить данный ресурс;
2) отслеживание состояния ресурса, то есть поддержание оперативной информации о том,
занят или не занят ресурс, а для делимых ресурсов — какое количество ресурса уже
распределено.
Вычислительные ресурсы можно разделить на две
категории — выгружаемые и невыгружаемые ресурсы. Ресурс считается выгружаемым, если
его можно во время работы процесса-владельца передать другому процессу без ущерба для
процесса-владельца. Память является выгружаемым ресурсом. А вот устройство записи
компакт-дисков является невыгружаемым ресурсом.
Задача управления ресурсами осложнена проблемой возможной взаимоблокировки процессов.
Взаимоблокировка — ситуация, когда одни процессы блокируют доступ другим процессам к
различным ресурсам. Она обусловлена тем, что в каждый конкретный момент времени один и
тот же ресурс может быть использован только в рамках одной задачи. Это особенно заметно при
использовании периферийного оборудования, к примеру в случае сканирования или печати
документа или же при работе с файловой системой. Взаимоблокировка выгружаемых ресурсов
разрешается путем перераспределения ресурсов между процессами. Взаимоблокировка
невыгружаемых ресурсов может быть решена путем блокировки процесса до тех пор, пока не
освободится запрошенный ресурс.
11.
Планирование процессов
Одним из важнейших понятий операционных систем является понятие процесса.
Процесс — программа, которая в данный момент выполняется вычислительной
машиной.
Каждому процессу выделяется отдельный, изолированный от других, сегмент памяти,
который называется адресным пространством процесса.
В адресном пространстве процесса, кроме самого процесса, также хранятся входные и
выходные данные процесса. Для обеспечения корректной работы процессов
необходимо отслеживать состояние каждого процесса, чтобы возобновлять его
выполнение с того момента, где в последний раз процесс был остановлен.
Кроме состояния процесса необходимо также отслеживать информацию об
используемых им ресурсах.
Вся информация о процессах хранится в таблице процессов — массиве структур
данных, записями которого является информация по каждому процессу, запущенному
в системе.
Таблица процессов представляется обычно в виде дерева, потому что большинство
процессов, выполняемых на машине, способно порождать дочерние процессы для
решения вспомогательных задач, и для каждого процесса необходимо учитывать не
только его собственное состояние, но и состояние всех связанных с ним процессов.
12.
Файловая система
Сами программы и данные для их работы хранятся на различных носителях.
Способ организации данных на носителе называется файловой системой.
Другой категорией служебных файлов является ярлык, или ссылка.
Ярлык хранит путь к файлу и при вызове открывает сам файл. Ярлыки
используются для ускорения доступа к файлам.
Свойства файла в рамках конкретной файловой системы
называются атрибутами файла. К атрибутам относят дату и время создания
файла, тип файла, права доступа к файлу.
13.
Обслуживание ввода-вывода. Прерывания. Виртуальная
память
Устройства ввода-вывода делятся на две категории —
блочные и символьные.
•Блочные устройства — оперируют блоками данных, размер
которых варьируется в зависимости от устройства. Каждый
блок в блочном устройстве имеет собственный адрес.
Примером блочного устройства может служить любой
накопитель. Одним из наиболее важных свойств блочного
устройства является возможность независимого доступа к
блокам данных.
•Символьные устройства — оперируют потоками данных, не
имеющими структуры или адреса. Большинство устройств
являются символьными.
14.
Устройство ввода-вывода обычно состоит из двух частей — само
устройство и его контроллер.
Контроллер осуществляет управление работой устройства на
физическом уровне. Контроллер выполняется в виде набора
микросхем и либо совмещен с устройством, либо установлен на
системной плате. Каждый контроллер, помимо буфера, имеет
также несколько регистров, посредством которых процессор
может управлять работой контроллера.
Существует два альтернативных способа управления контроллерами
устройств.
•Первый способ заключается в том, что каждому регистру назначается
уникальный номер порта ввода-вывода.
•Второй способ заключается в выделении каждому регистру отдельного
сегмента оперативной памяти.
15.
Прерывание — это сигнал процессору о том, что ему
необходимо прервать выполнение текущего процесса и
вызвать обработчик прерывания.
Обработчик прерывания — это программа, которую
процессор должен выполнить при возникновении прерывания.
Обработчик прерывания является частью драйвера
устройства.
Драйвером устройства называют программу, которая
обеспечивает взаимодействие устройства с операционной
системой.
16.
Виртуальной памятью называют такой метод работы с памятью, когда
в памяти хранятся только те части программы, которые используются в
конкретный момент времени.
При работе с виртуальной памятью вся доступная память разбивается
на страничные блоки фиксированного объема.
При обращении к какой-либо ячейке памяти запрос сначала передается
диспетчеру памяти, который преобразовывает виртуальный адрес в
реальный, и передает полученный адрес на шину, который затем
обрабатывается надлежащим образом.
17.
Контрольные вопросы
•В чем отличие базового программного обеспечения от прикладного?
•Какие программы считаются сервисными?
•Что такое операционная система?
•Каковы функции операционной системы?
•Как классифицируются операционные системы?
•Как операционная система управляет вычислительными ресурсами?
•Что такое файловая система? Какой вид файловой системы использует
операционная система вашего компьютера?
•Какая информация содержится в драйвере устройства?
•Что такое виртуальная память?
Источник: ppt-online.org
Свойства операционных систем Свойства, которыми обладают операционные системы, делятся на две группы – машинно-независимые и машинно-зависимые. Машинно-независимые. — презентация
Презентация на тему: » Свойства операционных систем Свойства, которыми обладают операционные системы, делятся на две группы – машинно-независимые и машинно-зависимые. Машинно-независимые.» — Транскрипт:
1 Свойства операционных систем Свойства, которыми обладают операционные системы, делятся на две группы – машинно-независимые и машинно-зависимые. Машинно-независимые свойства характеризуют возможности ОС: по управлению вычислительными ресурсами, особенности организации вычислительных процессов, способы организации файловых структур. К машинно-зависимым свойствам современных ОС относят: многозадачность, возможность одновременной работы нескольких пользователей, возможность многопроцессорной обработки данных, возможность распараллеливания вычислений и многие другие.
2 Тема 2. Функции операционных систем Вопрос 1. Машинно-зависимые свойства операционных систем. 1. Процессы и потоки 2. Устройства ввода-вывода. Прерывания. 3. Виртуальная память. Вопрос 2. Машинно-независимые свойства операционных систем. 1. Файловая система.
2. Управление ресурсами. 3. Планирование заданий.
3 Тема 2. Функции операционных систем Вопрос 1. Машинно-зависимые свойства операционных систем. Процессы и потоки Процессом называют программу Процессом называют программу, которая в данный момент выполняется вычислительной машиной. адресным пространством процесса. Каждому процессу выделяется отдельный, изолированный от других, сегмент памяти, который называют адресным пространством процесса. адресном пространстве процесса В адресном пространстве процесса, кроме самого процесса, также хранятся входные и выходные данные процесса.
4 многозадачной В многозадачной ОС все процессы выполняются по очереди таким образом, что в каждый момент времени выполняется только один процесс. состояние каждого процесса Для обеспечения корректной работы процессов необходимо отслеживать состояние каждого процесса, чтобы возобновлять его выполнение с того момента, где в последний раз процесс был остановлен.
5 Таблица процессов Таблица процессов – массив структур данных, записями которого является информация по каждому процессу, запущенному в системе. Таблица процессов Таблица процессов представляется обычно в виде дерева, потому что большинство процессов, выполняемых на машине, способно порождать дочерние процессы для решения вспомогательных задач, и для каждого процесса необходимо учитывать не только его собственное состояние, но и состояние всех связанных с ним процессов.
6 два идентификатора Каждому процессу назначается два идентификатора: первый первый из которых указывает на сам процесс, второй второй – на процесс, его породивший. базовый процесс Традиционно, при загрузке ОС запускается некий базовый процесс, который порождает все прочие процессы – как системные, так и пользовательские. контроль вычислительных ресурсов. Этот процесс реализует главную функцию ОС – контроль вычислительных ресурсов. В современных версиях Windows этот процесс называется «System Idle».
7 Задача планирования процессов вычислительных ресурсов Задача планирования процессов заключается в отслеживании их состояния и использования ими вычислительных ресурсов. Вычислительный ресурс Вычислительный ресурс в каждый конкретный момент времени может быть задействован только одним процессом. Если несколько процессов должны использовать один и тот же ресурс, то они используют его по очереди. Очередность использования определяется приоритетом процесса. Чем выше приоритет процесса, тем чаще он будет получать доступ к требуемым ресурсам.
8 Каждый процесс представлен как минимум одним потоком. Потоком называют последовательность исполняемых команд. В рамках одного и того же процесса может выполняться несколько разных потоков. Использование нескольких потоков позволяет сократить время исполнения программы.
Такой подход удобен, если этапы решения задачи, для которой создавалась программа, можно выполнять параллельно. Потоки обладают некоторыми свойствами процессов. В отличие от процессов, потоки существуют в одном и том же адресном пространстве и могут одновременно работать с выделенными процессу ресурсами.
9 Устройства ввода-вывода. Прерывания. блочные и символьные Устройства ввода-вывода делятся на две категории – блочные и символьные. Блочное устройство Блочное устройство оперирует блоками данных, размер которых варьируется в зависимости от устройства. Каждый блок в блочном устройстве имеет собственный адрес. Примером блочного устройства может служить любой накопитель.
Одним из наиболее важных свойств блочного устройства является возможность независимого доступа к блокам данных. Символьные устройства Символьные устройства оперируют потоками данных, не имеющими структуры или адреса. Большинство устройств являются символьными.
10 Устройство ввода-вывода Устройство ввода-вывода состоит из двух частей – само устройство и его контроллер. Контроллер осуществляет управление работой устройства на физическом уровне. Контроллер выполняется в виде набора микросхем и либо совмещен с устройством, либо установлен на системной плате. Если контроллер установлен на системной плате, то обычно он позволяет работать с двумя и более устройствами данного типа.
11 Задачей контроллера Задачей контроллера является преобразование потока битов в блок байтов. Считываемые биты накапливаются в памяти контроллера, которая называется буфером данных, и затем в виде блоков байтов передаются в оперативную память. Каждый контроллер, помимо буфера, имеет также несколько регистров, посредством которых процессор может управлять работой контроллера.
12 Два альтернативных способа управления контроллерами устройствами. Первый способ уникальный номер порта ввода-вывода Первый способ заключается в том, что каждому регистру назначается уникальный номер порта ввода-вывода. При таком способе адресное пространство оперативной памяти не пересекается с адресным пространством устройств ввода- вывода. Второй способ сегмента оперативной памяти Второй способ заключается в выделении каждому регистру отдельного сегмента оперативной памяти.
13 Преимущество второго способа: для программирования работы устройств не нужно прибегать к машинным языкам, при таком подходе для защиты от несанкционированного доступа к устройствам достаточно исключить часть адресного пространства устройств ввода-вывода из блока адресов памяти, доступных пользователям.
14 Недостатком этого подхода Недостатком этого подхода в том, что для его реализации необходимо использование более сложной аппаратуры. Повышение сложности аппаратуры обуславливается тем фактором, что некоторые приемы, используемые для ускорения работы с памятью, могут привести к катастрофическим последствиям при использовании их с устройствами ввода-вывода.
15 DMA DMA предназначен для ускорения обмена данными между процессором и устройствами. Контроллер DMA Контроллер DMA обеспечивает чтение данных с устройства в память и запись данных из памяти на устройство. Механизм прямого доступа к памяти (DMA)
16 DMA DMA работает следующим образом: Процессор программирует контроллер DMA на выполнение необходимой операции, сообщая контроллеру, с каким устройством необходимо выполнить требуемую операцию, и по какому адресу в памяти размещаются данные. Пока контроллер выполняет операцию, процессор может выполнять другие процессы. Когда контроллер DMA завершает порученную ему задачу, он посылает процессору сигнал о том, что операция завершена, после чего процессор приостанавливает выполнение текущей задачи, и начинает выполнять тот процесс, который затребовал ввод-вывод данных.
17 Прерывание Прерывание – это сигнал процессору о том, что ему необходимо прервать выполнение текущего процесса и вызвать обработчик прерывания. Обработчик прерывания Обработчик прерывания – это программа, которую процессор должен выполнить при возникновении прерывания. Обработчик прерывания является частью драйвера устройства. Драйвер устройства Драйвер устройства — обеспечивает взаимодействие устройства с операционной системой.
18 Виртуальная память. Виртуальной памятью называют такой метод работы с памятью, когда в оперативной памяти хранятся только те части программы, которые используются в конкретный момент времени. Все прочие части программы, равно как и данные, хранятся на диске. Этот способ организации памяти позволяет выполнять программы, чей суммарный объем вместе с данными может превышать объем доступной физической памяти.
19 Механизм страничной организации памяти. При работе с виртуальной памятью вся доступная память разбивается на страничные блоки фиксированного объема. При обращении к какой-либо ячейке памяти запрос сначала передается диспетчеру памяти, который преобразовывает виртуальный адрес в реальный, и передает полученный адрес на шину, который затем обрабатывается надлежащим образом. Объем виртуальной памяти, доступной программам, выбирается операционной системой автоматически.
20 Вопрос 2. Машинно-независимые свойства операционных систем Файловая система. Файловая система Файловая система — способ организации данных на носителе. Файл Файл — именованная область данных на носителе, хранящая некоторый массив информации. Размер файла Размер файла — объем некоторого пространства на носителе, которое занимает файл.
Тип хранимых данных Тип хранимых данных — Например, текстовые файлы, программы, аудиофайлы, видеофайлы, программные модули, служебные файлы и многие другие. Атрибуты файла Атрибуты файла — характеристики файла в рамках конкретной файловой системы. К атрибутам относят дату и время создания файла, имя и тип файла, права доступа к файлу.
21 Каталог Каталог — массив файлов, сгруппированных по какому-либо признаку. Каталог, как и любой другой файл, имеет собственное имя. Именем Именем конечного файла при таком способе организации файловой структуры является полный путь до каталога, в котором хранится файл плюс само имя файла. Ярлык Ярлык хранит путь к файлу и при вызове открывает сам файл. Ярлыки используются для ускорения доступа к файлам или во избежание ненужного дублирования данных.
22 Стандарты на файловую систему В зависимости от типа носителя выделяют различные файловые системы (ФС). FAT, NTFS, UFS К примеру, для дисковых и flash накопителей используются файловые системы FAT, NTFS, UFS. ISO9660UDF А для компакт-дисков принято использовать файловые системы ISO9660 или UDF. Требования к хранению данных.
ФС дисковых накопителей должны обеспечивать механизмы обеспечения целостности данных в условиях постоянного выполнения операций чтения-записи данных сравнительно большим количеством процессов. ФС для компакт-дисков требуется обеспечение простого доступа к данным на большом количестве различного оборудования, в том числе и бытового.
23 разметкой носителя Операция подготовки носителя к использованию называется разметкой носителя. При разметке носителя определяется количество и размеры областей, которые в дальнейшем будут использованы для хранения файлов. физическим диском Традиционно, носитель называется физическим диском. логическим диском Каждая область, сформированная при разметке носителя, называется логическим диском. имя Каждый логический диск получает имя, уникальное для данной операционной системы. один Каждый физический диск имеет, как минимум, один логический диск.
24 форматированием диска Операция по подготовке логического диска к использованию файловой системы называется форматированием диска. кластерами При форматировании, логический диск разбивается на блоки фиксированного размера, именуемые кластерами. Размер кластера 512 байт Размер кластера зависит от конкретной файловой системы и может варьироваться от 512 байт до нескольких килобайт. минимуму потери дискового пространства быстродействия операций чтения-записи данных В зависимости от емкости логического диска, операционная система выбирает размер кластера таким образом, чтобы свести к минимуму потери дискового пространства, сохраняя при этом некоторый уровень быстродействия операций чтения-записи данных.
25 Управление ресурсами. Две задачи: планирование ресурса планирование ресурса – определение, кому, когда и в каком количестве, необходимо выделить данный ресурс; отслеживание состояния ресурса отслеживание состояния ресурса -поддержание оперативной информации о том, занят или не занят ресурс, а для делимых ресурсов, какое количество ресурса уже распределено. Две категории выгружаемые и невыгружаемые ресурсы. выгружаемым Ресурс считается выгружаемым, если его можно во время работы процесса-владельца передать другому процессу без ущерба для процесса-владельца. Память Память является выгружаемым ресурсом. Устройство записи компакт-дисков невыгружаемым Устройство записи компакт-дисков является невыгружаемым ресурсом.
26 Взаимоблокировкой Взаимоблокировкой называется ситуация, когда одни процессы блокируют доступ другим процессам к различным ресурсам. Она обусловлена тем, что в каждый конкретный момент времени один и тот же ресурс может быть использован только в рамках одной задачи. Это особенно заметно при использовании периферийного оборудования, к примеру, в случае сканирования или печати документа, или же при работе с файловой системой. Взаимоблокировка выгружаемых ресурсов Взаимоблокировка выгружаемых ресурсов разрешается путем перераспределения ресурсов между процессами. Взаимоблокировка невыгружаемых ресурсов Взаимоблокировка невыгружаемых ресурсов может быть решена путем блокировки процесса до тех пор, пока не освободится запрошенный ресурс.
27 Использование ресурса можно разделить на три этапа – запрос, использование и возврат ресурса запрос, использование и возврат ресурса. Для каждого их этих этапов должны существовать определенные механизмы защиты процессов от взаимоблокировки. запрос ресурса, отказ, ожидание Если процесс запрашивает ресурс, который в данный момент уже используется другим процессом, то процесс попадает в короткий цикл – запрос ресурса, отказ, ожидание. специальный системный вызов В одних системах существует специальный системный вызов, который позволяет процессам в явном виде запрашивать использование ресурса. канал В других системах каждому ресурсу сопоставлен файл или канал, посредством которого процесс может использовать ресурс.
28 ВСЕ Для возникновения взаимоблокировки должны выполняться ВСЕ следующие условия: 1. Взаимное исключение 1. Взаимное исключение – каждый ресурс либо доступен, либо используется одним процессом; 2. Удержание и ожидание 2. Удержание и ожидание – процесс, уже получивший какой-либо ресурс и, не освобождая его, запрашивает новый ресурс; 3. Отсутствие принудительной выгрузки ресурса 3. Отсутствие принудительной выгрузки ресурса – отсутствует механизм принудительного освобождения ресурсов у занимающих их процессов; 4. Циклическое ожидание 4. Циклическое ожидание – каждый из процессов в системе ожидает освобождения ресурса, занятого другим процессом.
29 При решении данной проблемы может использоваться любой из следующих подходов: игнорирование проблемы, реакция на возникшую взаимоблокировку, аккуратное управление ресурсами, структурное опровержение каждого из условий для предотвращения возникновения взаимоблокировок.
30 Первый подход Первый подход применим в том случае, если при решаемых задачах вероятность возникновения взаимоблокировки минимальна либо невозможна. При втором подходе При втором подходе система не предотвращает взаимоблокировки, но производит мониторинг всех действий, выполняемых системой, чтобы после возникновения взаимоблокировки откатить систему к моменту ее возникновения и скорректировать работу системы таким образом, чтобы избежать повторения ситуации в дальнейшем.
31 Предотвращение взаимоблокировок возможно, когда вероятность каждого из необходимых условий сведена к минимуму. Первое условие Первое условие – принудительное ограничение числа процессов-претендентов на каждый ресурс. Второе условие Второе условие блокируется, если обязать процессы резервировать все ресурсы перед выполнением.
Если какой- либо ресурс недоступен, процессу отказывают в исполнении до тех пор, пока ресурс не освободится. Третье условие Третье условие блокировке не поддается, потому что может привести к самым непредсказуемым последствиям, вплоть до поломки оборудования. Четвертое условие Четвертое условие поддается блокировке путем определения порядка использования ресурсов процессами во избежание заведомо тупиковых ситуаций.
32 Планирование заданий Заданием называют задачу Заданием называют задачу, которая решается на данной аппаратной платформе при помощи некоторого приложения. В промышленных системах В промышленных системах, роль ОС исполняет само приложение, решающее задачу. И в этом случае, проблема планирования заданий не возникает в принципе, ибо все вычислительные ресурсы системы направлены только на решение этой задачи с максимальной эффективностью. В традиционных системах В традиционных системах – одновременного решения требует множество задач, каждая из которых решается не одной программой, а целым программным комплексом. Грубо говоря, если в рамках решения задачи требуется использование параллельных вычислений, то независимо от того, сколько процессоров установлено на данный момент в системе, эта необходимость будет реализована тем или иным методом, в зависимости от механизма планирования процессов, который может быть реализован на данной аппаратной платформе.
33 Механизм планирования заданий Механизм планирования заданий определяет облик ОС в целом, ее парадигму. Механизм планирования процессов Механизм планирования процессов отвечает за работу ОС на конкретном аппаратном обеспечении и его тип определяется на этапе установки ОС на данную аппаратную платформу. Задача планирования заданий планирования Задача планирования заданий, сводится к необходимости планирования: в какой момент времени, какому процессу, отвечающему за некоторый этап решения задачи, какое количество процессорного времени необходимо выделить.
34 Существует два класса ОС Существует два класса ОС, кардинально различающихся по подходу к задаче планирования заданий: 1. ОС разделения времени, 2. ОС реального времени. Системы первого класса Системы первого класса каждому заданию выделяют столько времени, чтобы создать и поддерживать иллюзию монопольной работы в системе. К данному классу относятся ОС для домашнего использования или для рабочих станций. Системы второго класса Системы второго класса спроектированы для решения задач, для которых существует жесткое ограничение на время их решения. К примеру, задача управления транспортными потоками города.
35 Таким образом, можно сделать заключение, что: на этапе планирования заданий на этапе планирования заданий ОС определяет, на какой этап решения задачи сколько процессорного времени выделять; на этапе планирования процессов на этапе планирования процессов – сколько и каких ресурсов выделять конкретным процессам в соответствии с приоритетом заданий и самих процессов; на этапе планирования ресурсов на этапе планирования ресурсов – как спланировать использование ресурсов с учетом потребностей всех процессов с максимальной эффективностью.
Источник: www.myshared.ru