UIUC CS241 讲义：众包系统编程书（5）

UIUC CS241 讲义：众包系统编程书（4）https://developer.aliyun.com/article/1427162

同步，第八部分：环形缓冲区示例

什么是环形缓冲区？

环形缓冲区是一种简单的、通常是固定大小的存储机制，其中连续的内存被视为循环的，并且两个索引计数器跟踪队列的当前开始和结束。由于数组索引不是循环的，所以当移动到数组的末尾时，索引计数器必须回绕到零。当数据被添加（入队）到队列的前端或从队列的尾部移除（出队）时，缓冲区中的当前项目形成一个似乎环绕轨道的列车！一个简单的（单线程）实现如下所示。请注意，enqueue 和 dequeue 没有防止下溢或上溢——当队列已满时可能添加一个项目，当队列为空时可能移除一个项目。例如，如果我们向队列中添加了 20 个整数（1,2,3…），并且没有移除任何项目，那么值17,18,19,20将覆盖1,2,3,4。我们现在不会解决这个问题，而是在创建多线程版本时，我们将确保在环形缓冲区已满或为空时，enqueue 和 dequeue 线程被阻塞。

void *buffer[16];
int in = 0, out = 0;
void enqueue(void *value) { /* Add one item to the front of the queue*/
  buffer[in] = value;
  in++; /* Advance the index for next time */
  if (in == 16) in = 0; /* Wrap around! */
}
void *dequeue() { /* Remove one item to the end of the queue.*/
  void *result = buffer[out];
  out++;
  if (out == 16) out = 0;
  return result;
}

实现环形缓冲区的注意事项是什么？

很容易写出 enqueue 或 dequeue 方法的以下紧凑形式（N 是缓冲区的容量，例如 16）：

void enqueue(void *value)
  b[ (in++) % N ] = value;
}

这种方法似乎可以工作（通过简单的测试等），但包含一个微妙的错误。通过足够多的 enqueue 操作（略多于 20 亿次），in的 int 值将溢出并变为负数！模运算符％保留符号。因此，你可能会写入b[-14]，例如！

一个紧凑的形式是正确的使用位掩码，提供 N 是 2^x（16,32,64,…）

b[ (in++) & (N-1) ] = value;

这个缓冲区还没有防止缓冲区下溢或上溢。为此，我们将转向我们的多线程尝试，它将阻塞一个线程，直到有空间或至少有一个项目可以移除。

检查多线程实现的正确性（示例 1）

以下代码是一个不正确的实现。会发生什么？enqueue和/或dequeue会阻塞吗？互斥性是否得到满足？缓冲区会下溢吗？缓冲区会上溢吗？为了清晰起见，pthread_mutex缩写为p_m，我们假设 sem_wait 不会被中断。

#define N 16
void *b[N]
int in = 0, out = 0
p_m_t lock
sem_t s1,s2
void init() { 
    p_m_init(&lock, NULL)
    sem_init(&s1, 0, 16)
    sem_init(&s2, 0, 0)
}
enqueue(void *value) {
    p_m_lock(&lock)
    // Hint: Wait while zero. Decrement and return
    sem_wait( &s1 ) 
    b[ (in++) & (N-1) ] = value
    // Hint: Increment. Will wake up a waiting thread 
    sem_post(&s1) 
    p_m_unlock(&lock)
}
void *dequeue(){
    p_m_lock(&lock)
    sem_wait(&s2)
    void *result = b[(out++) & (N-1) ]
    sem_post(&s2)
    p_m_unlock(&lock)
    return result
}

分析

在继续阅读之前，看看你能找到多少错误。然后确定如果线程调用 enqueue 和 dequeue 方法会发生什么。

• enqueue 方法在同一个信号量（s1）上等待和发布，equeue 也是如此（s2）即我们减少值然后立即增加值，因此在函数结束时，信号量值不变！
  
• s1 的初始值为 16，因此信号量永远不会减少到零——如果环形缓冲区已满，enqueue 不会阻塞——因此可能会发生溢出。
  
• s2 的初始值为零，因此调用 dequeue 将始终阻塞并且永远不会返回！
  
• 互斥锁和 sem_wait 的顺序需要交换（但是这个示例是如此破碎，以至于这个错误没有影响！）##检查多线程实现的正确性（示例 1）
  

以下代码是一个不正确的实现。会发生什么？enqueue和/或dequeue会阻塞吗？互斥性是否得到满足？缓冲区会下溢吗？缓冲区会上溢吗？为了清晰起见，pthread_mutex缩写为p_m，我们假设 sem_wait 不会被中断。

void *b[16]
int in = 0, out = 0
p_m_t lock
sem_t s1, s2
void init() {
    sem_init(&s1,0,16)
    sem_init(&s2,0,0)
}
enqueue(void *value){
 sem_wait(&s2)
 p_m_lock(&lock)
 b[ (in++) & (N-1) ] = value
 p_m_unlock(&lock)
 sem_post(&s1)
}
void *dequeue(){
  sem_wait(&s1)
  p_m_lock(&lock)
  void *result = b[(out++) & 15]
  p_m_unlock(&lock)
  sem_post(&s2)
  return result;
}

分析

• s2 的初始值为 0。因此，在第一次调用 sem_wait 时，enqueue 将阻塞，即使缓冲区为空！
  
• s1 的初始值为 16。因此，在第一次调用 sem_wait 时，dequeue 不会阻塞，即使缓冲区为空——糟糕，下溢！dequeue 方法将返回无效数据。
  
• 该代码不满足互斥性；两个线程可以同时修改 in 或 out！ 该代码似乎使用了互斥锁。不幸的是，该锁从未使用 pthread_mutex_init() 或 PTHREAD_MUTEX_INITIALIZER 进行初始化 - 因此该锁可能无效（pthread_mutex_lock 可能什么也不做）
  

正确实现环形缓冲区

伪代码（pthread_mutex 缩写为 p_m 等）如下所示。

由于互斥锁存储在全局（静态）内存中，因此可以使用 PTHREAD_MUTEX_INITIALIZER 进行初始化。如果我们在堆上为互斥锁分配了空间，那么我们将使用 pthread_mutex_init(ptr, NULL)

#include <pthread.h>
#include <semaphore.h>
// N must be 2^i
#define N (16)
void *b[N]
int in = 0, out = 0
p_m_t lock = PTHREAD_MUTEX_INITIALIZER
sem_t countsem, spacesem
void init() {
  sem_init(&countsem, 0, 0)
  sem_init(&spacesem, 0, 16)
}

enqueue 方法如下所示。请注意：

• 该锁仅在临界区（对数据结构的访问）期间保持。
  
• 完整的实现需要防止由于 POSIX 信号而导致 sem_wait 提前返回。
  

enqueue(void *value){
 // wait if there is no space left:
 sem_wait( &spacesem )
 p_m_lock(&lock)
 b[ (in++) & (N-1) ] = value
 p_m_unlock(&lock)
 // increment the count of the number of items
 sem_post(&countsem)
}

dequeue 实现如下所示。请注意 enqueue 的同步调用的对称性。在两种情况下，如果空间计数或项目计数为零，函数首先会等待。

void *dequeue(){
  // Wait if there are no items in the buffer
  sem_wait(&countsem)
  p_m_lock(&lock)
  void *result = b[(out++) & (N-1)]
  p_m_unlock(&lock)
  // Increment the count of the number of spaces
  sem_post(&spacesem)
  return result
}

思考

• 如果 pthread_mutex_unlock 和 sem_post 调用的顺序被交换会发生什么？
  
• 如果 sem_wait 和 pthread_mutex_lock 调用的顺序被交换会发生什么？
  

同步复习问题

主题

• 原子操作
  
• 临界区
  
• 生产者消费者问题
  
• 使用条件变量
  
• 使用计数信号量
  
• 实现一个屏障
  
• 实现环形缓冲区
  
• 使用 pthread_mutex
  
• 实现生产者消费者
  
• 分析多线程代码
  

问题

• 什么是原子操作？
  
• 为什么以下内容在并行代码中不起作用？
  

//In the global section
size_t a;
//In pthread function
for(int i = 0; i < 100000000; i++) a++;

这将会是什么？

//In the global section
atomic_size_t a;
//In pthread function
for(int i = 0; i < 100000000; i++) atomic_fetch_add(a, 1);

• 原子操作有哪些缺点？哪个更快：保留一个本地变量还是进行多个原子操作？
  
• 什么是临界区？
  
• 一旦确定了临界区，保证只有一个线程会进入该区域的一种方法是什么？
  
• 在这里确定临界区
  

struct linked_list;
struct node;
void add_linked_list(linked_list *ll, void* elem){
    node* packaged = new_node(elem);
    if(ll->head){
         ll->head = 
    }else{
         packaged->next = ll->head;
         ll->head = packaged;
         ll->size++;
    }
}
void* pop_elem(linked_list *ll, size_t index){
    if(index >= ll->size) return NULL;
    node *i, *prev;
    for(i = ll->head; i && index; i = i->next, index--){
        prev = i;
    }
    //i points to the element we need to pop, prev before
    if(prev->next) prev->next = prev->next->next;
    ll->size--;
    void* elem = i->elem;
    destroy_node(i);
    return elem;
}

临界区可以有多紧凑？

• 什么是生产者消费者问题？以上述部分如何成为生产者消费者问题？生产者消费者问题与读者写者问题有什么关系？
  
• 什么是条件变量？为什么使用条件变量比使用“while”循环更有优势？
  
• 为什么这段代码很危险？
  

if(not_ready){
     pthread_cond_wait(&cv, &mtx);
}

• 什么是计数信号量？给我一个类似于饼干罐/比萨盒/有限食物的比喻。
  
• 什么是线程屏障？
  
• 使用计数信号量来实现屏障。
  
• 编写一个生产者/消费者队列，再来一个生产者/消费者栈？
  
• 给我一个使用条件变量的读者-写者锁的实现，使用你需要的任何结构，它只需要支持以下函数
  

void reader_lock(rw_lock_t* lck);
void writer_lock(rw_lock_t* lck);
void reader_unlock(rw_lock_t* lck);
void writer_unlock(rw_lock_t* lck);

唯一的规定是在“reader_lock”和“reader_unlock”之间，没有写者可以写。在写者锁之间，只有一个写者可以一次写作。

• 编写代码使用仅三个计数信号量实现生产者消费者。假设可以有多个线程调用 enqueue 和 dequeue。确定每个信号量的初始值。
  
• 编写代码使用条件变量和互斥锁实现生产者消费者。假设可以有多个线程调用 enqueue 和 dequeue。
  
• 使用 CVs 实现 add(unsigned int)和 subtract(unsigned int)阻塞函数，永远不允许全局值大于 100。
  
• 使用 CVs 为 15 个线程实现一个屏障。
  
• 以下陈述有多少是真的？

• 可以有多个活跃的读者
  
• 可以有多个活跃的写者
  
• 当有活跃的写者时，活跃的读者数量必须为零
  
• 如果有活跃的读者，则活跃的写者数量必须为零
  
• 一个写者必须等到当前活跃的读者完成
  

• 待办事项：分析多线程代码片段
  

六、死锁

死锁，第一部分：资源分配图

什么是资源分配图？

资源分配图跟踪哪个进程持有哪个资源，以及哪个进程正在等待特定类型的资源。这是一个非常强大而简单的工具，用来说明交互进程如何发生死锁。如果一个进程使用一个资源，就从资源节点到进程节点画一个箭头。如果一个进程请求一个资源，就从进程节点到资源节点画一个箭头。

如果资源分配图中有一个循环，并且循环中的每个资源只提供一个实例，那么进程将发生死锁。例如，如果进程 1 持有资源 A，进程 2 持有资源 B，进程 1 正在等待 B，进程 2 正在等待 A，那么进程 1 和 2 将发生死锁。

这里有另一个例子，显示了进程 1 和 2 获取资源 1 和 2，而进程 3 正在等待获取这两个资源。在这个例子中，没有死锁，因为没有循环依赖。

死锁！

很多时候，我们不知道资源可能被获取的具体顺序，所以我们可以绘制有向图。

作为可能性矩阵。然后我们可以画箭头，看看是否有一个有向版本会导致死锁。

考虑以下资源分配图（假设进程请求对文件的独占访问）。如果有一堆进程在运行，并且它们请求资源，操作系统最终处于这种状态，你就会发生死锁！你可能看不到这一点，因为操作系统可能会抢占一些进程来打破循环，但你的三个孤独进程仍然有可能发生死锁。你也可以使用make和规则依赖关系（例如我们的 parmake MP）制作这种类型的图表。

死锁，第二部分：死锁条件

Coffman 条件

死锁有四个必要和充分条件。这些被称为 Coffman 条件。

• 互斥
  
• 循环等待
  
• 持有并等待
  
• 无抢占
  

如果打破其中任何一个，就不会发生死锁！

所有这些条件都是死锁所必需的，所以让我们依次讨论每一个。首先是简单的-

• 互斥：资源不能被共享
  
• 循环等待：资源分配图中存在一个循环。存在一组进程{P1，P2，…}，使得 P1 正在等待 P2 持有的资源，P2 正在等待 P3，…，P3 正在等待 P1 持有的资源。
  
• 持有并等待：一个进程获取了一个不完整的资源集，并在等待其他资源时保持它们。
  
• 无抢占：一旦一个进程获取了一个资源，该资源就不能被从一个进程那里拿走，而且进程也不会自愿放弃一个资源。
  

打破 Coffman 条件

两个学生需要一支笔和一张纸：

• 学生们共享一支笔和一张纸。避免了死锁，因为不需要互斥。
  
• 学生们都同意先拿笔再拿纸。避免了死锁，因为不会有循环等待。
  
• 学生们一次拿起笔和纸（“要么都拿，要么都不拿”）。避免了死锁，因为没有持有并等待
  
• 学生们是朋友，会要求对方放弃持有的资源。避免了死锁，因为允许抢占。
  

活锁

活锁不是死锁-

考虑以下的“解决方案”

• 如果他们无法在 10 秒内拿起另一个资源，学生们会放下一个持有的资源。这个解决方案避免了死锁，但可能会遭受活锁。

活锁发生在一个进程继续执行但无法取得进展。在实践中，活锁可能是因为程序员已经采取措施避免死锁。在上面的例子中，在繁忙的系统中，学生将不断释放第一个资源，因为他们永远无法获得第二个资源。系统不是死锁（学生进程仍在执行），但也没有取得任何进展。

死锁预防/避免 vs 死锁检测

死锁预防是确保死锁不会发生，这意味着你打破了 Coffman 条件。这在单个程序内效果最好，软件工程师可以选择打破某个 Coffman 条件。考虑银行家算法。这是另一个用于避免死锁的算法。整个实现超出了本课程的范围，只需知道操作系统有更通用的算法。

另一方面，死锁检测允许系统进入死锁状态。进入后，系统使用其拥有的信息来打破死锁。例如，考虑多个进程访问文件。操作系统能够通过文件描述符在某个级别（通过 API 或直接）跟踪所有文件/资源。如果操作系统在操作系统文件描述符表中检测到一个有向循环，它可能会打破一个进程的持有（例如通过调度）并让系统继续进行。

餐桌哲学家

餐桌哲学家问题是一个经典的同步问题。想象我邀请 N（假设为 5）位哲学家共进晚餐。我们将他们安排在一张桌子旁，放置 5 根筷子（每位哲学家之间各有一根）。哲学家交替地想要吃饭或思考。为了吃饭，哲学家必须拿起他们位置两侧的两根筷子（原始问题要求每位哲学家有两把叉子）。然而这些筷子是与他的邻居共享的。

设计一种有效的解决方案，使所有哲学家都能吃饭吗？或者，会有一些哲学家挨饿，永远得不到第二根筷子吗？或者他们全部陷入僵局？例如，想象每个客人都拿起左边的筷子，然后等待右边的筷子空闲。哎呀 - 我们的哲学家陷入了僵局！

死锁，第三部分：餐桌上的哲学家

背景故事

所以你的哲学家们围坐在桌子周围，都想吃点意大利面（或者其他什么），他们真的很饿。每个哲学家本质上都是一样的，这意味着每个哲学家都有相同的指令集，基于其他哲学家，也就是说你不能让每个偶数哲学家做一件事，每个奇数哲学家做另一件事。

失败的解决方案

左右死锁

我们该怎么办？让我们尝试一个简单的解决方案

void* philosopher(void* forks){
     info phil_info = forks;
     pthread_mutex_t* left_fork = phil_info->left_fork;
     pthread_mutex_t* right_fork = phil_info->right_fork;
     while(phil_info->simulation){
          pthread_mutex_lock(left_fork);
          pthread_mutex_lock(right_fork);
          eat(left_fork, right_fork);
          pthread_mutex_unlock(left_fork);
          pthread_mutex_unlock(right_fork);
     }
}

但是这会遇到一个问题！如果每个人都拿起他们的左手叉子，正在等待他们的右手叉子呢？我们已经死锁了程序。重要的是要注意，死锁并不总是发生，而且这个解决方案死锁的概率随着哲学家的数量增加而降低。真正重要的是，最终这个解决方案会死锁，让线程挨饿，这是不好的。

Trylock？更像是活锁

所以现在你在考虑打破柯夫曼条件之一。我们有

• 互斥
  
• 没有抢占
  
• 持有并等待
  
• 循环等待
  

嗯，我们不能让两个哲学家同时使用一个叉子，互斥被排除在外。在我们当前的简单模型中，我们不能让哲学家一旦拿到互斥锁就放开它，所以我们现在就排除这个解决方案——关于这个解决方案有一些注释在页面底部。让我们打破持有并等待！

void* philosopher(void* forks){
     info phil_info = forks;
     pthread_mutex_t* left_fork = phil_info->left_fork;
     pthread_mutex_t* right_fork = phil_info->right_fork;
     while(phil_info->simulation){
          pthread_mutex_lock(left_fork);
          int failed = pthread_mutex_trylock(right_fork);
          if(!failed){
               eat(left_fork, right_fork);
               pthread_mutex_unlock(right_fork);
          }
          pthread_mutex_unlock(left_fork);
     }
}

现在我们的哲学家拿起左边的叉子，试图抓住右边的叉子。如果右边的叉子可用，他们就吃。如果不可用，他们放下左边的叉子再试一次。没有死锁！

但是，有一个问题。如果所有的哲学家同时拿起他们的左手，试图抓住他们的右手，放下他们的左手，再拿起他们的左手，试图抓住他们的右手……我们现在活锁了我们的解决方案！我们可怜的哲学家们仍然饿着，所以让我们给他们一些合适的解决方案。

可行的解决方案

仲裁者（天真和高级）。

天真的仲裁者解决方案是有一个仲裁者（例如一个互斥锁）。让每个哲学家请求仲裁者的许可来吃饭。这个解决方案一次只允许一个哲学家吃饭。当他们吃完后，另一个哲学家可以请求吃饭的许可。

这可以防止死锁，因为没有循环等待！没有哲学家需要等待其他哲学家。

高级仲裁者解决方案是实现一个类，确定哲学家的叉子是否在仲裁者的控制下。如果是，他们把叉子给哲学家，让他吃，然后拿回叉子。这有一个额外的好处，就是能够让多个哲学家同时吃饭。

问题：

• 这些解决方案很慢
  
• 他们有一个单一的故障点，仲裁者使其成为一个瓶颈
  
• 仲裁者在第二个解决方案中也需要公平，并且能够确定死锁
  
• 在实际系统中，仲裁者倾向于重复地将叉子交给刚刚吃过的哲学家，因为进程调度
  

离开桌子（Stallings 的解决方案）

为什么第一个解决方案会死锁？嗯，有 n 个哲学家和 n 根筷子。如果桌子上只有 1 个哲学家怎么办？我们会死锁吗？不会。

2 个哲学家怎么样？3 个？……你可以看出这是怎么回事。Stallings 的解决方案是从桌子上移除哲学家，直到死锁不可能发生——想想桌子上的哲学家的魔数是多少。在实际系统中，通过信号量来实现这一点，并让一定数量的哲学家通过。

问题：

• 解决方案需要大量的上下文切换，这对 CPU 来说非常昂贵
  
• 你需要提前知道资源的数量，以便只让那么多的哲学家
  
• 再次优先考虑那些已经吃过的进程。
  

部分排序（Dijkstra 的解决方案）

这是 Dijkstra 的解决方案（他是在考试中提出这个问题的人）。为什么第一个解决方案会死锁？Dijkstra 认为最后一个拿起他左边叉子的哲学家（导致解决方案死锁）应该拿起他的右边叉子。他通过给叉子编号 1…n，并告诉每个哲学家拿起他较小编号的叉子来实现这一点。

让我们再次运行死锁条件。每个人都试图先拿起他们较小编号的叉子。哲学家 1 拿到叉子 1，哲学家 2 拿到叉子 2，依此类推，直到我们到达哲学家 n。他们必须在叉子 1 和 n 之间做出选择。叉子 1 已经被哲学家 1 拿起，所以他们不能拿起那个叉子，这意味着他不会拿起叉子 n。我们打破了循环等待！这意味着死锁是不可能的。

问题：

• 哲学家在抓取任何资源之前需要知道资源的集合顺序。
  
• 您需要为所有资源定义一个偏序。
  
• 优先考虑已经吃过饭的哲学家。
  

高级解决方案

还有许多更高级的解决方案，非穷尽列表包括

• 干净/脏叉子（钱德拉/米斯拉解决方案）
  
• 演员模型（其他消息传递模型）
  
• 超级仲裁者（复杂的管道）
  

死锁复习问题

主题

Coffman 条件资源分配图餐厅哲学家

• 失败的 DP 解决方案
  
• 活锁 DP 解决方案
  
• 工作的 DP 解决方案：优缺点
  

问题

• 科夫曼条件是什么？
  
• 科夫曼条件的每个意思是什么？（例如，你能提供每个条件的定义吗？）
  
• 举一个打破科夫曼条件的真实例子。一个需要考虑的情况：画家，油漆，画笔等。你如何确保工作会完成？
  
• 能够识别餐厅哲学家代码何时导致死锁（或者不导致）。例如，如果你看到以下代码片段，哪个科夫曼条件没有满足？
  

// Get both locks or none.
pthread_mutex_lock( a );
if( pthread_mutex_trylock( b ) ) { /*failed*/
   pthread_mutex_unlock( a );
   ...
}

• 如果一个线程调用

pthread_mutex_lock(m1) // success
  pthread_mutex_lock(m2) // blocks

还有另一个线程调用

pthread_mutex_lock(m2) // success
  pthread_mutex_lock(m1) // blocks

发生了什么，为什么？如果第三个线程调用pthread_mutex_lock(m1)会发生什么？

• 有多少进程被阻塞？通常情况下，假设一个进程能够完成，如果它能够获取下面列出的所有资源。

• P1 获取 R1
  
• P2 获取 R2
  
• P1 获取 R3
  
• P2 等待 R3
  
• P3 获取 R5
  
• P1 等待 R4
  
• P3 等待 R1
  
• P4 等待 R5
  
• P5 等待 R1
  

（画出资源图！）

七、进程间通信和调度

虚拟内存，第一部分：虚拟内存简介

什么是虚拟内存？

在非常简单的嵌入式系统和早期计算机中，进程直接访问内存，即“地址 1234”对应于物理内存的特定部分中存储的特定字节。在现代系统中，情况已经不再是这样。相反，每个进程都是隔离的；并且存在着一个地址转换过程，将进程的特定 CPU 指令或数据的地址与物理内存（“RAM”）的实际字节对应起来。内存地址不再是“真实的”；进程在虚拟内存中运行。虚拟内存不仅可以保护进程的安全（因为一个进程不能直接读取或修改另一个进程的内存），还允许系统有效地分配和重新分配内存的部分给不同的进程。

MMU 是什么？

内存管理单元是 CPU 的一部分。它将虚拟内存地址转换为物理地址。如果当前没有从特定虚拟地址到物理地址的映射，或者当前 CPU 指令尝试写入进程只有读取访问权限的位置，MMU 也可能中断 CPU。

那么我们如何将虚拟地址转换为物理地址？

想象一下你有一台 32 位的机器。指针可以保存 32 位，即它们可以寻址 2^32 个不同的位置，即 4GB 的内存（我们将遵循一个地址可以保存一个字节的标准约定）。

想象我们有一个大表 - 这是聪明的部分 - 存储在内存中！对于每个可能的地址（共 40 亿个），我们将存储“真实”即物理地址。每个物理地址将需要 4 个字节（以容纳 32 位）。这种方案将需要 160 亿字节来存储所有条目。哎呀 - 我们的查找方案将消耗我们可能为我们的 4GB 机器购买的所有内存。我们需要做得比这更好。我们的查找表最好比我们拥有的内存小，否则我们将没有空间留给我们的实际程序和操作系统数据。解决方案是将内存分成称为“页面”和“帧”的小区域，并为每个页面使用查找表。

什么是页面？有多少个页面？

页面是一块虚拟内存。Linux 操作系统上的典型块大小为 4KB（即 2^12 个地址），尽管您可以找到更大块的示例。

因此，我们不再谈论单个字节，而是谈论 4KB 的块，每个块称为一个页面。我们还可以对我们的页面进行编号（“页面 0”“页面 1”等）

例如：32 位机器有多少页（假设页面大小为 4KB）？

答案：2^32 地址 / 2^12 = 2^20 页。

记住 2^10 是 1024，所以 2^20 略大于一百万。

对于 64 位机器，2^64 / 2^12 = 2^52，大约是 10^15 页。

什么是帧？

帧（有时称为“页帧”）是一块物理内存或 RAM（=随机存取存储器）。这种内存有时被称为“主存储器”（与较慢的辅助存储器相对，例如具有较低访问时间的旋转磁盘）

一个帧的字节数与虚拟页面相同。如果 32 位机器有 2^32（4GB）的 RAM，那么在机器的可寻址空间中将有相同数量的帧。64 位机器不太可能有 2^64 字节的 RAM - 你能看出为什么吗？

什么是页面表，它有多大？

页面表是页面到帧之间的映射。例如，页面 1 可能映射到帧 45，页面 2 映射到帧 30。其他帧可能目前未使用或分配给其他正在运行的进程，或者由操作系统内部使用。

一个简单的页面表就是一个数组，int frame = table[ page_num ];

对于一个 32 位机器，每个 4KB 页面的条目需要保存一个帧号-即 20 位，因为我们计算出有 2^20 个帧。每个条目需要 2.5 个字节！实际上，我们将每个条目四舍五入到 4 个字节，并找到这些多余位的用途。每个条目需要 4 个字节 x 2^20 个条目= 4MB 的物理内存用于存储页表。

对于一个 64 位机器，每个 4KB 页面的条目需要 52 位。让我们将每个条目四舍五入到 64 位（8 字节）。有 2^52 个条目，大约需要 2^55 字节（大约 40PB…）哎呀，我们的页表太大了。

在 64 位体系结构中，内存地址是稀疏的，因此我们需要一种机制来减小页表的大小，因为大多数条目永远不会被使用。

这里有一个页表的视觉示例。想象访问一个数组并获取数组元素。

偏移量是什么，它是如何使用的？

记住，我们的页表将页面映射到帧，但每个页面都是一块连续的地址。我们如何计算在特定帧内使用哪个特定字节？解决方案是直接重用虚拟内存地址的最低位。例如，假设我们的进程正在读取以下地址- VirtualAddress = 11110000111100001111000010101010（二进制）

在页面大小为 256 字节的机器上，最低的 8 位（10101010）将被用作偏移量。剩下的上位位将是页号（111100001111000011110000）。

多级页表

多级页面是 64 位体系结构的页表大小问题的一种解决方案。我们将看看最简单的实现-两级页表。每个表都是指向下一级表的指针列表，不需要所有子表都存在。下面是 32 位体系结构的两级页表的示例-

VirtualAddress = 11110000111111110000000010101010 (binary)
                 |_Index1_||        ||          | 10 bit Directory index
                           |_Index2_||          | 10 bit Sub-table index
                                     |__________| 12 bit offset (passed directly to RAM)

在上述方案中，确定帧号需要两次内存读取：使用顶部的 10 位在页表目录中。如果每个条目使用 2 个字节，我们只需要 2KB 来存储整个目录。每个子表将指向物理帧（即需要 4 个字节来存储 20 位）。然而，对于只需要微小内存的进程，我们只需要指定低内存地址（用于堆和程序代码）和高内存地址（用于堆栈）的条目。每个子表是 1024 个条目 x 4 个字节，即每个子表需要 4KB。因此，我们的多级页表的总内存开销已经从 4MB（单级）减少到 3 帧内存（12KB）！

页表会使内存访问变慢吗？（TLB 是什么）

是的-显著！（但由于聪明的硬件，通常不会…）与直接读取或写入内存相比。对于单个页表，我们的机器现在慢了一倍！（需要两次内存访问）对于两级页表，内存访问现在慢了三倍。（需要三次内存访问）

为了克服这种开销，MMU 包括一个最近使用的虚拟页到帧查找的关联缓存。这个缓存被称为 TLB（“转换旁路缓冲区”）。每当需要将虚拟地址转换为物理内存位置时，TLB 与页表并行查询。对于大多数程序的大多数内存访问，TLB 缓存结果的机会很大。但是，如果一个程序没有良好的缓存一致性（例如从许多不同页面的随机内存位置读取），那么 TLB 将不会有结果缓存，现在 MMU 必须使用速度慢得多的页表来确定物理帧。

这可能是如何分割多级页表的方式。

高级帧和页面保护

帧可以在进程之间共享吗？它们可以被专门化吗？

是的！除了存储帧编号之外，页面表还可以用于存储进程是否可以写入或只读特定帧。只读帧可以安全地在多个进程之间共享。例如，C 库指令代码可以在所有动态将代码加载到进程内存中的进程之间共享。每个进程只能读取该内存。这意味着如果您尝试写入内存中的只读页面，您将收到SEGFAULT。这就是为什么有时内存访问会导致段错误，有时不会，这完全取决于您的硬件是否允许您访问。

此外，进程可以使用mmap系统调用与子进程共享页面。mmap是一个有趣的调用，因为它不是将每个虚拟地址绑定到物理帧，而是绑定到其他东西。这个其他东西可以是文件、GPU 单元或者你能想到的任何其他内存映射操作！写入内存地址可能会直接写入设备，或者写入可能会被操作系统暂停，但这是一个非常强大的抽象，因为操作系统通常能够执行优化（多个进程内存映射相同的文件可以让内核创建一个映射）。

页面表中还存储了什么，以及为什么？

除了上面讨论的只读位和使用统计信息之外，通常至少存储只读、修改和执行信息。

什么是页面故障？

页面故障是指运行中的程序尝试访问其地址空间中未映射到物理内存的某些虚拟内存。页面故障也会在其他情况下发生。

有三种类型的页面故障

次要 如果页面尚未映射，但是是有效地址。这可能是sbrk(2)要求的内存，但尚未写入，这意味着操作系统可以在分配空间之前等待第一次写入。操作系统只需创建页面，将其加载到内存中，然后继续进行。

主要 如果页面的映射不在内存中而在磁盘上。这将会将页面交换到内存中，并将另一个页面交换出去。如果这种情况发生频繁，您的程序就会被称为抖动MMU。

无效 当您尝试写入不可写内存地址或读取不可读内存地址时。MMU 会生成一个无效故障，操作系统通常会生成一个SIGSEGV，表示分段违规，这意味着您写入了超出您可以写入的段的位置。

只读位

只读位将页面标记为只读。尝试写入页面将导致页面故障。然后内核将处理页面故障。只读页面的两个例子包括在多个进程之间共享 c 运行时库（出于安全考虑，您不希望允许一个进程修改库）；以及写时复制，其中复制页面的成本可以延迟到第一次写入发生时。

脏位

en.wikipedia.org/wiki/Page_table#Page_table_data

脏位允许进行性能优化。从磁盘分页到物理内存，然后再次读取，然后再次分页出去的页面不需要写回磁盘，因为页面没有更改。但是，如果页面在分页后被写入，其脏位将被设置，表示页面必须写回备份存储。这种策略要求备份存储在将页面分页到内存后保留页面的副本。当不使用脏位时，备份存储只需与任何时刻分页出的所有页面的瞬时总大小一样大。当使用脏位时，始终会存在一些页面既存在于物理内存中又存在于备份存储中。

执行位

执行位定义了页面中的字节是否可以作为 CPU 指令执行。通过禁用页面，可以防止恶意存储在进程内存中的代码（例如通过堆栈溢出）被轻易执行。（更多阅读：en.wikipedia.org/wiki/NX_bit#Hardware_background）

了解更多

在 x86 平台上，有关分页和页面位的更低级别的技术讨论可在[wiki.osdev.org/Paging]找到。

管道，第一部分：管道介绍

什么是 IPC？

进程间通信是一个进程与另一个进程交流的任何方式。你已经看到了这种虚拟内存的一种形式！一块虚拟内存可以在父进程和子进程之间共享，从而进行通信。你可能想把那块内存包装在pthread_mutexattr_setpshared(&attrmutex, PTHREAD_PROCESS_SHARED);互斥锁（或者进程范围的互斥锁）中，以防止竞争条件。

还有更多标准的 IPC 方式，比如管道！考虑一下，如果你在终端中输入以下内容

$ ls -1 | cut -d'.' -f1 | uniq | sort | tee dir_contents

以下代码做了什么（如果你愿意，你可以跳过这个）？好吧，它ls当前目录（-1 表示它每行输出一个条目）。然后cut命令取得第一个句点之前的所有内容。Uniq 确保所有行都是唯一的，sort 对它们进行排序，tee 输出到一个文件。

重要的部分是 bash 创建了5 个单独的进程并将它们的标准输出/标准输入与管道连接起来，轨迹看起来像这样。

(0) ls (1)------>(0) cut (1)------->(0) uniq (1)------>(0) sort (1)------>(0) tee (1)

管道中的数字是每个进程的文件描述符，箭头表示重定向或管道输出的位置。

什么是管道？

POSIX 管道几乎像它的真实对应物 - 你可以把字节塞进一端，它们会按照相同的顺序出现在另一端。然而，与真实的管道不同，流动方向总是相同的，一个文件描述符用于读取，另一个用于写入。pipe系统调用用于创建管道。

int filedes[2];
pipe (filedes);
printf("read from %d, write to %d\n", filedes[0], filedes[1]);

这些文件描述符可以与read一起使用 -

// To read...
char buffer[80];
int bytesread = read(filedes[0], buffer, sizeof(buffer));

和write -

write(filedes[1], "Go!", 4);

我怎样使用管道与子进程通信？

使用管道的常见方法是在分叉之前创建管道。

int filedes[2];
pipe (filedes);
pid_t child = fork();
if (child > 0) { /* I must be the parent */
    char buffer[80];
    int bytesread = read(filedes[0], buffer, sizeof(buffer));
    // do something with the bytes read 
}

然后子进程可以向父进程发送消息：

if (child == 0) {
   write(filedes[1], "done", 4);
}

我可以在单个进程中使用管道吗？

简短回答：是的，但我不确定你为什么要这样做 LOL！

以下是一个向自己发送消息的示例程序：

#include <unistd.h>
#include <stdlib.h>
#include <stdio.h>
int main() {
    int fh[2];
    pipe(fh);
    FILE *reader = fdopen(fh[0], "r");
    FILE *writer = fdopen(fh[1], "w");
    // Hurrah now I can use printf rather than using low-level read() write()
    printf("Writing...\n");
    fprintf(writer,"%d %d %d\n", 10, 20, 30);
    fflush(writer);
    printf("Reading...\n");
    int results[3];
    int ok = fscanf(reader,"%d %d %d", results, results + 1, results + 2);
    printf("%d values parsed: %d %d %d\n", ok, results[0], results[1], results[2]);
    return 0;
}

以这种方式使用管道的问题在于写入管道可能会阻塞，即管道只有有限的缓冲容量。如果管道已满，写入进程将被阻塞！缓冲区的最大大小取决于系统；典型值从 4KB 到 128KB。

int main() {
    int fh[2];
    pipe(fh);
    int b = 0;
    #define MESG "..............................."
    while(1) {
        printf("%d\n",b);
        write(fh[1], MESG, sizeof(MESG))
        b+=sizeof(MESG);
    }
    return 0;
}

参见Pipes，第二部分：管道编程秘密

管道，第二部分：管道编程秘密

管道陷阱

这里有一个完整的例子，但不起作用！子进程每次从管道中读取一个字节并打印出来-但我们从未看到消息！你能看出原因吗？

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <signal.h>
int main() {
    int fd[2];
    pipe(fd);
    //You must read from fd[0] and write from fd[1]
    printf("Reading from %d, writing to %d\n", fd[0], fd[1]);
    pid_t p = fork();
    if (p > 0) {
        /* I have a child therefore I am the parent*/
        write(fd[1],"Hi Child!",9);
        /*don't forget your child*/
        wait(NULL);
    } else {
        char buf;
        int bytesread;
        // read one byte at a time.
        while ((bytesread = read(fd[0], &buf, 1)) > 0) {
            putchar(buf);
        }
    }
    return 0;
}

父进程将字节H,i,(空格),C...!发送到管道中（如果管道已满，可能会阻塞）。子进程开始逐个字节读取管道。在上面的情况下，子进程将读取并打印每个字符。但它永远不会离开 while 循环！当没有字符可读时，它会简单地阻塞并等待更多。

调用putchar写出字符，但我们从未刷新stdout缓冲区。也就是说，我们已经将消息从一个进程传输到另一个进程，但它还没有被打印出来。要查看消息，我们可以刷新缓冲区，例如fflush(stdout)（或者如果输出是到终端，则printf("\n")）。更好的解决方案还可以通过检查消息结束标记来退出循环，

while ((bytesread = read(fd[0], &buf, 1)) > 0) {
            putchar(buf);
            if (buf == '!') break; /* End of message */
        }

当子进程退出时，消息将被刷新到终端。

想要使用 printf 和 scanf 与管道吗？使用 fdopen！

POSIX 文件描述符是简单的整数 0,1,2,3…在 C 库级别，C 用缓冲区和有用的函数如 printf 和 scanf 包装这些，所以我们可以轻松地打印或解析整数、字符串等。如果你已经有了一个文件描述符，那么你可以使用fdopen将其自己“包装”成一个 FILE 指针：

#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
int main() {
    char *name="Fred";
    int score = 123;
    int filedes = open("mydata.txt", "w", O_CREAT, S_IWUSR | S_IRUSR);
    FILE *f = fdopen(filedes, "w");
    fprintf(f, "Name:%s Score:%d\n", name, score);
    fclose(f);

对于写入文件来说，这是不必要的-只需使用fopen，它与open和fdopen相同。但是对于管道，我们已经有了一个文件描述符-所以现在是使用fdopen的好时机！

这里有一个使用管道的完整例子，几乎可以工作！你能发现错误吗？提示：父进程从未打印任何内容！

#include <unistd.h>
#include <stdlib.h>
#include <stdio.h>
int main() {
    int fh[2];
    pipe(fh);
    FILE *reader = fdopen(fh[0], "r");
    FILE *writer = fdopen(fh[1], "w");
    pid_t p = fork();
    if (p > 0) {
        int score;
        fscanf(reader, "Score %d", &score);
        printf("The child says the score is %d\n", score);
    } else {
        fprintf(writer, "Score %d", 10 + 10);
        fflush(writer);
    }
    return 0;
}

请注意，（未命名的）管道资源将在子进程和父进程都退出后消失。在上面的例子中，子进程将从管道发送字节，父进程将从管道接收字节。然而，从未发送换行符，因此fscanf将继续请求字节，因为它正在等待行结束，即它将永远等待！修复方法是确保我们发送一个换行符，这样fscanf将返回。

change:   fprintf(writer, "Score %d", 10 + 10);
to:       fprintf(writer, "Score %d\n", 10 + 10);

那我们也需要fflush吗？

是的，如果你希望你的字节立即发送到管道中！在本课程开始时，我们假设文件流始终是行缓冲，即 C 库每次发送换行符时都会刷新其缓冲区。实际上，这只对终端流有效-对于其他文件流，C 库尝试通过仅在其内部缓冲区满或文件关闭时刷新来提高性能。

我什么时候需要两个管道？

如果你需要异步地向子进程发送和接收数据，那么需要两个管道（每个方向一个）。否则，子进程将尝试读取自己的数据，这些数据是为父进程准备的（反之亦然）！

关闭管道的陷阱

当没有进程在监听时，进程会收到信号 SIGPIPE！来自 pipe(2)手册页-

If all file descriptors referring to the read end of a pipe have been closed,
 then a write(2) will cause a SIGPIPE signal to be generated for the calling process.

提示：注意只有写入者（不是读取者）可以使用此信号。为了通知读取者写入者正在关闭管道的端口，你可以写入自己的特殊字节（例如 0xff）或消息（"再见！"）

这里有一个捕捉这个信号的例子，但不起作用！你能看出原因吗？

#include <stdio.h>
#include <stdio.h>
#include <unistd.h>
#include <signal.h>
void no_one_listening(int signal) {
    write(1, "No one is listening!\n", 21);
}
int main() {
    signal(SIGPIPE, no_one_listening);
    int filedes[2];
    pipe(filedes);
    pid_t child = fork();
    if (child > 0) { 
        /* I must be the parent. Close the listening end of the pipe */
        /* I'm not listening anymore!*/
        close(filedes[0]);
    } else {
        /* Child writes messages to the pipe */
        write(filedes[1], "One", 3);
        sleep(2);
        // Will this write generate SIGPIPE ?
        write(filedes[1], "Two", 3);
        write(1, "Done\n", 5);
    }
    return 0;
}

上面代码中的错误是仍然有一个管道的读取者！子进程仍然保持着管道的第一个文件描述符，并记住规范？所有读取者必须关闭。

在分叉时，*关闭子进程和父进程中每个管道的不必要（未使用）端口是常见做法。例如，父进程可能关闭读取端口，子进程可能关闭写入端口（如果有两个管道，则反之亦然）

是什么填满了管道？当管道变满时会发生什么？

当写入者向管道写入过多而读者没有读取时，管道会被填满。当管道变满时，所有写入都会失败，直到发生读取。即使在这种情况下，如果管道还有一点空间但不足以容纳整个消息，写入也可能部分失败。

为了避免这种情况，通常有两种方法。要么增加管道的大小。或者更常见的是，修复你的程序设计，使得管道不断被读取。

管道是否进程安全？

是的！管道写入是原子的，直到管道的大小。这意味着如果两个进程尝试写入同一个管道，内核会使用管道的内部互斥锁来锁定，进行写入，然后返回。唯一需要注意的是当管道即将变满时。如果两个进程尝试写入，而管道只能满足部分写入，那么该管道写入就不是原子的–要小心！

管道的生命周期

无名管道（到目前为止我们见过的那种）存在于内存中（不占用任何磁盘空间），是一种简单高效的进程间通信（IPC）形式，对于流数据和简单消息非常有用。一旦所有进程关闭，管道资源就会被释放。

使用mkfifo创建命名管道是无名管道的一种替代方法。

命名管道

我如何创建命名管道？

从命令行：mkfifo 从 C 语言：int mkfifo(const char *pathname, mode_t mode);

你给它路径名和操作模式，它就准备好了！命名管道在磁盘上不占用空间。当操作系统告诉你有一个命名管道时，它实际上是在告诉你它会创建一个指向命名管道的无名管道，就是这样！没有额外的魔法。这只是为了编程方便，如果进程在没有分叉的情况下启动（这意味着无法为无名管道的子进程获取文件描述符）。

为什么我的管道挂起？

在命名管道上的读写会一直挂起，直到至少有一个读者和一个写者，记住这一点

1$ mkfifo fifo
1$ echo Hello > fifo
# This will hang until I do this on another terminal or another process
2$ cat fifo
Hello

当在命名管道上调用任何open时，内核会阻塞，直到另一个进程调用相反的 open。也就是说，echo 调用open(.., O_RDONLY)，但是它会阻塞，直到 cat 调用open(.., O_WRONLY)，然后程序才被允许继续。

命名管道的竞争条件。

以下程序有什么问题？

//Program 1
int main(){
    int fd = open("fifo", O_RDWR | O_TRUNC);
    write(fd, "Hello!", 6);
    close(fd);
    return 0;
}
//Program 2
int main() {
    char buffer[7];
    int fd = open("fifo", O_RDONLY);
    read(fd, buffer, 6);
    buffer[6] = '\0';
    printf("%s\n", buffer);
    return 0;
}

这可能永远不会打印 hello，因为存在竞争条件。由于你在第一个进程中以两种权限打开了管道，open 不会等待读者，因为你告诉操作系统你是读者！有时它看起来像是工作的，因为代码的执行看起来像这样。

有时候不会

文件，第一部分：处理文件

两种类型的文件

在 Linux 上，有两种文件抽象。第一种是 Linux 的fd级别抽象，这意味着你可以使用

• 打开
  
• 读
  
• 写
  
• 关闭
  
• lseek
  
• fcntl …
  

等等。Linux 接口非常强大和富有表现力，但有时我们需要可移植性（例如，如果我们在为 Mac 或 Windows 编写代码）。这就是 C 的抽象发挥作用的地方。在不同的操作系统上，C 使用低级函数来创建一个文件的包装器，你可以在任何地方使用，这意味着 Linux 上的 C 使用上述调用。C 有以下几种

• fopen
  
• fread或fgetc/fgets或fscanf
  
• fwrite或fprintf
  
• fclose
  
• fflush
  

但你无法获得 Linux 通过系统调用给你的表达能力，你可以在它们之间进行转换，使用int fileno(FILE* stream)和FILE* fdopen(int fd...)。

另一个重要的方面要注意的是 C 文件是缓冲的，这意味着它们的内容可能不会立即被写入。你可以通过 C 选项来改变这一点。

UIUC CS241 讲义：众包系统编程书（6）https://developer.aliyun.com/article/1427164