logo
简体中文
导航

03. 同步与互斥

同步与互斥

基本概念

临界区问题

临界区：访问共享资源的代码段，同一时刻只能有一个进程执行。

临界区特征：

  1. 互斥性：同一时刻只能有一个进程在临界区内
  2. 有限等待：进程等待进入临界区的时间是有限的
  3. 空闲让进：当没有进程在临界区内时，请求进入的进程应该能够进入

临界区结构：

do {
    entry_section();    // 进入区
    critical_section(); // 临界区
    exit_section();     // 退出区
    remainder_section(); // 剩余区
} while (true);

互斥与同步

互斥：多个进程不能同时访问共享资源。

同步：多个进程按照某种顺序执行，确保操作的正确性。

区别：

  • 互斥关注的是”不能同时”
  • 同步关注的是”按顺序执行”

软件方法

1. 单标志法

算法描述：

  • 设置一个标志位 turn
  • 只有 turn 指向的进程才能进入临界区

代码实现：

int turn = 0; // 初始化为进程0

// 进程0
while (turn != 0); // 等待
critical_section();
turn = 1;

// 进程1
while (turn != 1); // 等待
critical_section();
turn = 0;

问题：强制轮流进入，违背”空闲让进”原则。

2. 双标志法

算法描述：

  • 每个进程设置一个标志位
  • 进程进入临界区前检查其他进程的标志

代码实现：

bool flag[2] = {false, false};

// 进程i
flag[i] = true;
while (flag[j]); // 等待其他进程
critical_section();
flag[i] = false;

问题：可能同时进入临界区，违背”互斥性”。

3. 双标志法改进

算法描述：

  • 先设置自己的标志，再检查其他进程
  • 如果冲突，先清除自己的标志再重试

代码实现：

bool flag[2] = {false, false};

// 进程i
flag[i] = true;
while (flag[j]) {
    flag[i] = false;
    delay();
    flag[i] = true;
}
critical_section();
flag[i] = false;

问题：可能无限等待，违背”有限等待”原则。

4. Peterson 算法

算法描述：

  • 结合 turn 标志和 flag 标志
  • 满足临界区的三个要求

代码实现：

bool flag[2] = {false, false};
int turn = 0;

// 进程i
flag[i] = true;
turn = j;
while (flag[j] && turn == j);
critical_section();
flag[i] = false;

特点：

  • 满足互斥性、有限等待、空闲让进
  • 适用于两个进程
  • 可以扩展到多个进程

硬件方法

1. 中断屏蔽

原理：在进入临界区前关闭中断，退出时恢复中断。

代码实现：

// 进入临界区
disable_interrupts();
critical_section();
// 退出临界区
enable_interrupts();

特点：

  • 简单有效
  • 只适用于单处理器
  • 影响系统响应性

2. Test-and-Set 指令

原理：原子地测试并设置内存位置的值。

代码实现：

bool TestAndSet(bool *lock) {
    bool old = *lock;
    *lock = true;
    return old;
}

bool lock = false;

// 进程
while (TestAndSet(&lock));
critical_section();
lock = false;

特点：

  • 硬件支持，效率高
  • 适用于多处理器
  • 可能忙等待

3. Compare-and-Swap 指令

原理：原子地比较并交换内存位置的值。

代码实现：

int CompareAndSwap(int *value, int expected, int new_value) {
    int temp = *value;
    if (*value == expected)
        *value = new_value;
    return temp;
}

int lock = 0;

// 进程
while (CompareAndSwap(&lock, 0, 1) != 0);
critical_section();
lock = 0;

特点：

  • 硬件支持，效率高
  • 适用于多处理器
  • 比 Test-and-Set 更灵活

信号量

基本概念

信号量：一个整型变量，除了初始化外，只能通过两个原子操作访问：

  • P 操作（wait）：申请资源
  • V 操作（signal）：释放资源

信号量类型：

  1. 二元信号量：值为 0 或 1，用于互斥
  2. 计数信号量：值可以为任意非负整数，用于同步

信号量实现

结构定义：

typedef struct {
    int value;
    struct process *list;
} semaphore;

P 操作实现：

void P(semaphore *S) {
    S->value--;
    if (S->value < 0) {
        add_process_to_list(S->list);
        block();
    }
}

V 操作实现：

void V(semaphore *S) {
    S->value++;
    if (S->value <= 0) {
        remove_process_from_list(S->list);
        wakeup();
    }
}

信号量应用

1. 互斥：

semaphore mutex = 1;

// 进程
P(&mutex);
critical_section();
V(&mutex);

2. 同步：

semaphore sync = 0;

// 进程A
statement_a();
V(&sync);

// 进程B
P(&sync);
statement_b();

3. 资源管理：

semaphore resource = N; // N个资源

// 进程
P(&resource);
use_resource();
V(&resource);

管程

基本概念

管程：一种高级同步机制，将共享变量和对它们的操作封装在一个模块中。

管程特征：

  1. 封装性：共享变量只能通过管程内的过程访问
  2. 互斥性：同一时刻只能有一个进程在管程内执行
  3. 条件变量：用于进程间的同步

管程结构

monitor MonitorName {
    // 共享变量声明
    shared variables;

    // 条件变量
    condition x, y;

    // 过程定义
    procedure P1() {
        // 过程体
    }

    procedure P2() {
        // 过程体
    }

    // 初始化代码
    {
        // 初始化代码
    }
}

条件变量

操作：

  • wait(c)：进程在条件变量 c 上等待
  • signal(c)：唤醒在条件变量 c 上等待的进程

实现：

typedef struct {
    int value;
    struct process *list;
} condition;

void wait(condition *c) {
    c->value++;
    block();
}

void signal(condition *c) {
    if (c->value > 0) {
        c->value--;
        wakeup();
    }
}

经典同步问题

1. 生产者-消费者问题

问题描述：

  • 生产者进程生产数据放入缓冲区
  • 消费者进程从缓冲区取出数据
  • 缓冲区有限，需要同步

解决方案：

#define N 100
semaphore mutex = 1;
semaphore empty = N;
semaphore full = 0;

// 生产者
void producer() {
    while (true) {
        item = produce_item();
        P(&empty);
        P(&mutex);
        insert_item(item);
        V(&mutex);
        V(&full);
    }
}

// 消费者
void consumer() {
    while (true) {
        P(&full);
        P(&mutex);
        item = remove_item();
        V(&mutex);
        V(&empty);
        consume_item(item);
    }
}

2. 读者-写者问题

问题描述：

  • 多个读者可以同时读取共享数据
  • 写者必须独占访问
  • 读者和写者不能同时访问

读者优先解决方案：

semaphore mutex = 1;
semaphore wrt = 1;
int readcount = 0;

// 读者
void reader() {
    P(&mutex);
    readcount++;
    if (readcount == 1)
        P(&wrt);
    V(&mutex);

    read_data();

    P(&mutex);
    readcount--;
    if (readcount == 0)
        V(&wrt);
    V(&mutex);
}

// 写者
void writer() {
    P(&wrt);
    write_data();
    V(&wrt);
}

3. 哲学家进餐问题

问题描述：

  • 5 个哲学家围坐在圆桌旁
  • 每个哲学家需要两根筷子才能进餐
  • 筷子放在哲学家之间

解决方案：

semaphore chopstick[5] = {1, 1, 1, 1, 1};
semaphore mutex = 1;

void philosopher(int i) {
    while (true) {
        think();

        P(&mutex);
        P(&chopstick[i]);
        P(&chopstick[(i+1)%5]);
        V(&mutex);

        eat();

        V(&chopstick[i]);
        V(&chopstick[(i+1)%5]);
    }
}

死锁问题

死锁定义

死锁：多个进程因竞争资源而造成的一种互相等待的现象。

死锁条件

四个必要条件：

  1. 互斥条件：资源不能被多个进程同时使用
  2. 请求和保持条件：进程在等待其他资源时，不释放已占有的资源
  3. 不可剥夺条件：资源不能被强制剥夺
  4. 循环等待条件：存在进程等待链，形成循环

死锁预防

破坏互斥条件：

  • 使用可共享的资源
  • 使用虚拟化技术

破坏请求和保持条件：

  • 一次性分配所有资源
  • 资源预分配策略

破坏不可剥夺条件：

  • 允许资源抢占
  • 设置资源优先级

破坏循环等待条件：

  • 资源有序分配
  • 资源编号策略

死锁避免

银行家算法：

  • 检查资源分配是否安全
  • 只有在安全状态下才分配资源

安全状态检查：

bool is_safe_state() {
    int work[RESOURCES];
    bool finish[PROCESSES];

    // 初始化
    for (int i = 0; i < RESOURCES; i++)
        work[i] = available[i];
    for (int i = 0; i < PROCESSES; i++)
        finish[i] = false;

    // 查找可以完成的进程
    for (int count = 0; count < PROCESSES; count++) {
        bool found = false;
        for (int i = 0; i < PROCESSES; i++) {
            if (!finish[i] && can_allocate(i, work)) {
                for (int j = 0; j < RESOURCES; j++)
                    work[j] += allocation[i][j];
                finish[i] = true;
                found = true;
            }
        }
        if (!found) return false;
    }
    return true;
}

死锁检测

资源分配图：

  • 节点表示进程和资源
  • 边表示资源分配和请求关系
  • 检测图中是否存在环路

检测算法：

bool detect_deadlock() {
    // 简化资源分配图
    while (存在可以简化的节点) {
        简化节点;
    }

    // 检查是否还有边
    if (图中还有边)
        return true; // 存在死锁
    else
        return false; // 不存在死锁
}

死锁恢复

进程终止：

  • 终止所有死锁进程
  • 逐个终止死锁进程

资源抢占：

  • 选择牺牲进程
  • 回滚到安全状态
  • 重新分配资源