1 / 1 / 0
Регистрация: 21.02.2016
Сообщений: 27
1

Задача с семафорами

21.02.2016, 20:36. Показов 2945. Ответов 33

Дана такая задача:

Железная дорога, соединяющая города A и B, имеет участок с одним путем. Пусть движение поездов из A в B и из B в A – процессы. Используя семафоры, запрограммировать движение поездов таким образом, чтобы в любой момент времени по единственному пути поезда двигались только в одном направлении. Рассмотреть проблему бесконечного ожидания, варианты ее решения

Моё решение (w_ — означает west, приведен код только для движения в одну сторону — с запада на восток, в другую сторону — симметрично)
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
w_turnstile=Semaphore(1);
w_mutex=Semaphore(1);
lock=Semaphore(1);
w_counter=0;
 
void w_thread()
{
     P(w_turnstile);
     V(w_turnstile);
     
     P(w_mutex);
     w_counter++;
     if(w_counter==1){
          P(e_turnstile);
          P(lock);
          V(e_turnstile);
     }
     V(w_mutex);
 
     //движение поезда
 
     P(w_mutex);
     w_counter--;
     if(w_counter==0){
          V(lock);
     }
     V(v_mutex);
}
Бесконечное ожидание отсутствует из-за того, что когда появляется, допустим, поезд c востока на запад, он уменьшает значение семафора w_turnstile, и новые поезда с запада на восток ждут на этом семафоре и не могут увеличить счётчик w_counter, а старые поезда прийти могут, то есть в итоге lock будет отпущен.

Есть ли в этом решении ошибки и есть ли более оптимальное решение?
__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
21.02.2016, 20:36
Ответы с готовыми решениями:

работа с семафорами
Родительский процесс создаёт семафор (сем1) и общий файл. Дочерний процесс записывает в файл по...

Работа с семафорами
Здравствуйте, я написал код: #include <sys/sem.h> #include <unistd.h> #include <sys/types.h>...

Работа с семафорами.
помгите написать код:wall:...пож Cоздать два дочерних процесса. Родительский процесс создаёт...

Пул потоков с семафорами
Задача:написать свой пуль потоков Написал вот такой код #include <windows.h> #include...

33
1542 / 637 / 84
Регистрация: 01.10.2012
Сообщений: 3,128
22.02.2016, 07:58 2
Разобраться в Вашем коде нелегко, одни P и V чего стоят Просто "на глазок" не должно оно быть так сложно
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
QMutex mutex;
int numTrain = 0;  // + AB   - BA
 
void MyThread::run( void ) 
{
    while (true) {
        int AB = (qrand() % 2) ? 1 : -1;     // новый поезд напр-е AB или BА
 
        bool check = true;   
        while (check)  {
            mutex.lock();                   // захватываем мутекс чтобы изменить numTrain
            if (numTrain * AB >= 0)) {      // если нет поездов или они едут в том же напр-и
                numTrain += AB;
                check = false;  
            }
            mutex.unlock();     // всегда освобождаем mutex
        
            if (check)
                QThread::mSleep(5);  // ждем пока проедут все поезда в др напр-и
        }
 
        QThread::mSleep(100);   // поезд едет какое-то время
 
        mutex.lock();           // поезд проехал, уменьшаем счетчик под защитой 
        numTrain -= AB;
        mutex.unlock();         
    }
}
0
1 / 1 / 0
Регистрация: 21.02.2016
Сообщений: 27
22.02.2016, 08:22  [ТС] 3
Igor3D, P и V означают уменьшить или увеличить значение семафора на 1. Аналоги, например, sem_wait и sem_post в pthreads. В вашем коде присутствует бесконечное ожидание (starvation) — если будет много поездов в одном направлении, то поезд в другом направлении не сможет пройти. И ждать c помощью sleep и последующей проверки недопустимо в таких задачах — нужно ждать на семафоре.
1
1542 / 637 / 84
Регистрация: 01.10.2012
Сообщений: 3,128
22.02.2016, 09:05 4
Цитата Сообщение от noski Посмотреть сообщение
P и V означают уменьшить или увеличить значение семафора на 1. Аналоги, например, sem_wait и sem_post в pthreads.
Все равно ничего не пойму. По смыслу вроде мутексы, а Вы их присваиваете семафорам - это же не одно и то же. И я никогда не поверю что нужны аж 3 семафора и 2 симметричных варианта
Цитата Сообщение от noski Посмотреть сообщение
В вашем коде присутствует бесконечное ожидание (starvation) — если будет много поездов в одном направлении, то поезд в другом направлении не сможет пройти.
Как и в Вашем - ведь для этого нужно сравнивать кол-во поездов скопившихся с одной и другой стороны.
Цитата Сообщение от noski Посмотреть сообщение
И ждать c помощью sleep и последующей проверки недопустимо в таких задачах — нужно ждать на семафоре.
Это тоже несложно дорисовать, просто будет чуть больше кода и переменных, чего я в базовом примере хотел избежать. Но если Вы мне "указываете на недопустимость", то наверное Вы лучше знаете, а мне нужно помолчать
0
1 / 1 / 0
Регистрация: 21.02.2016
Сообщений: 27
22.02.2016, 11:52  [ТС] 5
Igor3D,
Цитата Сообщение от Igor3D Посмотреть сообщение
Все равно ничего не пойму. По смыслу вроде мутексы, а Вы их присваиваете семафорам - это же не одно и то же.
Не очень понятно, что вы имели в виду под «присвоить мутексы семафорам». В моём коде есть только семафоры. Вообще, мьютексы обычно используются для создания критической секции, поэтому семафор, который используется для этого я и назвал мьютексом. А для остальных я выбрал более понятные названия.
Цитата Сообщение от Igor3D Посмотреть сообщение
Как и в Вашем - ведь для этого нужно сравнивать кол-во поездов скопившихся с одной и другой стороны
Я же написал, как, на мой взгляд, в моём коде решается эта проблема:
Цитата Сообщение от noski Посмотреть сообщение
Бесконечное ожидание отсутствует из-за того, что когда появляется, допустим, поезд c востока на запад, он уменьшает значение семафора w_turnstile, и новые поезда с запада на восток ждут на этом семафоре и не могут увеличить счётчик w_counter, а старые поезда прийти могут, то есть в итоге lock будет отпущен.
То есть, в итоге семафор lock будет отпущен и поезда в другом направлении (с востока на запад) пройдут.
Цитата Сообщение от Igor3D Посмотреть сообщение
Это тоже несложно дорисовать, просто будет чуть больше кода и переменных, чего я в базовом примере хотел избежать. Но если Вы мне "указываете на недопустимость", то наверное Вы лучше знаете, а мне нужно помолчать
Я, наверное, слишком резко выразился. Я хотел просто уточнить условия задачи. В целом, меня больше интересуют полные решения (а не базовые примеры) без бесконечного ожидания и без sleep.
0
Модератор
2961 / 2100 / 450
Регистрация: 26.03.2015
Сообщений: 8,153
22.02.2016, 13:44 6
А в чём задача заключается? Написать код, который будет распределять процессорное время между двумя процессами? Или просто написать код который (в цикле) получает получает разделяемый ресурс, использует и освобождает? Или что-то другое?
0
1 / 1 / 0
Регистрация: 21.02.2016
Сообщений: 27
22.02.2016, 16:10  [ТС] 7
Shamil1, в общем, нужно запрограммировать движение поездов так, что каждый поезд — процесс. Каждый поезд двигается по дороге, его прибытие соответствуют завершению процесса. Ну и все условия, описанные в тексте задачи. Два примера кода в этой теме подходят под такой вариант решения.
0
1542 / 637 / 84
Регистрация: 01.10.2012
Сообщений: 3,128
22.02.2016, 16:29 8
Цитата Сообщение от noski Посмотреть сообщение
Я же написал, как, на мой взгляд, в моём коде решается эта проблема:
Это достигается гораздо меньшим числом блокировок и кода (см базовый пример). Но в обоих случаях "пока все-все восточные поезда не проедут - все западные стоят". Эдак действительно западным может придется долго ждать, особенно учитывая что появляются новые восточные. Но если хватает пропускной способности - бесконечным такое ожидание не является. Возможно речь о том что число ожидающих поездов должно быть примерно равным на обоих концах - но это нужно конкретизировать.
0
1 / 1 / 0
Регистрация: 21.02.2016
Сообщений: 27
22.02.2016, 16:50  [ТС] 9
Igor3D,
Цитата Сообщение от Igor3D Посмотреть сообщение
Эдак действительно западным может придется долго ждать, особенно учитывая что появляются новые восточные. Но если хватает пропускной способности - бесконечным такое ожидание не является.
По-моему, вы так и не прочитали мой комментарий. Напишу ещё раз. Новые восточные поезда не попадут в первый блок с мьютексом и не будут увеличивать e_counter, если будет хотя бы один западный поезд. А число поездов, уже прошедших семафор e_turnstile, ограничено, рано или поздно они все завершатся и дадут дорогу западным поездам. У вас же новые поезда будут постоянно увеличивать или уменьшать numTrain, и поезда другого направления никогда не пройдут. То есть они будут ждать бесконечно.
Цитата Сообщение от Igor3D Посмотреть сообщение
Возможно речь о том что число ожидающих поездов должно быть примерно равным на обоих концах - но это нужно конкретизировать.
Число ожидающих поездов на обоих концах может быть любым, такого ограничения нет.
0
Модератор
2961 / 2100 / 450
Регистрация: 26.03.2015
Сообщений: 8,153
22.02.2016, 17:49 10
Цитата Сообщение от noski Посмотреть сообщение
нужно запрограммировать движение поездов так, что каждый поезд — процесс
В такой формулировке задача элементарная. У нас есть список поездов-процессов. Запускаем каждый из них после того, как завершился предыдущий. Если про этот процесс ничего не известно, то лучше и не сделать. (Другое дело, если код для этого процесса пишем мы сами...). И мне не понятно, откуда берутся эти поезда-процессы, и как я о них узнаю.

Добавлено через 4 минуты
А если отвлечься от процессов и семафоров и представить себя железнодорожником, который вручную переключает светофоры... У нас есть несколько различных алгоритмов. В условии задачи ничего не сказано, что что-то надо оптимизировать. Поэтому задача опять элементарная. Я буду пускать поезда в том порядке, в котором они подошли.
0
1 / 1 / 0
Регистрация: 21.02.2016
Сообщений: 27
22.02.2016, 18:13  [ТС] 11
Цитата Сообщение от Shamil1 Посмотреть сообщение
Запускаем каждый из них после того, как завершился предыдущий.
Будет не совсем оптимально, так как в одном направлении могут двигаться несколько поездов, до того как один из них завершится. Поэтому так нельзя.
Цитата Сообщение от Shamil1 Посмотреть сообщение
Другое дело, если код для этого процесса пишем мы сами
Так и есть, пишем сами.
Цитата Сообщение от Shamil1 Посмотреть сообщение
И мне не понятно, откуда берутся эти поезда-процессы, и как я о них узнаю.
Постепенно подходят «из ниоткуда». Как только подходят, запускают свой процесс.
0
Модератор
2961 / 2100 / 450
Регистрация: 26.03.2015
Сообщений: 8,153
22.02.2016, 18:23 12
Цитата Сообщение от noski Посмотреть сообщение
Поэтому так нельзя.
В условии задачи об этом ни слова. Задача для телепатов?
0
1 / 1 / 0
Регистрация: 21.02.2016
Сообщений: 27
22.02.2016, 18:34  [ТС] 13
Shamil1, да, плохо, конечно, что об этом явно не сказано, но вообще мне такое условие кажется очевидным. Мне нужно было написать об этом в первом сообщении.
0
Модератор
2961 / 2100 / 450
Регистрация: 26.03.2015
Сообщений: 8,153
22.02.2016, 20:48 14
Цитата Сообщение от noski Посмотреть сообщение
вообще мне такое условие кажется очевидным
А мне оно не кажется очевидным. Какой параметр нужно оптимизировать?
0
1542 / 637 / 84
Регистрация: 01.10.2012
Сообщений: 3,128
23.02.2016, 05:42 15
Цитата Сообщение от noski Посмотреть сообщение
У вас же новые поезда будут постоянно увеличивать или уменьшать numTrain, и поезда другого направления никогда не пройдут. То есть они будут ждать бесконечно.
Логика точно такая же как у Вас, рано или поздно numTrain станет = 0.
Цитата Сообщение от Igor3D Посмотреть сообщение
if (numTrain * AB >= 0) { // если нет поездов или они едут в том же напр-и
Если if вернет true, то поезд проходит и затем numTrain корректируется в обратную сторону. А если же поезд должен ждать, то и numTrain пока не меняется. Может Вы не заметили что numTrain знаковый.

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

"Откуда берутся поезда" здесь неважно, это как бы за рамками задачи. А вот если каждый поезд - процесс (свое адресное пр-во и рулим через глобальные семафоры) - это может оказаться важным.

Цитата Сообщение от noski Посмотреть сообщение
Число ожидающих поездов на обоих концах может быть любым, такого ограничения нет.
Тогда что дальше? Заменить sleep на семафор - дело несложной техники, есть какие-то трудности - давайте напишу.
0
2057 / 1534 / 167
Регистрация: 14.12.2014
Сообщений: 13,348
23.02.2016, 06:34 16
Ну тут получается довольно простое решение: завести приоритет пропускания, который меняется на противоположный когда на рельсы пускаются поезда с одного направления. Т.е. примерно так - пустили поезда с востока, приоритет при этом у поездов с запада, поезда с востока ставятся в очередь. Прошел с востока - пустили всю скопившуюся пачку с запада, подошедшие новые западные при этом ставятся в очередь. Западные освободили рельсы - тут же пустили пачку скопившуюся за это время пачку на востоке. Ну само собой разумеется, что пока в процессе движения западных очередь восточных пуста западные ничего не ждут а сразу пускаются на пути. Но как только появился в очереди восточный, следующий западный ставится в очередь после него. ну и соответсвенно так же в обратную сторону. по большому счету задачка не на семафоры а на правильное занесение в очередь , как и все задачи диспетчирезации на транспорте.
0
1542 / 637 / 84
Регистрация: 01.10.2012
Сообщений: 3,128
23.02.2016, 07:40 17
Цитата Сообщение от Fulcrum_013 Посмотреть сообщение
Ну тут получается довольно простое решение:
Просто "пускать поезда" так и сяк действительно очень просто. А вот сделать то же самое "в параллельном варианте" совсем нет. Рискну утверждать что многие (если не большинство) вполне грамотных программистов просидит не один день даже с куда более простой изначальной постановкой ТС, не говоря уже о Вашей.

А если Вы со мной не согласны - то никто не мешает Вам предъявить параллельный код реализующий Ваши предложения
0
1 / 1 / 0
Регистрация: 21.02.2016
Сообщений: 27
23.02.2016, 11:25  [ТС] 18
Igor3D,
Цитата Сообщение от Igor3D Посмотреть сообщение
Логика точно такая же как у Вас, рано или поздно numTrain станет = 0
В том-то и дело, что если будет много поездов в одном направлении (пусть тогда AB=1), тогда, как я уже написал, новые поезда будут постоянно увеличивать numTrain, но не будут «успевать» уменьшать эту переменную до 0. То есть, другими словами, новые поезда будут приходить быстрее, чем завершаться старые.
Цитата Сообщение от Igor3D Посмотреть сообщение
Тогда что дальше? Заменить sleep на семафор - дело несложной техники, есть какие-то трудности - давайте напишу.
Меня интересует полное решение также и без бесконечного ожидания. Поэтому сначала вам нужно разобраться, почему оно присутствует в вашем коде.
Shamil1,
Цитата Сообщение от Shamil1 Посмотреть сообщение
А мне оно не кажется очевидным. Какой параметр нужно оптимизировать?
Например, время ожидания для каждого поезда и сложность решения. Вообще, не понимаю, с какой целью вы всё это спрашиваете. Тут не нужно ничего сверхъестественного, уже есть два примера кода, надо лишь сделать аналогично.
Fulcrum_013,
Цитата Сообщение от Fulcrum_013 Посмотреть сообщение
Прошел с востока - пустили всю скопившуюся пачку с запада, подошедшие новые западные при этом ставятся в очередь. Западные освободили рельсы - тут же пустили пачку скопившуюся за это время пачку на востоке.
Мой вариант примерно так и работает. В любом случае нужно написать код.
0
Модератор
2961 / 2100 / 450
Регистрация: 26.03.2015
Сообщений: 8,153
23.02.2016, 12:57 19
Цитата Сообщение от noski Посмотреть сообщение
Вообще, не понимаю, с какой целью вы всё это спрашиваете.
Потому что Вы пишите "запрограммируйте мне (любой) алгоритм". Кто-то тратит время, программирует, а Вы в ответ: "такой алгоритм мне не нужен (любой, но не такой же!)". Или это не Ваши проблемы, а проблемы тех, кто откликнется на Вашу просьбу помочь?

Цитата Сообщение от noski Посмотреть сообщение
уже есть два примера кода, надо лишь сделать аналогично
Есть два примера кода, делающий разные вещи. Как можно написать "аналогично"?

Кроме того, Ваш код нельзя запустить, чтобы посмотреть, что он делает. Я не знаю, из какой библиотеки у Вас Semaphore, но естественно предположить, что в конструкторе передаём макс количество одновременных "захватов". И значит, Ваши поезда будут идти по-очереди - то есть, следующий восточный поезд будет ждать, когда пройдёт предыдущий восточный поезд (и освободит lock). Я не утверждаю, а просто предположил.
0
1 / 1 / 0
Регистрация: 21.02.2016
Сообщений: 27
23.02.2016, 13:21  [ТС] 20
Shamil1,
Цитата Сообщение от Shamil1 Посмотреть сообщение
Потому что Вы пишите "запрограммируйте мне (любой) алгоритм". Кто-то тратит время, программирует, а Вы в ответ: "такой алгоритм мне не нужен (любой, но не такой же!)"
Просто вы спрашиваете про очевидные, на мой взгляд, вещи. Вот, например, Igor3D сразу меня понял без этих странных вопросов.
Цитата Сообщение от Shamil1 Посмотреть сообщение
Есть два примера кода, делающий разные вещи
У них есть и общее, это я и имел в виду. Мне кажется, вы притворяетесь, что этого не видите.
Цитата Сообщение от Shamil1 Посмотреть сообщение
Кроме того, Ваш код нельзя запустить, чтобы посмотреть, что он делает.
Если адаптировать к какому-либо языку программирования, то будет можно. Впрочем, это не важно.
Цитата Сообщение от Shamil1 Посмотреть сообщение
но естественно предположить, что в конструкторе передаём макс количество одновременных "захватов"
Да, так и есть.
Цитата Сообщение от Shamil1 Посмотреть сообщение
И значит, Ваши поезда будут идти по-очереди - то есть, следующий восточный поезд будет ждать, когда пройдёт предыдущий восточный поезд (и освободит lock). Я не утверждаю, а просто предположил.
Лучше сначала прочитать код, а потом уже что-то предполагать. Семафор lock инициализирован единицей, один раз его можно захватить без ожидания.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
23.02.2016, 13:21
Помогаю со студенческими работами здесь

Пример программы с семафорами
Всем привет. Нужен пример программы с симафорами. Поможете? Или обьясните чо ето такое)

Написать программу с семафорами которая входит в критическую секцию
На дом задали такую домашку "написать программу с семафорами которая входит в критическую секцию"....


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru