操作系统

3. 硬件视角的操作系统¶

strace 查看进程的系统调用 xxd 查看二进制文件

Linux下栈的大小一般为 --> 8192 KB

ulimit -s

#include <stdio.h>
#include <stdlib.h>

int x = 0;
int y = 0;

void T1() {
    x = 1;
    int t = y;
    printf(" %d",t);
}

void T2() {
    y = 1;
    int t = x;
    printf(" %d",t);
}


int main() {

    int pid = fork();
    if(pid == 0) {
      T1();  
    } else {
      T2();
    }
    return 0;
}

结果

绝大多数：00
少数：01、10
极少数：11

并发程序设计三要素: 原子性有序性可见性

什么是Peterson算法？

什么是自旋锁？

// 假设存在硬件原子操作：Test-and-Set(TAS)指令
// lock 表示自旋锁变量，初始化为 0，表示未锁定状态

function acquireLock(lock):
    while (TAS(lock) == 1):
        // 自旋等待，直到获取锁
        // TAS(lock) 返回 1 表示锁已经被其他线程占用，继续自旋等待
    // 获取到锁后退出循环
    return

function releaseLock(lock):
    lock = 0
    // 释放锁

// 在临界区内的代码
acquireLock(myLock)
// 执行临界区的代码
// ...
releaseLock(myLock)

上述伪代码假设有名为 TAS 的原子操作，它是一个基本的硬件原子指令，可以原子地设置一个变量为1并返回其旧值。如果该变量原来是0，则说明当前线程成功获取了锁。如果返回的旧值是1，则说明锁已经被其他线程占用，当前线程继续在循环中自旋等待。

使用xchg实现互斥

// lock 表示互斥锁变量，初始化为 0，表示未锁定状态

function acquireLock(lock):
    while (xchg(lock, 1) == 1):
        // 将 lock 的值和 1 交换，并返回原来的 lock 值
        // 如果返回的是 1，表示锁已经被其他线程占用，继续自旋等待
    // 获取到锁后退出循环
    return

function releaseLock(lock):
    lock = 0
    // 将 lock 的值设置为 0，释放锁

// 在临界区内的代码
acquireLock(myLock)
// 执行临界区的代码
// ...
releaseLock(myLock)

什么是cmpxchg

cmpxchg 是一种原子指令，用于在多处理器环境中执行原子比较和交换操作。在x86架构上，cmpxchg 指令用于比较一个内存位置的值和一个预期值，如果它们相等，则将该内存位置的值替换为一个新值。这个操作是原子的，意味着在执行期间不会被其他线程的操作中断。

在x86架构上，cmpxchg 指令有多个变种，主要取决于要比较和交换的数据类型。常见的几个变种包括 cmpxchg, cmpxchg8b, cmpxchg16b 等。这些指令用于处理不同大小的数据类型，如单字节、双字节、四字节、八字节或更大。

在编程中，cmpxchg 指令通常用于实现原子操作，如自旋锁、互斥锁、无锁数据结构等。它可以确保多个线程在并发访问共享资源时不会产生竞态条件或数据不一致的问题。

下面是一个简单的示例，展示了使用 cmpxchg 指令实现原子比较和交换的伪代码：

// 假设有一个共享的变量 sharedValue，和一个预期值 expectedValue

function atomicCompareAndSwap(sharedValue, expectedValue, newValue):
    if (sharedValue == expectedValue):
        // 如果 sharedValue 等于预期值 expectedValue
        // 则用 newValue 替换 sharedValue，并返回 true 表示交换成功
        // 否则返回 false 表示交换失败
        sharedValue = newValue
        return true
    else:
        return false

// 使用 atomicCompareAndSwap 来保护共享资源
function updateSharedResource(newValue):
    do:
        currentValue = sharedValue
        // 假设 currentValue 是共享资源的当前值
        if (atomicCompareAndSwap(sharedValue, currentValue, newValue)):
            // 交换成功，共享资源更新完成
            break
        // 交换失败，继续循环，重试更新共享资源
    while (true)

在这个示例中，atomicCompareAndSwap 函数利用了 cmpxchg 指令来比较 sharedValue 和 expectedValue 是否相等，如果相等，则用 newValue 替换 sharedValue，并返回交换是否成功的结果。如果交换失败，说明 sharedValue 已经被其他线程修改，此时需要重试更新共享资源，直到交换成功为止。

比较并交换(xmpxchg)操作的优势在于，它可以避免自旋等待，因为只有在操作成功的情况下，才会真正地修改内存位置的值，而失败时可以立即返回并重新尝试，减少了资源浪费。

互斥锁（Mutex）和自旋锁（Spin Lock）是两种常见的线程同步机制，它们有一些关键区别：

互斥锁是一种阻塞锁

而自旋锁是一种非阻塞锁

等待方式：
- 互斥锁：当一个线程尝试获取互斥锁时，如果锁已经被其他线程占用，该线程将被阻塞挂起，直到锁被释放。线程会进入睡眠状态，不会占用CPU资源。
- 自旋锁：当一个线程尝试获取自旋锁时，如果锁已经被其他线程占用，该线程将在循环中自旋等待，不会进入睡眠状态，而是一直占用CPU资源，直到获取到锁。
- 占用CPU资源：
- 互斥锁：由于等待时线程会进入睡眠状态，不会占用CPU资源，因此在互斥锁的等待过程中，CPU可以被其他可运行的线程利用。
- 自旋锁：等待时线程一直在自旋循环中，会占用CPU资源，这可能导致高CPU利用率，尤其在锁竞争激烈的情况下。
- 适用场景：
- 互斥锁：适用于临界区保护时间较长的情况，当线程需要等待较长时间才能获得锁时，互斥锁的阻塞等待方式是更合理的选择。
- 自旋锁：适用于临界区保护时间较短的情况，例如临界区的代码很短或在单核处理器上运行，这样自旋等待的开销相对较小，避免了线程切换带来的开销。
- 内存开销：
- 互斥锁：通常比自旋锁占用更多的内存，因为互斥锁需要维护一个等待队列来管理等待获取锁的线程。
- 自旋锁：通常比互斥锁占用更少的内存，因为自旋锁不需要维护等待队列，只需要一个简单的标志来表示锁的状态。

需要根据具体的应用场景和性能需求选择合适的线程同步机制。在多核处理器上，自旋锁可能会导致高CPU占用，因此通常推荐在临界区保护时间较长的情况下使用互斥锁。而在单核处理器上或临界区保护时间较短的情况下，自旋锁可能是一个更有效的选择。

自旋锁在线程上进行锁操作，互斥锁通过系统调用访问lock