四、存储管理

存储管理为了确保计算机有足够的内存处理数据；确保程序可以从可用内存中获取一部分内存使用；确保程序可以归还使用后的内存以供其他程序使用。

4.1 存储管理之内存分配与回收

内存分配的过程：单一连续分配（已经过时）、固定分区分配、动态分区分配（根据实际需要，动态的分配内存）。 动态分区分配算法：

1. 首次适应算法：分配内存时，从开始顺序查找适合内存区，若无合适内存区，则分配失败，每次从头部开始，使得头部地址空间不断被划分；
2. 最佳适应算法：要求空闲区链表按照容量大小排序，遍历以找到最佳适合的空闲区（会留下越来越多的内部碎片）。
3. 快速适应算法：要求有多个空闲区链表，每个空闲区链表存储一种容量的空闲区。

内存回收的过程：

1. 回收区在空闲区下方：不需要新建空闲链表节点；只需要把空闲区1的容量增大即可；
2. 回收区在空闲区上方：将回收区与空闲区合并；新的空闲区使用回收区的地址；
3. 回收区在空闲区中间方：将空闲区1、空闲区2和回收区合并；新的空闲区使用空闲区1的地址；
4. 仅仅剩余回收区：为回收区创建新的空闲节点；插入到相应的空闲区链表中去；

4.2 存储管理之段页式存储管理

页式存储管理：将进程逻辑空间等分成若干大小的页面，相应的把物理内存空间分成与页面大小的物理块，以页面为单位把进程空间装进物理内存中分散的物理块。

页面大小应该适中，过大难以分配，过小内存碎片过多；页面大小通常是512B~8K；

现代计算机系统中，可以支持非常大的逻辑地址空间(232~264)，具有32位逻辑地址空间的分页系统，规定页面大小为4KB，则在每个进程页表中的页表项可达1M(2个20)个，如果每个页表项占用1Byte，故每个进程仅仅页表就要占用1MB的内存空间。

段式存储管理：将进程逻辑空间分成若干段（不等分），段的长度由连续逻辑的长度决定。

页式和者段式存储管理相比：

1. 段式存储和页式存储都离散地管理了进程的逻辑空间；
2. 页是物理单位，段是逻辑单位；
3. 分页是为了合理利用空间，分段是满足用户要求页大小由硬件固定，段长度可动态变化；
4. 页表信息是一维的，段表信息是二维的；

段页式存储管理：现将逻辑空间按照段式管理分成若干段，再将内存空间按照页式管理分成若干页，分页可以有效提高内存利用率，分段可以更好的满足用户需求。

4.3 存储管理之虚拟内存

虚拟内存概述：是操作系统内存管理的关键技术，使得多道程序运行和大程序运行成为现实，把程序使用内存划分，将部分暂时不使用的内存放置在辅存，实际是对物理内存的扩充。

局部性原理：指CPU访问存储器时，无论是存取指令还是存取数据，所访问的存储单元都趋于聚集在一个较小的连续区域中。

虚拟内存的置换算法：先进先出（FIFO）、最不经常使用（LFU）、最近最少使用（LRU）

虚拟内存的特征：

• 多次性：无需再作业运行时一次性全部装入内存，而是允许被分成多次调入内存；
• 对换性：无需在作业运行时一直常驻内存，而是允许在作业运行过程中，将作业换入、换出；
• 虚拟性：从逻辑上扩充了内存的容量，使用户看到的内存用来，远大于实际的容量；

4.4 Linux的存储管理

Buddy内存管理算法：经典的内存管理算法，为解决内存外碎片的问题，算法基于计算机处理二进制的优势具有极高的效率。

Linux交换空间：交换空间（Swap）是磁盘的一个分区，Linux内存满时，会把一些内存交换至Swap空间，Swap空间是初始化系统时配置的。

Swap空间与虚拟内存的对比：

五、文件管理

5.1 操作系统的文件管理

文件的逻辑结构：

• 逻辑结构的文件类型：有结构文件（文本文件，文档，媒体文件）、无结构文件（二进制文件、链接库）。
• 顺序文件：按顺序放在存储介质中的文件，在逻辑文件当中存储效率最高，但不适合存储可变长文件。
• 索引文件：为解决可变长文件存储而发明，需要配合索引表存储。

辅存的存储空间分配：

• 辅存的分配方式：连续分配（读取文件容易，速度快）、链接分配（隐式链接和显式链接）、索引分配
• 辅存的存储空间管理：空闲表、空闲链表、位示图。

目录树：使得任何文件或目录都有唯一的路径。

Linux文件的基本操作：参考链接

Linux的文件系统：FAT、NTFS（对FAT进行改进）、EXT2/3/4（扩展文件系统，Linux的文件系统）

六、设备管理

I/O设备的基本概念：将数据输入输出计算机的外部设备；

广义的IO设备：

• 按照使用特性分类：存储设备（内存、磁盘、U盘）和交互IO设备（键盘、显示器、鼠标）；
• 按照信息交换分类：块设备（磁盘、SD卡）和字符设备（打印机、shell终端）；
• 按照设备共享属性分类：独占设备，共享设备，虚拟设备；
• 按照传输速率分类：低速设备，高速设备；

IO设备的缓冲区：减少CPU处理IO请求的频率，提高CPU与IO设备之间的并行性。

SPOOLing技术：虚拟设备技术，把同步调用低速设备改为异步调用，在输入、输出之间增加了排队转储环节(输入井、输出井)，SPoOLing负责输入（出）井与低速设备之间的调度，逻辑上，进程直接与高速设备交互，减少了进程的等待时间。

七、实现支持异步任务的线程池

线程池：线程池是存放多个线程的容器，CPU调度线程执行后不会销毁线程，将线程放回线程池重新利用。

使用线程池的原因：

1. 线程是稀缺资源 ，不应该频繁创建和销毁；
2. 架构解耦，业务创建和业务处理解耦，更加优雅；
3. 线程池是使用线程的最佳实践。

实现线程安全的队列Queue

• 队列：用于存放多个元素，是存放各种元素的“池”。
• 实现的基本功能：获取当前队列元素数量，往队列放入元素，往队列取出元素。
• 注意：队列可能有多个线程同时操作，因此需要保证线程安全，如下两种情况：

实现基本任务对象Task

实现的基本功能：任务参数，任务唯一标记（UUID），任务具体的执行逻辑

实现任务处理线程ProcessThread：任务处理线程需要不断地从任务队列里取任务执行，任务处理线程需要有一个标记，标记线程什么时候应该停止。

实现的基本功能：基本属性（任务队列、标记），线程执行的逻辑（run），线程停止（stop）。

实现任务处理线程池Pool：存放多个任务处理线程，负责多个线程的启停，管理向线程池的提交任务，下发给线程去执行。

实现的基本过程：基本属性，提交任务（put，batch_put），线程启停（start，join），线程池大小（size）。

实现异步任务处理AsyncTask：给任务添加一个标记，任务完成后，则标记为完成；任务完成时可直接获取任务运行结果；任务未完成时，获取任务结果，会阻塞获取线程。

主要实现的两个函数：设置运行结果（set_result），获取运行结果（get_result)