Системное программное обеспечение

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

Итак, мультипрограммирование более эффективно на уровне потоков, а не процессов. Каждый поток имеет собственный счетчик  команд и стек. Задача, оформленная  в виде нескольких потоков в рамках одного процесса, может быть выполнена  быстрее за счет псевдопараллельного (или параллельного в мультипроцессорной системе) выполнения ее отдельных частей.

Введение  нескольких потоков выполнения упрощает программирование. Например, в задачах  типа «писатель-читатель» один поток  выполняет запись в буфер, а другой считывает записи из него. Поскольку  они разделяют общий буфер, не стоит их делать отдельными процессами. Другой пример использования потоков  — управление сигналами, такими как  прерывание с клавиатуры (del или break). Вместо обработки сигнала прерывания один поток назначается для постоянного ожидания поступления сигналов. Таким образом, использование потоков может сократить необходимость в прерываниях пользовательского уровня. В этих примерах не столь важно параллельное выполнение, сколь важна ясность программы.

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

Состояния потока

  ОС выполняет планирование потоков, принимая во внимание их состояние. В мультипрограммной системе поток может находиться в одном из трех основных состояний:

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

 ожидание — пассивное состояние  потока, находясь в котором, поток  заблокирован по своим внутренним  причинам (ждет осуществления некоторого  события, например завершения  операции ввода-вывода, получения  сообщения от другого потока  или освобождения какого-либо  необходимого ему ресурса);

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

Контекст и дескриптор процесса

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

  Кроме этого, операционной системе для реализации планирования процессов требуется дополнительная информация: идентификатор процесса, состояние процесса, данные о степени привилегированности процесса, место нахождения кодового сегмента и другая информация. В некоторых ОС (например, в ОС UNIX) информацию такого рода, используемую ОС для планирования процессов, называют дескриптором процесса.

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

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

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

создать информационные структуры, описывающие  данный процесс, то есть его дескриптор и контекст;

включить дескриптор нового процесса в очередь готовых процессов;

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

5. Синхронизация процессов и потоков. Критическая секция. Алгоритм доступа к критической секции с помощью блокирующей переменной.  Синхронизация процессов и потоков: цели и средства синхронизации

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

Во многих операционных системах эти  средства называются средствами межпроцессного взаимодействия — Inter Process Communications (IPC), что отражает историческую первичность понятия «процесс» по отношению к понятию «поток».

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

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

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

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

Ежесекундно в системе происходят сотни событий, связанных с распределением и освобождением ресурсов, и ОС должна иметь надежные и производительные средства, которые бы позволяли ей синхронизировать потоки с происходящими  в системе событиями.

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

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

Критическая секция

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

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

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

 Блокирующие переменные

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

6. Вытесняющие алгоритмы планирования процессов и потоков. Вытесняющие и невытесняющие алгоритмы планирования

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

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

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

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