shesl-meow
博客 标签 分类 笔记
游戏
2048 Schulte
shesl-meow

期末复习

概念

快表，TLB（Translation Look-aside Buffer）：

反置页表

缺页中断

缺页中断的处理流程：

  1. 在内存中有空闲物理页面时，分配一物理页帧 f，转第 5 步；
  2. 依据 页面置换算法 选择将被替换的物理页帧 f，对应逻辑页 q；
  3. 如果 q 被修改过，则把它写回外存；
  4. 修改 q 的页表项中驻留位置为 0；
  5. 将需要访问的页 p 装入到物理页面 f；
  6. 修改 p 的页表项驻留位为 1，物理页帧号为 f；
  7. 重新执行产生缺页的指令；

进程间通信

进程间通信（InterProcess Communication）有哪些方式？

信号：信号是 Linux 系统中用于进程之间通信或操作的一种机制

  • 信号可以在任何时候发送给某一进程，而无须知道该进程的状态。

  • 如果该进程并未处于执行状态，则该信号就由内核保存起来，知道该进程恢复执行并传递给他为止。

  • 如果一个信号被进程设置为阻塞，则该信号的传递被延迟，直到其阻塞被取消时才被传递给进程。

管道：管道是 Linux 支持的最初 Unix IPC 形式之一

  • 管道是半双工的，数据只能向一个方向流动；需要双方通信时，需要建立起两个管道；

  • 匿名管道只能用于父子进程或者兄弟进程之间（具有亲缘关系的进程）；

    在 C 语言代码中，可以直接调用 pipe 函数：

    1
2

    int pipe_fd[2];
assert(pipe(pipe_fd) >= 0);

  • 命名管道有一个名字，命名管道的名字对应于一个磁盘索引节点，有了这个文件名，任何进程有相应的权限都可以对它进行访问。

    在 shell 中，使用如下两条命令创建是等价的：

    1
2
3

    $ mkfifo myfifo

$ mknod myfifo p

  • 单独构成一种独立的文件系统：管道对于管道两端的进程而言，就是一个文件，但它不是普通的文件，它不属于某种文件系统，而是自立门户，单独构成一种文件系统，并且只存在与内存中。

消息队列：一系列保存在内核中消息的列表。用户进程可以向消息队列添加消息，也可以向消息队列读取消息。

  • 消息队列与管道通信相比，其优势是对每个消息指定特定的消息类型，接收的时候不需要按照队列次序，而是可以根据自定义条件接收特定类型的消息。

  • 可以把消息看做一个记录，具有特定的格式以及特定的优先级。对消息队列有写权限的进程可以向消息队列中按照一定的规则添加新消息，对消息队列有读权限的进程可以从消息队列中读取消息。

共享内存：共享内存允许两个或多个进程共享一个给定的存储区

  • 这一段存储区可以被两个或两个以上的进程映射至自身的地址空间中，一个进程写入共享内存的信息，可以被其他使用这个共享内存的进程，通过一个简单的内存读取错做读出，从而实现了进程间的通信。

  • 采用共享内存进行通信的一个主要好处是效率高，因为进程可以直接读写内存，而不需要任何数据的拷贝，对于像管道和消息队里等通信方式，则需要再内核和用户空间进行四次的数据拷贝，而共享内存则只拷贝两次：一次从输入文件到共享内存区，另一次从共享内存到输出文件。

IPC 问题

有哪些 IPC 问题？

  • 生产者消费者问题；

  • 读者写者问题：读读不互斥、读写互斥、写写互斥；

    • 读者优先解决方案。一些变量的定义如下：

      1
2
3
4
5
6

      typedef int mutex;
int reader_amount = 0;
mutex writer_exclusive = 1, amount_exclusive = 1;

extern void P(mutex &);
extern void V(mutex &);

      读者和写者的代码如下：

       1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

      void read () {
  P(amount_exclusive);
  if (reader_amount++ == 0) P(writer_exclusive);
  V(amount_exclusive);

  do_read();

  P(amount_exclusive);
  if (--reader_amount == 0) V(writer_exclusive);
  V(amount_exclusive);
}

void write () {
  P(writer_exclusive);
  do_write();
  V(writer_exclusive);
}

    • 公平解决方案（没有任何一个在写者之后到来的读者，会先于它执行）。一些变量的定义如下：

      1
2
3
4
5
6
7

      typedef int mutex;
int reader_amount = 0, writer_amount = 0;
mutex ramount_exclusive = 1, wamount_exclusive = 1;
mutex fairness = 1, writer_exclusive = 1;

extern void P(mutex &);
extern void V(mutex &);

      读者和写者的代码如下：

       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

      void read () {
  P(fairness);
  P(ramount_exclusive);
  if (reader_amount++ == 0) P(writer_exclusive);
  V(ramount_exclusive);
  V(fairness);

  do_read();

  P(ramount_exclusive);
  if (--reader_amount == 0) V(writer_exclusive);
  V(ramount_exclusive);
}

void write () {
  P(wamount_exclusive);
  if (writer_amount++ == 0) P(fairness);
  V(wamount_exclusive);

  P(writer_exclusive);
  do_write();
  V(writer_exclusive);

  P(wamount_exclusive);
  if (--writer_amount == 0) V(fairness);
  V(wamount_exclusive);
}

  • 沉睡的理发师问题；

  • 哲学家就餐问题；

IPC 问题的解决方案？

  • 信号量：一种抽象的数据结构，由一个整形变量和两个原子操作（P 减少、V 增加）构成；
  • 管程：一个锁（控制管程代码互斥访问）和多个条件变量（管理共享数据的并发访问）构成；
    • 条件变量是管程内的等待机制，每个条件条件变量表示一个等待原因，对应一个等待队列；
    • 内部主要有两种函数操作 Wait() 与 Signal()；

进程调度算法

如何评价一个调度算法的优劣？

  • CPU 使用率：CPU 处于忙状态的时间百分比；
  • 吞吐量：单位时间内完成的进程数量；
  • 等待时间：进程在就绪队列中，没有执行任务的总时间；
  • 响应时间：从提交请求到产生响应所花费的总时间；
  • 周转时间：进程从开始到结束（包括等待时间）的总时间；

进程调度有哪些算法？

  • 先来先服务算法（First Come First Served, FCFS）；
  • 短进程优先算法（SPN）、短剩余时间优先算法（SRT）；
  • 高响应比优先算法（HRRN）；
  • 时间片轮转算法（Round-Robin, RR）；
  • 多级队列调度算法（MQ）；
  • 多级反馈队列算法（MLFQ）；
  • 优先级算法：静态优先级、动态优先级、线性优先级调度算法（SSR, Selfish Round Robin）

页面置换算法

什么是页面置换算法？

  • 作用：当出现缺页异常，需调入新页面而内存已满时，置换算法选择被置换的物理页面；
  • 目标：尽可能减少页面的调入调出次数；

页面置换算法有哪些？

  • 最优页面置换算法（OPT）：一种想象出来的理想算法；

  • 先进先出算法（First-In First-Out, FIFO）；

  • 最近最久未使用算法（Least Rencently Used, LRU）；

  • 最不常用算法（Least Frequently Used, LFU, NRU）；

  • 时钟置换算法（Clock）；