лекции СПО

о нез вершенных опер циях ввод -вывод , коды оши ок выполняемых д нным потоком системных вызовов и т. д.

з пуск ново о поток н выполнение.

Поскольку опер ция переключения контекстов существенно влияет н

производительность вычислительной системы, про р ммные модули ОС

выполняют диспетчериз цию потоков совместно с пп р тными средств ми процессор .

д нному потоку (содержимое ре истров, счетчик ком нд, режим процессор ).

контексты, дост точно лишь з менить контексты потоков, которые имеют меньший о ъем. Ан ло ично при переключении с поток одной руппы н поток дру ой руппы в предел х одно о процесс ло льный контекст не изменяется, изменяется лишь контекст руппы. Переключение же ло льных контекстов происходит только при переходе с поток одно о процесс н поток дру о о процесс .

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

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

трех основных состояний:

выполнение — ктивное состояние поток , во время которо о поток

о л д ет всеми нео ходимыми ресурс ми и непосредственно выполняется процессором;

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

отовность — т кже п ссивное состояние поток , но в этом случ е поток з локиров н в связи с внешним по отношению к нему о стоятельством (имеет

все тре уемые для не о ресурсы, отов выполняться, одн ко процессор з нят выполнением дру о о поток ).

В течение своей жизни к ждый поток переходит из одно о состояния в дру ое в соответствии с л оритмом пл ниров ния потоков, принятым в д нной

опер ционной системе.

Р ссмотрим типичный р ф состояния поток (рис. 4.3). Только что созд нный поток н ходится в состоянии отовности, он отов к выполнению и.

стоит в очереди к процессору. Ко д в результ те пл ниров ния подсистем

упр вления поток ми приним ет решение о ктивиз ции д нно о поток , он

соответственно ожид ющих и отовых потоков. Очереди потоков ор низуются

путем о ъединения в списки опис телей отдельных потоков. Т ким о р зом,

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

ор низ ция очередей позволяет ле ко их переупорядочив ть, включ ть и

исключ ть потоки, переводить потоки из одно о состояния в дру ое. Если предположить, что н рис. 4.4 пок з н очередь отовых потоков, то з пл ниров нный порядок выполнения вы лядит т к: А, В, Е, D, С.

Рис. 4.4. Очередь потоков

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

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

потоков. При вытесняющем мультипро р ммиров нии функции пл ниров ния потоков целиком сосредоточены в опер ционной системе и про р ммист пишет

Прикл дн я про р мм , получив упр вление от опер ционной системы, с м

определяет момент з вершения очередно о цикл свое о выполнения и только

з тем перед ет упр вление ОС с помощью к ко о-ли о системно о вызов . ОС формирует очереди потоков и вы ир ет в соответствии с некоторым пр вилом

н пример н текстовый ред ктор, в то время к к форм тиров ние продолж лось

отформ тиров ть одну дорожку дискеты и вернуть упр вление системе. После

выполнения дру их з д ч систем возвр тит упр вление про р мме

форм тиров ния, что ы т отформ тиров л следующую дорожку. Подо ный

предусмотрены ч стые перед чи упр вления опер ционной системе. Кр йним

проявлением «не дружественности» приложения является е о з вис ние,

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

центр льный пл нирующий мех низм имеет возможность снять з висшую

з д чу с выполнения.

Одн ко р спределение функций пл ниров ния потоков между системой

с м определяет в про р мме момент возвр щения упр вления, то при этом исключ ются нер цион льные прерыв ния про р мм в «неудо ные» для них моменты времени. Кроме то о, ле ко р зреш ются про лемы совместно о использов ния д нных: з д ч во время к ждо о цикл выполнения использует

Почти во всех современных опер ционных систем х, ориентиров нных

нвысокопроизводительное выполнение приложений (UNIX, Windows

NT/2000, OS/2, VAX/VMS), ре лизов ны вытесняющие л оритмы

пл ниров ния потоков (процессов). В последнее время дошл очередь и до ОС кл сс н стольных систем, н пример OS/2 Warp и Windows 95/98.

5.8 Алгоритмы планирования, основанные на квантовании

В основе мно их вытесняющих л оритмов пл ниров ния лежит концепция кв нтов ния. В соответствии с этой концепцией к ждому потоку

поток перешел в состояние ожид ния;

исчерп н кв нт процессорно о времени, отведенный д нному потоку.

Поток, который исчерп л свой кв нт, переводится в состояние

Рис. 4.6. Гр ф состояний поток в системе с кв нтов нием

Кв нты, выделяемые поток м, мо ут ыть один ковыми для всех потоков или р зличными. Р ссмотрим, н пример, случ й, ко д всем поток м

предост вляются кв нты один ковой длины q (рис. 4.7). Если в системе имеется п потоков, то время, которое поток проводит в ожид нии следующе о кв нт ,

Рис. 4.7. ллюстр ция р счет времени ожид ния в очереди Если кв нт короткий, то сумм рное время, которое проводит поток в

ожид нии процессор , прямо пропорцион льно времени, тре уемому для е о выполнения (то есть времени, которое потре ов лось ы для выполнения это о

поток при монопольном использов нии вычислительной системы).

Действительно, поскольку время ожид ния между двумя цикл ми выполнения р вно q(n-l), количество циклов B/q, де В — тре уемое время выполнения, то

этом не учитыв ется, что потоки мо ут использов ть кв нты не полностью, что ч сть времени они мо ут тр тить н ввод-вывод, что количество потоков в

системе может дин мически меняться и т. д.

Чем ольше кв нт, тем выше вероятность то о, что потоки з верш тся в результ те перво о же цикл выполнения, и тем менее явной ст новится

з висимость времени ожид ния потоков от их времени выполнения. При

дост точно ольшом кв нте л оритм кв нтов ния вырожд ется в л оритм последов тельной о р отки, присущий однопро р ммным систем м, при

котором время ожид ния з д чи в очереди воо ще ник к не з висит от ее длительности.

з р нее з д нной величины. В т ком случ е преимущество получ ют короткие

з д чи, которые успев ют выполняться в течение перво о кв нт , длительные

вычисления удут проводиться в фоновом режиме. Можно предст вить се е

л оритм пл ниров ния, в котором к ждый следующий кв нт, выделяемый

определенному потоку, ольше предыдуще о. Т кой подход позволяет

уменьшить н кл дные р сходы н переключение з д ч в том случ е, ко д

ср зу несколько з д ч выполняют длительные вычисления.

Потоки получ ют для выполнения кв нт времени, но некоторые из них используют е о не полностью, н пример из-з нео ходимости выполнить ввод или вывод д нных. В результ те возник ет ситу ция, ко д потоки с

интенсивными о р щениями к вводу-выводу используют только не ольшую ч сть выделенно о им процессорно о времени. Ал оритм пл ниров ния может

последующем о служив нии. Для это о пл нировщик созд ет две очереди

отовых потоков (рис. 4.8). Очередь 1 о р зов н поток ми, которые пришли в состояние отовности в результ те исчерп ния кв нт времени, очередь 2 —

поток ми, у которых з вершил сь опер ция ввод -вывод . При вы оре поток для выполнения прежде все о просм трив ется втор я очередь, и только если

Рис. 4.8. Кв нтов ние с предпочтением потоков, интенсивно о р щ ющихся к

вводу-выводу

5.9 Алгоритмы планирования, основанные на приоритетах

Дру ой в жной концепцией, леж щей в основе мно их вытесняющих

ресурсов вычислительной м шины, в ч стности процессорно о времени: чем выше приоритет, тем выше привиле ии, тем меньше времени удет проводить поток в очередях.

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

Вольшинстве опер ционных систем, поддержив ющих потоки,

приоритет поток непосредственно связ н с приоритетом процесс , в р мк х