работа ( по дисциплине “Организация ЭВМ и вычислительных систем”) «Операционные системы реального времени» (стр. 2 из 3)

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

Методы диспетчеризации потоков

· FIFO ( First In First Out) — Первый Вошел — Первый вышел. Сначала выполняется задача, которая первой вошла в очередь. Она выполняется пока не будет выполнена, либо пока не будет заблокирована в ожидании ресурса или какого-то события. После этого управления передается другой задаче в очереди. Такой механизм применяется, если у задач одинаковый приоритет.

· Карусельная многозадачность (round robin). В этом методе диспетчеризации задается константа — квант времени (time slice). Выполнение потока завершается либо при окончании его выполнения, либо при блокировании его в ожидании ресурса, либо при окончании кванта времени. После этого управление передается следующему потоку в очереди. По окончании выполнения последнего потока управление передается первому потоку, находящемуся в состоянии готовности. Т.е. Выполнение каждого потока разбито на последовательность временных циклов. Этот метод присущ для потоков с разным приоритетом.

Как происходит передача управления между потоками с разными приоритетами?

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

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

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

Диспетчирезация потоков в QNX.

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

В 1970 году Лиу и Лейленд предложили математический аппарат «Частотно монотонный анализ» для проверки систем на то, является ли она диспетчируемой, аппарат был принят в качестве стандарта такими организациями как USA Mitre, NASA, Boeing и др.

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

Механизмы синхронизации

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

Микроядро

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

Практическая часть

Установка QNX

QNX стоит сразу устанавливать на виртуальную машину. Версия для некоммерческого использования доступна для скачивания на веб-сайте разработчика www.qnx.com. При установке на VirtualBox у меня возникли проблемы, QNX не устанавливался скорее всего по причине отсутствия поддержки процессором виртуализации. Поэтому следующая попытка была поставить QNX на VMware Workstation. Там почти все заработало, но были проблемы с сетью. Установить QNX очень просто, установка заключается практически лишь только в выборе раздела для установки. Устанавливать QNX на жесткий диск в качестве полноценной ОС для работы не имеет смысла. Для разработки программного обеспечения, которое нуждается в реальном времени ( будет работать под управлением QNX) можно использовать модификацию IDE Eclipse — QNX Momentics, или же работать с QNX посредством, используя виртуализацию( Parallels, VMware, VirtualBox XEN). Следует с осторожностью подходить к выбору аппаратного обеспечения для работы проектов под управлением QNX, так для многого оборудования отсутствуют драйвера.

Тест на инверсию приоритетов

Код программы, написанном на С/С++:

#include <stdlib.h>

#include <stdio.h>

#include <iostream.h>

#include <string.h>

#include <unistd.h>

#include <pthread.h>

#include <semaphore.h>

const int THRNUM = 3, NCKL = 10, LINOUT = 5, BUFLEN = THRNUM * NCKL + 1;

inline void workfun( int n ) {

for( long i = 0; i < n; i++ ) double f = sqrt( 1. + sqrt( (double) rand() ) );

};

char buf[ BUFLEN ];

volatile unsigned ind = 0, nfin = 0;

long nrep = 1000;

bool bmutex = false, bsemaphore = false;

static pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;

static sem_t semaphore, semfinal;

void *thrfunc( void *p ) {

int t = (int)p;

if( t != 1 ) {

if( bmutex ) pthread_mutex_lock( &mutex );

if( bsemaphore ) sem_wait( &semaphore );

};

struct timespec tv;

tv.tv_sec = 0;

tv.tv_nsec =(long)( 1e+6 );

sem_trywait( &semfinal );

nanosleep( &tv, &tv );

for( int i = 0; i < NCKL; i++ ) {

buf[ ind++ ] = t + '0';

workfun( nrep );

};

if( t != 1 ) {

if( bmutex ) pthread_mutex_unlock( &mutex );

if( bsemaphore ) sem_post( &semaphore );

};

if( ++nfin == THRNUM ) sem_post( &semfinal );

};

int main( int argc, char *argv[] ) {

cout << "inverse test, QNX API, vers.1.05L" << endl;

int c = 0;

while( ( c = getopt( argc, argv, "hmst:" ) ) != -1 )

switch( c ) {

case 'h':

cout << "&bsol;t" << argv[ 0 ] << " [ h | { m | s } | t = value ]" << endl;

exit( EXIT_SUCCESS );

case 'm': bmutex = true; break;

case 's': bsemaphore = true; break;

case 't':

nrep = 1;

for( int i = 0; i < atoi( optarg ); i++ ) nrep *= 10;

break;

default: exit( EXIT_FAILURE );

};

sem_init( &semaphore, 0, 1 );

cout << "repeating number = " << nrep; // << ", debug level = " << ndebug;

if( bmutex ) cout << ", lock on mutex";

if( bsemaphore ) cout << ", lock on semaphore";

cout << endl;

struct sched_param param;

int polisy;

pthread_getschedparam( pthread_self(), &polisy, &param );

pthread_attr_t attr;

for( int i = 0; i < THRNUM; i++ ) {

pthread_attr_init( &attr );

pthread_attr_setdetachstate( &attr, PTHREAD_CREATE_DETACHED );

pthread_attr_setinheritsched( &attr, PTHREAD_EXPLICIT_SCHED );

pthread_attr_setschedpolicy( &attr, SCHED_RR );

attr.param.sched_priority = param.sched_priority + i + 1;

pthread_create( NULL, &attr, &thrfunc, (void*)i );

};

sem_init( &semfinal, 0, 0 );

sem_wait( &semfinal );

buf[ ind ] = '&bsol;0';

cout << buf << endl;

exit( EXIT_SUCCESS );

};

Скомпилируем и запустим его на QNX. Вот вывод программы:

repeating number = 100000, debug level = 1

2[13:13] 2[13:13] 2[13:13] 2[13:13] 2[13:13]

2[13:13] 2[13:13] 2[13:13] 2[13:13] 2[13:13]

1[12:12] 1[12:12] 1[12:12] 1[12:12] 1[12:12]

1[12:12] 1[12:12] 1[12:12] 1[12:12] 1[12:12]

0[11:11] 0[11:11] 0[11:11] 0[11:11] 0[11:11]

0[11:11] 0[11:11] 0[11:11] 0[11:11] 0[11:11]

repeating number = 100000, debug level = 1, lock on mutex

0[11:13] 0[11:13] 0[11:13] 0[11:13] 0[11:13]

0[11:13] 0[11:13] 0[11:13] 0[11:13] 0[11:13]