Ю.Ю. Громов и др. Информатика (2007)

Рис. 3.19. Обмен информации в сети с шинной конфигурацией

или послать собственное сообщение, перед тем как передать маркер следующей машине. Таким образом, машины в сети имеют равныевозможности вводить свои сообщения по мере циркуляции маркера в сети.

Другой протокол для координации распределения прав отправки сообщений применен в сетях Ethernet – популярной версии сети с шинной конфигурацией. В таких сетях право передачи сообщений регулируется протоколом CSMA/CD (Carrier Sence, Multiple Access with Collision Detection – множественный доступ с опросом несущей и разрешением конфликтов). Этот протокол предусматривает, что каждое посланное сообщение будет передано всем машинам, соединенным шиной (рис. 3.19). Каждая машина просматривает все поступающие сообщения, но отбирает только те, которые адресованы именно ей. Чтобы отправить собственное сообщение, машина ожидает, пока в шине наступит тишина, затем начинает отправку, одновременно продолжая наблюдать за шиной. Если в этот момент и другая машина пытается отправить свое сообщение, обе обнаруживают конфликт и делают паузу на произвольно короткий промежуток времени, а затем предпринимают попытку вновь начать отправку. В результате складывается ситуация, аналогичная той, которая возникает при разговоре в небольшой группе людей. Если два человека начинают говорить одновременно, оба замолкают. Различие состоит в том, что люди могут выйти из ситуации таким образом: "Простите, что вы хотели сказать?", "Нет, нет, говорите вы первым"; в то время как по протоколу CSMA/CD каждая машина просто делает следующую попытку.

Семейство протоколов TCP/IP. Спрос на открытые сети вызвал потребность в разработке открытых стандартов. Следуя этим стандартам, производители могли бы выпускать оборудование и программное обеспечение, корректно взаимодействующее с продуктами других фирм-производителей. Одним из таких стандартов является модель OSI (Open System Interconnection – взаимодействие открытых систем), разработанная Международной организацией по стандартизации (ISO). Этот стандарт предусматривает иерархию из семи уровней, в отличие от четырехуровневой системы, принятой в Internet. На модель OSI часто ссылаются, так как ее поддерживает авторитет международной организации. Но она так и не была окончательно внедрена, главным образом из-за того, что появилась уже после того, как семейство протоколов TCP/IP получило широкое распространение в Internet.

Семейство протоколов TCP/IP представляет собой набор протоколов, определяющих четырехуровневую иерархию, используемую в Internet, основанную на представлении о том, что сетевая инфраструктура содержит четыре вида объектов: ресурсы, процессы, хосты, сети (см. табл. 3.2).

В действительности TCP/IР – это название только двух протоколов: TCP (Transmission Control Protocol – протокол управления передачей) и IP (Internet Protocol); так что по отношению ко всему семейству такое название несколько неточно. Говоря точнее, протокол TCP определяет одну из версий транспортного уровня. Мы употребили слово "версия", так как в семействе протоколов TCP/IP для представления транспортного уровня существуют два способа; второй определяется протоколом UDP (User Datagram Protocol – протокол датаграмм пользователя). Это напоминает ситуацию, когда при отправке запчастей отправитель имеет возможность выбора среди различных компаний по доставке грузов, каждая из которых предлагает одинаковый набор основных услуг, но имеет собственные характеристики. Таким образом, в зависимости от специфики требуемого обслуживания программное обеспечение прикладного уровня может выбирать, с помощью какой версии транспортного уровня, протокола TCP или UDP будут отправлены данные.

Протоколы транспортного уровня вводят новый уровень адресации, так называемый номер порта (port number), который определяет, какому процессу на машине передаются данные. Существует список соответствия номеров портов приложениям, определенных в RFC1700 (Request For Comments – запрос для пояснений – данные документы описывают стандарты протоколов Internet и их взаимодействие). Некоторые зарезервированные порты представлены в табл. 3.3.

Таблица 3.3

Между протоколами TCP и UDP существуют два основных различия. Первое состоит в том, что, перед тем как передать данные на транспортный уровень, базирующийся на протоколе TCP, посылается сообщение транспортному уровню маши- ны-получателя, уведомляющее о том, что предназначенные ему данные готовы к отправке, и извещающее, какое именно программное обеспечение прикладного уровня должно их принять. Затем транспортный уровень машины-отправителя ожидает уведомления о получении адресатом этого предварительного сообщения, и только после его прихода он приступает к передаче сегментов данных. Говорят, что транспортный уровень с протоколом TCP сначала устанавливает соединение, а затем посылает данные. Транспортный уровень, основанный на UDP, не устанавливает никакие соединения, прежде чем послать данные. Он просто посылает данные по указанному адресу и забывает о них. Для него не имеет значения, работает ли вообще в данный момент машина, указанная как получатель. Поэтому протокол UDP называют протоколом без установки соединения.

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

Протокол IP – это стандарт Internet для сетевого уровня. Одна из его функций состоит в том, что каждый раз, когда использующий протокол IP сетевой уровень с протоколом IP подготавливает пакет к передаче на канальный уровень, он прикрепляет к пакету некоторое значение, называемое счетчиком переходов по сети, или временем жизни пакета. Это значение указывает, сколько раз пакет может пересылаться между машинами в попытках проложить свой путь через Internet. Каждый раз, когда использующий протокол IP сетевой уровень пересылает некоторый пакет, он уменьшает значение его счетчика переходов на единицу. С помощью этого механизма сетевой уровень защищает Internet от бесконечной циркуляции пакетов в системе. Хотя размеры Internet продолжают расти с каждым днем, начальное значение счетчика переходов по сети, равное 64, остается более чем достаточным для того, чтобы позволить пакету найти свой путь в лабиринте локальных и глобальных сетей и маршрутизаторов.

Вопросы для самопроверки

1.Какие уровни иерархии программного обеспечения Internet используются для пересылки исходящего сообщения в адрес другой машины?

2.Каковы различия между транспортным уровнем, основанным на протоколе TCP, и транспортным уровнем, основанным на UDP?

3.Как программное обеспечение Internet гарантирует, что сообщения не будут вечно блуждать по Internet?

4.Что удерживает подключенную к Internet машину от записи копий всех проходящих через нее сообщений?

3.7.БЕЗОПАСНОСТЬ

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

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

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

Другой подход к защите данных от несанкционированного доступа заключается в шифровании данных. Даже если похититель получит данные, заключенная в них информация будет ему недоступна. Для этого разработано множество методов шифрования. Одним из наиболее популярных методов шифрования сообщений, посылаемых через Internet, является шифрование с открытым ключом. Он позволяет посылать сообщения, не доступные посторонним. При шифровании с открытым ключом используются два значения, называемые ключами. Так называемый открытый ключ используется для кодирования сообщений и известен всем, кому разрешено создавать сообщения. Закрытый ключ требуется для декодирования сообщения и известен только тому, кто должен получать сообщения. Знание открытого ключа не позволяет декодировать сообщения. Так что большого вреда не будет, даже если он попадет в чужие руки; пользователь, получивший несанкционированный доступ, сможет посылать шифрованные сообщения, но не будет иметь возможности декодировать перехваченные сообщения. Знание закрытого ключа, безусловно, более существенно, но узнать его сложней, чем открытый, так как им владеет только один человек. Мы познакомимся с некоторыми системами кодирования с открытым ключом в главе 11.

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

ВСоединенных Штатах Америки многие из этих вопросов регулируются законом о тайне обмена электронной информацией (Electronic Communication Privacy Act, ECPA), принятым в 1986 году. В качестве его основы использовалось законодательство о перехвате информации. Хотя этот документ достаточно объемный, его содержание можно передать несколькими короткими выдержками.

За исключением особо оговоренных случаев, любое лицо, которое намеренно перехватывает, пытается перехватить или склоняет другое лицо к перехвату или попытке перехвата любой информации по проводам, в устной форме или в виде электронного сообщения... будет наказано в соответствии с подразделом 4 или подвергнуто судебному преследованию в соответствии с подразделом 5.

Вот еще одна выдержка:

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

Вцелом закон ЕСРА подтверждает право индивидуума на тайну общения; службы, не уполномоченные на то специально, не имеют права прослушивать информацию, которой обмениваются третьи лица. Также незаконными считаются действия провайдера сетевых услуг, связанные с распространением сведений о содержании информации, которой обмениваются его клиенты. Однако законом также устанавливается следующее.

Не будет незаконным... если должностное лицо, наемный работник или агент Федеральной комиссии по связи по долгу службы и при исполнении своих обязанностей по наблюдению, осуществляемому федеральной комиссией согласно положениям главы 5 статьи 47 Кодекса Соединенных Штатов Америки, перехватывает информацию, распространяемую по проводам или электронным коммуникациям, устные переговоры по радио, а также раскрывает или использует информацию, полученную таким путем.

Таким образом, закон ЕСРА в явном виде предоставляет Федеральной комиссии по связи (FCC) США право контролировать электронные средства связи с некоторыми ограничениями. Это приводит к определенным и довольно сложным проблемам. Чтобы комиссия FCC могла воспользоваться предоставленными ей законом ЕСРА правами, системы связи должны быть разработаны и запрограммированы так, чтобы наблюдение за ними было возможно. Для обеспечения этой возможности был принят акт о содействии средств связи выполнению закона (Communications Assistance for Law Enforcement Act, CALEA). Он требует от владельцев средств телекоммуникации модифицировать их оборудование таким образом, чтобы оно допускало перехваты, требуемые по закону. Однако практическая реализация этого закона оказалась делом настолько сложным и дорогостоящим, что это привело к определенному смягчению требований. Еще более спорная проблема заключается в конфликте между правом комиссии FCC осуществлять контроль за информацией и правом пользователей использовать шифрование. Ведь если контролируемые сообщения хорошо зашифрованы, то простой их перехват в линиях связи практически бесполезен для служителей закона. Поэтому правительство США пошло по пути создания системы регистрации, требующей обязательной регистрации ключей шифрования (или, возможно, ключей к ключам). Но мы живем в мире, где промышленный шпионаж получил столь же широкое распространение, как и военный. Отсюда понятно, что требование регистрации ключей шифрования ставит многих законопослушных граждан в затруднительное положение. Насколько надежной будет сама регистрирующая система? Этот вопрос важен не только для США. Возможность создания аналогичных систем регистрации рассматривалась также в Канаде и странах Европы.

Проблема вандализма иллюстрируется появлением таких неприятных явлений, как компьютерные вирусы и сетевые

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

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

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

Вопросы для самопроверки

1.С технической точки зрения термин "данные" означает некоторое представление информации, а "информация" – содержимое данных. Что защищает пароль – данные или информацию? Что из них защищает шифрование?

2.Каковы основные положения закона ЕСРА?

3.На примере закона CALEA покажите, что принятие требующего определенных действий закона может и не привести к выполнению этих требований на практике.

Упражнения

(Упражнения, отмеченные звездочкой, относятся к разделам для дополнительного чтения.)

1.Перечислите четыре вида действий, выполняемых типичной операционной системой.

2.Кратко охарактеризуйте различия между пакетной и интерактивной обработкой.

3.В чем состоит различие между интерактивной обработкой и обработкой в реальном масштабе времени?

4.Что такое многозадачная операционная система?

5.Какая информация содержится в таблице процессов, поддерживаемой операционной системой?

6.В чем различие между процессом, готовым к выполнению, и ожидающим процессом?

7.В чем заключается различие между виртуальной и основной памятью?

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

9.Дайте определение понятиям балансировки загрузки и масштабирования в контексте многопроцессорной архитекту-

ры.

10.Кратко опишите процесс первоначальной загрузки.

11.Предположим, что операционная система с разделением времени использует кванты времени длительностью 50 миллисекунд. Если обычно процедура позиционирования головки чтения/записи диска над нужной дорожкой занимает 8 миллисекунд и еще 17 миллисекунд будет затрачено, пока требуемые данные пройдут под головкой чтения/записи, то какую часть кванта времени программа проведет в ожидании выполнения операции чтения с диска? Если машина способна выполнять по одной команде за каждую миллисекунду, сколько команд она смогла бы выполнить за время этого ожидания? (Именно по этой причине системы с разделением времени обычно позволяют выполняться другим процессам, в то время как первый процесс будет ожидать окончания обслуживания периферийным устройством.)

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

13.Говорят, что процесс зависит от ввода/вывода, если ему требуется выполнить много операций ввода/вывода. Процесс, преимущественно выполняющий вычисления в пределах системы "ЦП-память", называют вычислительно зависимым. Если вычислительно зависимый процесс и процесс, зависимый от ввода/вывода, ожидают предоставления кванта времени, кому долженбытьпредоставленприоритет ипочему?

14.Какая система достигнет большей производительности – система, выполняющая два процесса, зависимых от ввода/вывода (см. вопрос 13), или система с одним процессом, зависимым от ввода/вывода, и вычислительно зависимым процессом? Почему?

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

16.Назовите компоненты информации о состоянии процесса.

17.Приведите пример ситуации в системе с разделением времени, при которой процесс не использует весь предоставленный ему квант времени.

18.Перечислите в хронологическом порядке основные события, которые происходят при прерывании процесса.

19.Опишите модель "клиент/сервер".

20.Что такое CORBA?

21.Опишите два способа классификации компьютерных сетей.

22.Укажите и опишите назначение составных частей следующего адреса электронной почты:

kermit@fгод.animals.com

23.Дайте определение следующим понятиям: а) Сервер имен.

б) Домен.

в) Маршрутизатор. г) Узел.

24.Предположим, что адрес узла в Internet задан как 134.48.4.123. Каков будет его 32-битовый адрес в шестнадцатеричном представлении?

25.В чем состоит различие между открытой и закрытой сетью?

26.Дайте определение для каждого из следующих понятий:

а) Гипертекст.

б) HTML.

в) Броузер.

27.Что такое World Wide Web?

28.Укажите компоненты следующего URL-адреса и объясните их значение: http://frogs.animals.com/animals/moviestars/kermit.html.

29.В чем состоит разница между червем и вирусом в контексте компьютерных сетей?

30.Что вызывает беспокойство в отношении безопасности и секретности работы в Internet?

31.Что такое ЕСРА и CALEA?

32*. Объясните назначение команды "проверить и установить", присутствующей во многих машинных языках. Почему важно, чтобы весь процесс "проверки и установки" был реализован в виде одной команды?

33*. Банкир, который имеет всего $ 100 000, дает взаймы по $ 50 000 двум клиентам. Позже оба клиента снова обращаются к нему с уверениями о том, что, прежде чем они смогут вернуть долг, им нужно еще по $ 10 000 для завершения тех сделок, в которых задействованы кредиты. Банкир решает проблему путем заимствования дополнительных сумм у внешнего источника и дает своим клиентам дополнительный кредит (под более высокий процент). Какое из трех условий тупиковой ситуации (ситуации взаимной блокировки) устранил банкир в данном случае?

34*. Студенты, желающие записаться на курс "Моделирование железных дорог" в местном университете, должны получить разрешение от преподавателя и внести плату за работу в лаборатории. Эти два требования могут выполняться независимо и в любом порядке, причем в различных точках студенческого городка. Количество слушателей ограничено 20 студентами. Это ограничение отслеживает как преподаватель, который выдаст разрешение только 20 студентам, так и финансовый отдел, который разрешит внести плату также только 20 студентам. Предположим, что 19 студентов уже зачислены на этот курс, а на последнее место претендуют два студента – один уже получил разрешение от преподавателя, а второй – уже внес плату. Какое условие возникновения тупиковой ситуации устраняется каждым из следующих возможных решений проблемы?

а) Обоим студентам разрешено посещать курс.

б) Группа уменьшена до 19 человек, так что ни одному из студентов не разрешено записаться на курс.

в) Ни одному из двух претендентов не разрешено участвовать в занятиях, а разрешение выдано третьему студенту.

г) Принято решение о том, что единственным требованием для зачисления на курс является внесение платы. Таким образом, студент, уже внесший плату, записывается на курс, а второй получает отказ.

35*. Объясните, как может возникнуть ситуация взаимной блокировки при игре в шахматы, когда пешки вплотную подходят друг к другу. Что выступает здесь в роли неделимого ресурса? Каким образом эта ситуация обычно преодолевается?

36*. Предположим, что неразделяемые ресурсы в компьютерной системе классифицированы как ресурсы первого, второго и третьего уровней. Также предположим, что каждому процессу в системе предписано запрашивать нужные ему ресурсы согласно этой классификации. Сначала он должен запросить все необходимые ему ресурсы первого уровня, прежде чем он сможет запрашивать какой-либо ресурс второго уровня. После того как все требуемые ресурсы первого уровня будут получены, процесс может запросить все необходимые ему ресурсы второго уровня и т.д. Может ли в этой схеме возникнуть ситуация взаимной блокировки и почему?

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

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

39*. Опишите, как можно использовать механизм очереди в процессе спулинга выводимой на принтер информации. 40*. Участок дороги в центре перекрестка можно рассматривать как неделимый ресурс, на который претендуют все

приближающиеся к перекрестку автомобили. Для распределения права доступа к этому ресурсу используется не операцион-

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

41*. По какой причине может зависнуть процесс, если диспетчер всегда выделяет кванты времени согласно системе приоритетов, в которой приоритет каждого процесса остается постоянным? (Подсказка. Какой приоритет у процесса, который только что завершил использование своего кванта времени по сравнению с ожидающими процессами, и, как следствие, какому процессу будет предоставлен следующий квант времени?)

42*. В чем сходство между ситуацией взаимной блокировки и зависанием (см. вопрос 41)? В чем отличие между ними? 43*. Какая проблема возникнет, если в системе с разделением времени размер кванта времени делать все меньше и

меньше? Что будет происходить, если делать эти кванты все больше и больше?

44*. Что представляет собой модель OSI, рекомендованная международным комитетом стандартов (OSI)?

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

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

47*. Опишите действия, выполняемые машиной при необходимости отправить сообщение по сети, работа которой регулируется протоколом CSMA/CD.

48*. Перечислите четыре уровня иерархии программного обеспечения Internet и опишите задачи, выполняемые каждым уровнем.

49*. С какой точки зрения протокол TCP представляется более удачным протоколом транспортного уровня, чем протокол UDP? В чем преимущества протокола UDP?

50*. Что означает утверждение о том, что UDP является протоколом, не устанавливающим соединения?

Ответы на вопросы для самопроверки Раздел 3.1

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

2.Пункты б и в.

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

4.Разделение времени – это метод, с помощью которого многозадачность реализуется на машине с одним процессором.

Раздел 3.2

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

Диспетчер. Контролирует распределение времени центрального процессора между различными процессами.

2.Граница между этими понятиями неясна, и различие часто проводится лишь умозрительно. Грубо говоря, утилиты выполняют основные, универсальные задачи, тогда как прикладное программное обеспечение выполняет задачи, специфические для данного пользователя.

3.Виртуальная память – это воображаемое пространство памяти, которое обеспечивается процессом перемещения (подкачки) данных и программ из памяти на жесткий диск и обратно.

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

Раздел 3.3

1.Программа – это множество команд. Процесс – это действия, выполняемые в соответствии с этими командами.

2.Центральный процессор завершает текущий машинный цикл, сохраняет состояние текущего процесса и устанавливает в счетчике адреса заранее определенное значение (которое является адресом обработчика прерываний). Таким образом, следующая выполняемая команда – это первая команда в обработчике прерываний.

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

4.Каждую секунду машина сможет выделять по одному полному кванту времени 18 процессам.

5.В целом 10/11 машинного времени может быть затрачено на собственно выполнение вычислительных процессов. Ко-

гда процесс запрашивает выполнение операции ввода/вывода данных, выделенный этому процессу квант времени процессо-

ра завершается и процессор приступает к обработке запроса. Таким образом, если каждый процесс будет выдавать запрос на ввод/вывод через 5 миллисекунд после получения кванта времени, эффективность работы машины может снизиться до 1/2. Иными словами, машина будет затрачивать на выполнение необходимых переключений столько же времени, сколько и на выполнение самих процессов.

6. В качестве примеров можно предложить работу компании "Товары – почтой" и обслуживаемых ею клиентов, биржевого брокера и его клиентов или фармацевта и его клиентов.

Раздел 3.4

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

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

3.а) Это гарантирует, что потребности в разделении ресурса не возникнет и он не будет распределяться между многими процессами, т.е. автомобиль получает в свое распоряжение или весь мост или не получает ничего.

б) Это означает, что неделимый ресурс может быть получен принудительно.

в) Это превращает неделимый ресурс в разделяемый, что устраняет всякую конкуренцию.

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

Раздел 3.5

1.Открытая сеть – это сеть с открытыми спецификациями и протоколами, позволяющими различным поставщикам производить совместимые продукты.

2.Маршрутизатор – это компьютер, соединяющий между собой две сети. Точнее, маршрутизатор – это компьютер, соединяющий между собой две сети, использующие один и тот же протокол Internet. Шлюз – это компьютер, соединяющий между собой две сети, которые для работы в Internet используют разные протоколы.

3.Полный адрес узла в Internet состоит из идентификатора сети и адреса узла.

4.Адрес URL – это, в сущности, адрес документа в подсистеме World Wide Web. Броузер – это программа, которая помогает пользователю получить доступ к гипертекстовому документу.

5.Любой разрыв в кольце может нарушить связь. Если же сообщение можно передавать в обоих направлениях, то один разрыв в кольце может и не повредить связь.

Раздел 3.6

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

2.В отличие от протокола TCP, UDP – это протокол без обратной связи, который не подтверждает получения сообщения адресатом.

3.Каждому сообщению присваивается счетчик переходов по сети, который определяет максимальное число выполнения передачи сообщения между компьютерами.

4.Фактически ничего. На любом компьютере в Internet программист может так модифицировать программное обеспечение, чтобы этот компьютер мог сохранять такие записи. Вот почему конфиденциальные данные следует шифровать.

Раздел 3.7

1.Использование паролей защищает данные (а значит, и информацию). Использование шифрования защищает только информацию.

2.В контексте нашего изложения ЕСРА определяет права собственности, имеющие отношение к электронным средствам связи.

3.Если соответствие закону технически невозможно, то этот закон не будет (не может) выполняться. Требования CALEA как технически, так и финансово трудновыполнимы. Это означает, что соответствие закону является проблематичным.

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

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

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

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

Вопросы для самопроверки

1.Охарактеризуйте различия между процессом, алгоритмом и программой.

2.Приведите примеры алгоритмов, с которыми вы знакомы. Действительно лиониявляются алгоритмамив строгом смысле этогослова?

3.Укажите элементы неопределенности в том неформальном определении алгоритма, которое было предложено в начале этогораздела.

4.Каким пунктам в определении алгоритма не соответствует приведенная ниже последовательность инструкций? Этап 1. Возьмитемонетуизвашегокарманаиположите еенастол.

Этап 2. Возвратитесь к этапу 1.

4.2.ПРЕДСТАВЛЕНИЕ АЛГОРИТМА

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

Вкомпьютерных науках эти проблемы решают путем создания четко определенного набора составных блоков, из которых могут конструироваться представления алгоритмов. Такие блоки называются примитивами (primiteve). То, что примитивам даются точные определения, устраняет многие проблемы неоднозначности и одновременно требует одинакового уровня детализации для всех описываемых с их помощью алгоритмов. Набор примитивов вместе с набором правил, устанавливающих, как эти примитивы могут комбинироваться для представления более сложных идей, образуют язык программирования. Каждый примитив состоит из двух частей: синтаксической и семантической. Синтаксис относится к символьному представлению примитива, а семантика – к представляемой концепции, т.е. к значению примитива. Например, синтаксис слова "воздух" включает шесть соответствующих символов, тогда как семантически – это окружающая нас газовая субстанция.

Вкачестве примера на рис. 4.3 представлены некоторые примитивы, используемые в искусстве оригами.

Рис. 4.2. Сложение птицы из квадратного листа бумаги

Рис. 4.3. Примитивы, используемые в оригами

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