Математическая модель задачи о читателях и писателях Хусаинов А.А. husainov51@yandex.ru husainov51@yandex.ru - презентация

1 Математическая модель задачи о читателях и писателях Хусаинов А.А.

2 2 Цель доклада Построение и применение асинхронной системы переходов для решения задачи о читателях и писателяхПостроение и применение асинхронной системы переходов для решения задачи о читателях и писателях

3 3 Задачи Рассмотреть различные методы решения задачи о читателях и писателяхРассмотреть различные методы решения задачи о читателях и писателях Дать определение и примеры асинхронных системДать определение и примеры асинхронных систем Построить асинхронную систему для задачи о читателях и писателяхПостроить асинхронную систему для задачи о читателях и писателях Разработать программное обеспечениеРазработать программное обеспечение

4 4 Задача о читателях и писателях В многопроцессорный компьютер в случайные моменты времени загружаются два типа процессов – читатели и писатели, осуществляющие сеансы работы (транзакции) с общей базой данных. Читатели выполняют чтение, писатели – чтение и запись. Транзакции изменяют состояние системы. База Данных Читатель Писатель 1.Писатель может работать только один. 2.Читателей может быть несколько 3.Писатели имеют приоритет перед читателями – если появился писатель, новые читатели не могут получить доступ к базе.

5 5 Решение с помощью одного семафора int nr =0; // количество читателей Semaphore rw(1,1); // мьютекс на доступ к базе данных Reader(){ read(); }Writer(){P(rw);write();V(rw)}

6 6 Уточнение неделимых операций int nr =0; // количество читателей Semaphore rw(1,1); // максимальное и начальное значения =1 Semaphore mr(1,1); Reader(){ // // P(mr); nr++; if (nr==1) P(rw); V(mr); read(); // // P(mr); nr--; if (nr==0) V(rw); V(mr); P(mr); nr--; if (nr==0) V(rw); V(mr);}Writer(){P(rw);write();V(rw)} // Бесконечный поток читателей может блокировать работу писателей

7 7 Условная синхронизация для приоритета писателей int nr =0; // количество читателей, имеющих доступ к базе int nw=0; // количество писателей, имеющих доступ // (nr==0 || nw==0) && nw 1 -- глобальный инвариант // читатель ждет условия (nw==0) // писатель ждет условия (nr==0 || nw==0) Reader(){ read(); }Writer(){ write();} Проблема: реализовать Проблема: реализовать

8 8 Детализация условной синхронизации методом передачи эстафеты int nr =0, // количество читателей, имеющих доступ к базе dr=0; // приостановленных читателей int nw=0, // количество писателей, имеющих доступ dw=0; // приостановленных писателей Semaphore e(1,1), // мьютекс для упр входом в неделимые действия r(1,0), // равен 1 если (nw==0) w(1,0); // равен 1 если (nr==0 && nw==0) Reader(){ // // P(e); if (nw>0) {dr++; V(e); P(r);} nr++;SIGNAL; read(); // // P(e); nr--; SIGNAL; }Writer(){ // // P(e); if (nr>0 || nw>0) {dw++; V(e); P(w);} nw++; SIGNAL; write(); // // P(e); nw--; SIGNAL; } SIGNAL: if (nw==0 && dr > 0) V(r); else if ((nw==0|| nr==0) && dw>0) V(w) else if (dr==0 && dw==0) V(e);

9 9 Решение с помощью монитора Монитор = объект класса с исключительным запуском составных функций Monitor RW { // инв (nr==0 || nw==0) && (nw 1) int nr=0, nw=0; cond oktoread, // сигнал nw==0 oktowrite; // сигнал nr==0 && nw==0; Procedure req_read() { while (nw>0) wait(oktoread); nr++; } Procedure release_read() { nr--; if (nr==0) signal(oktowrite); } Procedure req_write() { while (nr>0||nw>0) wait(oktowrite); nw++; } Procedure release_write() { nw--; signal(oktowrite); signal_all(oktoread); } Reader() { RW.req_read(); read(); RW.release_read(); } Writer() { RW.req_write(); read(); RW.release_write(); }

10 10 Асинхронные системы A=(S, s 0, E, I, Tran)A=(S, s 0, E, I, Tran) S - множество состояний, s 0 S начальное состояние s 0 S, E - множество событий, I E E - антирефлексивного симметричного отношения независимости. Если (s,a,s') Tran & (s,a,s'') Tran, то s'=s''.Если (s,a,s') Tran & (s,a,s'') Tran, то s'=s''. Если (a,b) I & (s, a, s') Tran & (s', b, s'') Tran, то существует такой s 1 S, что (s,b,s 1 ) Tran & (s 1, a, s'') Tran.Если (a,b) I & (s, a, s') Tran & (s', b, s'') Tran, то существует такой s 1 S, что (s,b,s 1 ) Tran & (s 1, a, s'') Tran.

11 11 Асинхронная система для задачи о читателях и писателях Состояния (r,w), r – число активных читателей, w – число загруженных писателей Начальное (0,0). I={(b,c),(c,b)}. E состоит из следующих событий: a – читатель пытается получить доступ к базе; b – читатель закончил работу с базой; c – поступил новый писатель; d – писатель закончил работу с базой.

0) { V(m); return;" title="12 Решение с помощью асинхронной системы int r=0, w=0; Semaphore m(1,1), // семафор доступа к (r,w) en(1,1); // разрешение записи Event req0=0; // событие "значение r равно 0" Reader() { P(m); // "a" (читатель пытается войти) if (w>0) { V(m); return;" class="link_thumb"> 12 12 Решение с помощью асинхронной системы int r=0, w=0; Semaphore m(1,1), // семафор доступа к (r,w) en(1,1); // разрешение записи Event req0=0; // событие "значение r равно 0" Reader() { P(m); // "a" (читатель пытается войти) if (w>0) { V(m); return; } r++; // читатель получил доступ Reset(req0); V(m); read(); P(m); // "b" (читатель закончил работу) r--; if (r==0) SetEvent(req0); V(m); } W riter() { P(m); // событие "c" w++; // поступил писатель V(m); Wait(req0); P(en); write(); // производит запись V(en); P(m); // событие "d" w--; // писатель выгружается V(m); } 0) { V(m); return;"> 0) { V(m); return; } r++; // читатель получил доступ Reset(req0); V(m); read(); P(m); // "b" (читатель закончил работу) r--; if (r==0) SetEvent(req0); V(m); } W riter() { P(m); // событие "c" w++; // поступил писатель V(m); Wait(req0); P(en); write(); // производит запись V(en); P(m); // событие "d" w--; // писатель выгружается V(m); }"> 0) { V(m); return;" title="12 Решение с помощью асинхронной системы int r=0, w=0; Semaphore m(1,1), // семафор доступа к (r,w) en(1,1); // разрешение записи Event req0=0; // событие "значение r равно 0" Reader() { P(m); // "a" (читатель пытается войти) if (w>0) { V(m); return;">

13 13 Разбиение семафора доступа к числам читателей и писателей int r=0, w=0; Semaphore mr(1,1), // семафор доступа к r mw(1,1), // семафор доступа к w en(1,1); // разрешение записи Event req0=0; // событие "значение r равно 0" Reader() { P(mr); // "a" (читатель пытается войти) P(mw); if (w>0) { V(m); return; } r++; // читатель получил доступ Reset(req0); V(mw); V(mr); read(); P(mr); // "b" (читатель закончил работу) r--; if (r==0) SetEvent(req0); V(mr); } W riter() { P(mw); // событие "c w++; // поступил писатель V(mw); Wait(req0); P(en); write(); // производит запись V(en); P(mr); P(mw); // событие "d" w--; // писатель выгружается V(mw); V(mr); } События b и c можно обрабатывать параллельно 0) { V(m); return; } r++; // читатель получил доступ Reset(req0); V(mw); V(mr); read(); P(mr); // "b" (читатель закончил работу) r--; if (r==0) SetEvent(req0); V(mr); } W riter() { P(mw); // событие "c w++; // поступил писатель V(mw); Wait(req0); P(en); write(); // производит запись V(en); P(mr); P(mw); // событие "d" w--; // писатель выгружается V(mw); V(mr); } События b и c можно обрабатывать параллельно">

14 14 Читатели ожидают возможности чтения базы int r=0, w=0; Semaphore mr(1,1), // семафор доступа к r Semaphore mw(1,1), // семафор доступа к w en(1,1); // разрешение записи Event req0=0,// событие "значение r равно 0 weq0=0;// событие "значение w равно 0 Reader() { Wait(weq0);//ждем оконч.раб. писателей P(mw); // "a" (читатель пытается войти) P(mr); r++; // читатель получил доступ Reset(req0); V(mr); V(mw); read(); P(mr); // "b" (читатель закончил работу) r--; if (r==0) SetEvent(req0); V(mr); } Writer() { P(mw); // событие "c" w++; // поступил писатель Reset(weq0); V(mw); Wait(req0); P(en); write(); // производит запись V(en); P(mw); // событие "d P(mr); w--; // писатель выгружается if (w==0) SetEvent(weq0); V(mr); V(mw); } Читатели и писатели ждут разрешения

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