操作系统笔记

单道/多道批处理，分时系统

操作系统的四个特征：并发、共享、异步、虚拟

进程

进程的概念：动态、并发、独立、异步

进程控制块：pid、状态、优先级、现场信息

进程同步和互斥

生产者-消费者；哲学家；读者-写者

进程调度：高级调度（作业调度），低级调度（进程调度）。后备队列，就绪队列，等待（阻塞）队列
调度算法：FIFO、短作业、高响应比（1+等待/要求，不存在抢占）、优先级（需要优先级）
属性：提交时间、要求执行时间、开始执行时间、完成时间、周转时间（完成-提交）、带权周转时间（周转/要求）

进程通信：共享存储器、管道、消息传递通信

死锁产生的必要条件：互斥、占有且等待、不可剥夺、循环等待
解决方法：银行家算法（进程、最大值、已分配、还需要、可用）；资源分配图（圈是进程，方块是资源；箭头由圈指向方块表示需求，由方块指向圈表示已分配）

逻辑块叫页或页面（page），物理块叫页框或帧（frame）；页面大小一般为4KB=2^12
十进制逻辑地址=页号*页面大小+页内地址，十六进制需要变成二进制再根据逻辑地址结构划分页内地址和页号；由页号查页表得物理块号（第一次访问内存），乘以加上页内地址即得物理地址（再去取数据的话是第二次访问内存）；页号和业内地址都是从0开始
页号小于等于表项数-1，表项数=页表大小/表项大小；但页表也要存放在页面里，所以页表的最大大小=页面大小；页表的最大表项数一般为4KB/4B=1024个
表项（PTE）大小与逻辑地址或内存大小对应，一般为4B=32bit，其中20bit用于页号（实际上10bit二级，10bit一级），12bit用于页内偏移
进程的所需的页面数也即实际表项数=进程大小/页面大小；这些表项占的空间=表项数*表项大小；储存这个页表需要占的页面数=表项占的空间/页面大小=实际表项数/一个页表的表项数
如果访问的页号超过实际表项数，会产生越界中断

以缺页次数作为判断好坏的依据
属性（第一列）：页走向、1、2、3（内存块数）、缺页（如果有，标为+；第一次调入也算）
算法：OPT（无法实现，淘汰未来最晚用到的）、FIFO、最久未使用算法LRU（访问一次后移到最上面）、最近最少使用置换算法LFU（是按频次不是时间）、时钟CLOCK算法/最近未用NUR（访问一次把某标志记为1，一段时间自动变0）
页面缓冲算法：全局分配、局部置换策略，FIFO置换算法；内存包括：已修改页面链表（但暂时不使用）、空闲页面链表、进程占据的内存

表项大小是0.5B的整数倍，FAT32的表项大小为4B；表项决定能管理多大的磁盘空间（索引到那里）2^32 × 磁盘块大小（一般为4KB或1KB）；但事实上FAT32的高四位是不用的，这样算下来就是1TB，但MBR在引导区只使用4B记录扇区数，即2T
磁盘块的数量 = 分区容量/磁盘块大小，整个FAT表的大小=磁盘块的数量 × 表项大小
支持的单文件最大大小，FAT32是4GB，因为文件长度用4B储存

能管理的最大磁盘空间：2^(8×表项大小) × 磁盘块大小；非混合索引能支持的最大文件大小：(磁盘块大小/表项大小) × 索引级数 × 磁盘块大小
混合索引：0-9号是直接索引10 × 4KB = 40KB，每个都算一个间接盘块；10号是一级间接索引1 × (4KB/4B) × 4KB = 4MB，如果占满的话存在(1+1K)个间接盘块，连带直接索引一起就是1010个