Jack's Blog Site操作系统概记
Contents
操作系统概述
什么是操作系统
- 计算机硬件和应用之间的一层软件
- 操作系统的五大管理功能：
- 进程管理（CPU管理）
- 存储管理（内存管理）
- 设备管理（磁盘管理）
- 文件管理
- 作业管理（终端管理）
- 斯坦福学生的怎么学操作系统：
- 扩展线程：实现线程调度
- 实现系统调度：将整个接口剥掉，添加
- 实现虚存管理：扩展实现内存管理
- 扩展文件系统：扩展实现一个文件管理
- 绝知此事要躬行
开始揭开钢琴的盖子
- 从通用图灵机到冯诺依曼的存储程序思想
- 将程序放进内存，用PC指针指向它，然后取值，执行，取值，执行……
- 计算机由五大部件组成：输入设备，输出设备，存储器，运算器，控制器
- 打开电源，计算机执行的第一句指令是什么？
- 开机时，CS=0xFFFF，IP=0x0000，寻址BIOS（0xFFFF0）（CS：段寄存器，IP：段内偏移）
- BIOS程序检查内存，赋存，外设…
- BIOS程序将磁盘0扇面0磁道0扇区读入地址：0x7c00
- BIOS程序设置CS=0x07c0，IP=0x0000
- 开始分段读入整个操作系统：
- 开始执行引导扇区512字节的程序（硬盘的第一个扇区存放着开机后执行的第一段我们可以控制的程序）、
- 通过boot扇区读setup扇区：通过int 0x13中断读磁盘：从第2个扇区开始，读4个扇区
- 在boot扇区中通过int 0x10中断打印logo并读system模块
- 通过跳转指令跳转到setup扇区，交出控制权到setup扇区
- BIOS的主要功能是系统自检与初始化工作。它会对设备进行检测与初始化,设置运行环境,加载boot设备的第一个扇区到内存执行。Boot扇区的作用是准备系统环境,加载操作系统启动代码
- 操作系统启动过程中,CPU控制权的交接顺序一般是:
- 上电后,CPU首先执行BIOS程序。
- BIOS initializes CPU和硬件,然后读取MBR引导扇区到内存。
- BIOS将控制权转交给MBR中的引导加载程序(Bootloader)。
- Bootloader读取setup分区并进行系统初始化配置。
- 之后Bootloader加载内核程序,并转交控制权给内核。
- 内核完成自身初始化后,开始执行操作系统代码。
- 最后操作系统启动完成,转入正常运行状态。
- 所以严格说来,CPU控制权的交接顺序是:BIOS -> Bootloader -> 内核 -> 操作系统。而不是交给setup分区,setup分区只是被动被Bootloader读取和解析,以便进行必要的系统初始化配置,它不会获得CPU控制权。
操作系统启动
- setup模块：
- setup将完成OS启动前的设置
- 读硬件参数存储到内存数据结构中
- 将system移动到0地址
- 初始化GDT表（GDT全局描述符表用于存储段描述符：基地址，限长，权限；IDT中断描述符表用于存储中断向量和中断处理程序入口点之间的映射；idt和gdt可以放在内存中任意位置，相关寄存器指向起始地址）
- 启动保护模式，跳转到0地址处
- 保护模式：
- 操作系统启动过程中，CPU初始化后工作在实模式下，此时只有1MB的地址空间，不足以实现内存保护和虚拟内存等功能。
- 通过mov cr0，1进入保护模式：CPU、寄存器、地址线从16位切换到32位模式，段寄存器仍为16位，寻址方式改变，走另外一条电路，不再是CS*16+IP；CS里放的是段选择子，用于查gdt表项，取基址，再加偏移，查表是硬件实现的
- System模块：
- 操作系统源码通过Makefile编译为image
- system中的第一个模块是head.s，完成初始化idt、gdt的工作，通过ret main从进入main函数
- main.c完成初始化工作，如trap_init、mem_init，推出后进入死循环
- mem_init初始化了mem_map页表
操作系统接口
- 接口就是用户和计算机的交互：命令行，图形按钮
- 命令行：shell程序在死循环中执行命令，命令就是一段程序
- 图形按钮：硬件输入存到系统消息队列中，通过消息循环GetMessage获取消息并处理
- 用户使用计算机的本质是通过程序，即普通c代码或者重要函数进入操作系统内核；操作系统提供的这类重要函数，就是操作系统接口，也叫系统调用
系统调用的实现
- 系统调用的作用：提供统一接口供上层使用；作为用户态通往内核态的大门。
- 内核中存储重要数据，不让用户态访问
- 用户态不能通过jmp到内核中，也不能通过mov指令访问内核数据
- 隔离用户态和内核态的具体实现：
- Intel的CPU提供了特权环机制实现特权级检查（硬件检查）
- CPL（当前特权级）和DPL（描述符特权级）：在访问/跳转到一个目标内存区域（段）之时，只有CPL<=DPL时，指令才能被执行
- CPL位于CS段寄存器的最后两位，即当前指令所在段的特权级
- DPL位是GDT表中的段描述符，即目标内存段的特权级
- 系统调用进入内核态细节：中断是进入内核的唯一手段
- 系统调用的核心：就是一段包含中断的代码
- 系统调用的实现：应用程序调用printf->库函数printf->库函数write->系统调用write；系统调用write中包含软中断int 0x80，通过EAX寄存器的值选择具体的系统调用服务进行调用
- 细节：
- IDT表初始化：sched_init——>set_system_gate设置中断处理，向IDT表中写入system_call偏移地址，段选择符和DPL=3；由于DPL=3，所以当前指令能够执行，成功调用内核态函数system_call，并且CS段选择符被置为内核区域
- int0x80中断的处理：在跳转中断处理程序时，DPL被强行置为3，成功跳转到内核态；跳转后CPL被置为0，可以访问任何内存区域；执行中断处理程序system_call
- system_call：call _sys_call_table(, %eax, 4)，全局函数指针数组；通过eax传入系统调用号，找到sys_write；调用sys_write内核态函数
操作系统历史
- 操作系统的接口可以分为5个层次：
- 硬件层：包括CPU、内存、存储设备、外部设备等。操作系统需要管理与调度硬件资源,为上层提供抽象接口
- 内核层：包括进程管理、内存管理、文件系统、设备管理等模块。内核层是操作系统的核心,负责系统资源的管理与调度
- 系统调用层：提供程序界面(API)让进程调用内核服务。系统调用层包括用于进程、文件、内存操作的函数接口
- 库层：封装底层的细节,提供更易用的函数接口给程序使用。库层包括C库、数学库、网络库等
- 应用层：包括用户程序、编译器等,最终为用户提供服务
- 多进程图谱：CPU、内存，伴随着Unix的出现
- 文件操作图谱：文件、磁盘、IO，伴随着DOS/Windows的出现
进程管理和作业管理
插入一个对比：批处理操作系统&分时操作系统；作业&进程：
- 作业是批处理系统的执行单元，进程是分时交互性系统的执行单元
- 作业以非交互性和断续的方式执行，进程以交互性和并发的方式执行
- 作业执行时占用临时的物理空间，进程则有自己的虚拟地址空间
- 作业没有权限管理，进程可以为不同用户分配不同的权限
- 作业的调度主要依靠优先级，进程的调度更加复杂
- 任意时刻只有一个作业的程序在内存中执行，一个作业的执行通常需要分成多个段来完成,在两个执行段之间作业程序会被换出内存，高优先级作业的程序会抢占低优先级作业的内存空间执行，作业结束后,其程序及数据会从内存中删除,内存空间会被回收供下一个作业使用
CPU管理的直接想法
- CPU的核心，也是计算机的核心：取指执行
- 单程序系统的问题：遇到IO执行卡住，CPU利用率太低。解决方法就是内存中加载多程序，并进行不停切换，充分利用CPU资源。这也就需要PC等寄存器结构来保存程序运行中的信息，引入进程概念：运行中的程序，使用PCB来存放运行信息
- CPU管理的核心：多进程并发执行
多进程图像
- System模块中main函数，创建初始化进程，启动shell/图形化，在其中启动其他进程
- 操作系统使用PCB来组织多进程，将相应的PCB放到队列中：运行态，就绪态，阻塞态，终止态
- 多进程交替执行：将pCur指向的当前PCB放入阻塞队列，调用schedule函数通过getNext采用调度算法选择下一个PCB，并用pNew指向
- 多进程内存隔离：进程之间使用映射表实现进程间的内存隔离，解决了进程相互访问可能带来的问题
- 多进程的合作：生产者进程和消费者进程通过进程共享技术对某个数据进行操作，可能造成处理异常，需要通过给进程上锁实现进程同步
用户级线程
- 进程=内存资源（堆，代码区，全局区）+指令执行序列（PC指针、栈），所以进程的切换也分为两部分：指令和内存切换
- 线程共享内存资源，切换线程只需切换指令执行序列，保留并发的同时降低了切换代价
- Chrome多标签采用多进程，Firefox多标签采用多线程
- 用户级线程的创建和切换：
- TCB结构：
- threadID：线程的唯一标识
- status：线程的运行状态
- register：线程关于CPU中寄存器的情况
- PC程序计数器：线程执行的下一条指令的地址
- 优先级：线程在操作系统调度的时候的优先级
- 线程的专属存储区：线程单独的存储区域
- 用户栈：线程执行的用户方法栈，用来保存线程当前执行的用户方法的信息
- 内核栈：线程执行的内核方法栈，用来保存线程当前执行的内核方法信息
- 创建Create：通过malloc动态分配内存创建TCB和栈，将函数地址压栈，TCB保存栈顶指针
- 切换Yield：每个线程都需要自己的栈，栈切换需要TCB保存栈顶指针，不需要主动切换PC，因为pc已经在栈里了（不用jmp，直接返回）
- 操作系统完全感知不到用户级线程，用户级线程阻塞时CPU会切换到另一进程，而不是另一用户级线程；内核级线程由操作系统托管，并发性能更好
- TCB结构：
内核级线程
- 多处理器和多核的区别：多处理器是每个CPU都有一套Cache和MMU，多核是多个CPU公用一套Cache和MMU。只有内核级线程才能发挥多核特点。
- 内核级线程的创建：ThreadCreate系统调用，内核负责管理TCB、切换线程
- 每个内核级线程都是一套栈：用户栈&内核栈；切换的时候用户栈和内核栈都切换
- 用户栈&内核栈的关联：
- 对比用户级线程的切换使用TCB进行切换，核心级线程也用TCB切换，不过这个TCB在内核中，而且根据TCB的切换来切换一套栈，内核栈和用户栈都得切换
- 内核级线程切换的五段论：
- 线程Aint中断引发中断处理进入内核栈
- read函数的中断处理函数使线程进入阻塞状态，引入CPU调度，调用schedule
- schedule中根据调度策略找到另一个线程B的内核栈的指针,准备切换上下文，根据找到的TCB，调用switch_to
- 保存线程A的上下文到其TCB（寄存器状态、内核栈指针和用户栈指针），恢复线程B上下文，通过TCB进行线程B的内核栈切换
- 线程B执行,直到再次中断或被抢占,返回用户模式使用其用户栈，通过iret返回线程B的用户栈
- 内核级线程的创建：创建TCB——>创建用户栈和内核栈并关联——>TCB指向内核栈顶——>TCB进入队列
内核级线程实现
以fork为例，通过中断进入内核，复制了一份子进程后退出内核
- 切换
- schedule
- linux0.1使用TSS而不是TCB内核栈切换
- linux0.1通过长跳转指令进行切换，因为不能使用指令流水所以很慢（ljmp：把当前CPU的寄存器现场放到TSS中，根据TSS(n)找到新TSS，覆盖到CPU的寄存器上）
- EIP也通过TSS覆盖，没有用到栈传递
- 创建
- _sys_fork中调用了_copy_process，将当前所有寄存器作为参数传入
- 申请一页内存作为PCB和TSS
- 在PCB上方创建内核栈并用tss->esp0指向栈顶
- 和父进程共用一个用户栈，并用tss->esp指向栈顶
- tss的eip和cs通过传入参数赋值，eax置为0（作为子进程的返回值）
- 执行目标代码
- 子进程调用exec(cmd)函数
- 调用sys_execve系统调用，进入内核态
- 调用do_execve，将内核栈的ret_eip置为cmd程序的入口地址（从可执行文件的head处读取，SS：SP处被置为新的用户栈顶
- iret返回后，执行目标程序代码
操作系统之“树”
操作系统的核心就是：CPU管理和内存管理
- 实现在屏幕交替打出A和B
- 父进程进入内核，将两个子进程的PCB创建好，并修改tss-eip为打印A和打印B
- 父进程执行到wait时阻塞，进入内核调用schedule，调度策略选择next，通过执行switch_to(next)将目标子进程的tss覆盖到当前CPU寄存器，切换到子进程
- 两个子进程之间利用时钟中断进入内核，分配时间片counter，为0的时候调用schedule切换tss进而切换进程
CPU调度策略
- 前台任务（I/O约束性任务）关注响应时间，后台任务（CPU约束性任务）关注周转时间
- 任务响应时间和任务周转时间存在一定的矛盾关系：提高响应时间可能会导致切换次数多，减少任务可用处理器时间,从而降低系统吞吐量
- 最简单的CPU调度策略：FCFS，会导致任务集的平均周转时间很长。
- SJF算法（短作业优先）：平均周转时间最短
- RR算法（时间片轮询）：按照时间片轮转调度，减少响应时间
- 优先级算法：综合考虑，前台任务队列用RR，后台任务队列用SJF，之间用优先级调度保证前台任务的响应时间不会被后台任务拖慢
- 优先级调度可能造成进程饥饿，还需综合考虑
一个实际的schedule函数
- counter有两个含义，一是优先级，二是时间片。简单理解就是，时间片多的，优先级高。然后每次调度的时候，找到counter最大的就绪任务，也就是优先级最高的就绪任务去执行
- 而那些正在阻塞的进程（IO约束性任务）会额外分配一些时间，具体大小是它还剩下的counter的值的一半，IO时间越长，counter越大，照顾了前台进程
-
- counter有两个含义，一是优先级，二是时间片。简单理解就是，时间片多的，优先级高。然后每次调度的时候，找到counter最大的就绪任务，也就是优先级最高的就绪任务去执行
- 而那些正在阻塞的进程（IO约束性任务）会额外分配一些时间，具体大小是它还剩下的counter的值的一半，IO时间越长，counter越大，照顾了前台进程
- 后台进程是近似按照SJF调度，因为采用时间片切割轮转，那么肯定短时间的任务肯定就结束的快。
进程同步与信号量
- 为了保证进程间合理有序地推进，需要根据信号让进程走走停停
- 信号量用来判断可供使用的资源数量
- 信号量的定义：
为了操作PCB，P操作和V操作被做成了系统调用
1 2 3 4 5 6V(semaphore s){ s.value++; if(s.value <= 0){ wakeup } } - 使用P/V操作解决生产者-消费者问题：
- empty表示空闲单元数量，full表示生产内容的数量，mutex表示只能让一个进程修改缓冲区
- 空闲单元为0时生产者停下来（p(empty)），消费者对应增加（V(empty)）；生产内容为0时消费者停下 来（p(full)），生产者对应增加（V(full)）
- 本质：一个信号量的含义是表示能让对应的进程能够使用多少次
信号量临界区保护
- 我们把一个时间段内允许一个进程的使用的资源，称为临界资源
- 并发错误由多个进程同时操作共享数据引起,需要加锁机制保护共享数据
- 临界区必须成对出现,一方进入则其他方被互斥在外。互斥进入是实现互斥访问的基本原则
- 进入与退出临界区的代码实现是关键,需要遵循的原则：
- 互斥进入：只允许一个线程进入临界区,其他线程被互斥拒绝进入。这个原则保证了在同一时刻只有一个线程可以访问共享资源,避免出现竞争状态
- 有限等待：当多个线程同时请求进入临界区时,线程只会在有限时间内等待。如果超过最大等待时间仍未获得临界区访问权,线程将放弃等待并执行其他操作。这个原则避免了某些线程由于优先级太低或其他原因导致无限期等待,从而 “饿死”
- 有空让进：当占用临界区的线程完成工作准备离开临界区时,如果存在其他线程等待进入,应尽快让该线程进入。这个原则实现了对临界区的公平访问,避免某些线程长时间无法进入临界区
- 进程互斥的软件实现方法：
- 单标志法：
- 满足互斥进入原则，违背有空让进原则，因为只有一个标志，所以一定是按照P0->P1->P0-P1…顺序进行轮流访问
- 双标志先检查：
- 若按照①⑤②⑥③⑦…的顺序执行，P0和P1将会同时访问临界区；违背互斥进入原则，原因是进入临界区的检查和上锁两个处理不是一气呵成的，检查和上锁之间可能发生进程切换
- 双标志后检查；
- 前一个算法的问题是先“检查”后“上锁”，无法一气呵成。因此，想到先“上锁”后“检查”的方法来避免上述问题
- 但还是有缺陷，若按照①⑤②⑥….的顺序执行，P0和P1将都无法进入临界区，解决了互斥进入，违背了有限等待和有空让进
- Peterson算法：
- 如果双方都想进入临界区，可以让进程主动谦让。自己的进程意愿设为true，还要表示谦让把trun设为对方的值。这样就解决了上一个方法的问题。
- Peterson算法用软件方法解决了进程互斥问题，遵循了互斥进入、有空让进、有限等待三个原则
- 但是依然未遵循让权等待的原则，会发生忙等，因为如果他自己进不去临界区，就会一直卡在while循环，而他依旧是在处理机上的，在占着资源
- 单标志法：
- 进程互斥的硬件实现方法：
- 中断屏蔽方法：
- 利用“开/关中断指令”实现，优点是简单高效，缺点是只能用于单处理器的机器，只适用于操作系统内核进程
- TestAndSet（TS指令/TSL指令）和 Swap指令（XCHG指令）
- 用硬件实现执行的过程不允许被中断，由硬件强制一气呵成
- 中断屏蔽方法：
- Peterson算法通过标记位与轮转实现互斥,简单高效
- 在单核CPU上,可以使用cli/sti指令通过开关中断来上锁,禁止其他进程被调度运行,简单实现互斥
- 可以使用CPU的原子指令(cmpxchg等)上锁,效率高且不会被中断,比使用信号量上锁更为简单高效
信号量的代码实现
死锁处理
- 死锁的原因：进程占有一些别人需要的资源不释放，再去申请别人的资源，各自占有的资源和申请的资源形成了环路等待
- 产生死锁的4个必要条件：
- 互斥条件:资源被一个进程使用时其他进程不能使用
- 占有且等待条件:进程已经占用了至少一个资源,但又申请新的资源时必须等待
- 不可剥夺条件:进程已获得的资源在未使用完之前不能强行剥夺
- 环路等待条件:在一个进程正在等待的资源中,必须存在一个由其他进程占用且正在等待的资源,形成一个环形链
- 死锁的处理方法：
- 死锁预防：破坏产生死锁的四个必要条件中的至少一个条件。例如规定所有进程以固定的顺序申请资源,避免环路等待资源形成
- 死锁避免：在运行时根据资源分配情况判断是否会产生死锁,如果会产生则不分配资源。主要方法是检测安全状态,只在安全状态下分配资源
- 死锁检测+恢复：允许死锁发生,然后进行检测并进行恢复。主要方法是使用资源分配图检测是否发生死锁。一旦检测到死锁,需要将进程回滚到安全状态并重新申请资源
- 死锁忽略：简单地忽略死锁问题,让死锁在系统中自然解除。这种方法极不可取,因为死锁进程会永远阻塞,占用资源却无法运行
存储管理
内存使用与分段
- 编译时重定位，载入时重定位，运行时重定位
- 编译时重定位在编译结束前完成，只能放到固定位置
- 载入时重定位在程序载入内存前完成，不能满足换入换出的需求
- 运行时重定位随程序执行持续进行，每执行一条指令都要从逻辑地址计算出物理地址（地址翻译），基址放到PCB中，进程运行时赋值给基地址寄存器
- 分段：
- 将程序按照功能划分为不同段，分段放入内存
- 段表：用来保存每个段的地址，包括段号，段基址，长度和段属性
- 操作系统的段表叫GDT，每个进程的段表叫LDT
- 载入时将LDT赋值给PCB，进程运行时再由PCB进行重定位修改LDT的值，重新计算各段指令的物理地址
内存分区与分页
- 内存分区：
- 内存分区是段的存放载体，程序的各个段载入到相应的内粗分区
- 可变分区算法：最先适配，最差适配，最佳适配
- 分页：
- 采用内存分区+分段的方式很容易造成内存碎片的问题，为了解决这个问题，引入了分页
- 分区用于虚拟内存的划分，分页用于物理内存的划分
- 将每个段分成多个4K的页
- 通过逻辑地址根据段表计算出虚拟地址，再通过虚拟地址根据页表计算出物理地址
- 页表：保存页号和页框的对应关系，CR3寄存器用于存储页目录表的物理基地址（页框是对内存进行分框，页是对进程进行分页）
多级页表与快表
- 问题所在：
- 页存在的目的就是为了充分利用空间，所以页很小，导致页数量激增，页表异常大
- 但是每个进程实际上只用到了很小部分的页，大部分的页是用不到的；解决方法如果是只存放用到的页表项，页表查找很费时，所以不行，页表项必须连续存放，那怎么办呢？答案就是多级页表
- 多级页表：
- 通过“页目录表”和“页表”形成多杰页表查找，通过页目录表为用到的页表提供索引，没用到的页表无需放入内存；这样既保证了页表项连续存放，又能减少页表对内存空间的占用
- 在32位地址空间下，多级页表一般采用2级结构：10+10+12
- 第1级是页目录表：定义1k个4字节的目录项，对应4G虚拟地址空间
- 第2级是页表：定义1k个4字节的页表项，对应4M虚拟地址空间
- 页框大小固定4KB，存储实际数据或指令
- 图示：
- 快表：
- 多级页表能减少内存的占用，但增加了访存次数，故引入了TLB
- TLB是一组快速存储寄存器，保存经常用到的页表项，通过硬件实现查找
- TLB命中直接取TLB中的页表项对应的物理内存，未命中通过多级页表补充查找
- TLB页表项很少的理论依据：程序的空间局部性原理
- TLB和Cache的区别：
- 功能上：Cache是数据缓冲区，加速CPU的数据读取；TLB是地址翻译缓冲区，加速地址翻译映射
- 粒度上：Cache粒度大，以64字节为Cache行进行数据映射；TLB粒度小，以4字节为页地址进行地址映射
- 类型上：Cache是数据映射，TLB是地址映射
- 硬件实现上：Cache通常再CPU芯片上实现；TLB通常在MMU中实现
段页结合的实际内存管理
- 操作系统的虚拟内存：用户角度的段式和物理内存角度的页式，使用内存需要经过两次地址翻译
- 以fork为例介绍一个实际的段页式内存管理：
- 分配虚存，建段表
- 分配内存，建页表
- 父子进程共用同一个物理页（并设置为Read Only），子进程按照虚拟地址换算来建立新的顶级页表项，并分配内存建立新的二级页表，并拷贝父进程的二级页表
- 修改新进程的CR3寄存器
- 为共享的页框增加引用计数，表示该页框同时被多个进程共享和使用
- 处理写时复制。如果原进程对共享的页框进行写操作,就会触发写时复制,产生该页框的独立副本给新进程使用,并更新对应的页表项和引用计数
- 父子进程共享物理页主要是指用户空间,利用写时复制机制来节省内存并实现共享执行环境。而内核空间仍然是相互隔离的,以维护内核空间的安全性和正确性
内存换入——请求调页
- 分段分页内存管理的核心是虚拟内存，虚拟内存的核心是内存换入换出
- 虚拟地址=线性地址
- 用内存的换入换出实现比物理内存更大的内存（虚拟地址空间大于物理地址空间的实现机理就是多个虚拟内存页绑定同一个物理内存页框）
- 内存换入的核心：缺页中断从磁盘读入缺页到内存空间
- 处理缺页中断（do_no_page）
- 获取物理空闲页：
page=get_free_page() - 从磁盘设备读入到物理页：
bread_page(page, current->executable->i_dev, ) - 虚拟地址和物理页关联：
put_page(page, address)
- 获取物理空闲页：
内存换出
- 内存有限，不可能一直get_free_page，有进就有出，内存不够了需要按照页面置换算法选择一页淘汰，换出到磁盘
- 页面置换算法：目标是降低缺页次数
- FIFO：先进来的先置换
- MIN：选择未来最远使用的页置换，理想最优方案，但由于不能未卜先知，所以只能依据程序的时间局部性原理设计出LRU算法（假设最近访问过的页面在不远的将来很可能再次访问,所以应该保留在内存中）
- LRU：最近最少使用，Least Recently Used
- 两种精确实现方案：每页维护一个时间戳、维护一个页码栈，时间代价都很高，所以采用LRU的高效率近似算法：Clock算法
- Clock：
- 将时间计数变为0或1，表示是或否，记录最近一段时间是否使用；这样每次访问页就可以顺便写入并且只用修改一位，时间代价很低、
- 缺页的时候转动指针，为1置为0继续转动，为0换出
- 当缺页很少时，退化为FIFO算法：因为当几乎不发生缺页中断的时候，指针不会转动，所以指针会很长时间都不会做转动，这和LRU中的最近矛盾，所以需要对算法做出改进
- 再增加一个定时清除R位的扫描指针
设备管理
I/O与显示器
- 外设工作的3个关键部分
- CPU访问外设：CPU可以通过执行in/out指令直接读取或写入外设的控制和数据寄存器，从而控制外设的工作。这是外设和CPU之间最基本的交互方式
- 操作系统提供文件接口：操作系统会为外设建立文件抽象，屏蔽底层寄存器的操作细节。应用程序通过标准文件操作接口（open、read、write、close）来控制外设，这简化了应用程序的实现并提高了其可移植性
- 中断机制：外设通过中断机制来响应操作系统和应用程序发出的请求或者通知其状态变化。当外设操作完成或状态变更时,会发出中断信号通知CPU。CPU接收到中断后会执行相应的中断处理程序(通常在操作系统内核中),然后唤醒等待该外设操作完成的进程。
- 操作外设的的程序：
1 2 3 4 5int fd = open(“/dev/xxx”); for (int i = 0; i < 10; i++) { write(fd,i,sizeof(int)); } close(fd);- 无论什么设备，操作系统都为外设提供了统一的文件视图接口：open、read、write、close
- 不同的设备对应不同的设备文件，根据设备文件找到控制器的地址，内容格式等
- 显示器的输出：
- 找到设备
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24printf(“Host Name: %s”, name); ->write(1, buf, ...); ->sys_write(fd, buf, ...); //通过fd找到文件的索引 sys_write{ struct file *file; file = current->filp[fd]; //current进程 inode = file->f_inode; //显示器信息保存在inode中 } //fd=1的filp从父进程shell fork拷贝而来 void init(void) { open(“dev/tty0”,O_RDWR,0);dup(0);dup(0); //dup用来复制一个文件描述符，并指向同一个设备 execve("/bin/sh",argv,envp) } //open系统调用 int sys_open(const char* filename, int flag) { i=open_namei(filename,flag,&inode); //inode保存设备信息 cuurent->filp[fd]=f; // 第一个空闲的fd f->f_mode=inode->i_mode; f->f_inode=inode; f->f_count=1; return fd; } - 向屏幕输出
- inode->i_zone[0]获取设备号，crw_table是字符设备接口，从中找到tty
- tty_write是输出的核心函数，往write_q缓冲区队列中写
- tty->write，在tty_struct中，从缓冲区队列中往屏幕上写，内部用到mov ax, pos，往显存中写字符
- 统一编址用pos，独立编制用out
- 写设备驱动，就是包装out，编写驱动函数并注册到tty_struct中
- 找到设备
键盘
- 从键盘中断开始，从0x60端口读扫描码，调用key_table
- key_table：函数表，包含do_self等
- do_self专门用于处理可显示字符，从key_map中获取arscii码
- 将arscii码放入read_q缓冲队列中，供程序使用
生磁盘的使用
- 磁盘的基本概念：
- 磁道(柱面)，扇区，(磁头)盘面：根据这三个指标能定位一个512字节的扇区
- IO过程
- 控制器
- 寻道：磁头移动到目的磁道，确定了磁道和盘面
- 旋转：旋转磁盘到目的扇区，确定了扇区
- 传输：磁生电（读缓冲区），电生磁（写缓冲区）
- CPU通过out往控制器中写柱面、磁头、扇区的位置
- 第一层抽象：根据盘块号读写磁盘
- 磁盘驱动负责从盘块号计算得到扇区号，根据扇区号计算得到CHS(C:柱面数;H:磁头号;S:扇区号)
- 第二层抽象：多个进程通过队列使用磁盘
- 磁盘调度的目的：减少寻道时间。磁盘的访问时延主要由寻道时间和数据传输时间组成。其中寻道时间是磁头定位到目标磁道所需要的时间,数据传输时间取决于目标扇区的数量。相比数据传输,寻道时间的影响更大。
- 磁盘调度算法：
- FCFS：按请求到达的先后顺序进行服务,没有考虑寻道时间的影响
- SSTF（最短寻道）：每次选择与当前磁头位置最近的请求进行服务,可以在一定程度上减少磁头移动和提高吞吐量。但是可能产生工作驻留现象,某个区域的请求饥饿
- SCAN（SSTF+中途不回折）：与SSTF算法相同,但是在一条磁道完成请求后,磁头会立即移动到同方向下一条磁道,而不会回折选择其他相近的请求。这样可以避免工作驻留现象,保证所有请求会被服务
- C-SCAN（电梯算法）：将SCAN算法进一步扩展,当磁头移动到磁盘最末尾后,直接回到磁盘最开始的磁道。这样可以视为磁头以定轨道扫描整个磁盘,更加公平和可预测。但是磁头移动幅度较大,寻道时间也较长
- 生磁盘的使用整理
- in：进程发出读请求后睡眠，磁盘将数据准备到缓冲内存，通过终端唤醒内存
- out：通过out往CHL写
- 磁盘是一个共享资源,多个进程可以同时发出读请求,但同一时刻只能有一个进程访问磁盘进行写操作。读操作是并发的,需要队列进行排序和调度;写操作是互斥的,直接执行,不需要排队
文件管理
从生磁盘到文件
- 第三层抽象：根据文件到盘块号
- 用户眼里的文件是字符序列，磁盘中的文件是盘块集合
- 文件的关键：建立字符流到盘块集合的映射关系
- 磁盘的三种存储结构：
- 顺序结构：访问速度慢但空间利用率高,适合批量存储
- 链式结构：访问速度快但空间浪费较多,用于动态变化的数据
- 索引结构：既有较高访问速度又能较高空间利用率,实现复杂,用于经常访问的数据
- 通过FCB找到文件对应的inode，找到索引块（存放索引的盘块），找到目标字符序列对应的盘块
- 多级索引：可以表示很大的文件，很小的文件也能高效访问
文件使用磁盘的实现d
目录与文件系统
- 磁盘的最后一层抽象：将整个磁盘抽象成一棵目录树
- 一个磁盘块集合的抽象：文件
- 整个磁盘的抽象：文件系统
- 目录树
- 引入目录树来实现文件的层次结构
- 目录项：文件名，FCB地址的对应关系
- 关键是根据树状结构产生的路径名，找到对应文件的inode，一个文件对应一个inode
- FCB中保存着inode，是文件的索引。根据inode索引找到数据盘块，数据盘块中保存着目录项
- 目录项中包含FCB的编号和字符串，通过字符串匹配编号，通过编号找到FCB，通过FCB再找到数据盘快，循环递归，就构成了操作系统的文件目录层次结构
- 根目录的FCB编号固定为0
- 格式化
- 操作系统每个分区都能格式化为不同的文件系统
- 格式化后的硬盘结构如下：
- 超级块；各个部分位置信息，mount操作实际上就是读超级块，然后挂载到目标外存的根目录位置
- 引导块：如果该外存中存储了操作系统程序并且需要启动操作系统，则需要引导块
- 经过的四层抽象后的磁盘使用：
