计算机基础·操作系统 文章目录操作系统的定义内核与操作系统的关系用户态切换为内核态系统调用通过trap自陷实现进程与线程进程定义执行中的程序进程包含的资源静态资源(地址空间文件资源)和动态资源(栈PC寄存器)进程控制块 PCB进程的PID,运行状态程序计数器PC寄存器文件资源等进程运行状态就绪状态只需要CPU就能运行执行状态等待/阻塞状态需要外部设备才能运行父子进程级联终止递归的终止每一个子进程孤儿进程父进程终止子进程仍未终止僵尸进程进程已结束但是OS未收回其进程控制块占用的资源线程轻量级进程进程的一个执行流特点共享静态资源例如地址空间和文件独立拥有运行时状态PC栈和寄存器进程 vs 线程进程间通信共享内存低成本同步问题消费者生产者问题消息传递较高成本无同步问题进程间同步问题竞态多个进程同步访问同一个共享资源导致产生错误结果原子操作不可被中断和拆分的操作临界区当多个进程访问同一处代码段时该代码段称为临界区解决同步问题的要求互斥进展有限等待解决同步问题软件双标志法flag标识是否准备和turn标识其他条件Peterson算法谦让算法将资格让给别人Dekker算法主动放弃 / 取消准备多进程方法面包店算法原始面包店算法为什么失败1.相同取号 2.选号不同步实现(选号,进程号)标识对于选号加锁互斥锁有锁不能进入临界区信号量多个共享资源的锁结构体信号量避免阻塞进程处于就绪态占用资源经典同步问题及其解决有限缓冲区问题使用两个信号量互斥锁多个读写者的问题写者和第一个读者拿互斥锁最后一个读者放弃锁哲学家问题同时拿一双筷子加锁解决同步硬件test_and_setcompare_and_swap死锁死锁的必要条件互斥保持等待非抢占循环等待死锁预防破坏死锁的条件互斥保持等待非抢占式循环等待数据库并发事务的死锁预防Wait-die和Wound-die事务事务是一组数据库操作等待-死亡法 Wait-die时间戳早的老进程可以等待年轻进程的锁年轻进程请求老进程的锁会自毁创伤-等待法 Wound-die年轻进程可以请求老进程的锁老进程请求年轻进程的锁时直接杀死年轻进程。死锁避免银行家算法资源分配向量最大需求向量当前需求向量和当前资源向量流程死锁检测检测死锁并且解决杀死某个进程直接抢占某个进程的资源CPU调度调度器的种类长期中期和短期长期调度器负责调度作业到准备态频率最低短期调度器负责调度准备态进程到运行态频率最高中期调度器负责调度等待态进程到内存中以节省资源CPU调度算法评价标准FCFS先到先得SJF短作业优先非抢占SRTF最短剩余时间优先抢占式优先级调度固定优先级Round Robin轮询算法每一个进程固定时间片多级队列权重分层算法独立不可流动多级反馈队列权重随执行次数降低算法独立可以流动实时CPU调度算法进程的实时性某些进程必须在特定周期得到执行单调速率调度根据周期倒数确定权重EDFS最短截至时间优先实时比较不同进程的截至时间优先执行接近截至时间的进程虚拟内存技术虚拟地址(逻辑地址) vs 物理地址内存管理单元 MMU保护程序不访问错误物理地址内存划分方法固定内存划分分为固定的分区内碎片问题变长内存划分根据程序内存需要划分外碎片问题分段技术变长区域段表外碎片分页技术固定长度页表内碎片页表查询逻辑地址虚拟页号(VPN)偏移单级别页表查询多级页表查询先查下一级页表所在块然后递归查询直到数据页表的内存问题转置页表下标代表物理页号表项代表逻辑页号偏移页表的访问TLB快表技术。共享页面一般进程间的页面是不共享的请求分页技术进程按需加载内存页错误实际上只是当前进程所需的内存未加载到物理内存中页面替换算法先到先来算法永远将第一个页面进行交换LRU谁最久没被使用过就交换谁磁盘磁盘的组成读写头轨道圆形分布的数据块扇区数据块磁盘的读写的延迟旋转时延寻道时延传输时延寻道算法先到先来 FCFS最短寻道时间优先 SSTF优先去离当前磁头最近的扇区电梯算法 SCAN从左到右扫描到右端终点后反向遍历C-SCAN从左到右扫描到右端后回到最左端不处理中间请求LOOK电梯算法快速版只扫描最小请求和最大请求的区域不扫描全部扇区C-LOOKC-SCAN快速版只扫描最小请求和最大请求的区域不扫描全部扇区RAID冗余磁盘阵列RAID的定义思想多个物理磁盘组成一个/少量逻辑磁盘将数据分散到各个物理磁盘上增加读写性能和数据安全性。条带化数据切片分散存储到多个磁盘上。镜像数据复制到多个磁盘上备份检验牺牲磁盘空间保存检验信息根据检验信息还原损坏数据RAID0条带化读写性能强RAID1镜像保护读性能快写性能慢RAID5条带化检验和磁盘利用率低读速度较快写速度较慢RAID10条带化镜像化条带化存储子磁盘系统使用镜像化保护文件系统定义操作系统管理和组织文件的软件系统文件不代表真实数据包含数据的元信息文件系统的组织结构inodelinux系统管理文件的数据结构目录项文件名inode超级块有多少个目录项和inode块组织结构磁盘中的多个扇区组成一个文件块磁盘系统分为inode目录项和超级块。文件存储方式连续存储文件包含首个块和块数量的信息非连续存储文件包含首位块和末位块的指针使用链表链接空间文件块管理查表法链表法空闲文件块链接起来位图法链接Link一个文件关联到另一个文件硬链接文件a和文件b链接文件a和b的指向的inode都相同删除任一一个文件不影响其他文件的数据引用软链接文件a和文件b链接文件b指向文件a如果文件a被删除那么文件b就是指向空链接。I/O 方式程序化IO中断化IO直接内存访问 DMA中断处理本质为程序操作系统的定义一个管理计算机硬件与软件资源的程序内核与操作系统的关系内核是操作系统的核心需要特权内存管理和CPU调用。内核不等于操作系统。操作系统还包括GUI和用户相关的一些接口。用户态切换为内核态系统调用通过trap自陷实现进程与线程进程定义执行中的程序进程包含的资源静态资源(地址空间文件资源)和动态资源(栈PC寄存器)进程控制块 PCB进程的PID,运行状态程序计数器PC寄存器文件资源等包括程序状态程序指针栈CPU寄存器状态内存占用文件列表等等。包括进程状态运行状态和进程编号。进程运行状态就绪状态只需要CPU就能运行执行状态等待/阻塞状态需要外部设备才能运行例如等待打印机-外部设备需要进行IO读取操作等等。信号量也是一种外部设备。父子进程级联终止递归的终止每一个子进程孤儿进程父进程终止子进程仍未终止僵尸进程进程已结束但是OS未收回其进程控制块占用的资源线程轻量级进程进程的一个执行流特点共享静态资源例如地址空间和文件独立拥有运行时状态PC栈和寄存器进程 vs 线程对比项进程线程基本概念正在运行的程序实例进程中的执行流资源拥有拥有独立的地址空间和系统资源不独立拥有资源主要共享所属进程的资源内存空间进程之间内存相互独立同一进程内线程共享代码段、数据段、堆等栈空间每个进程有自己的地址空间每个线程有自己的栈和寄存器状态创建/销毁开销较大较小切换开销较大需要切换地址空间等较小同进程线程切换更轻量通信方式进程间通信较复杂如管道、消息队列、共享内存、Socket线程间通信较简单可直接共享变量安全性/隔离性隔离性强一个进程崩溃通常不直接影响其他进程隔离性弱一个线程出错可能导致整个进程崩溃适合场景需要资源隔离、稳定性较高的任务需要并发执行、共享数据、低开销切换的任务进程间通信共享内存低成本同步问题消费者生产者问题多个进程通讯时可以划分同一块使用的进程每一个进程的某个内存区域都用来存储其地址。建立共享内存需要较多时间但是几乎没有其他的通信成本。缺点存在明显的进程间不同步问题写和读没有任何限制。消息传递较高成本无同步问题两个进程通讯时使用内核的消息队列。从消息队列中按顺序产出和消费消息同步问题少。缺点生成消息和消费消息都需要切换到内核态使用系统调用会有较大成本。进程间同步问题竞态多个进程同步访问同一个共享资源导致产生错误结果原子操作不可被中断和拆分的操作临界区当多个进程访问同一处代码段时该代码段称为临界区解决同步问题的要求互斥进展有限等待解决同步问题软件双标志法flag标识是否准备和turn标识其他条件Peterson算法谦让算法将资格让给别人Dekker算法主动放弃 / 取消准备钥匙在对方主动放弃(取消准备)让别人先进入临界区别人结束后再重新准备进入临界区。多进程方法面包店算法原始面包店算法为什么失败1.相同取号 2.选号不同步实现(选号,进程号)标识对于选号加锁互斥锁有锁不能进入临界区有锁不能进入临界区信号量多个共享资源的锁结构体信号量避免阻塞进程处于就绪态占用资源wait如果有可用资源则减少当前资源数否则阻塞signal释放资源可用资源1经典同步问题及其解决有限缓冲区问题使用两个信号量互斥锁多个读写者的问题写者和第一个读者拿互斥锁最后一个读者放弃锁哲学家问题同时拿一双筷子加锁n个哲学家n个筷子需要同时拿两个筷子才能就餐。解决同步硬件test_and_setcompare_and_swap死锁死锁的必要条件互斥保持等待非抢占循环等待死锁预防破坏死锁的条件互斥保持等待非抢占式循环等待互斥不能解决保持等待只能一次性请求资源否则放弃自身所有资源非抢占抢占其他进程的资源循环等待每一个进程请求资源的编号递增 (请求资源号只能递增)数据库并发事务的死锁预防Wait-die和Wound-die事务事务是一组数据库操作等待-死亡法 Wait-die时间戳早的老进程可以等待年轻进程的锁年轻进程请求老进程的锁会自毁创伤-等待法 Wound-die年轻进程可以请求老进程的锁老进程请求年轻进程的锁时直接杀死年轻进程。死锁避免银行家算法资源分配向量最大需求向量当前需求向量和当前资源向量确定进程现在分配了多少资源进程运行所需要的各个资源数进程还剩下多少资源流程1.比对当前资源是否能满足当前进程2.如果可以直接分配给当前进程并且等待进程执行完释放资源。更新可以支配的资源3.如果不行跳转下一个进程4.反复循环直到为每一个进程都分配足够的资源并执行否则无法避免死锁。死锁检测检测死锁并且解决杀死某个进程直接抢占某个进程的资源CPU调度调度器的种类长期中期和短期长期调度器负责调度作业到准备态频率最低短期调度器负责调度准备态进程到运行态频率最高中期调度器负责调度等待态进程到内存中以节省资源CPU调度算法评价标准等待事件周转率CPU利用率FCFS先到先得SJF短作业优先非抢占根据当前就绪进程的预估执行事件来选择执行。不会抢占一直执行到底 \color{red}{不会抢占一直执行到底}不会抢占一直执行到底。SRTF最短剩余时间优先抢占式实时进行检查如果有预估执行时间少于当前执行进程的进程优先执行该进程抢占当前进程的执行权 \color{red}{抢占当前进程的执行权}抢占当前进程的执行权。优先级调度固定优先级Round Robin轮询算法每一个进程固定时间片多级队列权重分层算法独立不可流动多级反馈队列权重随执行次数降低算法独立可以流动实时CPU调度算法进程的实时性某些进程必须在特定周期得到执行单调速率调度根据周期倒数确定权重EDFS最短截至时间优先实时比较不同进程的截至时间优先执行接近截至时间的进程虚拟内存技术虚拟地址(逻辑地址) vs 物理地址程序只知道逻辑地址所以看上去貌似是连续的。但很多时候对应的物理地址不是连续的。逻辑地址是私有的连续的。内存管理单元 MMU保护程序不访问错误物理地址由base和limit组成base标识程序逻辑地址对应的第一个物理地址。limit标识程序最多可以访问多少大小的物理/逻辑空间。内存划分方法固定内存划分分为固定的分区内碎片问题变长内存划分根据程序内存需要划分外碎片问题分段技术变长区域段表外碎片程序根据自身需要进行分段分为多个可能不等长的段。根据段表来存储程序段到物理段的映射关系。因为不等长所以段表需要存储段号和当前段长。分页技术固定长度页表内碎片进程的内存和物理内存分为固定大小的帧通过页表查询物理帧。页表包括逻辑帧对应哪一个物理帧。页表查询逻辑地址虚拟页号(VPN)偏移单级别页表查询先查虚拟页号VPN然后查表使用TLB块表或者其他方式最后得到物理页号PPN加上偏移得到真实数据地址。多级页表查询先查下一级页表所在块然后递归查询直到数据页表的内存问题转置页表下标代表物理页号表项代表逻辑页号偏移每一个进程都有固定的页表标识逻辑页号-物理页号会很占用空间转置页表就是每一个下标都是物理页表对应逻辑页表进程号全局共享。页表的访问TLB快表技术。记录映射和是否修改的记录。共享页面一般进程间的页面是不共享的请求分页技术进程按需加载内存一个进程需要的内存比实际内存大得多。只在必要时将进程所需要的内存加载到物理内存的页中否则放在磁盘里。页错误实际上只是当前进程所需的内存未加载到物理内存中页面替换算法先到先来算法永远将第一个页面进行交换LRU谁最久没被使用过就交换谁其实就是页面命中时要增加权重放在第一位更新LRU缓存。每次都将LRU缓存中最后一位(标识最久没使用)的页面交换出去。磁盘磁盘的组成读写头轨道圆形分布的数据块扇区数据块读写头用于读和写的媒介轨道一个 磁盘由多个轨道tracks组成。扇区扇区就是对应的数据块。磁盘的读写的延迟旋转时延寻道时延传输时延旋转时延与转速有关寻道时延读写头移动到某个扇区的时间有关传输时延数据进行读取和写入和时延寻道算法先到先来 FCFS最短寻道时间优先 SSTF优先去离当前磁头最近的扇区电梯算法 SCAN从左到右扫描到右端终点后反向遍历C-SCAN从左到右扫描到右端后回到最左端不处理中间请求LOOK电梯算法快速版只扫描最小请求和最大请求的区域不扫描全部扇区C-LOOKC-SCAN快速版只扫描最小请求和最大请求的区域不扫描全部扇区RAID冗余磁盘阵列RAID的定义思想多个物理磁盘组成一个/少量逻辑磁盘将数据分散到各个物理磁盘上增加读写性能和数据安全性。条带化数据切片分散存储到多个磁盘上。镜像数据复制到多个磁盘上备份检验牺牲磁盘空间保存检验信息根据检验信息还原损坏数据RAID0条带化读写性能强RAID1镜像保护读性能快写性能慢RAID5条带化检验和磁盘利用率低读速度较快写速度较慢RAID10条带化镜像化条带化存储子磁盘系统使用镜像化保护文件系统定义操作系统管理和组织文件的软件系统文件不代表真实数据包含数据的元信息文件系统的组织结构inodelinux系统管理文件的数据结构包括文件大小时间戳和真实存储位置的指针等信息。目录项文件名inode超级块有多少个目录项和inode块文件系统的存储情况包括存储了多个inode目录和块大小信息。组织结构磁盘中的多个扇区组成一个文件块磁盘系统分为inode目录项和超级块。文件存储方式连续存储文件包含首个块和块数量的信息非连续存储文件包含首位块和末位块的指针使用链表链接空间文件块管理查表法链表法空闲文件块链接起来位图法链接Link一个文件关联到另一个文件硬链接文件a和文件b链接文件a和b的指向的inode都相同删除任一一个文件不影响其他文件的数据引用软链接文件a和文件b链接文件b指向文件a如果文件a被删除那么文件b就是指向空链接。I/O 方式程序化IOCPU一直询问缓存器是否准备好一旦缓存区准备好CPU直接开始将其传输到内存中去。中断化IOCPU首先询问缓存是否准备好如果没准备好则等待缓存区准备好。如果准备好则向CPU发送中断CPU停止当前的事情开始负责传输到内存中。直接内存访问 DMADMA负责CPU和磁盘的沟通CPU发送查询命令DMA负责将磁盘中的内存复制到内存然后再中断CPU程序。CPU负责将其从内存传输到内核区。中断处理本质为程序中断当前的事务保存CPU现场程序的PC栈指针和CPU当前寄存器状态等等。根据中断向量查询中断服务程序。执行中断服务程序。回复现场和重新执行。