YiNotes

题27

Jun 19, 20257 min read

题27

题目

[!question]+
【2023 统考真题】现要求学生使用 swap 指令和布尔型变量 lock 实现临界区互斥。lock 为线程间共享的变量, 当 lock 的值为 TRUE 时线程不能进入临界区, 为 FALSE 时线程能够进入临界区。某同学编写的实现临界区互斥的伪代码如下图所示。

某同学编写的伪代码

bool lock = FALSE; // 共享变量
...
bool key = TRUE;   // 进入区
if (key == TRUE)
    swap(key, lock); // 交换key和lock的值
临界区：
    // 临界区代码
    lock = TRUE; // 退出区
...

newSwap()的代码

void newSwap(bool &a, bool &b) {
    bool temp = *a;
    *a = *b;
    *b = temp;
}

请回答下列问题。

  1. 图(a)的伪代码中哪些语句存在错误? 将其改为正确的语句 (不增加语句的条数)。
  2. 图(b)给出了交换两个变量值的函数 newSwap() 的代码, 是否可以用函数调用语句 “newSwap(&key, &lock)” 代替指令 “swap key, lock” 以实现临界区互斥? 为什么?

分析

[!NOTE]+
原始伪代码：

bool lock = FALSE;    // 共享变量
...
void T0() {
    bool key = TRUE;
    if (key == TRUE)
        swap key, lock;    // 交换key和lock的值
    临界区;
    lock = TRUE;
    ...
}
void T1() {
    bool key = TRUE;
    if (key == TRUE)
        swap key, lock;    // 交换key和lock的值
    临界区;
    lock = TRUE;
    ...
}

初始状态：

  • lock = FALSE (表示临界区当前未被占用)
    线程 T0 和 T1 同时尝试进入临界区：
  1. T0 执行:
    • bool key = TRUE; (T0 的局部变量 key 被初始化为 TRUE)
    • if (key == TRUE) (条件成立，执行下一步)
    • swap key, lock; (交换 key 和 lock 的值)
      • 执行前： key = TRUE, lock = FALSE
      • 执行后： key = FALSE, lock = TRUE
    • 临界区; (T0 进入临界区)
  2. 此时 T1 开始执行，与 T0 并发:
    • bool key = TRUE; (T1 的局部变量 key 被初始化为 TRUE)
    • if (key == TRUE) (条件成立，执行下一步)
    • swap key, lock; (交换 key 和 lock 的值)
      • 执行前： key = TRUE, lock = TRUE
      • 执行后： key = TRUE, lock = TRUE
    • 临界区; (T1 进入临界区)
  3. T0 执行:
    • lock = TRUE; (T0 退出临界区，但 lock 的值已经是 TRUE，没有起到解锁的作用)
  4. T1 执行:
    • lock = TRUE; (T1 退出临界区，但 lock 的值已经是 TRUE，没有起到解锁的作用)
      分析结果：
  • T0 先执行： T0 进入临界区后，lock 被设置为 TRUE。
  • T1 并发执行： T1 在 T0 还在临界区内时执行，并交换了key 和 lock 的值，此时 lock 的值已经为 true，key 的值变为 true，依然能进入临界区。
  • 互斥失效： T0 和 T1 都进入了临界区，没有实现互斥访问。
  • 未解锁： 两个线程执行结束时，lock 的值最终都是 TRUE，没有进行解锁操作，导致后续线程无法进入临界区。
    关键错误点：
  1. if 条件判断： 使用 if (key == TRUE) 只能执行一次 swap 操作，无法保证线程在 lock 为 TRUE 时等待。
  2. 退出区错误： 使用 lock = TRUE 退出临界区是错误的，应该将 lock 的值设置为 FALSE 以释放锁。
    总结：
    原始伪代码的问题在于：
  • 没有实现等待： 当 lock 为 TRUE 时，其他线程应该等待，但 if 语句无法实现这个功能。
  • 退出区错误： 没有正确的解锁操作，导致其他线程永远无法进入临界区。
    为了实现互斥访问，需要使用循环等待（while）和正确的解锁操作（lock = FALSE 或 swap key, lock）。

    模拟两个线程同时运行这个代码，就知道是否互斥了，不能只想一个进程在跑，因为这里又公共变量

解

[!done]+

  1. if 语句无法实现对临界区的互斥访问, 因为 if 语句执行后, 不论结果如何, 线程都能访问临界区。本题使用 swap 指令和 lock 变量来实现对临界区的互斥访问, 当线程不能进入临界区时, 本身并不会主动放弃 CPU, 因此需要要让线程在进入区中循环检查 lock 值, 可以使用 while 循环, 当 lock 值为 TRUE 时, 线程一直执行 while 循环的内容, 直到 lock 值被修改为 FALSE 时, 线程才能进入临界区, 因此将进入区中的语句 “if (key = TRUE) swap key, lock” 修改为 “while (key = TRUE) swap key, lock”。在退出区中,代表该线程对临界资源的访问已经结束, 此时需要将 lock 值设为 FALSE, 代表其他线程可以访问临界区, 因此将退出区中的语句 “lock = TRUE” 修改为 “lock = FALSE”。
  2. 否。因为多个线程可以并发执行 newSwap(), newSwap() 执行时传递给形参 b 的是共享变量 lock 的地址, 在 newSwap() 中对 lock 既有读操作又有写操作, 并发执行时不能保证实现两个变量值的原子交换,从而导致并发执行的线程同时进入临界区。例如,线程 A 和线程 B 并发执行,初始时 lock 值为 FALSE,当线程 A 执行完 *a = *b 后发生了进程调度,切换到线程 B 执行, 线程 B 执行完 newSwap 后发生线程切换, 此时线程 A 和 B 都能进入临界区, 不能实现互斥访问。

Graph View

Backlinks