6. 4 Разделение времени. Многозадачность



Скачать 137.54 Kb.
Дата18.02.2013
Размер137.54 Kb.
ТипДокументы


6.4 Разделение времени. Многозадачность

Резидентные программы вводят в DOS элемент многозадачности. Действительно, резидентную программу можно рассматривать как отдельный процесс, который возникает по внешнему событию (прерыванию) и поэтому выполняется асинхронно по отношению к основной программе. Естественно, что прерываемая программа функционирует как основной процесс. Следующим шагом является введение такой системы управления, в которой группа процессов является равноправной, причем каждый из них выполняется с собственной скоростью, зависящей в частности, от его взаимодействия с внешними объектами и другими процессами. Такая модель носит название МОДЕЛЬ АСИНХРОННЫХ ПАРАЛЛЕЛЬНЫХ ПРОЦЕССОВ, а режим работы операционной системы, в котором она осуществляется, называется, соответственно, РАЗДЕЛЕНИЕМ ВРЕМЕНИ.

Переключение процессов. Состояние процесса

Понятие независимых (асинхронных) процессов тесно связано с понятие ПЕРЕКЛЮЧЕНИЯ и СОСТОЯНИЯ. Состоянием процесса называется совокупность данных, которая позволяет в любой момент времени “свернуть” выполнение процесса, а затем возобновить его так, что результат его работы не изменится. То есть такая приостановка выполнения процесса обладает свойством ПРОЗРАЧНОСТИ. Переключением процессов называется “свертка” состояния одного процесса и восстановление состояния другого. Очевидно, в системе должна быть программная компонента, которая периодически вызывает переключение процессов и реализует, таким образом, их псевдо-параллельное протекание в режиме РАЗДЕЛЕНИЯ ВРЕМЕНИ. Такая компонента обычно называется ДИСПЕТЧЕРОМ.

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

Модель системы процессов, работающих в разделении времени

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

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

// Дескриптор процесса -------------------------------------

struct PROCESS

{

unsigned SS,SP; // Указатель стека процесса

char *PS; // Область стека процесса

unsigned STATUS; // Слово состояния процесса

unsigned DELAY; // Тайм - аут

}

TASK[NT], // Массив дескрипторов процессов

*PT; // Указатель на дескриптор текущего процесса

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

-АКТИВЕН - в данный момент выполняется (или прерван),

-ГОТОВ - может быть выполнен;

-БЛОКИРОВАН - не может быть выполнен по каким-либо внешним причинам.

На активный процесс в модели ссылается указатель PT. В слове состояния процесса STATUS определяются биты блокировки, каждый из которых отмечает одну из причин блокировки. Их отсутствие определяет состояние готовности процесса к выполнению.
// Биты блокировки процесса ---------------------------

#define TWAIT 1 // Тайм - аут процесса

#define IO 2 // Ввод - вывод

#define MESS 4 // Ожидание сообщения

#define SEM 8 // Семафор

#define OFF 16 // Не активен
Идея переключения процессов реализована в обработчике прерываний по таймеру. В момент прерывания (которое происходит 18.2 раз в секунду) он запоминает указатель стека текущего процесса, после чего ищет, начиная с процесса, следующего за текущим, активный процесс. Если таковой найден, то он устанавливает его указатель стека и таким образом переключается на его запомненное состояние в момент предыдущего прерывания. При выходе из прерывания процесс уже будет восстановлен "физически", то есть продолжит свое выполнение с точки прерывания.
// Обработчик прерывания по таймеру ------------------------------

void interrupt TIMER(bp,di,si,ds,es,dx,cx,bx,ax,ip,cs,flgs)

{

static int n;

//----- Запоминание состояния задачи ----------------------

(*OLDTIM)(); // Старый обработчик прерывания

if (DISP) return; // Диспетчер занят - переключение невозможно

DISP++; // Занять диспетчер - защита от повторного входа

PT->SP = _SP; // Сохранить текущий указатель стека

PT->SS = _SS;

//----- Поиск готового процесса --------------------------

if (RUN) {DISP--; return; }

for (CT++,n=0; n < NT; n++,CT++)

{ // Поиск “по кругу” от текущего процесса

CT %= NT; // Выбирается готовый - без битов блокировок

if (TASK[CT].STATUS ==0) break;

}

//----- Отсутствие готовых процессов ---------------------------

if (n == NT) printf("a-a-a-a-a-a-a-a");

//----- Восстановление состояния нового процесса------------

PT = TASK + CT; // Указатель на новый активный процесс

_SS = PT->SS; // Установить стек процесса

_SP = PT->SP;

DISP--;

} // Выйти из прерывания через стек нового

// процесса - переключиться на новый

Обработчик прерывания от таймера выполняет функции ДИСПЕТЧЕРА параллельных процессов. Поскольку в работе системы могут возникнуть ситуации, когда переключение процессов запрещено, и, наоборот, при работе диспетчера следует защититься от выполнения некоторых действий, которые могут быть связаны с изменением данных в дескрипторах процессов, то в программу вводятся переменные RUN, запрещающая переключение задач, и DISP, индицирующая, что в данный момент работает диспетчер.

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

Функция FORK ищет "выключенный" процесс в массиве дескрипторов, (блокированный в состоянии OFF), создает динамический массив для размещения его стека, после чего устанавливает на него указатели стека и заполняет его текущее состояние. Для этого используется определение структурированной переменной STACK, последовательность элементов в которой соответствует последовательности запоминания переменных в стеке функцией обработки прерывания типа void interrupt.
// Стек функции обработки прерывания ------------------

struct STACK

{ unsigned bp,di,si,ds,es,dx,cx,bx,ax,ip,cs,flgs; };

//--------------------------------------------------------

// Запуск процесса в режиме разделения времени

// Возвращает номер процесса

int FORK(void (*pf)())

{

int nt,n;

struct STACK *sp;

RUN++; // Запретить переключение процессов

for (nt=-1,n=0; n < NT; n++) // Искать свободный дескриптор

if (TASK[n].STATUS & OFF) break;

if (n != NT)

{

nt = n; // Резервировать память под стек

TASK[nt].PS = (char *)malloc(SIZE);

// Текущий указатель стека с конца

// выделенной памяти (стек “вверх дном”)

sp = (struct STACK *)(TASK[nt].PS + SIZE - sizeof(struct STACK));

sp->ax = sp->bx = sp->cx = sp->dx = 0;

sp->si = sp->di = 0; // Сформировать начальное состояние стека

sp->ds = sp->es = _DS;

sp->cs = _CS;

sp->ip = (unsigned)pf; // Начало процесса - адрес функции

TASK[nt].SS = _DS; // Указатель на стек процесса в дескрипторе

TASK[nt].SP = (unsigned)sp;

TASK[nt].STATUS = 0; //Процесс - ГОТОВ

}

RUN--;

return(nt);

}

Функция возвращает номер созданного процесса в массиве дескрипторов. Функция-процесс, которая вызывает FORK, называется порождающим процессом и может использовать этот номер для дальнейшего взаимодействия с порожденным процессом. Заметим, что при порождении процесса переключения процессов запрещаются (устанавливается признак RUN).

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

void BLOCK(int mask)

{

RUN++;

PT->STATUS |= mask;

RUN--;

geninterrupt(TIMVEC);

}

С использованием этого механизма процесс может уничтожить себя, или "приостановиться" на заданное число тиков таймера. В последнем случае он устанавливает в своем дескрипторе счетчик, из которого в каждом прерывании диспетчером вычитается 1. Когда счетчик обнуляется, диспетчер сбрасывает признак блокировки, и процесс снова переходит в состояние готовности.
// Уничтожение текущего процесса -------------------------

void KILL()

{

RUN++;

asm cli

PT->STATUS |= OFF;

free(PT->PS);

RUN--;

asm sti

geninterrupt(TIMVEC);

}

// Тайм - аут процесса -------------------------------------

void WAIT( unsigned tt)

{

PT->DELAY = tt;

BLOCK(TWAIT);

}

В диспетчер добавляется соответствующий цикл, который “отсчитывает” время для блокированных процессов и по завершению их блокировки - возвращает в состояние готовности.
// Вычисление тайм - аутов в диспетчере -------------------

if (!NOCLOCK)

{

for (n=0; n
if (TASK[n].STATUS & TWAIT)

if (--TASK[n].DELAY ==0) TASK[n].STATUS &= ~TWAIT;

} NOCLOCK=0;

Основная функция main имеет в себе отдельные нюансы, которые могут быть поняты только в терминах процессов. Дело в том, что она начинает выполняться в режиме обычной последовательной программы и в этом режиме готовит структуры данных для системы процессов. Затем происходит неявное переключение в режим квазипараллельных процессов, причем main становится в нем единственным или “нулевым” процессом. Для этого он настраивает структуры данных соответствующим образом - первое прерывание по таймеру осуществляется при единственно готовом “нулевом” процессе. “Нулевой” процесс не требует себе отдельного стека, а использует стек породившей его программы.
void main()

{ int n;

RUN = DISP = 0;

TASK[0].STATUS=0;

for (n=1; n < NT; n++) TASK[n].STATUS = OFF;

RUN++;

CT = 0;

PT = TASK;

OLDTIM = getvect(TIMVEC);

setvect(TIMVEC,TIMER);

// В момент первого прерывания от таймера main становится

// нулевым процессом (это можно сделать и принудительно)

geninterrupt(TIMVEC);

textbackground(BLACK);

clrscr();

FORK(consume);

FORK(produce);

RUN--;

// В данном примере “нулевой” процесс ничего не делает, хотя

// он может выполнять все функции обычного процесса

// (geninterrupt используется для принудительного переключения

// процессов, а NOCLOCK вводится в диспетчер, чтобы не учитывать

// такие принудительные прерывания для ожидающих (блокированных)

// процессов)

for(STOP=0;!STOP;)

{ NOCLOCK++; geninterrupt(TIMVEC); }

setvect(TIMVEC,OLDTIM);

clrscr();

}

Синхронизация процессов

С взаимодействием процессов тесно связано понятие синхронизации. Синхронизация необходима для корректного разделения общих ресурсов, обмена данными между процессами и т.п.. Сразу же заметим, что для синхронизации процессов должен быть создан набор непрерываемых (целостных) примитивов (элементарных действий), выполнение которых одним процессом не должно прерываться аналогичными действиями других процессов. Такие фрагменты программного кода называются еще “критическими секциями”. В нашей программе мы уже сталкивались с простейшим способом ограничения таких переключений - установка в 1 переменной RUN любым процессом приводит к запрещению его переключения диспетчером, поэтому любой процесс ограждает свою критическую секцию операциями RUN++ ... RUN—

Механизмы синхронизации могут быть разными. Широко используются “почтовые ящики” - сообщений с неделимыми операциями “послать”, “проверить” и “получить” сообщение. Другим механизмом, который в силу своей простоты является наиболее универсальным и поэтому используется для проектирования других систем синхронизации, является семафор.

Семафор -- целая переменная с неделимыми операциями изменения, проверки и ожидания

Семафор имеет некоторое начальное значение и две операции P и V. Операция P уменьшает на 1 значение семафора, если он не равен 0. Иначе процесс ожидает (с блокировкой или без нее), пока значение семафора не станет отличным от 0. V - операция увеличивает на 1 значение семафора. Операции проверки и изменения значения переменной являются неделимыми. В нашей модели эти операции (с циклическим ожиданием) выглядят следующим образом (Заметим, что явное переключение процессов - в данном случае вещь чисто техническая и не принципиальная, предназначенная для более быстрой реакции нужных процессов по произошедшим событиям).
void P(int *sem)

{while(1)

{ RUN++; // “Критическая секция”

if (*sem!=0) // Уменьшить ненулевой семафор и выйти

{ (*sem)--; RUN--; return; }

else // Повторить (с переключение процессов)

{ RUN--; NOCLOCK++;

geninterrupt(TIMVEC);

}

}}
void V(int *sem) // Увеличить семафор

{ RUN++; (*sem)++; RUN--; // Выйти (с переключением процессов)

NOCLOCK++; geninterrupt(TIMVEC);

}

В заключение приведем пример решения классической задачи “поставщик - потребитель” , взаимодействующих через общий циклический буфер.
#define N 5 // Размер буфера

#define TW 18*2 // Время “работы” потребителя

int EMPTY=N, // Семафор “БУФЕР ПОЛОН”

FULL=0, // Семафор “БУФЕР ПУСТ”

SEMBUF=1; // Семафор “ОПЕРАЦИЯ С БУФЕРОМ”

int fst=0,lst=0; // Циклическая очередь

char BUFF[N];
void consume() // Процесс - потребитель

{ while(1)

{ WAIT(TW); // Процесс “работает”

P(&FULL); // P(Буфер не пуст)

P(&SEMBUF); // P(Операция с буфером)

char s=BUFF[fst]; // Получить из буфера

fst=(fst+1)%N; // и вывести

textbackground(BLUE);

putch(s);

V(&SEMBUF); // V(Операция с буфером)

V(&EMPTY); // V(Буфер не полон)

}}
void produce() // Процесс - производитель

{ while(1)

{

if (kbhit()) { // Если есть ввод

char c=getch();

textbackground(BLACK);

putch(c);

if (c=='\r') STOP++;

P(&EMPTY); // P(Буфер не полон)

P(&SEMBUF); // P(Операция с буфером)

textbackground(MAGENTA);

putch(c);

BUFF[lst]=c; // Поместить в буфер

lst=(lst+1)%N;

V(&SEMBUF); // V(Операция с буфером)

V(&FULL); // V(Буфер не пуст)

}}}



Романов Е.Л. Информатика и программирование. Язык Си. (конспект лекций) .


Похожие:

6. 4 Разделение времени. Многозадачность iconПрограмма по дисциплине: ветхий завет
Понятие о Священном Писании. Наименования состава священных книг. Главный предмет Священного Писания. Значение науки о Священном...
6. 4 Разделение времени. Многозадачность iconОртогональное частотное разделение каналов с мультиплексированием
Следовательно, в точке приема результирующий сигнал представляет собой суперпозицию (интерференцию) многих сигналов, имеющих различные...
6. 4 Разделение времени. Многозадачность iconУчебное пособие Для студентов вузов Кемерово 2006 удк 113/119 (075) ббк 87я7 К56 Рецензенты: И. Ф
Охватывает не только механическое разделение труда, но и политическое, сословно-классовое разделение. Во втором виде он выделял простую...
6. 4 Разделение времени. Многозадачность iconСорбционное концентрирование и разделение ионов Cu(II) и
Сорбционное концентрирование и разделение ионов Cu(II) и Zn(II) на некоторых ионитах из хлоридных растворов
6. 4 Разделение времени. Многозадачность iconВместо введения Глава первая. Многозадачность в современном мире, и как этого избежать?
В чем опасность не умения работать в режиме многозадачности? И к чему это мочжет привести
6. 4 Разделение времени. Многозадачность iconБитва Microsoft ibm на рынке настольных ос
Эти технологии включают многозадачность и многонитевость, способность выполнять dos-программы с помощью виртуальных машин процессоров...
6. 4 Разделение времени. Многозадачность iconСтационарное уравнение Шредингера Особое место занимают задачи, в которых потенциальная энергия зависит только координат
Такие состояния называются стационарными, так как в них сохраняется энергия системы E. Отсутствие явной зависимости гамильтониана...
6. 4 Разделение времени. Многозадачность iconOS/2 постепенные улучшения
Она должна была поддерживать вытесняющую многозадачность, виртуальную память, графический пользовательский интерфейс, виртуальную...
6. 4 Разделение времени. Многозадачность iconЗакон или принцип, возможно ли разделение закона единства и борьбы противопложностей?
Что первично в познании – закон или принцип, возможно ли разделение закона единства и борьбы противопложностей?
6. 4 Разделение времени. Многозадачность iconИ разделение лантаноидов гидрометаллургическими методами при комплексной переработке низкоконцентрированного сырья
Звлечение и разделение лантаноидов гидрометаллургическими методами при комплексной переработке низкоконцентрированного сырья
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org