Puitar's Blog
0%

OS期末铧锺碘

Posted on Edited on In ,

操作系统铧锺碘

期末考占总评的40%

老师提到的考试复习指南：

  • 注重应用，需要直到API怎么用，各个参数是什么
  • 能够举一些例子
  • 从网络上找一些经典的资料

四个简答题

分值：5分一个

进程

  • 各种调度算法是什么样的。各种调度算法有什么特点，还存在什么问题？
  • 多级反馈队列为什么常用，彩票调度算法和步长调度算法等公平份额算法为什么不行？

各种调度算法的特点和优缺点

先进先出(FIFO)
  • 先进先出（First In First Out，FIFO），或者又叫做先到先服务（First Come First Served，FCFS）

image-20220614133547462

  • 优点：简单，易于实现（最符合直觉的策略）
  • 存在问题：
    • 存在护航效应（一些耗时较少的潜在资源消费 者被排在重量级的资源消费者之后）。简而言之就是：先到达的长进程让后到达的短进程饿死。
    • 周转时间和响应时间都是糟糕的。
最短任务(作业)优先(SJF)
  • 最短任务优先（First Job First，SJF）：先运行最短的任务，然后是次短的任务，如此下去。

image-20220614133837340

  • 特点：
    • SJF在所有作业同时到达的情况下是最优（optmial，opt）调度算法。
    • 它是非抢占式的，如果长任务比短任务先到达，还是会有护航效应。
  • 优点：
    • 周转时间很好
  • 缺点：
    • 响应时间不好
最短完成时间优先(STCF)
  • 向SJF添加抢占，就是最短完成时间优先（Shortest Time-to-Completion First，STCF）或者称作抢占式最短作业优先（Preemptive Shortest Job）调度程序

image-20220614135705282

  • 特点：
    • STCF在作业不同时到达的情况下延续了SJF的最优性
    • 它是抢占式的，如果长任务先到达，短任务后到达，短任务会抢占CPU先执行。
  • 优点：
    • 周转时间很好
  • 缺点：
    • 响应时间不好
轮转
  • 轮转（Round-Robin，RR），又称作时间切片（time-slicing）：RR在一个时间片（time slice，有时称为调度量子，scheduling quantum）内工作，然后切换到运行队列的下一个任务，而不是运行一个任务直到结束。它反复运行，直到所有任务完成。

image-20220614140940324

  • 时间片长度影响性能：越短，响应时间越好；太短，频繁切换上下文影响整体性能。
  • 特点：是一种公平调度算法
  • 优点：
    • 响应时间好
  • 缺点：
    • 周转时间差
  • 进一步优化：重叠RR，考虑了IO，需要IO的任务让出CPU在完成前不参与调度。
多级反馈队列(MLFQ)
  • 规则：期中考过了，我觉得不会再考，但是仍然很重要。
    • 规则1：如果A的优先级>B的优先级，运行A（不运行B）。
    • 规则2：如果A的优先级=B的优先级，轮转运行A和B。
    • 规则3：工作进入系统时，放在最高优先级（最上层队列）。
    • 规则4：一旦工作用完了在某一层中的时间配额（无论中间主动放弃多少次CPU），就降低优先级（移入低一级队列）。
    • 规则5：经过一段时间S，就将系统中所有工作重新加入最高优先级队列。
  • 特点：
    • 在没有任务长短的先验知识情况下，同时优化了周转时间和响应时间。
    • 采用多级队列，每个队列代表一个优先级。
  • 优点：
    • 对于短时间运行的交互型工作，获得类似SJF/STCF的很好的全局性能（周转时间）。
    • 同时对长时间运行的CPU密集型负载也可以公平地运行（响应时间）。
彩票调度(Lottery)
  • 给每个进程分发⼀定量的彩票，每次调 度时随机抽出⼀个号码，被抽中的进程获得CPU。
  • 彩票数（tickets）代表了进程占有某个资源地份额。一个进程拥有的彩票占总数地百分比，就是占有资源的份额。

image-20220614142733606

  • 特点：
    • 充分利用了随机性
    • 从概率上满足期望的比例，但不能确保。运行时间越长，得到的CPU时间比例越接近期望。
  • 优点：
    • 可以避免奇怪的边角情况。
    • 很轻量，几乎不需要记录任何状态
    • 随机方法很快
  • 缺点：
    • 工作时间很短的时，平均不公平度很差。只有运行很多时间片时，才得到期望结果。
步长调度算法(Stride)
  • 给每个进程分发⼀定量的彩票，用一个大数除以彩票得到步长，程序被调度⼀次则累计⼀次行程值（pass值 += 步长），每次调度行程值最小的进程。

image-20220614144327579

  • 优点：在给定优先级的情况下，达到绝对公平，比彩票调度优化了确定性。
  • 缺点：需要一个全局状态(pass值)

为什么MLFQ可用，彩票步长不用

  • MLFQ可用的原因就是它的优点：

    • 对于短时间运行的交互型工作，获得类似SJF/STCF的很好的全局性能（周转时间）。
    • 同时对长时间运行的CPU密集型负载也可以公平地运行。

  • 彩票步长不广泛使用的原因：

    • 一个原因是这两种方式都不能很好地适合I/O；
    • 另一个原因是其中最难的票数分配问题并没有确定的解决方式。

虚拟内存

  • 虚拟内存空间是什么？
  • 为什么需要虚拟内存空间而不是直接使用物理内存空间？
  • 使用虚拟内存空间的目标或者说是指标是什么？

什么时虚拟内存空间？

虚拟内存是计算机系统内存管理的一种技术。它负责为程序提供一 个巨大的、稀疏的、私有的地址空间的假象，其中保存了程序的所有指令和数据。而实际上，它通常是被分隔成多个物理内存片段，还有部分暂时存储在外部磁盘存储器上，在需要时进行数据交换。

为什么需要虚拟内存空间？

主要是虚拟内存提供了三个主要的好处：易于使用，高性能，可靠。

  • 虚拟内存可以为进程提供独立的内存空间并引入多层的页表结构将虚拟内存翻译成物理内存，进程之间可以共享物理内存减少开销，也能简化程序的链接、装载以及内存分配过程；
  • 虚拟内存可以结合磁盘和物理内存的优势为进程提供看起来速度足够快并且容量足够大的存储；
  • 虚拟内存可以控制进程对物理内存的访问，隔离不同进程的访问权限，提高系统的安全性；

虚拟内存的目标（指标）

image-20220615010114930

image-20220615010135694

并发

  • 什么是并发？并发的概念是什么？
  • 竞态条件、临界区等概念

什么是并发

并发当有多个线程在操作时,如果系统只有一个CPU,则它不可能真正同时进行一个以上的线程，它只能把CPU运行时间划分成若干个时间段,再将时间段分配给各个线程执行，在一个时间段的线程代码运行时，其它线程处于挂起状。这种方式我们称之为并发。

什么是临界区、竞态条件等

image-20220614155546936

持久

明确为：崩溃一致性

  • 什么是崩溃一致性
  • 崩溃一致性存在什么例子

什么是崩溃一致性问题

文件系统如何在出现断电（power loss）或系统崩溃（system crash）的情况下，更新持久数据结构。这称为崩溃一致性问题。

存在什么例子

  • 课本42.1

简单描述就是：

image-20220615161654399

考虑一种情况是将单个数据块附加到原有文件末尾。则这个过程文件需要更新的有：数据位图增加一个表示数据块有效的位；更新inode中的数据块指针等；更新数据块Db。

现在我们考虑6种不一致现象：

  • 只更新了数据块。此时，该文件的inode中没有指向Db的指针。Db的写入相当于无效。
  • 只更新了inode。此时，数据块没有更新，导致读取这个块返回给用户垃圾数据。同时出现文件系统不一致，数据位图告诉我们Db这个块未分配，但是inode认为它分配了。
  • 只更新了数据位图。此时，同样出现文件系统不一致，数据位图认为Db这个块分配了，但是inode没有指向它。如果不解决，会造成空间泄露。
  • 只更新了inode和数据位图。此时文件系统的元数据是一致的。但是数据没有更新，造成了垃圾数据。
  • 只更新了inode和数据块。inode能够指向正确的数据块。但是又出现了文件系统给元数据不一致（inode和位图）。
  • 只更新了数据位图和数据块。inode和位图的不一致性问题。没有inode指向这个块。

五个计算题加分析题

共计80分，其中由于计科期中考试进程考的比较多，进程部分的分值会少一点

五个答题主要是1+2+1+1：进程一个，虚拟内存两个，并发一个，文件部分一个

进程x1

没给提示。有可能是fork和exec相关的。

  • （12 分）描述进程与线程以及它们之间的区别和联系。分析给出下图代码（图 5-1）在控 制台可能输出的信息；代码（图 5-2）可能会创建多少个进程，多少个线程。（答案5，2）

image-20220615163218702

image-20220615163231423

img

虚拟内存x2

有两个题，由于现代操作系统普遍使用分页管理机制，而不是分段管理机制，所以着重在分页上（自己体会这句话）。而且他不怎么说分段，所以肯定考分页。

  • 首先要搞懂最简单的线性页表，它有什么缺陷？
  • 页表使得访存需要增加额外的访问页表的成本，所以很慢。为此有了TLB加速缓存。TLB是怎么工作的。
  • 线性页表（一级）存储太大，所以有了多级页表。搞清楚怎么做的特别是二级三级页表。（我觉得是三级页表，老师提到了两三次）
  • 在页表中除了物理页号，还有一些其他的属性位，都有些什么，它们代表什么含义？（例如有效位、存在位等）
  • 通过上面的页表机制，给定一个虚拟地址，怎么计算它的物理地址？
  • 超越物理内存（置换策略）

  • 线性页表（linear page table），就是一个数组。操作系统通过虚拟页号（VPN）检索该数组，并在该索引处查找页表项（PTE），以便找到期望的物理帧号（PFN）。

  • 线性页表存在的问题就是太慢和太大

    • 对应的解决办法就是TLB和分级页表

  • TLB和多级页表很重要，但是请见书本。

  • 一些属性位：

    image-20220614162257586

    上图包含一个存在位（P），确定是否允 许写入该页面的读/写位（R/W） 确定用户模式进程是否可以访问该页面的用户/超级用户位 （U/S），有几位（PWT、PCD、PAT 和 G）确定硬件缓存如何为这些页面工作，一个访问位 （A）和一个脏位（D），最后是页帧号（PFN）本身。

    • 有效位(V)：用于指定特定的地址转换是否有效
    • 保护位(R/W)：表明页是否可以读取、写入或执行
    • 存在位(P)：表示该页是在物理存储器上还是在磁盘交换区上
    • 参考位(A)：又称访问位，用于追踪页是否被访问，也用于确定哪些页很受欢迎，应该保留在内存中。
    • 脏位(D)：标示该页是否被写过

  • 怎么用页表进行地址转换请看书

    • 不难，就是查表
    • 需要注意，物理页（帧）号拼上页偏移才是物理地址。

  • 超越物理内存（置换策略）

    • 平均内存访问时间（Average Memory Access Time，AMAT）

    • 最优策略是MIN（无法实现，作为策略追求的性能上界）

    • 简单策略FIFO

      image-20220614163007021

    • 随机策略

      image-20220614163049148

    • 最近最少使用（Least-Recently-Used，LRU）

      image-20220614163141209

    • 最不经常使用”（Least-Frequently-Used， LFU）（历史信息中使用频次最低的）

  • image-20220615021516526

    • 基本思想：
      • 分段是指将虚拟地址空间中代码、堆、栈等段分别映射到物理内存，而不是将整 个虚拟地址空间全部映射到物理内存。
      • 分页是将虚拟地址空间等分为固定大小的页 （如 4KB），以页的方式将虚拟地址空间与物理内存进行映射。
    • 地址转换过程：
      • 分段主要是把不同的段，借助两个寄存器（基址寄存器和界限寄存器），其中物理地址等同于基址寄存器中存储的段机制加上段内偏移。界限寄存器主要实现了段的保护功能。
      • 页的地址转换是将虚拟地址分成虚拟页号部分和页偏移部分。虚拟页号通过页表存储的物理帧号实现虚拟页号到物理页号的映射。由于偏移不变，所以把得到的物理页号拼上偏移就是物理地址。
    • 优缺点：
      • 分段的优点是硬件支 持比较简单；缺点是可能会导致外部碎片、空闲空间的管理比较复杂。
      • 分页的优点是 空间管理简单、没有外部碎片，缺点是页表存储空间大、地址翻译慢（需要 TLB 加 速），因此需要硬件的支持较多。

并发x1

由于并发的计算分析大题只考一个，而且老师又提示说会考一提编程相关的代码题，要会用函数，会用接口。肯定就是这题。

用信号量解决理发师问题。如果有余力也可以看看信号量解决吸烟者问题。我觉得就是理发师

类似这个历年真题。把打印员换成理发师，就是经典的理发师问题。

image-20220615151151214

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
#define NUM_CHAIR 5					// 最大等待椅子数目
#define NUM_CUST  10				// 顾客数量
sem_t customers;         			// 表示有顾客的条件变量
sem_t barber;    	     			// 表示理发师醒了的条件变量
sem_t mutex;              			// 空闲椅子数是共享资源，需要互斥量
int freechairs;      				// 空椅子的数量

void * Barber() {
    while (ture) {	     			// 理发师持续不断工作或者睡眠
        sem_wait(&customers);		// 试图为一个顾客理发，如果没有顾客就睡着
        sem_wait(&mutex);			// 需要修改空椅子的数量(全局变量)，需要上锁
        freechair++;			    // 为一个顾客理发，顾客起身，空一张椅子出来
        sem_post(&barber);			// 此时理发师可以工作，通知顾客过来理发
        sem_post(&mutex);			// 修改完空椅子数目，释放锁
        /* 理发师在理发... */
    }
}

void * Customers() { 	 			// 一个线程仅仅表示一名顾客
    sem_wait(&mutex);    		 	// 想要坐到一张椅子上等待
    if (freechairs > 0) {			// 如果还有空椅子的话
        freechairs--;				// 顾客坐到一张椅子上等待
        sem_post(&customers);		// 唤醒理发师，有顾客来了
        sem_post(&mutex);			// 顾客已经坐到椅子上等待，释放互斥量
        sem_wait(&barber);			// 如果理发师还在忙，就等他
        /* 抢到理发师，此时顾客开始理发 */
    } 
    else {							// 没有空着的椅子 
        sem_post(&mutex);			// 不要忘记试图坐下上的锁(第20行)
        /* 没有椅子坐，直接走了 */
    }
}

int main() {
	/* 初始化 */
    sem_init(&customers, 0, 0);
    sem_init(&barbers, 0, 0);
    sem_init(&mutex, 0, 1);
    freechairs = NUM_CHAIR;
    
    /* 启动理发师和顾客 */
    pthread_t bar, cust[NUM_CUST];
    Pthread_create(&bar, NULL, Barber, NULL);	  	
    for (int i = 0; i < NUM_CUST; i++) {
        Pthread_create(&cust[i], NULL, Customers, NULL);
        sleep(randint(NULL));	  // 每隔一个随机时间来一个顾客
    }
    return 0;
}

补充之吸烟者问题

这里只用到了信号量，因为座子上的资源只够一个人吸烟，不会有共享

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

文件x1

  • 存储管理
    • 磁盘结构是什么样的？旋转寻道传输以及这方面的知识以及有关的时间是怎么算的？
    • RAID（0/1/4/5）各自有什么特点和优缺点，稳态吞吐量怎么算的
  • 文件系统
    • 数据进行读写，要经历什么样的步骤
    • 元数据的成员有哪些：修改时间、…、直接指针、间接指针
      • 放在一个应用场景中让你进行设计（大概率是设计分配直接指针和间接指针[二级、三级]）
      • 对应消耗多少空间，对应的数据块又有多大？

磁盘结构

image-20220614164632169

image-20220615015619442

各种时间怎么算

有两个真题,可以理解一下

  • 真题1

image-20220615171059400

image-20220615171145581

  • 真题2:

image-20220615171003028

image-20220615170926641

RAID各级的优缺点以及特点

  • 【RAID 0——RAID中速度最快】

    原理：采用数据条带技术（Striping），将数据分成“块”保存在不同磁盘上，读写时以并行的方式对各磁盘同时进行操作。

    优点：组建低成本，且具有传输速度快、存储空间利用率高等优点；

    缺点：不提供数据冗余保护，任何一块硬盘发生损坏，则所有的数据将不可恢复；

  • 【RAID 1——RAID中安全性最高】

    原理：俗称“磁盘镜像”，将数据完全一致地分别写到工作磁盘和镜像磁盘，一旦工作磁盘发生故障，系统自动从镜像磁盘读取数据，不会影响用户工作。

    优点：磁盘数据呈现完全镜像，具有安全性好、技术简单、管理方便等优点；

    缺点：实现成本高，磁盘空间利用率仅 50%；

  • 【RAID 4——条带分布+专用盘校验】

    原理：其中一块硬盘上存储校验数据，当某块硬盘出现故障时，其它硬盘可以通过校验数据将有故障的硬盘的数据重新恢复出来。

    优点：1、磁盘利用率较高(N-1)；2、并行I/O传输，顺序读性能较高

    缺点：1、专用校验盘成为性能瓶颈；2、每次读写牵动整个组，每次只能完成一次I/O 传输

  • 【RAID 5——RAID中综合性能最佳】

    原理：采用校验码冗余数据，校验块旋转地分布在多个磁盘上，当某个磁盘出现故障，可以使用其他磁盘上校验信息来恢复数据。

    优点：兼顾存储性能、数据安全和存储成本等；

    缺点：1、写入性能相对低；2、重建数据时，性能会受到较大的影响；

文件系统相关

  • 真题:

文件系统的实现需要考虑元数据（metadata）的处理，请回答跟元数据相关的下列问题：

（1）文件系统中的inode的作用是什么？inode中一般包含哪些信息？（4分）

（2）为了描述文件的大小，需要在元数据中给定指向数据的指针，指针一般分为直接指针（direct pointer）和间接指针（indirect pointer），假设数据块的大小为4KB，每个指针占用4字节的空间，那么10个直接指针和1个一级间接指针可以寻址的文件大小是多少？1个二级间接指针可以寻址的文件大小是多少？请给出分析和计算过程。（8分）

image-20220615145705046

  • 直接指针间接指针的好坏(来不及了…略)

    • 主要就是直接指针数目多,索引快,但是指向的数据块小
    • 间接指针需要额外的索引时间,但是数目少,指向的块的总大小很大

    image-20220615175410707

日志

日志记一下这五点吧,估计最多考这样

image-20220615175448501