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

Задачи:

1. Определение момента времени для смены процесса (решается программным способом)

2. Выбор процесса на выполнение из очереди готовых процессов (решается программным способом).

3. Переключение контекстов для старого и нового процессов (решается операторным способом).

Алгоритмы, основанные на:

Ø Квантовании: смена активного процесса происходит в случае, если:

Процесс завершился

Произошла ошибка

Процесс перешел в состояние ожидания

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

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

Алгоритмы, использующие:

§ Абсолютный приоритет (ОС может прервать выполнение процесса, выбрав другой)

§ Относительный приоритет (процесс будет выполняться до конца)

На выполнение будет выбираться процесс с наивысшим приоритетом.

Планирование:

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

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

Алгоритм RR:

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

Ситуация:

1) Время непрерывного использования процессора, необходимое процессу, меньшее кванту времени. Тогда про­цесс сам освободит процессор.

2) Продолжительность больше кванта времени. Процесс прервется.

где и – использование, г – готовность

Время ожидания Р0 – 5 единиц

Р1 – 4 единицы

Р2 – 8 единиц

Среднее время ожидания – 5,6 единиц

Полное время выполнения для Р0 – 18 единиц

Р1 – 8 единиц

Р2 – 9 единиц

Среднее время выполнения 11, 6 единиц

Если величина кванта времени взять в 1, то

Р0 – 5

Р1 – 5

Р2 –2

Среднее время – 4 единицы, среднее время исполнения – 10 единиц.

Если большой квант времени, процессы выполняются полностью.

Вопрос 10: Алгоритмы планирования процессов. SJF.

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

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

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

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

Примером эффективного использования невытесняющей многозадачности является файл-сервер NetWare, в ко­тором, в значительной степени благодаря этому, достигнута высокая скорость выполнения файловых операций. Менее удачным оказалось использование невытесняющей многозадачности в операционной среде Windows 3.х.

Однако почти во всех современных операционных системах, ориентированных на высокопроизводительное выполнение приложений (UNIX, Windows NT, OS/2, VAX/VMS), реализована вытесняющая многозадачность. В послед­нее время дошла очередь и до ОС класса настольных систем, например, OS/2 Warp и Windows 95. Возможно в связи с этим вытесняющую многозадачность часто называют истинной многозадачностью.

Алгоритм SJF (кратная работа первого)

Пример невытесняющего алгоритма

Р0 Р1 Р2 Р3

5 3 7 1

Порядок: Р3, Р1, Р0, Р2.

Среднее время ожидания 3, 5 единиц. Если Р0, Р1, Р2, Р3 FIFO – 7 единиц. Выигрыш в два раза.

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

Вопрос 11: Управление процессами. Синхронизация процессов. Семафоры.

Управление процессами.

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

В многозадачной (многопроцессорной) системе процесс может находиться в одном из трех основных состоя­ний:

ВЫПОЛНЕНИЕ - активное состояние процесса, во время которого процесс обладает всеми необходимыми ре­сурсами и непосредственно выполняется процессором;

ОЖИДАНИЕ - пассивное состояние процесса, процесс заблокирован, он не может выполняться по своим внут­ренним причинам, он ждет осуществления некоторого события, например, завершения операции ввода-вывода, получе­ния сообщения от другого процесса, освобождения какого-либо необходимого ему ресурса;

ГОТОВНОСТЬ - также пассивное состояние процесса, но в этом случае процесс заблокирован в связи с внеш­ними по отношению к нему обстоятельствами: процесс имеет все требуемые для него ресурсы, он готов выполняться, однако процессор занят выполнением другого процесса.

В ходе жизненного цикла каждый процесс переходит из одного состояния в другое в соответствии с алгорит­мом планирования процессов, реализуемым в данной операционной системе. В состоянии ВЫПОЛНЕНИЕ в однопро­цессорной системе может находиться только один процесс, а в каждом из состояний ОЖИДАНИЕ и ГОТОВНОСТЬ - несколько процессов, эти процессы образуют очереди соответственно ожидающих и готовых процессов. Жизненный цикл процесса начинается с состояния ГОТОВНОСТЬ, когда процесс готов к выполнению и ждет своей очереди. При активизации процесс переходит в состояние ВЫПОЛНЕНИЕ и находится в нем до тех пор, пока либо он сам освободит процессор, перейдя в состояние ОЖИДАНИЯ какого-нибудь события, либо будет насильно "вытеснен" из процессора, например, вследствие исчерпания отведенного данному процессу кванта процессорного времени. В последнем случае процесс возвращается в состояние ГОТОВНОСТЬ. В это же состояние процесс переходит из состояния ОЖИДАНИЕ, после того, как ожидаемое событие произойдет.

Синхронизация процессов. Семафоры.

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

Пренебрежение вопросами синхронизации процессов, выполняющихся в режиме мультипрограммирования, может привести к их неправильной работе или даже к краху системы. Рассмотрим программу печати файлов (принт-сервер). Эта программа печатает по очереди все файлы, имена которых последовательно в порядке поступления записы­вают в специальный общедоступный файл "заказов" другие программы. Особая переменная NEXT, также доступная всем процессам-клиентам, содержит номер первой свободной для записи имени файла позиции файла "заказов". Про­цессы-клиенты читают эту переменную, записывают в соответствующую позицию файла "заказов" имя своего файла и наращивают значение NEXT на единицу. Предположим, что в некоторый момент процесс R решил распечатать свой файл, для этого он прочитал значение переменной NEXT, значение которой для определенности предположим равным 4. Процесс запомнил это значение, но поместить имя файла не успел, так как его выполнение было прервано (например, в следствие исчерпания кванта). Очередной процесс S, желающий распечатать файл, прочитал то же самое значение переменной NEXT, поместил в четвертую позицию имя своего файла и нарастил значение переменной на единицу. Ко­гда в очередной раз управление будет передано процессу R, то он, продолжая свое выполнение, в полном соответствии со значением текущей свободной позиции, полученным во время предыдущей итерации, запишет имя файла также в позицию 4, поверх имени файла процесса S.

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

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

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

Другим способом является использование блокирующих переменных. С каждым разделяемым ресурсом связы­вается двоичная переменная, которая принимает значение 1, если ресурс свободен (то есть ни один процесс не нахо­дится в данный момент в критической секции, связанной с данным процессом), и значение 0, если ресурс занят. На ри­сунке 2.4 показан фрагмент алгоритма процесса, использующего для реализации взаимного исключения доступа к раз­деляемому ресурсу D блокирующую переменную F(D). Перед входом в критическую секцию процесс проверяет, свобо­ден ли ресурс D. Если он занят, то проверка циклически повторяется, если свободен, то значение переменной F(D) уста­навливается в 0, и процесс входит в критическую секцию. После того, как процесс выполнит все действия с разделяе­мым ресурсом D, значение переменной F(D) снова устанавливается равным 1.

Если все процессы написаны с использованием вышеописанных соглашений, то взаимное исключение гаран­тируется. Следует заметить, что операция проверки и установки блокирующей переменной должна быть неделимой. Поясним это. Пусть в результате проверки переменной процесс определил, что ресурс свободен, но сразу после этого, не успев установить переменную в 0, был прерван. За время его приостановки другой процесс занял ресурс, вошел в свою критическую секцию, но также был прерван, не завершив работы с разделяемым ресурсом. Когда управление было воз­вращено первому процессу, он, считая ресурс свободным, установил признак занятости и начал выполнять свою крити­ческую секцию. Таким образом был нарушен принцип взаимного исключения, что потенциально может привести к не­желаемым последствиям. Во избежание таких ситуаций в системе команд машины желательно иметь единую команду "проверка-установка", или же реализовывать системными средствами соответствующие программные примитивы, кото­рые бы запрещали прерывания на протяжении всей операции проверки и установки.

Реализация критических секций с использованием блокирующих переменных имеет существенный недостаток: в течение времени, когда один процесс находится в критической секции, другой процесс, которому требуется тот же ресурс, будет выполнять рутинные действия по опросу блокирующей переменной, бесполезно тратя процессорное время. Для устранения таких ситуаций может быть использован так называемый аппарат событий. С помощью этого средства могут решаться не только проблемы взаимного исключения, но и более общие задачи синхронизации процес­сов. В разных операционных системах аппарат событий реализуется по своему, но в любом случае используются сис­темные функции аналогичного назначения, которые условно назовем WAIT(x) и POST(x), где x - идентификатор неко­торого события. Если ресурс занят, то процесс не выполняет циклический опрос, а вызывает системную функцию WAIT(D), здесь D обозначает событие, заключающееся в освобождении ресурса D. Функция WAIT(D) переводит актив­ный процесс в состояние ОЖИДАНИЕ и делает отметку в его дескрипторе о том, что процесс ожидает события D. Про­цесс, который в это время использует ресурс D, после выхода из критической секции выполняет системную функцию POST(D), в результате чего операционная система просматривает очередь ожидающих процессов и переводит процесс, ожидающий события D, в состояние ГОТОВНОСТЬ.

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

V(S): переменная S увеличивается на 1 одним неделимым действием; выборка, инкремент и запоминание не могут быть прерваны, и к S нет доступа другим процессам во время выполнения этой операции.

P(S): уменьшение S на 1, если это возможно. Если S=0, то невозможно уменьшить S и остаться в области целых неотрицательных значений, в этом случае процесс, вызывающий P-операцию, ждет, пока это уменьшение станет воз­можным. Успешная проверка и уменьшение также является неделимой операцией.

В частном случае, когда семафор S может принимать только значения 0 и 1, он превращается в блокирующую переменную. Операция P заключает в себе потенциальную возможность перехода процесса, который ее выполняет, в состояние ожидания, в то время как V-операция может при некоторых обстоятельствах активизировать другой процесс, приостановленный операцией P (сравните эти операции с системными функциями WAIT и POST).

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

Введем два семафора: e - число пустых буферов и f - число заполненных буферов. Предположим, что запись в буфер и считывание из буфера являются критическими секциями (как в примере с принт-сервером в начале данного раздела). Введем также двоичный семафор b, используемый для обеспечения взаимного исключения. Тогда процессы могут быть описаны следующим образом:

// Глобальные переменные

#define N 256

int e = N, f = 0, b = 1;

void Writer ()

{while(1)

{

PrepareNextRecord(); /* подготовка новой записи */

P(e); /* Уменьшить число свободных буферов, если они есть */

/* в противном случае - ждать, пока они освободятся */

P(b); /* Вход в критическую секцию */

AddToBuffer(); /* Добавить новую запись в буфер */

V(b); /* Выход из критической секции */

V(f); /* Увеличить число занятых буферов */

}

}

void Reader ()

{

while(1)

{

P(f); /* Уменьшить число занятых буферов, если они есть */

/* в противном случае ждать, пока они появятся */

P(b); /* Вход в критическую секцию */

GetFromBuffer(); /* Взять запись из буфера */

V(b); /* Выход из критической секции */

V(e); /* Увеличить число свободных буферов */

ProcessRecord(); /* Обработать запись */

}

}

Вопрос 12: Управление процессами. Сообщения. Тупики. Способы борьбы с тупи­ками.

Тупики. Способы борьбы с тупиками.

Еще одна проблема синхронизации - взаимные блокировки, называемые также дедлоками (deadlocks), клинчами (clinch) или тупиками. Рассмотрим пример тупика. Пусть двум процессам, выполняющимся в режиме мультипрограммирова­ния, для выполнения их работы нужно два ресурса, например, принтер и диск. И пусть после того, как процесс А занял принтер (установил блокирующую переменную), он был прерван. Управление получил процесс В, который сначала занял диск, но при выполнении следующей команды был заблокирован, так как принтер оказался уже занятым процессом А. Управление снова получил процесс А, который в соответствии со своей программой сделал попытку занять диск и был заблокирован: диск уже распределен процессу В. В таком положении процессы А и В могут находиться сколь угодно долго.

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

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

Проблема тупиков включает в себя следующие задачи:

· предотвращение тупиков,

· распознавание тупиков,

· восстановление системы после тупиков.

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

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

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

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

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

Нити

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

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

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

Для этих целей современные ОС предлагают использовать сравнительно новый механизм многонитевой обработки (multithreading). При этом вводится новое понятие "нить" (thread), а понятие "процесс" в значительной степени меняет смысл.

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

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

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

Нити иногда называют облегченными процессами или мини-процессами. Действительно, нити во многих отношениях подобны процессам. Каждая нить выполняется строго последовательно и имеет свой собственный программный счетчик и стек. Нити, как и процессы, могут, например, порождать нити-потомки, могут переходить из состояния в состояние. Подобно тради­ционным процессам (то есть процессам, состоящим из одной нити), нити могут находится в одном из следующих состояний: ВЫПОЛНЕНИЕ, ОЖИДАНИЕ и ГОТОВНОСТЬ. Пока одна нить заблокирована, другая нить того же процесса может выпол­няться. Нити разделяют процессор так, как это делают процессы, в соответствии с различными вариантами планирования.

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

Итак, нити имеют собственные:

· программный счетчик,

· стек,

· регистры,

· нити-потомки,

· состояние.

Нити разделяют:

· адресное пространство,

· глобальные переменные,

· открытые файлы,

· таймеры,

· семафоры,

· статистическую информацию.

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

Широкое применение находит многонитевая обработка в распределенных системах. Смотрите об этом в разделе "Процессы и нити в распределенных системах".

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

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

Вопрос 13: Условия возникновения тупиков. Основные направления борьбы с тупиками