CS240FZ Note 4 | Operating Systems & Communications & Concurrency 4

Key Points：

• Memory Management
• Bit Map && Linked List
• File Systems
• Paged memory architecture

CS240 2022版 Note-4

• Lecture 18 – Introduction to Memory Management
• Lecture 19 and 20 – Memory Management II
• Lecture 21 and 22 and 23 – File Systems

---

Lecture 18 – Introduction to Memory Management

内存的基本知识 Memory Basic intro

内存是用于存放数据的硬件。程序执行前需要先放到内存中才能被CPU处理。

内存管理

操作系统负责：

1. 需要对内存空间进行分配与回收
2. 需要提供某种技术，从逻辑上对内存空间进行扩充
3. 需要提供地址转换功能，负责逻辑地址与物理地址的转换
4. 需要提供内存保护功能，保证各进程在各自存储空间内允许，互不干涉

内存的分配与回收：

1. 单一连续分配
2. 固定分区分配
3. 动态分区分配

内部碎片：分配给某进程的内存区域中，有些部分没有利用上。

外部碎片：内存中的某些空闲分区由于太小，难以利用上。

1. 单一连续分配

无外部碎片，实现简单

有内部碎片，存储器利用率低

2. 固定分区分配

无外部碎片，实现简单

有内部碎片，存储器利用率低

3. 动态分区分配

• 空闲分区表
• 空闲分区链(double-linked)

Bit Map && Linked List

1、Bit Map

The bitmap contains a single bit for each allocation unit which indicates the status of that unit, e.g. 1 for used, 0 for unused.

位图包含每个分配单元的单个位，表示该单元的状态，例如:1表示已使用，0表示未使用。

2、Linked List

Maintain an information record describing the size and location of each of the variable sized free blocks and to keep this variable number of records in a dynamic linked list structure.

维护一个信息记录，描述每个可变大小的空闲块的大小和位置，并在动态链表结构中保持这个可变数量的记录。

有外部碎片

无内部碎片（通过拼凑Compaction）

阶段Overall-1

---

Lecture 19 Memory Management II

动态分区分配算法

• First Fit
• Best Fit
• Worst Fit
• Next Fit

1. First Fit 区分法

空闲分区以地址递增的次序排列，每次分配时按顺序查找空闲分区链

2. Best Fit 切分法

空闲分区按容量递增次序链接，每次分配内存时按顺序查找空闲分区链

3. Worst Fit (Largest Fit) 截出排序法

按照容量递减次序链接，每次分配内存时按照顺序查找空闲分区链。

解决了产生外部碎片的问题，但会导致大进程无处安放的问题。

4. Next Fit

按照地址递增的顺序排列。每次分配内存时从上次查找结束的位置开始查找空闲分区，直到找到第一个可以满足的分区。

不需要重新排列链表，可以减少系统算法的开销(Overhead)

阶段Overall-2

---

Lecture 20-1 Memory Management III

连续分配：为用户分配的必须是一个连续的内存空间。

非连续分配：可以是一些分散的内存空间。

第19章我们介绍了连续分配分区的管理方式，接下来我们介绍非连续分配管理方式：

1. 基本分页
2. 基本分段
3. 段页式
4. 请求分页
5. …

1、基本分页存储管理

 

页号 = 逻辑地址/页面长度
页内偏移量 = 逻辑地址 % 页面长度

 

 

Overall-3

Lance说：本章的学习，一定要注意区分清楚各个名称的含义、意义！
1、页号
2、页内偏移量
3、页表：记录了各个逻辑页面到实际的物理页框之间的关系
......

---

Lecture 20-2 Memory Management III

2、基本分段式存储管理

 

1、段号
2、段内地址
3、段表：各个逻辑段到实际的物理内存位置的映射关系
4、段长

对比 分页 && 分段

1. 分页对用户不可见；分段对用户可见；
2. 分段比分页更容易实现信息的共享与保护；
3. 分段比分页更快，系统消耗更小。

---

Lecture 20-3 Memory Management IIII

请求分页，是一种特殊的基本分页

3、请求分页管理方式 Demand Paging

 

名词：
*1、请求页表
2、状态位
3、访问字段
4、修改位
5、外存地址
*6、缺页中断机构
*7、地址变换机构

---

页面置换算法（课件里的名称）

• OPT (Optimal Page Replacement) 最佳置换算法
• FIFO (First In First Out) 先进先出
• LRU (Least Recently Used) 最近最久未使用
• C-lock (Clock) 时钟页面置换算法
• LFU (Least Frequently Used) 最不常用算法

1. OPT 最佳置换

每次选择淘汰的页面将是以后永不使用，或者在最长时间内，不再被访问的页面。这样可以保证最低的缺页率。

Each culled page is which won't be used for the longest time.

2. FIFO 先进先出

每次淘汰的页面是最早进入内存的页面。

Each culled page is the first one to enter memory.

 

3. LUR (Least Recently Used) 最近最久未使用

每次淘汰的是最近最久未使用的页面。

Each culled page is the most recent unused page.

4. CLOCK（NRU） 时钟置换算法

Clock是比较折中的算法，兼顾了上述各个算法的优缺点。

5. LFU (Least Frequently Used) 最不常用算法

当一个缺页中断发生时，选择访问次数最少的那个页面，并淘汰。

When a page-missing interrupt occurs, select the page with the least number of visits and weed it out.

LRU和LFU的对比 :

LRU考察的是多久未访问, 时间越短越好；

LFU考察的是访问的次数和频度, 访问次数越多越好。

Overall-4

---

Lecture 21 – File Systems

文件：一组有意义的信息的集合

A file is a collection of related information, defined by its creator and stored on non volatile storage.

文件管理

一个文件有哪些属性：

1. 文件名
2. 标识符（一个系统内，各个文件标识符各不相同，用于区分）
3. 类型
4. 位置（存放路径）
5. 大小
6. 创建时间、上一次修改时间、创建者
7. 保护信息（对文件进行保护的访问控制信息）

 

 

 

操作系统向上提供的基本功能：

Ex. 用基本功能实现复杂功能：
copy() = 1 create() + 2 read() + 3 write()

 

阶段Overall-1

---

Lecture 22 and 23 – File Systems

文件的物理结构

• 1、连续分配
• 2、链接分配
• 隐式链接
• 显式链接
• 3、索引分配

操作系统为文件分配存储空间都是以块为单位的。

用户通过逻辑地址来操作自己的文件，操作系统要负责实现从逻辑地址到物理地址的映射。

1. 连续分配 Continuous distribution

物理块号 = 起始块号 + 逻辑块号

优点：

1. 可以直接算出逻辑块号对应的物理块号
2. 支持顺序访问 & 直接访问（即随机访问）
3. 连续分配在顺序读/写文件时，速度最快

缺点：

1. 不方便拓展
2. 存储空间利用率低，会产生难以利用的磁盘碎片（Disk Fragmentation）类似外部碎片，利用紧凑来解决，但overhead很高

2. 链接分配（离散分配）

• 1、隐式 Implicit
• 2、显式 explicit

隐式链接

显式链接

 

链式分配 Overall

 

需要注意的是，如果题目中没有指明是隐式还是显式，则默认为隐式。

3. 索引分配

 

文件分配方式 总结 Overall

---

额外Tutor 历年卷相关试题解析

Lance说：为了更好地和考试链接，这里提供两道历年考题答疑：

Tutor-1 2019-Autumn-Q7

Compare the bitmap approach to the linked list approach for keeping track of a free memory space. 比较位图方法和链表方法，对于记录空闲内存空间。

(1) 大小上：bitmap是固定大小的数据结构，而linked list是动态大小

(2) 分配空间上：bitmap是根据大小确定分配的效率，linked list是需要一个很长list的搜索

(3) 重新分配上：bitmap非常迅速，linked list需要对整个linked list进行操作

(4) 碎片上：bitmap平均1/2的内部碎片，linked list不存在内部碎片

 

Tutor-2 2019-Summer-Q9

Explain the advantages of using paged memory architectures. Are there any drawbacks to using this approach?

解释使用分页内存架构的优点。使用这种方法有什么缺点吗?

考点：Paged memory architectures

定位：Method 4 – Paged Architecture

Advantages：

1. No outer fragments, the last page may have inner fragments but not big;
2. The architectures does not have to be stored continuously;
3. It is convenient to change the size of the space occupied.

Disadvantages：

4. The program needs to be fully loaded into memory, which increased machine cost and system overhead.
5. Page mapping still slows down the access time to memory slightly.

优点：

1. 没有外部碎片，最后一页可能有内碎片但不大;
2. 程序不必连续存放;
3. 便于改变程序占用空间大小。

缺点：

4. 程序仍需要全部装入内存（基本页式存储管理）如：地址变换机构缺页中断的产生和选择淘汰页面等，增加了机器成本和系统开销。
5. 页面映射仍然会稍微减慢对内存的访问时间（Slow）

基本分页存储管理的思想:

参考：《操作系统：连续分配、分页和分段三种存储分配机制的优缺点》
http://t.csdn.cn/FbQo7

---

Lance写在最后

你好，我是Lance，因为在最后的18-23章里，CS240的课件实在是做得太差了，因此我大部分都采用国内（王道考研）的408课件来做笔记。

 

毫不客气的说，MIEC的CS240这门课，所有课件都做得非常糟糕，上下文之间缺乏逻辑对接，以至于每一页之间都显得毫无干系，老师讲起课来费劲，学生听起课来也折磨，这是我过去一个学期以来的真实体验，而这也是为何我选择把自己的笔记开源的原因，希望可以帮助大家进行更高效的复习。

 

最后，我想说的是：倡导知识付费，是因为知识创建、整理的过程复杂，需要付诸许多心血，而人的精力实在有限，知识付费让这一切关系变得健康；而倡导知识开源，恰恰也正是因为知识宝贵，所以需要让更多人受益，从而充分发挥人的劳动价值——这是在计划里的捐献

 

如果你觉得这个网站做得不错，对你有所帮助，希望我在未来产出更多高质量的复习包，来帮助更多的人。可以扫描下面二维码对本站的服务器进行donate，不在于多，只是小小心意，我也倍加珍重！

 

 

备注你可行的联系方式（例如e-mail），我会特别地向你邮件致谢。再次谢谢你的支持！

 

我们高处见！

by Lance Cai 2022-06-28