马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。
您需要 登录 才可以下载或查看，没有账号？立即注册
x
1. 定义
死锁是指两个或多个进程（或线程）在实验过程中，因争取资源而造成的一种僵局，每个进程都无穷期地等待其他进程释放它们所持有的资源。在这种情况下，没有任何进程能够继续实验，除非有外部干预。
2. 死锁的须要条件
根据Dijkstra的理论，死锁的发生必须同时满足以下四个须要条件：
- 互斥条件（Mutual Exclusion）：
- 资源不能被共享，一次只能被一个进程使用。比方，打印机、磁带机等资源在使用时不能被多个进程同时占用。
- 哀求与保持条件（Hold and Wait）：
- 一个进程已经持有一个资源，但又哀求新的资源。如果新资源被其他进程占用，哀求进程将被阻塞，但它仍然保持对已有资源的占用。
- 不可剥夺条件（No Preemption）：
- 资源不能被强制剥夺，只能由占用它的进程主动释放。比方，内存资源不能被强制从一个进程转移到另一个进程。
- 循环等待条件（Circular Wait）：
- 存在一个进程序列 P1,P2,…,Pn，使得 P1 等待 P2 持有的资源，P2 等待 P3 持有的资源，……，Pn 等待 P1 持有的资源，形成一个等待环路。
3. 死锁的示例
哲学家进餐问题
哲学家进餐问题是死锁的经典示例。五位哲学家围坐在一张圆桌旁，每位哲学家眼前有一支叉子，左右各一支。哲学家需要同时拿起左右两支叉子才能进餐。如果每位哲学家都先拿起左边的叉子，然后等待右边的叉子，最终会导致全部哲学家都饿死，因为每个人都持有一支叉子并等待另一支叉子。
银行家算法
银行家算法是一种预防死锁的算法，通过资源分配图来检测系统是否处于安全状态。如果系统处于安全状态，银行家算法会分配资源；否则，它会等待，直到系统进入安全状态。银行家算法通过确保系统不会进入不安全状态来预防死锁。
4. 死锁的处理惩罚策略
- 预防死锁（Deadlock Prevention）：
- 通过破坏死锁的须要条件之一来预防死锁的发生。比方：
- 资源分级：对资源举行编号，哲学家总是先拿起编号较小的叉子，再拿起编号较大的叉子，从而破坏循环等待条件。
- 限制资源分配：限制同时哀求资源的数量，确保系统不会进入死锁状态。
- 克制死锁（Deadlock Avoidance）：
- 动态地查抄资源分配是否会导致死锁。比方：
- 银行家算法：通过资源分配图来检测系统是否处于安全状态，只在安全状态下分配资源。
- 检测死锁（Deadlock Detection）：
- 定期查抄系统是否处于死锁状态。如果检测到死锁，采取步伐办理。比方：
- 资源分配图：通过资源分配图检测循环等待条件。
- 超机遇制：如果某个进程等待资源的时间凌驾某个阈值，认为系统大概进入死锁状态。
- 恢复死锁（Deadlock Recovery）：
- 当检测到死锁时，采取步伐恢复系统。比方：
- 资源剥夺：强制剥夺某些进程持有的资源，使其能够继续实验。
- 进程停止：停止某些进程，释放其持有的资源。
5. 死锁的示例代码
以下是一个简朴的C语言示例，展示如何通过资源分级来预防死锁。
- #include <stdio.h>
- #include <stdlib.h>
- #include <pthread.h>
- #include <semaphore.h>
- #include <unistd.h>
- #define NUM_PHILOSOPHERS 5
- sem_t forks[NUM_PHILOSOPHERS];
- void* philosopher(void* arg) {
- int id = *(int*)arg;
- int left_fork = id;
- int right_fork = (id + 1) % NUM_PHILOSOPHERS;
- while (1) {
- // 思考
- printf("Philosopher %d is thinking\n", id);
- sleep(1);
- // 饿了，尝试拿起叉子
- printf("Philosopher %d is hungry\n", id);
- // 确保先拿起编号较小的叉子
- if (left_fork < right_fork) {
- sem_wait(&forks[left_fork]);
- printf("Philosopher %d picked up left fork %d\n", id, left_fork);
- sem_wait(&forks[right_fork]);
- printf("Philosopher %d picked up right fork %d\n", id, right_fork);
- } else {
- sem_wait(&forks[right_fork]);
- printf("Philosopher %d picked up right fork %d\n", id, right_fork);
- sem_wait(&forks[left_fork]);
- printf("Philosopher %d picked up left fork %d\n", id, left_fork);
- }
- // 吃饭
- printf("Philosopher %d is eating\n", id);
- sleep(1);
- // 放下叉子
- sem_post(&forks[right_fork]);
- printf("Philosopher %d put down right fork %d\n", id, right_fork);
- sem_post(&forks[left_fork]);
- printf("Philosopher %d put down left fork %d\n", id, left_fork);
- }
- }
- int main() {
- pthread_t philosophers[NUM_PHILOSOPHERS];
- int ids[NUM_PHILOSOPHERS];
- // 初始化信号量
- for (int i = 0; i < NUM_PHILOSOPHERS; i++) {
- sem_init(&forks[i], 0, 1);
- }
- // 创建哲学家线程
- for (int i = 0; i < NUM_PHILOSOPHERS; i++) {
- ids[i] = i;
- pthread_create(&philosophers[i], NULL, philosopher, &ids[i]);
- }
- // 等待线程结束
- for (int i = 0; i < NUM_PHILOSOPHERS; i++) {
- pthread_join(philosophers[i], NULL);
- }
- // 清理信号量
- for (int i = 0; i < NUM_PHILOSOPHERS; i++) {
- sem_destroy(&forks[i]);
- }
- return 0;
- }
- 资源分级：哲学家总是先拿起编号较小的叉子，再拿起编号较大的叉子，从而破坏循环等待条件。
- 信号量：使用信号量来控制叉子的获取和释放，确保资源的互斥访问。
总结
死锁是并发系统中一个常见的问题，通过理解死锁的须要条件和采取得当的处理惩罚策略，可以有用地预防和办理死锁问题。资源分级是一种简朴而有用的预防死锁的方法，通过突破循环等待条件，确保系统不会进入死锁状态。
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。 |
