1 Conditions for deadlock formation
Deadlock refers to a deadlock caused by multiple threads or processes competing for limited system resources during operation. When processes or threads are in this deadlock, they will be unable to move forward without external force. As shown in the figure below, thread A wants to obtain the thread
Process B’s lock, thread
B
Want to get thread
C
lock, thread
C
Want to get thread
D
lock, thread
D
Want to get thread A.
lock, thus building a resource acquisition loop.
The existence of deadlock is due to the existence of resource acquisition loop, so as long as the resource acquisition loop can be detected, it is equivalent to detecting
The existence of deadlock.
2. Deadlock detection principle
Deadlock detection is a key component in computer systems, used to detect and solve deadlock problems to ensure the normal operation of the system. The implementation principle of the deadlock detection component usually includes the following key steps:
1. Construction of resource allocation graph: Deadlock detection is usually based on resource allocation graph. The resource allocation graph is a directed graph, in which nodes represent processes and resources, and edges represent resource allocation relationships and request relationships. Each process and resource has a corresponding node, and there are directed edges representing the process’s behavior of requesting resources and releasing resources.
2. Graph conversion: Convert the resource allocation graph into a data structure that is easier to analyze, usually a wait-for graph (Wait-For Graph) or resource allocation matrix. A wait graph is a simplified version of a resource allocation graph that only includes wait relationships. The resource allocation matrix is a matrix in which rows represent processes, columns represent resources, and elements represent resource allocation.
3. Detect loops: Detect whether there are loops by analyzing the waiting graph or resource allocation matrix. If a loop exists, there may be a deadlock. This is because a loop represents the resource request and release relationship between a group of processes, which form a loop with each other, making it impossible for each process to continue executing.
4. Deadlock recovery: If a deadlock is detected, the deadlock detection component can take different measures to resolve the deadlock. These actions include terminating certain processes to free up resources, rolling back the state of processes, or waiting for resources to be released.
5. Periodic detection: The deadlock detection component usually runs periodically to detect potential deadlock situations at any time. This allows deadlocks to be identified and handled at an early stage to reduce the impact on the system.
It should be noted that although deadlock detection can detect and solve deadlock problems, it is not the most efficient method because it needs to be run regularly and may introduce some system overhead. A better approach is to prevent deadlocks from occurring through well-designed algorithms and strategies. Deadlock prevention methods include resource allocation strategies, resource request sequence regulations, and process scheduling strategies. These methods help reduce the probability of deadlock and fundamentally reduce the occurrence of deadlock problems.
3. Implementation of deadlock detection component
#define _GNU_SOURCE
#include <dlfcn.h>
#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>
#include <pthread.h>
#if 1
#include <stdint.h>
typedef unsigned long int uint64;
#define MAX 100
enum Type {PROCESS, RESOURCE};
struct source_type {
uint64 id;
enum Type type;
uint64 lock_id;
int degress;
};
struct vertex {
struct source_type s;
struct vertex *next;
};
struct task_graph {
struct vertex list[MAX];
int num;
struct source_type locklist[MAX];
int lockidx;
pthread_mutex_t mutex;
};
struct task_graph *tg = NULL;
int path[MAX + 1];
int visited[MAX];
int k = 0;
int deadlock = 0;
struct vertex *create_vertex(struct source_type type) {
struct vertex *tex = (struct vertex *)malloc(sizeof(struct vertex ));
tex->s = type;
tex->next = NULL;
return tex;
}
int search_vertex(struct source_type type) {
int i = 0;
for (i = 0;i < tg->num;i + + ) {
if (tg->list[i].s.type == type.type & amp; & amp; tg->list[i].s.id == type.id) {
return i;
}
}
return -1;
}
void add_vertex(struct source_type type) {
if (search_vertex(type) == -1) {
tg->list[tg->num].s = type;
tg->list[tg->num].next = NULL;
tg->num + + ;
}
}
int add_edge(struct source_type from, struct source_type to) {
add_vertex(from);
add_vertex(to);
struct vertex *v = & amp;(tg->list[search_vertex(from)]);
while (v->next != NULL) {
v = v->next;
}
v->next = create_vertex(to);
}
int verify_edge(struct source_type i, struct source_type j) {
if (tg->num == 0) return 0;
int idx = search_vertex(i);
if (idx == -1) {
return 0;
}
struct vertex *v = & amp;(tg->list[idx]);
while (v != NULL) {
if (v->s.id == j.id) return 1;
v = v->next;
\t\t
}
return 0;
}
int remove_edge(struct source_type from, struct source_type to) {
int idxi = search_vertex(from);
int idxj = search_vertex(to);
if (idxi != -1 & amp; & amp; idxj != -1) {
struct vertex *v = & amp;tg->list[idxi];
struct vertex *remove;
while (v->next != NULL) {
if (v->next->s.id == to.id) {
remove = v->next;
v->next = v->next->next;
free(remove);
break;
}
v = v->next;
}
}
}
void print_deadlock(void) {
int i = 0;
printf("cycle : ");
for (i = 0;i < k-1;i + + ) {
printf("%ld --> ", tg->list[path[i]].s.id);
}
printf("%ld\
", tg->list[path[i]].s.id);
}
int DFS(int idx) {
struct vertex *ver = & amp;tg->list[idx];
if (visited[idx] == 1) {
path[k + + ] = idx;
print_deadlock();
deadlock = 1;
\t\t
return 0;
}
visited[idx] = 1;
path[k + + ] = idx;
while (ver->next != NULL) {
DFS(search_vertex(ver->next->s));
k --;
\t\t
ver = ver->next;
}
\t
return 1;
}
int search_for_cycle(int idx) {
\t
struct vertex *ver = & amp;tg->list[idx];
visited[idx] = 1;
k = 0;
path[k + + ] = idx;
while (ver->next != NULL) {
int i = 0;
for (i = 0;i < tg->num;i + + ) {
if (i == idx) continue;
\t\t\t
visited[i] = 0;
}
for (i = 1;i <= MAX;i + + ) {
path[i] = -1;
}
k = 1;
DFS(search_vertex(ver->next->s));
ver = ver->next;
}
}
#endif
int search_lock(uint64 lock) {
int i = 0;
\t
for (i = 0;i < tg->lockidx;i + + ) {
\t\t
if (tg->locklist[i].lock_id == lock) {
return i;
}
}
return -1;
}
int search_empty_lock(uint64 lock) {
int i = 0;
\t
for (i = 0;i < tg->lockidx;i + + ) {
\t\t
if (tg->locklist[i].lock_id == 0) {
return i;
}
}
return tg->lockidx;
}
void lock_before(uint64_t tid, uint64_t lockaddr) {
int idx = 0;
for(;idx < tg->lockidx; idx + + ) {
if(tg->locklist[idx].lock_id == lockaddr) {
struct source_type from;
from.id = tid;
from.type = PROCESS;
add_vertex(from);
struct source_type to;
to.id = tg->locklist[idx].id;
to.type = PROCESS;
add_vertex(to);
tg->locklist[idx].degress + + ;
if(!verify_edge(from, to))
add_edge(from, to);
}
}
}
void lock_after(uint64_t tid, uint64_t lockaddr) {
int idx = 0;
if(-1 == (idx = search_lock(lockaddr))) {
int edix = search_empty_lock(lockaddr);
tg->locklist[edix].id = tid;
tg->locklist[edix].lock_id = lockaddr;
tg->lockidx + + ;
} else{
struct source_type from;
from.id = tid;
from.type = PROCESS;
add_vertex(from);
struct source_type to;
to.id = tg->locklist[idx].id;
to.type = PROCESS;
add_vertex(to);
tg->locklist[idx].degress --;
if(verify_edge(from, to));
remove_edge(from, to);
tg->locklist[idx].id = tid;
}
}
void unlock_after(uint64_t tid, uint64_t lockaddr) {
int idx = search_lock(lockaddr);
if(tg->locklist[idx].degress == 0) {
tg->locklist[idx].id = 0;
tg->locklist[idx].lock_id = 0;
}
}
void check_dead_lock(void) {
int i = 0;
deadlock = 0;
for (i = 0;i < tg->num;i + + ) {
if (deadlock == 1) break;
search_for_cycle(i);
}
if (deadlock == 0) {
printf("no deadlock\
");
}
}
static void *thread_routine(void *args) {
while (1) {
sleep(5);
check_dead_lock();
}
}
void start_check(void) {
tg = (struct task_graph*)malloc(sizeof(struct task_graph));
tg->num = 0;
tg->lockidx = 0;
\t
pthread_t tid;
pthread_create( & amp;tid, NULL, thread_routine, NULL);
}
typedef int (*pthread_mutex_lock_t)(pthread_mutex_t *mutex);
pthread_mutex_lock_t pthread_mutex_lock_f = NULL;
typedef int (*pthread_mutex_unlock_t)(pthread_mutex_t *mutex);
pthread_mutex_unlock_t pthread_mutex_unlock_f = NULL;
int pthread_mutex_lock(pthread_mutex_t *mutex) {
pthread_t selfid = pthread_self();
lock_before((uint64_t)selfid,(uint64_t)mutex);
pthread_mutex_lock_f(mutex);
lock_after((uint64_t)selfid,(uint64_t)mutex);
//printf("[%s:%s;%d] pthread_mutex_lock selfid: %ld, %p\
", \
__FILE__,__func__,__LINE__,selfid,mutex);
}
int pthread_mutex_unlock(pthread_mutex_t *mutex) {
pthread_t selfid = pthread_self();
pthread_mutex_unlock_f(mutex);
unlock_after((uint64_t)selfid,(uint64_t)mutex);
//printf("[%s:%s;%d] pthread_mutex_lock selfid: %ld, %p\
",\
__FILE__,__func__,__LINE__,selfid,mutex);
}
void init_hook(void) {
if(!pthread_mutex_lock_f) {
pthread_mutex_lock_f = dlsym(RTLD_NEXT, "pthread_mutex_lock");
}
if(!pthread_mutex_unlock_f) {
pthread_mutex_unlock_f = dlsym(RTLD_NEXT, "pthread_mutex_unlock");
}
}
/*
Just add this file to the program that needs to detect deadlock, and add the following two lines of code in the main function of the program to compile and execute.
init_hook();
start_check();
*/
#if 0
pthread_mutex_t r1 = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t r2 = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t r3 = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t r4 = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t r5 = PTHREAD_MUTEX_INITIALIZER;
void *t1_cb(void *arg) {
pthread_mutex_lock( & amp;r1);
sleep(1);
pthread_mutex_lock( & amp;r2);
pthread_mutex_unlock( & amp;r2);
pthread_mutex_unlock( & amp;r1);
}
void *t2_cb(void *arg) {
pthread_mutex_lock( & amp;r2);
sleep(1);
pthread_mutex_lock( & amp;r3);
pthread_mutex_unlock( & amp;r3);
pthread_mutex_unlock( & amp;r2);
}
void *t3_cb(void *arg) {
pthread_mutex_lock( & amp;r3);
sleep(1);
pthread_mutex_lock( & amp;r4);
pthread_mutex_unlock( & amp;r4);
pthread_mutex_unlock( & amp;r3);
}
void *t4_cb(void *arg) {
pthread_mutex_lock( & amp;r4);
sleep(1);
#if 1
pthread_mutex_lock( & amp;r2);
pthread_mutex_unlock( & amp;r2);
#endif
pthread_mutex_unlock( & amp;r4);
}
void *t5_cb(void *arg) {
pthread_mutex_lock( & amp;r5);
sleep(1);
#if 0
pthread_mutex_lock( & amp;r1);
pthread_mutex_unlock( & amp;r1);
#endif
pthread_mutex_unlock( & amp;r5);
}
int main(void) {
init_hook();
start_check();
pthread_t t1,t2,t3,t4,t5;
pthread_create( & amp;t1, NULL,t1_cb, NULL);
pthread_create( & amp;t2, NULL,t2_cb, NULL);
pthread_create( & amp;t3, NULL,t3_cb, NULL);
pthread_create( & amp;t4, NULL,t4_cb, NULL);
pthread_create( & amp;t5, NULL,t5_cb, NULL);
pthread_join(t1, NULL);
pthread_join(t2, NULL);
pthread_join(t3, NULL);
pthread_join(t4, NULL);
pthread_join(t5, NULL);
printf("complete\
");
return 0;
}
#endif
Results obtained by simulating different deadlock scenarios:
