Anran758's blog

0%

操作系统复习笔记

发表于 更新于 分类于 阅读次数： Disqus：
本文字数： 3.7k 阅读时长 ≈ 5 分钟

「操作系统」课程的相关学习笔记。

操作系统调度

什么是多道程序设计?

多道程序设计是一种允许多个程序同时存在于内存中，并且能够被处理器轮流处理的技术。这种方法提高了计算机系统的利用率和吞吐量。

多处理器调度算法设计

在多处理器系统中，调度算法的设计不仅要决定选择哪一个进程执行，还需决定它将在哪一个CPU上执行。考虑因素包括：

  • 进程在多个CPU之间迁移时的开销，例如高速缓存失效、TLB失效。
  • 尽量使进程在同一个CPU上执行以减少高速缓存失效和TLB失效问题。
  • 考虑负载均衡，使所有CPU都处于忙碌状态。

重点概念

  • 调度时机
  • 进程切换
  • 抢占/非抢占
  • 时间片
  • 优先级反转
  • 饥饿
  • 优先级与优先数
  • 优先级提升
  • 先来先服务 (FCFS)
  • 短作业优先 (SJF)
  • 多级队列反馈
  • 吞吐量
  • 周转时间
  • 响应时间

进程同步与互斥

进程的并发执行

并发是操作系统设计的基础，也是许多问题产生的源头。当多个进程并发执行时，为了防止对共享资源的冲突访问，需要实现进程间的同步和互斥。

竞争条件指两个或多个进程在读写某些共享数据时，最终结果依赖于进程运行的具体时序。

进程互斥

进程互斥可以通过软件方案或硬件方案来解决。

软件方案:

  • Dekker 解法 和 Peterson 解法: 这两种算法都是在软件层面解决进程互斥的经典方法，适用于双进程系统，通过共享变量协调进程，以避免临界区的同时访问。
  • 编程技巧: 包括使用各种锁机制（如互斥锁）、条件变量等，在编程时实现进程互斥。

硬件方案:

  • 屏蔽中断: 这是一个在单处理器环境中有效的简单方法，通过暂时屏蔽中断来避免进程切换，从而保护临界区代码的执行。但它可能限制CPU的并发能力，且不适用于多处理器环境。
  • TSL(XCHG)指令: 这是一种硬件支持的原子操作，用于创建锁和其他同步机制。
  • 忙等待(busy waiting) 和 自旋锁: 在等待锁释放时持续检查锁的状态，适用于锁等待时间较短的场景。
  • 优先级反转: 解决多线程环境中由于线程优先级不同而造成的资源竞争问题。

进程同步

进程同步: 指系统中多个进程中发生的事件存在某种时序关系，需要相互合作共同完成一项任务。具体来说，一个进程在运行到某一点时，可能需要等待另一进程提供的消息，未获取消息前，进程进入阻塞态，获得消息后被唤醒进入就绪态。

生产者/消费者问题: 这是进程同步的一个典型案例。需要确保：

  • 当缓存区已满时，生产者不会继续向其中添加数据。
  • 当缓存区为空时，消费者不会从中移走数据。
  • 使用睡眠与唤醒操作（原语）来避免忙等待，这样生产者和消费者只在需要时被唤醒。

信号量

信号量是一种特殊类型的整数变量，主要用于进程间同步和互斥控制。它的值用于表示可用资源的数量或进程间的信号状态，它的示例代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int count;
    // 此处简化，实际应用中应有等待队列等更复杂的机制
} semaphore;

void initialize(semaphore *s, int value) {
    s->count = value;
}

void P(semaphore *s) {
    s->count--;
    if (s->count < 0) {
        // 进程进入等待状态
        // ...
    }
}

void V(semaphore *s) {
    s->count++;
    if (s->count <= 0) {
        // 唤醒等待队列中的一个进程
        // ...
    }
}

// 假设的共享资源
int sharedResource = 0;

void process1(semaphore *mutex) {
    P(mutex); // 请求进入临界区
    // 临界区开始
    sharedResource++;  // 对共享资源进行操作
    printf("Process 1 incremented shared resource to %d\n", sharedResource);
    // 临界区结束
    V(mutex); // 离开临界区，释放资源
}

void process2(semaphore *mutex) {
    P(mutex); // 请求进入临界区
    // 临界区开始
    sharedResource--;  // 对共享资源进行操作
    printf("Process 2 decremented shared resource to %d\n", sharedResource);
    // 临界区结束
    V(mutex); // 离开临界区，释放资源
}

int main() {
    semaphore mutex;
    initialize(&mutex, 1); // 初始化互斥信号量

    // 以下为简化表示，实际应用中需要创建线程或进程
    process1(&mutex); // 模拟进程1
    process2(&mutex); // 模拟进程2

    return 0;
}

解决互斥问题的基本步骤

  1. 分析并发进程的关键活动，划定临界区：

    • 在并发编程中，临界区是指那些访问共享资源（如共享变量）的代码段。
    • 临界区的访问需要被严格控制，以防止数据不一致或竞态条件。

  2. 设置一个信号量 mutex（互斥量），初始值为 1：

    • mutex 是一种特殊的信号量，用于控制对临界区的访问。
    • 初始值设为 1，表示一次只允许一个进程进入临界区。

  3. **在临界区前实施 P(mutex)**：

    • P 操作（也称为等待或申请操作）用于申请进入临界区。
    • 当 mutex 的值为 1（表示临界区可用），执行 P 操作会将其减为 0，进程进入临界区。
    • 如果 mutex 为 0（临界区正在被另一个进程占用），则执行 P 操作的进程会被阻塞，直到临界区变为可用。

  4. **在临界区之后实施 V(mutex)**：

    • V 操作（也称为信号或释放操作）用于释放临界区。
    • 执行 V 操作会将 mutex 增加 1，如果有其他进程因试图执行 P 操作而被阻塞，其中一个会被唤醒以进入临界区。

  5. 资源的申请与释放：

    • 每次 P 操作意味着进程请求分配到一个资源（在此上下文中，资源是对临界区的访问权限）。
    • 每次 V 操作意味着进程释放了一个资源，使得其他进程可以申请该资源。

  6. 信号量值 mutex <= 0 的情况：

    • 当 mutex 的值小于或等于 0 时，表示临界区不可用或有一个或多个进程在等待进入临界区。
    • 这种机制确保了对共享资源的互斥访问，防止了并发进程间的冲突。

重点概念：

  • 竞争条件
  • 与时间有关的错误
  • 忙等待
  • 临界资源
  • 临界区
  • 进程互斥
  • 进程同步
  • 信号量
  • p、v 操作
  • 锁
  • 自旋锁
  • 生产者消费者问题
  • 读者写者问题

管程：同步机制的进阶解决方案

管程是为了解决信号量机制在程序编写上的困难和易出错性而引入的。它是一种高级同步机制，被集成到多种高级编程语言中。

管程要解决两个问题：互斥和同步。

  • 互斥：管程确保任一时刻，只有一个进程可以执行管程内的代码，以保护数据结构的完整性。这种互斥性由编译器来保证。
  • 同步：管程使用条件变量及其等待和唤醒操作来解决同步问题。

可以将收银柜台作为一个管程。在这个管程中，一次只允许一位顾客（进程）进行结账（互斥访问）。在柜台前，有一个等待队列，其他顾客必须在这里排队，直到当前顾客完成结账并离开柜台（入口等待队列）。

顾客 A 正在柜台结账时，发现他忘记拿一瓶酱油了（等待条件未满足）。这时，顾客 A 不能继续结账，所以他暂时离开柜台去拿酱油（在一个条件变量上执行 wait 操作），同时允许下一位顾客 B 使用柜台。

管程的组成

  • 抽象数据类型：管程封装了数据和对数据的操作。
  • 操作集合：只有通过这些定义好的操作，才能访问和修改管程中的数据。

值得注意的是：管程内的资源只能通过管程的特定过程来访问。管程本身是互斥的，即任何时刻只允许一个进程或线程执行管程中的一个过程。

条件变量

条件变量是一种特殊类型的变量，用于管程内部，以提供进程间的通信或同步。常见操作包括 wait/signal、wait/notify 或 wait/broadcast。

I/O 性能问题

  • 使CPU利用率尽可能不被 I/O 降低
  • 使CPU尽可能摆脱 I/O

解决方案：

  • 缓冲技术：减少速度差异。
  • 异步 I/O：使 CPU 不需要等待 I/O 完成。
  • DMA 和通道：通过硬件手段减轻 CPU 的 I/O 负担。

异步传输 I/O

由系统实现：

  • 通过切换到其他线程保证 CPU 的利用率
  • 对少量数据的 I/O 操作会引入切换的开销

由用户的实现：

  • 将访问控制分为两段进行(发起读取请求，然后去做别的命令，当完成别的事情后回来，发现还在读取，使用 wait 命令继续等待)
  • 发出读取指令后继续做其他操作
  • 当需要用读入的数据时，再使用 wait 命令等待其完成
  • 不引入线程切换，减少开销

死锁、活锁、饥饿的区别

  • 死锁：多个进程相互等待对方持有的资源，导致无法前进。
  • 活锁：进程在尝试解决冲突时持续变更状态，但实际上没有取得进展。
  • 饥饿：某个进程由于资源分配策略，长时间无法获得所需资源。

置换算法

  1. 最佳置换算法 (OPTimal replacement，OPT)
  2. FIFO置换算法
  3. LRU置换算法
相关文章
「请笔者喝杯奶茶鼓励一下」

欢迎关注我的其它发布渠道