C 中带有信号量的死锁
Deadlocks in C with semaphores
我有一个关于 Dining Philosophers 程序死锁的作业。我被要求创建一个名为 "sections1.c" 的文件，该文件存在死锁问题，在完成创建死锁后，我将复制代码并解决文件 "sections2.c" 中的死锁情况。我的老师让我们用 MDAT 编程。 MDAT 应该 运行 就像他在 MDAT 指南中给我们的信号量和 pthread 函数一样。
void mdat_mutex_init(const char *name, pthread_mutex_t *lock,
pthread_mutexattr_t *attr);
void mdat_mutex_lock(pthread_mutex_t *lp);
void mdat_mutex_unlock(pthread_mutex_t *lp);
void mdat_sem_init(const char *name, sem_t *sem, int pshared, int value);
void mdat_sem_wait(sem_t *sp);
void mdat_sem_post(sem_t *sp);
MDAT 应该负责调度程序，并通过在 运行.
时播种当前时间来随机调度线程
在不允许我编辑的主文件中，函数 sectionInitGlobals 运行s 一次和 sectionRunPhilosopher 运行s 一次，每个 pthread_create.
一个问题可能是我以前从未使用过信号量，并且使用不正确。
// sections1.c: mutual exclusion model sections
#include <stdio.h>
#include <errno.h>
#include <stdlib.h>
#include <pthread.h>
#include <semaphore.h>
#include "sections.h"
#include "mdat.h"
// TODO: Declare shared variables here
int numPhils;
sem_t * sem_arr;
void sectionInitGlobals(int numPhilosophers)
{
// TODO: Complete this function
int i;
char char_arr[50];
sem_t arr[numPhilosophers];
numPhils = numPhilosophers;
for(i = 0; i < numPhilosophers; i++)
{
sprintf(char_arr,"%d", i);
mdat_sem_init(char_arr, &arr[i], 0, 0);
}
sem_arr = arr;
}
void sectionRunPhilosopher(int philosopherID, int numRounds)
{
int lChopstick = philosopherID;
int rChopstick;
int left;
int right;
int i;
int hasEaten;
int hasLeft;
int hasRight;
if(philosopherID == 0)
rChopstick = numPhils - 1;
else
rChopstick = philosopherID - 1;
for(i = 0; i < numRounds; i++)
{
hasEaten = 0;
hasLeft = 0;
hasRight = 0;
while(hasEaten == 0)
{
sem_getvalue(&sem_arr[lChopstick], &left);
if(left >= 0 || hasLeft == 1)
{
hasLeft = 1;
}
else
{
mdat_sem_wait(&sem_arr[lChopstick]);
}
sem_getvalue(&sem_arr[rChopstick], &right);
if(right >= 0 && hasLeft != 0)
{
hasRight = 1;
}
else
{
mdat_sem_wait(&sem_arr[rChopstick]);
}
if(hasLeft != 0 && hasRight != 0)
{
eat();
hasEaten = 1;
mdat_sem_post(&sem_arr[lChopstick]);
mdat_sem_post(&sem_arr[rChopstick]);
}
}
think();
}
}
在测试我的代码时，我得到了 运行 它与我想要的任意数量的线程和回合，但是，似乎有更多线程可以保证死锁。当我 运行 有 100 个线程的代码时，它每次都会陷入死锁，但是线程越多，它陷入死锁的机会就越小吗？
结果：
有 16 个线程和 10 个轮次，有时会出现死锁，具体取决于调度程序。
6 个线程和 5 个轮次，死锁发生率为 0%。
有 100 个线程和 5 个轮次，死锁发生的概率为 100%。
编辑：
未发生死锁且程序认为发生死锁时跟踪文件结束：
无死锁：
THREAD: 3
SECTION: DoneRounds
MESSAGE: Thread 3 has completed
*******************************************************************************
|ID |PROPERTY |LOC |SECTION |STATUS |WAITING ON |
|0 |0 |19 | |completed | |
|1 |1 |19 | |completed | |
|2 |2 |19 | |completed | |
|3 |3 |19 | |completed | |
|4 |4 |19 | |completed | |
|5 |5 |19 | |completed | |
|6 |6 |19 | |completed | |
|7 |7 |19 | |completed | |
|8 |8 |19 | |completed | |
|9 |9 |19 | |completed | |
|10 |10 |19 | |completed | |
|11 |11 |19 | |completed | |
|12 |12 |19 | |completed | |
|13 |13 |19 | |completed | |
|14 |14 |19 | |completed | |
|15 |15 |19 | |completed | |
-------------------------------------------------------------------------------
|LOCK NAME |STATUS |WAITING THREADS |
|lock_a |unlocked | |
|lock_b |unlocked | |
-------------------------------------------------------------------------------
|SEMAPHORE NAME |VALUE |WAITING THREADS |
|0 |20 | |
|1 |20 | |
|2 |20 | |
|3 |20 | |
|4 |20 | |
|5 |20 | |
|6 |20 | |
|7 |20 | |
|8 |20 | |
|9 |20 | |
|10 |20 | |
|11 |20 | |
|12 |20 | |
|13 |20 | |
|14 |20 | |
|15 |20 | |
*******************************************************************************
***** Program Trace End *****
死锁：
THREAD: 13
SECTION: DoneRounds
MESSAGE: Thread 13 has completed
*******************************************************************************
|ID |PROPERTY |LOC |SECTION |STATUS |WAITING ON |
|0 |0 |19 | |completed | |
|1 |1 |32 | |waiting-sem |1 |
|2 |2 |32 | |waiting-sem |2 |
|3 |3 |38 | |waiting-sem |2 |
|4 |4 |19 | |completed | |
|5 |5 |19 | |completed | |
|6 |6 |19 | |completed | |
|7 |7 |19 | |completed | |
|8 |8 |19 | |completed | |
|9 |9 |32 | |waiting-sem |9 |
|10 |10 |38 | |waiting-sem |9 |
|11 |11 |19 | |completed | |
|12 |12 |19 | |completed | |
|13 |13 |19 | |completed | |
|14 |14 |19 | |completed | |
|15 |15 |19 | |completed | |
-------------------------------------------------------------------------------
|LOCK NAME |STATUS |WAITING THREADS |
|lock_a |unlocked | |
|lock_b |unlocked | |
-------------------------------------------------------------------------------
|SEMAPHORE NAME |VALUE |WAITING THREADS |
|0 |10 | |
|1 |-1 |1 |
|2 |-2 |2 3 |
|3 |10 | |
|4 |20 | |
|5 |20 | |
|6 |20 | |
|7 |20 | |
|8 |10 | |
|9 |-2 |9 10 |
|10 |10 | |
|11 |20 | |
|12 |20 | |
|13 |20 | |
|14 |20 | |
|15 |20 | |
*******************************************************************************
ERROR! VIOLATION: No ready threads to schedule - possible DEADLOCK
***** Program Trace End *****
回答后编辑
感谢mevets！
最终代码：
section1.c - 想要死锁
// sections1.c: mutual exclusion model sections
#include <stdio.h>
#include <errno.h>
#include <stdlib.h>
#include <pthread.h>
#include <semaphore.h>
#include "sections.h"
#include "mdat.h"
// TODO: Declare shared variables here
int numPhils;
sem_t * sem_arr;
void sectionInitGlobals(int numPhilosophers)
{
// TODO: Complete this function
int i;
char char_arr[50];
sem_t arr[numPhilosophers];
numPhils = numPhilosophers;
for(i = 0; i < numPhilosophers; i++)
{
sprintf(char_arr,"%d", i);
mdat_sem_init(char_arr, &arr[i], 0, 1);
}
sem_arr = arr;
}
void sectionRunPhilosopher(int philosopherID, int numRounds)
{
int lChop = philosopherID;
int rChop;
int i;
if(philosopherID == 0)
rChop = numPhils - 1;
else
rChop = philosopherID - 1;
for(i = 0; i < numRounds; i++)
{
mdat_sem_wait(&sem_arr[lChop]);
mdat_sem_wait(&sem_arr[rChop]);
eat();
mdat_sem_post(&sem_arr[rChop]);
mdat_sem_post(&sem_arr[lChop]);
think();
}
}
section2.c - 不想死锁
// sections1.c: mutual exclusion model sections
#include <stdio.h>
#include <errno.h>
#include <stdlib.h>
#include <pthread.h>
#include <semaphore.h>
#include "sections.h"
#include "mdat.h"
// TODO: Declare shared variables here
int numPhils;
sem_t * sem_arr;
void sectionInitGlobals(int numPhilosophers)
{
// TODO: Complete this function
int i;
char char_arr[50];
sem_t arr[numPhilosophers];
numPhils = numPhilosophers;
for(i = 0; i < numPhilosophers; i++)
{
sprintf(char_arr,"%d", i);
mdat_sem_init(char_arr, &arr[i], 0, 1);
}
sem_arr = arr;
}
void sectionRunPhilosopher(int philosopherID, int numRounds)
{
int lChop = philosopherID;
int rChop;
int i;
if(philosopherID == 0)
rChop = numPhils - 1;
else
rChop = philosopherID - 1;
for(i = 0; i < numRounds; i++)
{
if(philosopherID != numPhils - 1)
{
mdat_sem_wait(&sem_arr[lChop]);
mdat_sem_wait(&sem_arr[rChop]);
eat();
mdat_sem_post(&sem_arr[rChop]);
mdat_sem_post(&sem_arr[lChop]);
}
else
{
mdat_sem_wait(&sem_arr[rChop]);
mdat_sem_wait(&sem_arr[lChop]);
eat();
mdat_sem_post(&sem_arr[lChop]);
mdat_sem_post(&sem_arr[rChop]);
}
think();
}
}
经典的哲学家就餐问题有N个哲学家和N个叉子；但每个人都需要 2 把叉子才能吃。一个给定的 fork 信号量可能有最大值 1 [available]，和最小值 -1（一个有 fork，一个正在等待 fork）。你的叉子值是 10 和 20?
按照你的逻辑，你检查信号量的值，如果>=0，你说你“有”，然后继续检查另一个；但你没有。在对它进行 wait 操作之前，你没有信号量。在 eat()ing 之后，你 post 给他们两个，即使你可能从来没有等过他们中的任何一个。这就是为什么你的信号量值高得离谱。
其次，当sem_get_value返回时，信号量的值可能已经改变。这是一个常见的同步问题，如此常见它有一个名字：TOCTOU（Time Of Check to Time Of Use）。您需要使用根据操作做出决策的机制，而不仅仅是检查状态。
第三，您将其更改为有效地坐在一个循环中：
sem_wait(left);
sem_wait(right);
eat();
sem_post(right);
sem_post(left);
您将遇到一个完全不同的同步问题，这就是 Dining Philosophers 旨在说明的问题。狩猎愉快！
我有一个关于 Dining Philosophers 程序死锁的作业。我被要求创建一个名为 "sections1.c" 的文件，该文件存在死锁问题，在完成创建死锁后，我将复制代码并解决文件 "sections2.c" 中的死锁情况。我的老师让我们用 MDAT 编程。 MDAT 应该 运行 就像他在 MDAT 指南中给我们的信号量和 pthread 函数一样。
void mdat_mutex_init(const char *name, pthread_mutex_t *lock,
pthread_mutexattr_t *attr);
void mdat_mutex_lock(pthread_mutex_t *lp);
void mdat_mutex_unlock(pthread_mutex_t *lp);
void mdat_sem_init(const char *name, sem_t *sem, int pshared, int value);
void mdat_sem_wait(sem_t *sp);
void mdat_sem_post(sem_t *sp);
MDAT 应该负责调度程序，并通过在 运行.
时播种当前时间来随机调度线程在不允许我编辑的主文件中，函数 sectionInitGlobals 运行s 一次和 sectionRunPhilosopher 运行s 一次，每个 pthread_create.
一个问题可能是我以前从未使用过信号量，并且使用不正确。
// sections1.c: mutual exclusion model sections
#include <stdio.h>
#include <errno.h>
#include <stdlib.h>
#include <pthread.h>
#include <semaphore.h>
#include "sections.h"
#include "mdat.h"
// TODO: Declare shared variables here
int numPhils;
sem_t * sem_arr;
void sectionInitGlobals(int numPhilosophers)
{
// TODO: Complete this function
int i;
char char_arr[50];
sem_t arr[numPhilosophers];
numPhils = numPhilosophers;
for(i = 0; i < numPhilosophers; i++)
{
sprintf(char_arr,"%d", i);
mdat_sem_init(char_arr, &arr[i], 0, 0);
}
sem_arr = arr;
}
void sectionRunPhilosopher(int philosopherID, int numRounds)
{
int lChopstick = philosopherID;
int rChopstick;
int left;
int right;
int i;
int hasEaten;
int hasLeft;
int hasRight;
if(philosopherID == 0)
rChopstick = numPhils - 1;
else
rChopstick = philosopherID - 1;
for(i = 0; i < numRounds; i++)
{
hasEaten = 0;
hasLeft = 0;
hasRight = 0;
while(hasEaten == 0)
{
sem_getvalue(&sem_arr[lChopstick], &left);
if(left >= 0 || hasLeft == 1)
{
hasLeft = 1;
}
else
{
mdat_sem_wait(&sem_arr[lChopstick]);
}
sem_getvalue(&sem_arr[rChopstick], &right);
if(right >= 0 && hasLeft != 0)
{
hasRight = 1;
}
else
{
mdat_sem_wait(&sem_arr[rChopstick]);
}
if(hasLeft != 0 && hasRight != 0)
{
eat();
hasEaten = 1;
mdat_sem_post(&sem_arr[lChopstick]);
mdat_sem_post(&sem_arr[rChopstick]);
}
}
think();
}
}
在测试我的代码时，我得到了 运行 它与我想要的任意数量的线程和回合，但是，似乎有更多线程可以保证死锁。当我 运行 有 100 个线程的代码时，它每次都会陷入死锁，但是线程越多，它陷入死锁的机会就越小吗？
结果：
有 16 个线程和 10 个轮次，有时会出现死锁，具体取决于调度程序。
6 个线程和 5 个轮次，死锁发生率为 0%。
有 100 个线程和 5 个轮次，死锁发生的概率为 100%。
编辑：
未发生死锁且程序认为发生死锁时跟踪文件结束：
无死锁：
THREAD: 3
SECTION: DoneRounds
MESSAGE: Thread 3 has completed
*******************************************************************************
|ID |PROPERTY |LOC |SECTION |STATUS |WAITING ON |
|0 |0 |19 | |completed | |
|1 |1 |19 | |completed | |
|2 |2 |19 | |completed | |
|3 |3 |19 | |completed | |
|4 |4 |19 | |completed | |
|5 |5 |19 | |completed | |
|6 |6 |19 | |completed | |
|7 |7 |19 | |completed | |
|8 |8 |19 | |completed | |
|9 |9 |19 | |completed | |
|10 |10 |19 | |completed | |
|11 |11 |19 | |completed | |
|12 |12 |19 | |completed | |
|13 |13 |19 | |completed | |
|14 |14 |19 | |completed | |
|15 |15 |19 | |completed | |
-------------------------------------------------------------------------------
|LOCK NAME |STATUS |WAITING THREADS |
|lock_a |unlocked | |
|lock_b |unlocked | |
-------------------------------------------------------------------------------
|SEMAPHORE NAME |VALUE |WAITING THREADS |
|0 |20 | |
|1 |20 | |
|2 |20 | |
|3 |20 | |
|4 |20 | |
|5 |20 | |
|6 |20 | |
|7 |20 | |
|8 |20 | |
|9 |20 | |
|10 |20 | |
|11 |20 | |
|12 |20 | |
|13 |20 | |
|14 |20 | |
|15 |20 | |
*******************************************************************************
***** Program Trace End *****
死锁：
THREAD: 13
SECTION: DoneRounds
MESSAGE: Thread 13 has completed
*******************************************************************************
|ID |PROPERTY |LOC |SECTION |STATUS |WAITING ON |
|0 |0 |19 | |completed | |
|1 |1 |32 | |waiting-sem |1 |
|2 |2 |32 | |waiting-sem |2 |
|3 |3 |38 | |waiting-sem |2 |
|4 |4 |19 | |completed | |
|5 |5 |19 | |completed | |
|6 |6 |19 | |completed | |
|7 |7 |19 | |completed | |
|8 |8 |19 | |completed | |
|9 |9 |32 | |waiting-sem |9 |
|10 |10 |38 | |waiting-sem |9 |
|11 |11 |19 | |completed | |
|12 |12 |19 | |completed | |
|13 |13 |19 | |completed | |
|14 |14 |19 | |completed | |
|15 |15 |19 | |completed | |
-------------------------------------------------------------------------------
|LOCK NAME |STATUS |WAITING THREADS |
|lock_a |unlocked | |
|lock_b |unlocked | |
-------------------------------------------------------------------------------
|SEMAPHORE NAME |VALUE |WAITING THREADS |
|0 |10 | |
|1 |-1 |1 |
|2 |-2 |2 3 |
|3 |10 | |
|4 |20 | |
|5 |20 | |
|6 |20 | |
|7 |20 | |
|8 |10 | |
|9 |-2 |9 10 |
|10 |10 | |
|11 |20 | |
|12 |20 | |
|13 |20 | |
|14 |20 | |
|15 |20 | |
*******************************************************************************
ERROR! VIOLATION: No ready threads to schedule - possible DEADLOCK
***** Program Trace End *****
回答后编辑
感谢mevets！ 最终代码： section1.c - 想要死锁
// sections1.c: mutual exclusion model sections
#include <stdio.h>
#include <errno.h>
#include <stdlib.h>
#include <pthread.h>
#include <semaphore.h>
#include "sections.h"
#include "mdat.h"
// TODO: Declare shared variables here
int numPhils;
sem_t * sem_arr;
void sectionInitGlobals(int numPhilosophers)
{
// TODO: Complete this function
int i;
char char_arr[50];
sem_t arr[numPhilosophers];
numPhils = numPhilosophers;
for(i = 0; i < numPhilosophers; i++)
{
sprintf(char_arr,"%d", i);
mdat_sem_init(char_arr, &arr[i], 0, 1);
}
sem_arr = arr;
}
void sectionRunPhilosopher(int philosopherID, int numRounds)
{
int lChop = philosopherID;
int rChop;
int i;
if(philosopherID == 0)
rChop = numPhils - 1;
else
rChop = philosopherID - 1;
for(i = 0; i < numRounds; i++)
{
mdat_sem_wait(&sem_arr[lChop]);
mdat_sem_wait(&sem_arr[rChop]);
eat();
mdat_sem_post(&sem_arr[rChop]);
mdat_sem_post(&sem_arr[lChop]);
think();
}
}
section2.c - 不想死锁
// sections1.c: mutual exclusion model sections
#include <stdio.h>
#include <errno.h>
#include <stdlib.h>
#include <pthread.h>
#include <semaphore.h>
#include "sections.h"
#include "mdat.h"
// TODO: Declare shared variables here
int numPhils;
sem_t * sem_arr;
void sectionInitGlobals(int numPhilosophers)
{
// TODO: Complete this function
int i;
char char_arr[50];
sem_t arr[numPhilosophers];
numPhils = numPhilosophers;
for(i = 0; i < numPhilosophers; i++)
{
sprintf(char_arr,"%d", i);
mdat_sem_init(char_arr, &arr[i], 0, 1);
}
sem_arr = arr;
}
void sectionRunPhilosopher(int philosopherID, int numRounds)
{
int lChop = philosopherID;
int rChop;
int i;
if(philosopherID == 0)
rChop = numPhils - 1;
else
rChop = philosopherID - 1;
for(i = 0; i < numRounds; i++)
{
if(philosopherID != numPhils - 1)
{
mdat_sem_wait(&sem_arr[lChop]);
mdat_sem_wait(&sem_arr[rChop]);
eat();
mdat_sem_post(&sem_arr[rChop]);
mdat_sem_post(&sem_arr[lChop]);
}
else
{
mdat_sem_wait(&sem_arr[rChop]);
mdat_sem_wait(&sem_arr[lChop]);
eat();
mdat_sem_post(&sem_arr[lChop]);
mdat_sem_post(&sem_arr[rChop]);
}
think();
}
}
经典的哲学家就餐问题有N个哲学家和N个叉子；但每个人都需要 2 把叉子才能吃。一个给定的 fork 信号量可能有最大值 1 [available]，和最小值 -1（一个有 fork，一个正在等待 fork）。你的叉子值是 10 和 20?
按照你的逻辑，你检查信号量的值，如果>=0，你说你“有”，然后继续检查另一个；但你没有。在对它进行 wait 操作之前，你没有信号量。在 eat()ing 之后，你 post 给他们两个，即使你可能从来没有等过他们中的任何一个。这就是为什么你的信号量值高得离谱。
其次，当sem_get_value返回时，信号量的值可能已经改变。这是一个常见的同步问题，如此常见它有一个名字：TOCTOU（Time Of Check to Time Of Use）。您需要使用根据操作做出决策的机制，而不仅仅是检查状态。
第三，您将其更改为有效地坐在一个循环中：
sem_wait(left);
sem_wait(right);
eat();
sem_post(right);
sem_post(left);
您将遇到一个完全不同的同步问题，这就是 Dining Philosophers 旨在说明的问题。狩猎愉快！