Форум программистов, компьютерный форум, киберфорум
Алгоритмы
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск  
 
 
Рейтинг 4.76/21: Рейтинг темы: голосов - 21, средняя оценка - 4.76
1 / 1 / 0
Регистрация: 21.02.2016
Сообщений: 27

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

21.02.2016, 20:36. Показов 4714. Ответов 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
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
21.02.2016, 20:36
Ответы с готовыми решениями:

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

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

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

33
1979 / 835 / 115
Регистрация: 01.10.2012
Сообщений: 5,179
Записей в блоге: 2
23.02.2016, 13:33
Студворк — интернет-сервис помощи студентам
Цитата Сообщение от noski Посмотреть сообщение
В том-то и дело, что если будет много поездов в одном направлении (пусть тогда AB=1), тогда, как я уже написал, новые поезда будут постоянно увеличивать numTrain, но не будут «успевать» уменьшать эту переменную до 0. То есть, другими словами, новые поезда будут приходить быстрее, чем завершаться старые.
И поэтому Вы останавливаете посылку восточных поездов если есть хоть один западный? Такое лекарство может оказаться хуже болезни, если на обоих концах скопилось какое-то кол-во поездов - будет посылаться по 1-2 поезда в один конец, пропускная способность резко упадет. Предлагаю переформулировать задачу напр так
Наблюдатель в A должен дождаться поезда из B за время не превышающее T * K где
T - время поезда в пути
K - задаваемая константа
А то развели тут "как только появился", "посылаем пачку" и.т.п.
Цитата Сообщение от noski Посмотреть сообщение
Поэтому сначала вам нужно разобраться,
А Вам неплохо бы сначала разобраться как обойтись одним примитивом синхронизации вместо пяти. Да и код писать хоть как-то поприличнее. А потом уж давать указания другим
0
1 / 1 / 0
Регистрация: 21.02.2016
Сообщений: 27
23.02.2016, 13:56  [ТС]
Цитата Сообщение от Igor3D Посмотреть сообщение
если на обоих концах скопилось какое-то кол-во поездов - будет посылаться по 1-2 поезда в один конец, пропускная способность резко упадет
Мне кажется, это не так. Пока доступ к поездам допустим, с востока на запад, закрыт, они ждут не на e_turnstile, а на мьютексе и один на семафоре lock. Как только семафор lock отпускается они сразу все проходят. Потом уже, в худшем случае, в «западном» потоке закрывается e_turnstile, но западные поезда ждут на тех же симметричных семафорах. И так далее. То есть поезда проходят «пачками». В любом случае, бесконечное ожидание отсутствует.
Цитата Сообщение от Igor3D Посмотреть сообщение
Предлагаю переформулировать задачу
И зачем это делать?
Цитата Сообщение от Igor3D Посмотреть сообщение
А Вам неплохо бы сначала разобраться как обойтись одним примитивом синхронизации вместо пяти
... и получить код, который не является решением? Опять же зачем?
Цитата Сообщение от Igor3D Посмотреть сообщение
Да и код писать хоть как-то поприличнее
А что в нём «неприличного»?
0
Модератор
Эксперт функциональных языков программирования
3141 / 2289 / 469
Регистрация: 26.03.2015
Сообщений: 8,912
23.02.2016, 15:14
Цитата Сообщение от noski Посмотреть сообщение
Вот, например, Igor3D сразу меня понял без этих странных вопросов.
Не думаю.
Вы имели ввиду алгоритм, который описал Fulcrum_013.
Igor3D же считает Вашу постановку задачи "куда более простой".
Просто Igor3D не такой формалист, как я, и готов гадать решать задачи, у которых нет строгой формулировки.

Цитата Сообщение от noski Посмотреть сообщение
Лучше сначала прочитать код, а потом уже что-то предполагать. Семафор lock инициализирован единицей, один раз его можно захватить без ожидания.
Код я прочитал, но недостаточно внимательно. Я упустил из виду, что lock захватывается не каждым поездом.
Теперь я вижу, что Ваш вариант работает так, как описал Fulcrum_013. (то есть, я предположил неправильно)

Цитата Сообщение от noski Посмотреть сообщение
Впрочем, это не важно.
Свой вопрос можно оформить по-разному. Можно так, чтобы было проще себе. А можно так, чтобы было удобней тому, кто будет на него отвечать.

Например, Вы могли:
Привести алгоритм, который Вы хотите реализовать (то, что написал Fulcrum_013).
Привести код, который можно запустить (например, в идеале - дополнительно дать ссылку на ideone.com).
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
void Main()
{
    Random rnd = new Random();
    for(int i = 0; i < 10; i++)
    {
        new Train(rnd.Next(2) == 0);
        Thread.Sleep(500);
    }
    
    Console.Read();
}
 
// Define other methods and classes here
class Railway
{
    public static Semaphore lock1 = new Semaphore(1, 1);
}
 
class Train
{
    static Semaphore w_turnstile = new Semaphore(1, 1);
    static Semaphore w_mutex = new Semaphore(1, 1);
    static int w_counter = 0;
    static Semaphore e_turnstile = new Semaphore(1, 1);
    static Semaphore e_mutex = new Semaphore(1, 1);
    static int e_counter = 0;
 
    bool West;
    public Thread Thrd;
    
    public Train(bool west)
    {
        West = west;
        Thrd = new Thread(this.Run);
        Thrd.Name = west ? "запад" : "восток";
        Thrd.Start();
    }
    
    private Semaphore turnstile { get { return West ? w_turnstile : e_turnstile; } }
    private Semaphore turnstile2 { get { return West ? e_turnstile : w_turnstile; } }
    private Semaphore mutex { get { return West ? w_mutex : e_mutex; } }
    private int counter { get { return West ? w_counter : e_counter; } }
    
    private void Inc()
    {
        if(West) w_counter++; else e_counter++;
    }
    
    private void Dec()
    {
        if(West) w_counter--; else e_counter--;
    }
    
    
    void Run()
    {
        Console.WriteLine("- Подошёл поезд на {0}", Thrd.Name);
    
        turnstile.WaitOne();
        turnstile.Release();
     
        mutex.WaitOne();
        Inc();
        if(counter == 1)
        {
            turnstile2.WaitOne();
            Railway.lock1.WaitOne();
            Console.WriteLine("! Стрелка на {0}", Thrd.Name);
            turnstile2.Release();
        }
        mutex.Release();
 
        //движение поезда
        Console.WriteLine("( Едет поезд на {0} ({1})", Thrd.Name, counter);
        Thread.Sleep(1000);
 
        mutex.WaitOne();
        Dec();
        if(counter == 0)
        {
            Railway.lock1.Release();
        }
        mutex.Release();    
        Console.WriteLine(") Проехал поезд на {0}  ({1})", Thrd.Name, counter);
    }
}
Код работает. Только в условии задачи "Используя семафоры", а у Вас используются исключительно мьютексы (Semaphore(1) - это, по сути, мьютекс).

Добавлено через 1 минуту
Фактически, в Вашем коде поезда проходят в том порядке, в котором они подошли.
0
1 / 1 / 0
Регистрация: 21.02.2016
Сообщений: 27
23.02.2016, 16:00  [ТС]
Цитата Сообщение от Shamil1 Посмотреть сообщение
Привести алгоритм, который Вы хотите реализовать (то, что написал Fulcrum_013).
По-моему, я написал примерно то же самое:
Цитата Сообщение от noski Посмотреть сообщение
Бесконечное ожидание отсутствует из-за того, что когда появляется, допустим, поезд c востока на запад, он уменьшает значение семафора w_turnstile, и новые поезда с запада на восток ждут на этом семафоре и не могут увеличить счётчик w_counter, а старые поезда прийти могут, то есть в итоге lock будет отпущен
Мне кажется, вместе с кодом это куда понятнее. И я вообще не уверен, что Fulcrum_013 имел в виду именно этот алгоритм.
Цитата Сообщение от Shamil1 Посмотреть сообщение
Привести код, который можно запустить
Спасибо за код, конечно, но я не вижу в этом никакого смысла. Ошибки в многопоточном приложении он все равно отловить не сможет, на своём опыте знаю, что бывают ошибки, которые появляются раз в час, а то и реже, и при особых условиях. Необходим анализ кода в уме и на бумаге. А это можно сделать и с кодом, который я привёл. Тем более, в нём нет ничего лишнего, как в вашем, а значит, его понять проще и быстрее.
Цитата Сообщение от Shamil1 Посмотреть сообщение
Только в условии задачи "Используя семафоры", а у Вас используются исключительно мьютексы (Semaphore(1) - это, по сути, мьютекс)
Только по сути (если не учитывать контроль на тем, какой поток может освободить мьютекс). А так ведь это семафоры. Условия «использовать хотя бы один недвоичный семафор» в задаче нет.
Цитата Сообщение от Shamil1 Посмотреть сообщение
Фактически, в Вашем коде поезда проходят в том порядке, в котором они подошли
Если поставить другую задержку (10), вывод будет совсем другой. Опять же, особенности реализации. Ещё одна причина, по которой реальный код не нужен.
0
Модератор
Эксперт функциональных языков программирования
3141 / 2289 / 469
Регистрация: 26.03.2015
Сообщений: 8,912
23.02.2016, 16:20
Цитата Сообщение от noski Посмотреть сообщение
По-моему, я написал примерно то же самое:
Нет. Это не то же самое. Существуют другие способы избежать бесконечного ожидания.

Цитата Сообщение от noski Посмотреть сообщение
Необходим анализ кода в уме и на бумаге. А это можно сделать и с кодом, который я привёл.
Код, который можно запустить, анализировать гораздо проще, чем "гипотетический" код.

Цитата Сообщение от noski Посмотреть сообщение
Если поставить другую задержку (10), вывод будет совсем другой.
Пусть сейчас едут поезда с запада и нет поездов с востока.
Если пришёл поезд с запада, то он поедет сразу за всеми поездами, которые едут с запада, то есть, в "порядке живой очереди".
Если пришёл поезд с востока, то он захватит "чужой" turnstile и будет ждать lock. То есть, он проедет после того, как проедут все поезда с запада, которые подошли раньше него. Но не даст проехать ни одному поезду с запада, которые приедут после него (они будут ждать свой turnstile). То есть, опять "порядке живой очереди".

Цитата Сообщение от noski Посмотреть сообщение
А так ведь это семафоры.
Конечно, всегда можно назвать мьютекс семафором (ведь мьютекс, это частный случай светофора).
Предположу, что задачу нужно решить с использованием семафоров и без использования counter.

Добавлено через 2 минуты
Цитата Сообщение от noski Посмотреть сообщение
Спасибо за код, конечно, но я не вижу в этом никакого смысла.
Смысла нет. Просто уважение к тем, кому задаёте вопрос. У Вас два варианта - сэкономить своё время за счёт времени отвечающих или наоборот. Каждый выбирает для себя сам.
0
1 / 1 / 0
Регистрация: 21.02.2016
Сообщений: 27
23.02.2016, 17:02  [ТС]
Цитата Сообщение от Shamil1 Посмотреть сообщение
Нет. Это не то же самое. Существуют другие способы избежать бесконечного ожидания.
Речь идёт о моём алгоритме. Тут же один способ.
Цитата Сообщение от Shamil1 Посмотреть сообщение
Код, который можно запустить, анализировать гораздо проще, чем "гипотетический" код.
По-моему, очень спорно.
Цитата Сообщение от Shamil1 Посмотреть сообщение
Но не даст проехать ни одному поезду с запада, которые приедут после него
А если приехал сначала поезд с запада, а потом с востока? Тогда вроде бы сначала приедет поезд с востока. И вообще, потоки же могут прерваться в любой момент, кроме того семафор (в теории) не гарантирует какого-либо порядка возобновления потоков. Тут, кстати, очевидно, возникает проблема в моём алгоритме... Правда, условие задачи довольно обтекаемо:
Цитата Сообщение от noski Посмотреть сообщение
в любой момент времени по единственному пути поезда двигались только в одном направлении
То есть, видимо, поезда могут друг друга обгонять.
Цитата Сообщение от Shamil1 Посмотреть сообщение
Смысла нет. Просто уважение к тем, кому задаёте вопрос.
Разве здесь не противоречие? Если в реальном коде нет смысла, то зачем его тогда вообще писать?
0
Модератор
Эксперт функциональных языков программирования
3141 / 2289 / 469
Регистрация: 26.03.2015
Сообщений: 8,912
23.02.2016, 17:53
Цитата Сообщение от noski Посмотреть сообщение
Речь идёт о моём алгоритме.
Вы же не привели свой алгоритм. Поэтому про Ваш алгоритм на тот момент могли знать только телепаты.

Цитата Сообщение от noski Посмотреть сообщение
По-моему, очень спорно.
На самом деле, бесспорно. Для анализа кода, который нельзя выводить, нужно все действия/подсчёты производить в уме (при этом помнить значения всех переменных и т.д.). Если запустить код под отладчиком, то эту рутинную работу можно доверить компьютеру.

Цитата Сообщение от noski Посмотреть сообщение
А если приехал сначала поезд с запада, а потом с востока?
У Вас есть код (мой). Просто напишите функцию main таким образом, чтобы поезд, который пришёл раньше, проехал позже (создавайте "поезда" не в цикле по рандному, а вручную). Вам это не сложно, если Вы придумали такую ситуацию. Это будет убедительнее любых слов.

Цитата Сообщение от noski Посмотреть сообщение
Если в реальном коде нет смысла
В реальном коде есть смысл - см. выше.
0
 Аватар для Fulcrum_013
2083 / 1576 / 169
Регистрация: 14.12.2014
Сообщений: 13,614
24.02.2016, 02:56
Цитата Сообщение от noski Посмотреть сообщение
Мой вариант примерно так и работает. В любом случае нужно написать код.
Самый простой способ это реализовать - семафор сигпализирующий "путь занят" и очередь поездов в common области памяти
0
1 / 1 / 0
Регистрация: 21.02.2016
Сообщений: 27
24.02.2016, 07:06  [ТС]
Shamil1,
Цитата Сообщение от Shamil1 Посмотреть сообщение
Вы же не привели свой алгоритм. Поэтому про Ваш алгоритм на тот момент могли знать только телепаты.
Простой код с пояснением — это и есть описание алгоритма.
Цитата Сообщение от Shamil1 Посмотреть сообщение
Для анализа кода, который нельзя выводить, нужно все действия/подсчёты производить в уме
Не так уж и много расчётов в данном случае. Вообще, можно использовать ручку и бумагу. Все равно это придётся делать, так как реальный код не покрывает всех возможных ситуаций.
Цитата Сообщение от Shamil1 Посмотреть сообщение
У Вас есть код (мой). Просто напишите функцию main таким образом, чтобы поезд, который пришёл раньше, проехал позже (создавайте "поезда" не в цикле по рандному, а вручную). Вам это не сложно, если Вы придумали такую ситуацию. Это будет убедительнее любых слов.
Это неправильный подход. Возможно, что какую-либо ситуацию смоделировать трудно. Да и при подробном объяснении на словах сразу понятно, почему так происходит. В данном случае, потому что новые восточные поезда ждут на e_mutex и на lock, как только lock отпускается, они сразу все проходят. Исходя из этого уже можно написать код:
C#
1
2
3
4
5
6
new Train(true);
new Train(true);
Thread.Sleep(100);
new Train(false);
new Train(true);
new Train(false);
Добавлено через 7 минут
http://ideone.com/w8AGc4
0
1979 / 835 / 115
Регистрация: 01.10.2012
Сообщений: 5,179
Записей в блоге: 2
24.02.2016, 09:11
Цитата Сообщение от noski Посмотреть сообщение
Ошибки в многопоточном приложении он все равно отловить не сможет, на своём опыте знаю, что бывают ошибки, которые появляются раз в час, а то и реже, и при особых условиях. Необходим анализ кода в уме и на бумаге. А это можно сделать и с кодом, который я привёл. Тем более, в нём нет ничего лишнего, как в вашем, а значит, его понять проще и быстрее.
Беда в том что Вы написали мозголомную конструкцию которая уже сожрала массу Вашего времени и будет жрать еще. Поэтому не нужно тратить время на ее анализ, попробуйте отвлечься и поискать в др направлении. Понимаю что советовать легче чем отказаться от своего кода , но все же

Пусть Вашего кода нет, только условие. Что тут военного? Да ничего, псевдокод
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void Process1Train( int direction )
{
 Semaphore sem;  // на этом семафоре поезд будет ждать
 
 while (true)
  mutex.lock();
  bool go = ShouldTrainGo(direction);   // решаем можно ли ехать под защитой мутекса
  if (go) numTrain += direction;   // обновляем счетик едущих
  mutex.unlock();
 
  if (go) break;
  else PutTrainInSleep(direction, &semaphore);   // нельзя ехать, спим
 } 
 
 MoveTrain();    // едем
 
  mutex.lock();
  numTrain -= direction;
  if (!numTrain)
   WakeUpTrains(direction);   // будим спящие поезда под защитой мутекса
  mutex.unlock();
}
Вот собсно "схема" фактически с одним мутексом, не нужны никакие тонны семафоров и симметричные варианты.

Разберемся с усыплением/побудкой поездов. Я бы сделал так
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
vector <Semaphore *> waitSem[2];
 
void PutTrainInSleep( int direction,  Semaphore * sem )
{
 int index = (direction > 0) ? 0 : 1;
 waitSem[index].push_back(sem);   // пополняем контейнер ждущих в напр-и direction
 sem->acquire();  // засыпаем
}
 
void WakeUpTrains( int direction )
{
  int invIndex = (direction > 0) ? 1 : 0;
  for (size_t i = 0; i < waitSem[invIndex].size(); ++i)
   waitSem[invIndex][i]->release();
 
  waitSem[index].clear();
}
Осталось лишь реализовать ShouldTrainGo. На мой взгляд, Ваша ошибка в реализации этого места "на семафорах" - а это совершенно не нужно. Просто заводите какие-то переменные и на основании их решаете "ехать или спать". Т.е. ShouldTrainGo выполняется под мутексом и больше никаких примитивов синхронизации не требует. Напр хотите "как у Вас сейчас" - на здоровье
C++
1
2
3
4
5
6
7
bool ShouldTrainGo( int direction )
{
  if (numTrain * direction < 0) return false;  // едут в др напр-и, только спать
  if (numTrain == 0) return true;         // никого нет, едем  
  int invIndex = (direction > 0) ? 1 : 0;
  return waitSem[invIndex] == 0;       // едем только если нет ждущих на др стороне
}
Хотя по-моему это решение худшее.

Итого: все цивильно, в любой момент времени мы можем знать сколько куда едет и сколько где ждет

Не по теме:

Ну вот, сейчас опять начнет "носик воротить" ("меня интересует" и все такое). Не, пошел, устал с таким :)



Добавлено через 30 минут
Ошибка: push_back должно выполняться по мутексом, (а acquire нет). Ну ничего, подправит
0
1 / 1 / 0
Регистрация: 21.02.2016
Сообщений: 27
24.02.2016, 11:18  [ТС]
Цитата Сообщение от Igor3D Посмотреть сообщение
Беда в том что Вы написали мозголомную конструкцию которая уже сожрала массу Вашего времени и будет жрать еще.
Неправда, совсем немного. Куда больше времени заняли разговоры на этом форуме, например, объяснение вам очевидных вещей. Я думал, здесь куда более опытные программисты. Если честно, уже сто раз пожалел, что задал тут вопрос.
Цитата Сообщение от Igor3D Посмотреть сообщение
Вот собсно "схема" фактически с одним мутексом, не нужны никакие тонны семафоров и симметричные варианты.
Мне кажется, вы меня троллите. У меня всего пять семафоров (при желании, думаю, можно сделать один мьютекс на два вида потоков), а у вас мьютекс, семафор в каждом потоке, два вектора семафоров и куда больше кода. Симметричные варианты нужны лишь для упрощения, у Shamil1 код без них, правда, на мой взгляд, так сложнее для понимания.

В любом случае, спасибо за решение. Правда, мне кажется, если будет много поездов с обеих сторон, они будут проходить по очереди. Дело в том, что поезда того же направления также «попадают» в свой вектор. Когда пробуждаются потоки противоположного направления, первый-то проходит (numTrain == 0), но следующие ждут из-за waitSem[invIndex] == 0. Ждут — то есть их семафоры помещаются в свой вектор, потом пробуждаются потоки противоположного направления и так далее. Может, что-то ещё есть, надо подумать...
Цитата Сообщение от Igor3D Посмотреть сообщение
Не, пошел, устал с таким
Цитата Сообщение от Igor3D Посмотреть сообщение
Ошибка: push_back должно выполняться по мутексом, (а acquire нет). Ну ничего, подправит
С возвращением!

Добавлено через 47 минут
Ещё одна интересная особенность. Пусть сейчас едут западные поезда. Потом восточный поезд прерывается на 10 строке в первом блоке кода, сразу после мьютекса. Пусть все западные поезда приходят и новых нет. Последний поток освобождает все восточные поезда. Тут возобновляется прерванный восточный поезд и добавляет себя в пустой вектор. Если теперь будут идти только восточные поезда, то этот рассматриваемый поезд никогда не проедет!
0
1979 / 835 / 115
Регистрация: 01.10.2012
Сообщений: 5,179
Записей в блоге: 2
24.02.2016, 12:10
Цитата Сообщение от noski Посмотреть сообщение
Я думал, здесь куда более опытные программисты. Если честно, уже сто раз пожалел, что задал тут вопрос.
Это классика, здесь где-то есть замечательный пост с примерным названием "как НЕ получить ответ". Оттуда по памяти
Я думал тут умеют решать, а здесь такие же бараны как я

Цитата Сообщение от noski Посмотреть сообщение
Неправда, совсем немного.
Ну не надо такое фуфло парить дедушке
Цитата Сообщение от noski Посмотреть сообщение
Куда больше времени заняли разговоры на этом форуме, например, объяснение вам очевидных вещей
Сами виноваты (что впрочем простительно при малом опыте на форумах). Вы употребляете термины значение которых Вам очевидно. Напр "бесконечное ожидание" - но это может оказаться загадкой для других, напр меня.

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

Цитата Сообщение от noski Посмотреть сообщение
Правда, мне кажется, если будет много поездов с обеих сторон, они будут проходить по очереди. Дело в том, что поезда того же направления также «попадают» в свой вектор. Когда пробуждаются потоки противоположного направления, первый-то проходит (numTrain == 0), но следующие ждут из-за waitSem[invIndex] == 0. Ждут — то есть их семафоры помещаются в свой вектор, потом пробуждаются потоки противоположного направления и так далее. Может, что-то ещё есть, надо подумать...
Хотите "пропустить всю пачку" - тогда напр так
C++
1
return awaken || (waitSem[invIndex] == 0);       // едем  если проснулись или нет ждущих на др стороне, awaken объявляется там же где и semaphore
Но мне это не кажется хорошим. По существу Ваше "как только появился поезд на др стороне" означает "максимальное время ожидания поезда в A равно 2 * время в пути" (конечно если этот поезд есть в B). Меньше 2 не получится, но это наихудший вариант для производительности. Но больше-то можно - ну и сделайте его явным параметром. Фиксируйте время когда добавляется первый эл-т вектора семафоров и ShouldTrainGo просто вычисляйте "пора или нет".
Цитата Сообщение от noski Посмотреть сообщение
И зачем это делать?
Ну почему доходит как до жирафа?

Добавлено через 5 минут
Цитата Сообщение от noski Посмотреть сообщение
Тут возобновляется прерванный восточный поезд и добавляет себя в пустой вектор.
Чего ж он себя добавит если западных уже нет?
0
1 / 1 / 0
Регистрация: 21.02.2016
Сообщений: 27
24.02.2016, 13:30  [ТС]
Цитата Сообщение от Igor3D Посмотреть сообщение
Это классика, здесь где-то есть замечательный пост с примерным названием "как НЕ получить ответ"
Ну и что? Адекватных возражений-то ни там, ни у вас нет. Да и написал я несколько по-другому. И вообще, что-то мне подсказывает, что лучшего решения, чем у меня я и так не получу...
Цитата Сообщение от Igor3D Посмотреть сообщение
Ну не надо такое фуфло парить дедушке
Мало того, что вы что-то там себе нафантазировали, так ещё твёрдо уверены в своей фантазии даже после опровержения...
Цитата Сообщение от Igor3D Посмотреть сообщение
что впрочем простительно при малом опыте на форумах
Ещё одна ничем не обоснованная фантазия.
Цитата Сообщение от Igor3D Посмотреть сообщение
Вы употребляете термины значение которых Вам очевидно. Напр "бесконечное ожидание" - но это может оказаться загадкой для других, напр меня
Обычно, если что-то непонятно в вопросе, нужно поискать в интернете, или, в худшем случае, спросить в теме, прежде чем отвечать.
Цитата Сообщение от Igor3D Посмотреть сообщение
Не нужно говорить "меня интересует полное решение", это разговор заказчика с исполнителем
Потому что вы так сказали? Наоборот, лучше уточнить требования к ответу.
Цитата Сообщение от Igor3D Посмотреть сообщение
В большинстве случаев не нужно показывать свой код
То же самое.
Цитата Сообщение от Igor3D Посмотреть сообщение
тем более доказывать что он лучше
Забавно то, что вы сами это делаете.
Цитата Сообщение от Igor3D Посмотреть сообщение
Ну почему доходит как до жирафа?
Печально, на старости лет вы так и не научились элементарной вежливости, судя по этому оскорблению.
Цитата Сообщение от Igor3D Посмотреть сообщение
Хотите "пропустить всю пачку" - тогда напр так
Лучше написать все участки исправленного кода, чтобы избежать недоразумений. Нельзя сказать однозначно, где происходит работа с переменной awaken. И что насчёт последнего замечания про бесконечное ожидание?
Цитата Сообщение от Igor3D Посмотреть сообщение
но это наихудший вариант для производительности
Лучше, чем бесконечное ожидание.

Добавлено через 3 минуты
Цитата Сообщение от Igor3D Посмотреть сообщение
Сами виноваты
Не согласен, вы могли бы сразу понять про бесконечное ожидание.

Добавлено через 18 минут
Цитата Сообщение от Igor3D Посмотреть сообщение
Чего ж он себя добавит если западных уже нет?
Извиняюсь, сразу не заметил. Он получит значение go, когда они ещё будут, потом прервётся, потом западные завершатся, и тогда он себя добавит.
0
1979 / 835 / 115
Регистрация: 01.10.2012
Сообщений: 5,179
Записей в блоге: 2
25.02.2016, 04:11
Вот полный, почищенный текст, компилится. Более четкий "пуск пачки". Добавил управление (см комментарии)
Кликните здесь для просмотра всего текста
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include <QMutex>
#include <QSemaphore>
#include <QVector>
#include <QTime>
#include <QThread>
 
QMutex mutex;
 
int numGoing = 0;           // число едущих поездов
int numAwake = 0;           // число проснувшихся поездов
int travelTime = 100;       // время поезда в пути
float waitFactor = 1.0;     // коэффициент ожидания (имеет эффект если > 2)
QTime waitStart[2];         // время когда поезд ушел спать
 
typedef QVector <QSemaphore *> TSemVec;
TSemVec waitSem[2];
 
bool ShouldTrainGo( int direction, bool awaken )
{
    if (numGoing * direction < 0) return false; // едут в др напр-и, спать
    if (numAwake * direction < 0) return false; // не все еще пошли в др напр-и, спать 
    if (numAwake) {   // пропускаем проснувшихся (и тех кто успел)
        if (awaken) 
            numAwake -= direction;
        return true;
    }
 
    if (!numGoing) return true;  // никого нет, едем
    
    int invIndex = (direction > 0) ? 1 : 0;
    if (waitSem[invIndex].size()) {        // есть ждущие на др стороне
#if 1
        // если сейчас пустим из А - когда дождемся из B  
        QTime arriveTime = QTime::currentTime();
        arriveTime.addMSecs(travelTime * 2);
 
        // вычисляем время от прибытия в B до прибытия в A
        int totalWeight = waitStart[invIndex].msecsTo(arriveTime);
 
        // сравниваем с пределом
        if (totalWeight > travelTime * waitFactor) return false;
#else
        return false;
#endif
    }
    return true;
}
 
void PrepareWait( int direction, QSemaphore * sem )
{
    int index = (direction > 0) ? 0 : 1;
    waitSem[index].push_back(sem);
    if (waitSem[index].size() == 1)
        waitStart[index].start();
}
 
void WakeUpTrains( int direction )
{
    int invIndex = (direction > 0) ? 1 : 0;
    for (int i = 0; i < waitSem[invIndex].size(); ++i)
        waitSem[invIndex][i]->release();
 
    numAwake = waitSem[invIndex].size() * direction; // сохраняем число разбуженных
    waitSem[invIndex].clear();
}
 
void MoveTrain( void )
{
    QThread::msleep(travelTime);
}
 
void Process1Train( int direction )
{
    QSemaphore sem;       // на этом семафоре поезд будет ждать
    bool awaken = false;  // truе если поезд спал
 
    while (true) {
        mutex.lock();
        bool go = ShouldTrainGo(direction, awaken);   // решаем можно ли ехать под защитой мутекса
        if (go) 
            numGoing += direction;   // обновляем счетик едущих
        else {
            awaken = true;
            PrepareWait(direction, &sem);
        }
        mutex.unlock();
 
        if (go) 
            break;
        else 
            sem.acquire();   // нельзя ехать, спим
    } 
 
    MoveTrain();    // едем
 
    mutex.lock();
    numGoing -= direction;
    if (!numGoing)
        WakeUpTrains(direction);   // будим спящие поезда под защитой мутекса
    mutex.unlock();
}
Да, интересная оказалась задачка, решал с удовольствием
1
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
25.02.2016, 04:11

Пул потоков с семафорами
Задача:написать свой пуль потоков Написал вот такой код #include &lt;windows.h&gt; #include &quot;Worker.h&quot; #include&lt;list&gt; ...

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

Написать программу с семафорами которая входит в критическую секцию
На дом задали такую домашку &quot;написать программу с семафорами которая входит в критическую секцию&quot;. Препод сказал по своему желанию её...


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

Или воспользуйтесь поиском по форуму:
34
Ответ Создать тему
Новые блоги и статьи
Запрет дублирования строк в табличной части
Maks 13.09.2026
Реализация из решения ниже выполнена на нетиповом справочнике "Нормы ТО" с табличной часть "Виды ТО", разработанного в КА2, со следующими реквизитами: - ВидТО (СправочникСсылка. ВидыТО); - ВидГСМ. . .
Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр.
Jin X 06.09.2026
Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр. Работая с форумом и нейросетями в браузере часто хочется что-то подкорректировать или добавить какого-то функционала. Ниже прикреплён. . .
Программа опроса у.з. расходомера SLS-720F
Argus19 02.09.2026
Программа опроса у. з. расходомера SLS-720F Программа опрашивает один раз в минуту три ультразвуковых расходомера SLS-720F через интерфейс RS-485 по протоколу Modbus RTU. Опрашиваются регистры. . .
Hyper-V: Компьютер должен поддерживать доверенный платформенный модуль 2.0.
Maks 31.08.2026
При установке Windows 11 на виртуальную машину Hyper-V 2-го поколения вылезла такая ошибка: Решение: в параметрах виртуальной машины, в разделе "Безопасность" (Security) активировать флаг. . .
Архитектура биовида Стива в Майнкрафте: Зачем бонобо кубический каннибализм
anaschu 30.08.2026
Кубический Вагинокапитализм в Minecraft: Математический инвариант ОДУ и рок Стивов-бонобо Главная задача разработанной «Модели Всего» — наглядно продемонстрировать наличие системной «судьбы». . .
Оттачиваю умение писать js программы.
russiannick 30.08.2026
Проектом выходного дня стало написание Книги шифров Виженера. Итогом стала версия 200, синий туман. Синий туман назван так, потому что замораживает текст под собой. Нажатие синих кнопок управляют. . .
мат медиц модель 30. презентация проекта
anaschu 27.08.2026
хоп хоп хоп хидахоп, а я кладую))
Как у меня протекала болезнь
zorxor 27.08.2026
Здравствуйте, друзья! Эта запись блога предназначена именно для вас - для моих дорогих друзей, которые знали меня лично. Чтобы ответить на вопрос - а что же со мной произошло на самом деле? Я учился. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru