Решение задачи "читатели и писатели"

Размещено на http://allbest.ru

Министерство образования и науки Украины

Севастопольский национальный технический университет

Кафедра Кибернетики и вычислительной техники

Лабораторная работа

по курсу: «Параллельные и распределенные вычисления»

Решение задачи «читатели и писатели»

Выполнил: ст. гр. М-34д

Ярославцев Д.А.

Проверил: Абрамов Т.А.

Севастополь

2010 г.



1. Исходные данные

программирование java семафор

Цель:

Исследовать возможности, предоставляемые системой программирования JAVA для решения задачи синхронизации «читатели и писатели».

Задание на лабораторную работу:

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

Исследовать поведение программы при использовании различных методов синхронизации (событийные переменные, семафоры)

Проанализировать полученные результаты.

2. Ход работы

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

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

1) Возьмём базовый пример и исправим его в соответствии с заданием по своему варианту. Введем возможность управления режимом работы программы:

а) С использованием пассивного ожидания на основе ввода событийных переменных.

б) Без использования вышеуказанных.

в) С использованием семафоров (java.util.concurrent.Semaphore)

Результаты приводим для простого случая с наличием 2-х писателей и 4 читателей.

3. Текст программы

import java.util.concurrent.locks.*;

class PC {public static void main(int readers, int writers, boolean mode)

{Q q = new Q();

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

new Reader(q, i);}

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

new Writer(q, i);}

try {Thread.sleep(5000);} catch (InterruptedException e);

q.work = false;

q.mode = mode;

class Q {

final Lock lock = new ReentrantLock();

final Condition ReaderCanStart = lock.newCondition();

final Condition WriterCanStart = lock.newCondition();

int WaitingReader = 0;

int RunningReader = 0;

int WaitingWriter = 0;

int RunningWriter = 0;

String n;

boolean work = true;

boolean mode;

String read() {

if (mode) { StartRead(); }

Thread t = Thread.currentThread();

System.out.println(t.getName() + " try...");

System.out.println(t.getName() + " reading...");

try {

Thread.sleep(50);

} catch (InterruptedException e) {}

System.out.println(t.getName() + ":" + Minimum(n));

if (mode) {StopRead();} return n; }

void write(String str) {if (mode) {StartWrite();}

Thread t = Thread.currentThread();

System.out.println(t.getName() + " try...");

System.out.println(t.getName() + " writing...");

try {Thread.sleep(10);} catch (InterruptedException e) {}

n = str;

System.out.println(t.getName() + ":" + n);

if (mode) {StopWrite();}

void StartRead() {lock.lock();try {

if ((RunningWriter > 0) | (WaitingWriter > 0)) {

WaitingReader++;

try {ReaderCanStart.await();

catch (InterruptedException e) {}

else {RunningReader++;}

finally {lock.unlock();}

void StopRead() {lock.lock();

try {RunningReader--;

if ((RunningReader == 0) & (WaitingWriter > 0)) {

WaitingWriter--;

RunningWriter++;

WriterCanStart.signal();}

finally { lock.unlock(); }

void StartWrite() {lock.lock();

try {if ((RunningWriter > 0) | (RunningReader > 0)) {

WaitingWriter++;

try {

WriterCanStart.await();

} catch (InterruptedException e) {}

} else {

RunningWriter++;}

} finally {

lock.unlock();

void StopWrite() {

lock.lock();

try {RunningWriter--;

if (WaitingReader > 0) {

while (WaitingReader > 0) {

RunningReader++;

WaitingReader--;

ReaderCanStart.signal();}

} else {

if (WaitingWriter > 0) {

WaitingWriter--;

RunningWriter++;

WriterCanStart.signal();}

} finally {

lock.unlock();}

static int Minimum(String str) {

int[] n = null;

try {

String[] nn = str.split(" ");

n = new int[nn.length];

for (int i = 0; i < nn.length; i++) {

n[i] = Integer.parseInt(nn[i] + "");}

} catch (Exception r) { }

if (n == null) { return 0; }

int min = n[0];

for (int i = 1; i < n.length; i++) {

if (min > n[i]) {

min = n[i];}

return min;

class Writer implements Runnable {

Q q;

Writer(Q q, int num) {

this.q = q;

new Thread(this, "Writer " + num).start();}

public void run() {

while (q.work) {

q.write(NumberToString(GenerNatural(10)));} }

int[] GenerNatural(int n) {

int[] k = new int[n];

for (int i = 0; i < k.length; i++) {

k[i] = (int) (Math.random() * 100); } return k; }

String NumberToString(int[] n) {

String str = "";

for (int i = 0; i < n.length; i++) {

str += n[i] + " ";

} return str; }}

class Reader implements Runnable {

Q q;

Reader(Q q, int num) {

this.q = q;

new Thread(this, "Reader " + num).start();}

public void run() {

while (q.work) {

q.read();}}

4. Результаты

а) Без использования механизма пассивного ожидания программа работает некорректно:

Writer 2:47 4 77 79 30 75 80 14 64 45

Writer 2 try...

Writer 2 writing...

Writer 1:29 45 64 13 56 95 88 83 29 88

Writer 1 try...

Writer 1 writing...

Reader 4:13

Reader 3:13

Reader 3 try...

Reader 3 reading...

Reader 4 try...

Reader 4 reading...

Writer 2:92 42 57 84 55 87 6 40 14 33

Writer 2 try...

Writer 2 writing...

Writer 1:87 42 23 9 96 36 57 78 59 93

Writer 1 try...

Writer 1 writing...

Writer 2:50 66 18 62 17 7 47 74 13 32

Writer 2 try...

Writer 2 writing...

Reader 1:7

Reader 1 try...

Reader 1 reading...

Writer 1:52 84 56 25 70 82 86 96 65 46

Writer 1 try...

Writer 1 writing...

Writer 2:47 69 42 14 31 18 88 90 86 89

Writer 2 try...

Writer 2 writing...

Reader 2:14

Reader 2 try...

Reader 2 reading...

Writer 1:22 79 81 75 36 50 94 7 37 20

Writer 2:17 1 8 6 96 20 76 84 59 45

Reader 4:1

Reader 3:1

Reader 1:1

Reader 2:1

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

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

Процесс-читатель сможет продолжать работу в том случае, если нет работающих процессов-писателей, независимо от количества работающих процессов-читателей. Процесс-писатель сможет продолжать работу, если нет работающих процессов, как писателей, так и читателей.

Программа отработает в режиме пассивного ожидания (т.е., процесс, который не может продолжать работу, будет помещаться в очередь). Соответственно, потребуются средства, освобождающие ожидающие процессы. Установим, что процесс при завершении работы с общим ресурсом должен будет выполнить действия по освобождению ресурса (процедуры StopRead и StopWrite).

Результат отработки программы примет следующий вид:

Writer 2 try...

Writer 2 writing...

Writer 2:7 66 42 89 89 23 38 5 50 65

Reader 2 try...

Reader 2 reading...

Reader 2:5

Writer 2 try...

Writer 2 writing...

Writer 2:24 91 52 46 29 70 87 77 75 4

Reader 4 try...

Reader 4 reading...

Reader 1 try...

Reader 1 reading...

Reader 3 try...

Reader 3 reading...

Reader 2 try...

Reader 2 reading...

Reader 1:4

Reader 3:4

Reader 4:4

Reader 2:4

Writer 1 try...

Writer 1 writing...

Writer 1:31 16 56 41 53 27 20 10 77 41

Reader 1 try...

Reader 1 reading...

Reader 3 try...

Reader 3 reading...

Reader 4 try...

Reader 4 reading...

Reader 2 try...

Reader 2 reading...

Reader 1:10

Reader 2:10

Reader 3:10

Reader 4:10

Writer 2 try...

Writer 2 writing...

Writer 2:27 13 83 75 41 87 80 81 40 64

Reader 2 try...

Reader 2 reading...

Reader 3 try...

Reader 3 reading...

Reader 4 try...

Reader 4 reading...

Reader 1 try...

Reader 1 reading...

Reader 3:13

Reader 1:13

Reader 2:13

Reader 4:13

Writer 1 try...

Writer 1 writing...

Writer 1:98 22 11 94 3 51 2 3 38 23

Reader 3 try...

Reader 3 reading...

Reader 1 try...

Reader 1 reading...

Reader 2 try...

Reader 2 reading...

Reader 4 try...

Reader 4 reading...

Reader 2:2

Reader 3:2

Reader 1:2

Reader 4:2

Writer 2 try...

Writer 2 writing...

Writer 2:37 6 22 56 39 43 10 66 78 99

Reader 2 try...

Reader 3 try...

Reader 3 reading...

Reader 4 try...

Reader 4 reading...

Reader 2 reading...

Reader 1 try...

Reader 1 reading...

Reader 4:6

Reader 1:6



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

Приоритет может задаваться временем ожидания (метод «sleep»), начальным значением семафоров, собственно может быть изменен приоритет создаваемых объектов-потоков в Java.

Как можно видеть из вышеуказанного примера, большим приоритетом обладают читатели, и писатели могут изменять общую переменную только когда все 4 читателя закончили работу, что соответствует заданному варианту.

в) Используем для синхронизации семафоры (java.util.concurrent.Semaphore).

import java.util.concurrent.*;

class PCSem {

public static void main() {

Q q = new Q();

new Writer(q,1);

new Writer(q,2);

new Reader(q,1);

new Reader(q,2);

new Reader(q,3);

new Reader(q,4);

try {Thread.sleep(2000);} catch(InterruptedException {System.out.println("Прерывание главного потока");} ;

q.work = false;}}

class Q {

Semaphore sema = new Semaphore(4, true);

String n;

boolean work = true;

String read() {

int numerOfPerm = sema.availablePermits();

if (numerOfPerm < 0){ sema.release(3); }

try { sema.acquire(); } catch (InterruptedException e) {}

Thread t = Thread.currentThread();

System.out.println(t.getName()+" try...");

System.out.println(t.getName()+" reading...");

try { Thread.sleep(50); } catch (InterruptedException e) {}

System.out.println(t.getName()+":"+Minimum(n));

sema.release();

return n;}

void write(String str) {

int numerOfPerm = sema.availablePermits();

if (numerOfPerm >= 4) {

try {sema.acquire();sema.acquire();sema.acquire();sema.acquire(); } catch (InterruptedException e) {}

Thread t = Thread.currentThread();

System.out.println(t.getName()+" try...");

System.out.println(t.getName()+" writing...");

try { Thread.sleep(10); } catch (InterruptedException e) {}

n = str;

System.out.println(t.getName()+":"+n);

sema.release();sema.release();sema.release();sema.release();}}

static int Minimum (String str) {

int [] n=null;

try{String []nn=str.split(" "); n=new int[nn.length];

for(int i=0;i<nn.length;i++) n[i]=Integer.parseInt(nn[i]+"");} catch(Exception r){}

if (n == null) {return 0;}

int min=n[0];

for (int i=1; i<n.length; i++) {

if (min > n[i]) min = n[i]; }

return min;}}

class Writer implements Runnable {

Q q;

Writer(Q q,int num) {

this.q = q;

new Thread(this, "Writer "+num).start();}

public void run() {

while (q.work) { q.write(NumberToString(GenerNatural(10))); }}

int [] GenerNatural (int n) {

int [] k = new int [n];

for (int i=0; i<k.length; i++) {

k[i] = (int) (Math.random()*100); }

return k; }

String NumberToString(int []n){ String str="";

for (int i=0; i<n.length; i++) {

str+=n[i]+" "; }

return str;}}

class Reader implements Runnable {

this.q=q;

new Thread(this, "Reader "+num).start(); }

public void run() {while (q.work) { q.read(); } }

Результат отработки программы примет следующий вид:

Writer 1 try...

Writer 1 writing...

Writer 1:61 67 91 44 97 67 37 41 3 39

Reader 1 try...

Reader 1 reading...

Reader 2 try...

Reader 2 reading...

Reader 4 try...

Reader 4 reading...

Reader 1:3

Reader 2:3

Reader 4:3

Writer 2 try...

Writer 2 writing...

Writer 2:86 97 40 62 60 53 4 45 66 16

Reader 3 try...

Reader 3 reading...

Reader 1 try...

Reader 1 reading...

Reader 2 try...

Reader 2 reading...

Reader 4 try...

Reader 4 reading...

Reader 4:4

Reader 3:4

Reader 1:4

Reader 2:4

Writer 1 try...

Writer 1 writing...

Writer 1:0 55 82 17 15 33 49 27 69 86

Reader 3 try...

Reader 3 reading...

Reader 1 try...

Reader 1 reading...

Reader 4 try...

Reader 4 reading...

Reader 2 try...

Reader 2 reading...

Reader 1:0

Reader 2:0

Reader 4:0

Reader 3:0

Writer 2 try...

Writer 2 writing...

Writer 2:82 19 37 66 48 67 9 8 50 97

Reader 1 try...

Reader 2 try...

Reader 2 reading...

Reader 3 try...

Reader 3 reading...

Reader 1 reading...

Reader 4 try...

Reader 4 reading...

Reader 2:8

Reader 4:8

Reader 1:8

Reader 3:8

Writer 1 try...



Выводы

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

Размещено на Allbest.ru

...