操作系统 4. 外设与文件系统 2021-04-13 浏览量 613 暂无评论 [TOC] ## 4.1 IO系统 显示器与键盘为终端设备。 ### 4.1.1 IO与显示器 给外设的控制器/存储器写入指令，让其操控设备，操控完向CPU发出中断。 形成**文件视图**；发出OUT指令；形成中断处理。 每个设备都有自己的访问方式（格式），为了使用方便，将它们写成文件，形成文件视图。 无论什么设备，系统的调用接口都是`open(), read(), write(), close()`。 每个接口下面都有好多分支，根据信息一步步找到需要操作的设备并操作。  ### 4.1.2 键盘 每个键都有一个扫描码，根据键表中对应的扫描码作出响应。  ## 4.2 磁盘与文件 ### 4.2.1 生磁盘的使用 比键盘和显示器复杂得多。 磁盘由一个个盘面组成，每个盘面外环为磁道，内环为扇区，扇区是磁盘的访问单位，大小为512字节。  磁盘IO过程：控制器-->寻道（磁臂）-->旋转（磁道）-->传输 控制器需要的参数：柱面（cyl）、磁头（head）、扇区（sec）、缓存位置 再进一步： 通过盘块号（block）读写磁盘，**磁盘驱动**负责从block计算出cyl，head，sec（CHS） 怎么计算呢？ 由一维向三维编址 如何编址：要让block相邻的盘块可以快速读出（满足实际） 磁盘访问时间 = 写入控制器时间 + 寻道时间 （12ms to 8ms）+ 旋转时间（7200r/min, 半周4ms） + 传输时间（50M/s, 0.3ms） 寻道时间最长，那么要让相邻的盘块放在相邻的扇区或盘面（磁头），由此可得到 $block=C*(Heads*Sectors)+H*Sectors+S$ 盘块可以包含多个扇区，这样一次读取多个连续扇区，可以提高读写速度（以牺牲空间为代价） **多个进程通过队列使用磁盘** 涉及到调度，主要目标是平均访问延迟小，寻道时间占主要部分 FCFS SSTF（短寻道优先，不公平） SCAN C-SCAN（电梯算法，完成一次-复位【复位的时间很短】） ### 4.2.2 从生磁盘到文件 关键：从文件得到盘块号 用户：文件为字符流 磁盘：文件为盘块 文件：建立字符流到盘块号集合的映射关系 每个文件都有个对应的FCB，存放文件存放的起始块 不同的文件使用不同的实现方式（如word需要动态增长） 实现方式： - 连续结构，不适合动态增长，适合直接读写 - 链式结构 - 索引结构，多级索引 ### 4.2.3 文件使用磁盘的实现 inode->盘块号->电梯队列->CHS->out磁盘控制器->驱动马达->电磁形成数据 其他设备，inode->对应设备函数 ## 4.3 文件系统 ### 4.3.1 目录与文件系统 磁盘-->目录树 核心问题：怎么将一系列文件映射到整个磁盘 发展：所有文件放在一起-->分用户存放-->目录树（分治） **如何高效地根据路径名，得到文件的FCB（inode）？** 首先，不能在每次读取目录下的文件时，将该目录下所有文件的PCB读进内存，这样太浪费资源，而且频繁的硬盘读会降低速度 目录项：文件名+对应的FCB地址（<data, 103>） 根目录（存在硬盘的FCB数组中的第0个，根据根目录文件找到它的数据块（目录中存放的内容））-->匹配数据块的目标字符<xx, 12>，再定位FCB数组中第12个元素找到下一个数据块，依次往下进行，知道找到目标文件的FCB 那么，要使整个系统能够自举，还需要存储一些信息，比如根目录的位置，通常，磁盘被格式化为如下形式： 引导块 超级块 inode位图 盘块位图 inode 数据区 引导块：大小一般固定 超级块：存放inode位图和盘块位图的位置（**在系统中mount，其实就是读超级块**） inode位图：哪些文件的inode是空的（可以再被分配使用） 盘块位图：哪些盘块是空的 疑问：inode位图取多大呢？怎么知道我将来要放的文件的数量呢？ ### 4.3.2 目录解析代码实现 1. 解析根目录： 在系统启动shell时，mount_root() 2. 读取inode--iget() 3. 找到目录项--find_entry() 匹配文件（夹）名 跳至2，直到树底 操作系统全图： 进程带动 多进程视图+文件视图 - 阅读全文 -
操作系统 3. 内存管理 2021-04-07 浏览量 617 暂无评论 [TOC] ## 3.1 内存管理 ### 3.1.1 内存使用与分段 时间：2021-03-28 场景：汇编中，call 40这条指令表明要跳到40这个地址（逻辑地址、相对地址）执行，那么把程序载入到内存中时，物理内存的40位置一定要存放对应的程序，如果不对内存进行分段的话，这显然不切实际，因为40这个地址可能存放了别的程序（事实上，0开始的位置存放的是操作系统），所以，程序在载入内存时应当找到一段空闲内存，并修改相应的逻辑地址为物理地址（==重定位==）。 重定位也有两种方式： 1. 编译时（硬系统，如一些嵌入式的系统，效率高，但不灵活） 2. 载入时（灵活通过，==但目前来讲，程序载入进内存就不能移动了==） 怎么才能让载入内存的程序实现移动呢？ ==swap==：如果进程发生阻塞，那把它放在内存中有点浪费内存，这时候将该进程睡眠，换出到磁盘（已经重定位过了物理地址），想执行的时候再换入，那么问题来了，怎么保证它换入时的物理内存地址和原来一样呢？==运行时重定位（地址翻译）== `base+offset` `base`保存在哪呢？==PCB====>==基址寄存器== 还有个问题：如果找不到一段足够大的空闲内存放程序怎么办呢？ 将程序分段，每个段有各自的特点、用途，如代码段（只读）、数据段（可写），每个段都是从0开始编址（用户可独立考虑每个段[==分治==]） 这样就可以将一个程序的每个段分别放入内存，==段号+段内偏移== 这时候PCB里要存放每个段的基址（进程段表LDT，和操作系统对应的段表GDT同理） ### 3.1.2 内存分区与分页（Memory Partition and Paging） 时间：2021-03-29 **程序进入内存的步骤：** 1. 程序分段 2. 在内存中找出空闲区域 3. 将程序从磁盘中读到内存 **为什么要分区？** 由上一小节很容易引出内存分区，因为要看哪些部分是空闲的，大小为多少 **怎么分区呢？** 固定分区与可变分区 可变分区的管理：请求分配，释放内存，再次申请（涉及到分配哪块空闲的） 分配哪块呢？首选适配（第一个，快），最佳适配（大小最合适，O(n)），最差适配（每个段均匀）  <font color='red'>实际的系统的物理内存并不使用内存分区，而是内存分页</font> **为什么要分页？** 解决内存分区导致的内存效率问题，比如内存碎片，需要将空闲分区合并（内存紧缩），但执行该操作的时候CPU不能干别的。 **怎么分页？** 将内存分成，比如每4K一页，针对每个段内存请求，将段打散，系统一页一页地分配给这个段，（那重定位就变得复杂点，得知道它想跳转的地方被分到了哪个页，地址//页大小（根据这个找到页框的物理地址）+地址%页大小），需要用到页表（cr3），==MMU会自动计算== ### 3.1.3 多级页表和快表 时间：2021-04-01 之前的分页方法有什么问题？ 为了提高内存的空间利用率，页应该小，但是页小了页表就大了 怎么解决？ 尝试1：分配给进程中的逻辑页中，有的逻辑页用不到，（要问为什么用不到还要分配给它的话，考虑重定位时的逻辑页总数：地址//页大小 + 1），那就只保留用到的逻辑页的页表项 问题1：这时的页表不连续，查找起来费时，顺序查找-->折半查找，但这也费时，降低运行速度，页号连续的话查找就很快，怎么结合这两个呢？==多级页表就来了== 尝试2：页目录表+页表（类比书的目录） 可以，但访问内存的次数变多，时间上更奢侈 尝试3：快表（TLB，相联快速存储，是寄存器） 快表中存放最近使用的页表项，找不到的话再到多级页表中找 要让快表好使，它的命中率一定要高，所以快表越大越好（但它贵呀，一般64~1024）；同时，置换的算法也很重要  ### 3.1.4 段页结合的实际内存管理 程序（分段）-->虚拟内存（地址空间，段->页）-->物理内存（分页） 逻辑地址-->虚拟地址-->物理地址 段面向用户，页面向硬件 虚拟内存不用管理吗？还是说浪费了也没事，有碎片就有碎片，反正不贵 ``` 段页式内存下程序如何载入内存？ 1. 在虚拟内存中分配段 2. 将程序对应段放到虚拟内存对应段； 3. 将虚拟内存的段分页放到物理内存； 4. 建立页表； 5. 使用。 ``` ## 3.2 虚拟内存 使用换入换出实现虚拟内存。 ### 3.2.1 请求调页与内存换入（Swap in） 2021-04-06 物理内存小于虚拟内存，虚拟内存比较规整，就算物理内存没那么大，虚拟内存也能让用户感觉可以使用那么大，不用因为物理内存的大小而头疼，那么就**使用换入换出实现“大内存”**，用到程序的哪段就把这段从硬盘换入到物理内存。 ### 3.2.2 内存换出（Swap out） 2021-04-07 还记得请求调页时候的`get_free_page`吗？而内存是有限的，并不能总是获得新的页，需要选择一页淘汰，换出到磁盘，那怎么选择呢？用缺页次数来评价方案的好坏。 - FIFO，刚换出去又要换进来的话，就很麻烦 - MIN，选最远将使用的页淘汰，是最优方案，但是要知道将来发生的事 - LRU（Least recently used），用过去的历史预测将来，选最近最长一段时间没有使用的页淘汰 LRU怎么实现呢？ **时间戳（time stamp）** 每页维护一个时间戳，记录该页在第几个时刻使用到了。（每执行一条指令，都要维护这个时间戳） **页码栈** 每执行一条指令，都要更新栈 LRU近似实现SCR[又叫Clock Algorithm]（因为准确实现太奢侈） 将时间计数变为是和否，每页加1个引用位R，每次访问一页时，硬件自动设置该位（就不用软件维护时间戳了，直接MMU），选择淘汰页：扫描该位，是1时清0，并继续扫描，是0时淘汰。 但如果缺页很少的话，几乎所有的R都为1（因为只有缺页时才会将0变为1），那需要换页的时候，指针会循环一遍，把所有的1变为0，然后换掉第一次指向的页，SCR退化为FIFO。 原因：记录了太长的历史信息 怎么办：定时清除R位（再来一个快的扫描指针），确保“最近” 给进程分配多少页框（frame）呢？ 求工作集，覆盖局部。 与页框分配有关的问题：系统颠簸  - 阅读全文 -
操作系统 2. 进程与线程 2021-04-06 浏览量 646 暂无评论 #### 操作系统之进程与线程 - [x] L8 CPU管理的直观想法 2021-03-19 管理CPU IO指令执行特别慢，比计算语句为10^6:1，如果计算指令与IO指令顺序执行，CPU利用率特别低，要提高CPU的利用率，多道程序交替执行  并发：多道程序放在内存中，CPU交替执行，切过去，切回来（改PC，即IP） 怎么实现这种交替执行呢？ - 记录返回地址和继续执行需要的数据 进程：进行中的程序 - [x] L9 多进程图像（Multiple Processes） 2021-03-20 用户创建多个进程，操作系统使用PCB（Process Control Block）记录这些进程，按合理的次序推进 多进程图像从启动开始到关机结束 main中的fork()创建了第一个进程，init执行了shell（Windows桌面） `if(!fork) {init();}` shell再启动其他进程 ```cpp int main(int argc, char* argv[]) { while(1) { scanf("%s", cmd); if(!fork()) {exec(cmd);} wait(); } } ``` 多进程的组织：PCB+状态+队列 交替：队列操作（设计到怎么取下一个进程）+调度+切换 ```cpp // 要使用汇编来精细控制 switch_to(pCur,pNew) { pCur.ax = CPU.ax; pCur.bx = CPU.bx; ... pCur.cs = CPU.cs; pCur.retpc = CPU.pc; CPU.ax = pNew.ax; CPU.bx = pNew.bx; ... CPU.cs = pNew.cs; CPU.retpc = pNew.pc; } ``` 如何解决多进程间的相互影响？多进程的地址空间分离（内存管理，映射表） 如何解决多进程间的相互合作？进程同步（锁！切换条件，检查锁，上锁，开锁） `fork()`：在现有进程中创建子进程，子进程是父进程的副本，它将获得父进程数据空间、堆栈等资源的**副本**，后面需要使用时，再分离修改。 - [x] L10 用户级线程（User Threads）yield 2021-03-20 进程 = 资源 + 指令执行序列 如果能将资源和指令执行分开，切换指令而资源不变，岂不美哉？==>线程（映射表不变而PC指针变） 线程和进程肯定都有自己适用的地方 线程： 概念：多个执行序列 + 一个地址空间 适用场景：多个线程配合完成一个任务，不需要地址隔离 实现：`pthread_create`创建，`yield`切换 存在的问题：如果两个线程共用一个栈，那么切换会出问题，线程内部函数切换和线程间切换就乱套了 解决：当然是隔离栈啦 ```cpp // 寄存器esp指向当前栈的指针 void Yield() { TCB2.esp = esp; esp = TCB1.esp; jmp xxx; // 这句话应该去掉，不然后面的}无法执行，少弹(ret)了一次栈 } // 创建TCB，并和栈关联 void ThreadCreate(A) { TCB *tcb = malloc(); *stack = malloc(); *stack = A; tcb.esp = stack; } ``` 缺点：如果一个线程进入内核后发生阻塞（如访问网卡IO，访问硬件需要通过内核），那么内核将会切换到其他进程，看不到这个线程后的其他线程，但是核心级线程是在内核中，并发性更好 - [x] L11 核心级线程（Kernel Threads）schedule 内核级线程才能真正发挥多核CPU的功能，因为用户级线程无法对硬件进行分配 多进程也不能，因为多核CPU的Cache和MMU是共享的 从用户级到内核级：两个栈到两套栈（每个都有用户栈和内核栈），内核级线程比用户级多了一步内核栈切换 那么内核栈在哪呢？中断进入（INT）内核时自动启用内核栈（硬件实现），IRET退出 - [x] L12 核心级线程实现实例 2021-03-22 <font color='red'>没有实际写代码，对汇编和C要求很高</font> - [x] L13 操作系统的那棵树 2021-03-23 梳理怎样从简单的顺序执行到用户态多进程再到内核态多进程 - [x] L14 CPU调度策略 根据任务需求综合考虑：响应时间，周转时间，系统内耗（切换次数） 前台任务、后台任务；IO约束型、CPU约束型 常见的调度算法： 1. First Come, First Served (FCFS)  2. 短作业优先（SJF）<u>那怎么知道谁长谁短呢？</u> 周转时间最短（后台任务），但是响应时间得不到保证 3. 轮转（RR）按时间片轮转调度 响应时间可以得到保证（前台任务），通过时间片大小控制，但是要控制进程数N 4. 优先级调度 前台任务优先级大于后台任务，但只用优先级调度会造成后台任务饥饿 如果后台任务优先级动态升高，前台的响应时间又得不到保证 如果前后台都是用时间片，那后台任务的SJF又得不到体现 - [x] L15 一个实际的schedule函数 2021-03-23 ```cpp void Schedule(void) { while(1) { c = -1; next = 0; i = NR_TASKS; p = &task[NR_TASKS]; // 这句话没明白；明白了（数组的末尾存放PCB） while(--i) // 下面的p没变吧；PPT中的程序少了 { if(!*--p) continue; // counter既有优先级的作用，又有时间片的作用 if((*p)->state==TASK_RUNNING&&(*p)->counter>c) c = (*p)->counter, next = i; // 找到就绪态counter最大的进程 } if(c) break; for(p=&LAST_TASK;p>&FIRST_TASK;--p) { if(*p) // 保证进入IO的进程再出来后优先级变大 (*p)->counter = ((*p)->counter>>1) + (*p)->priority; } } switch_to(next); } // counter时间片的作用 void do_timer(...) { if (--(current->counter)>0) return; current->counter = 0; // 到点就执行 schedule(); } ``` - [x] L16 进程同步与信号量 2021-03-24 场景：进程合作，多进程共同完成一个任务 只发信号不能处理多对多（多个生产者消费者）的问题，需要使用信号量 生产进程，消耗进程 - [ ] L17 对信号量的临界区保护 2021-03-25 问题： 不同进程共同修改（调度）信号量时可能会出错，导致信号量的含义不对。  解决方案： 上锁保护，修改信号量的代码放在临界区（一次只允许一个进程进入的该进程的那段代码） 临界区代码的保护原则： 1. 互斥进入； 2. 有空让进； 3. 有限等待 第一种：对称法容易造成卡死，非对称=轮转+标记（Peterson算法） 两个进程：Peterson算法 多进程：面包店算法（复杂） 第二种：硬件阻止另一个进程进入临界区，也就是阻止调度=>关中断（cli，sti），但是多核时不好使，只能控制一个CPU 第三种：硬件原子指令  - [x] L18 信号量的代码实现 2021-03-26 很隐蔽的队列：编译的时候，tmp放在当前进程的内核栈中，那么task_struct就能找到tmp，tmp又指向前一个task_struct  - [x] L19 死锁处理 2021-03-26 多进程环路等待 成因（比如信号量临界区的上锁和解锁间加入了别的信号量）： 1. 互斥使用； 2. 不可抢占； 3. 请求和保持； 4. 循环等待。 解决方案： 1. 死锁预防（资源浪费）； 2. 死锁避免，判断系统中的所有进程是否存在一个可完成的执行序列，即安全状态（银行家算法，时间复杂度高），如果可能产生死锁，则拒绝此次资源申请； 3. 死锁检测+恢复，不每次申请的时候都执行银行家算法，转而定时检测或者发现资源利用率低的时候检测（但发现问题时想回滚挺麻烦）； 4. 死锁忽略（因为最简单，而且出现死锁的概率小，并且重启可以解决，都采用这个方法我笑了） - 阅读全文 -
操作系统 1. 基础 2021-04-04 浏览量 781 暂无评论 操作系统--哈工大李治军 ## 操作系统之基础 打开电源CS=0xFFFF, IP=0x0000 寻址0xFFFF0（ROM BIOS映射区） 检查RAM，键盘，显示器，软硬磁盘 将磁盘0磁道0扇区（引导扇区512字节）读入0x7C00处 设置CS=0x07C0, IP=0x0000 执行bootsect （.s） 将引导0x7C00移动到0x9000:0x0000处 载入setup模块（4个扇区）到0x9000:0x0200处（int 0x13） 获取磁盘数 读光标--显示Loading system 读入system模块（0x1000+0x8000[SYSSIZE, 编译操作系统时设置]） jmpi 0, SETUPSEG 执行setup 取出光标位置（0x90000），扩展内存大小（0x90002） 将system模块移到0地址（所以上面要先将引导扇区移到0x9000:0x0000处） 进入保护模式并跳转至0地址（mov ax, #0x0001 mov cr0, ax jmpi 0, 8） [cr0寄存器最后一位设为1时，进入保护模式，寻址方式发生改变，使用地址翻译（从GDT全局描述符表中选择基址），0时为实模式] 执行system 第一部分代码为head.s（32位汇编代码），利用压栈调用C函数（main.c） 进入main函数（各种初始化） 进入main函数后永不退出，操作系统一直运行 - [x] L1 什么是操作系统 2021-03-17 - [x] L2 开始揭开钢琴的盖子 2021-03-17 - [x] L3 操作系统启动 2021-03-17 - [x] L4 操作系统接口 2021-03-18 系统接口就是提供一些函数来完成系统调用，实现应用程序和操作系统的交流。POSIX标准 - [x] L5 系统调用的实现 2021-03-18 既然应用程序和内核都在内存中，为什么应用程序不能直接访问内存，获取想要的东西，而要通过系统调用？那当然啦，不然岂不是什么都能轻易被人拿去了，密码随便就没了 **那怎么禁止这种乱用（jmp，mov）内核呢？** 使用硬件实现隔离（内核态，用户态），目标特权级（DPL），当前特权级（CPL，CS的最后两位），数字越小，特权越大 硬件也提供了主动进入内核的方法，让系统调用可以进入内核执行，**int 0x80中断指令**，将DPL设为3，进入内核后，CPL置为0 应用程序-->库函数-->系统调用（内嵌汇编，包含int指令，根据编号执行相应指令） **int 0x80:** ``` void sched_init(void) { set_system_gate(0x80, &system_call)} ``` **怎么添加系统调用呢？** 修改kernel/system_calls.s中的系统调用总数nr_system_calls， 在include/linux/sys.h中的sys_call_table添加对应的系统调用函数 新增who.c文件，里面编写sys_iam和sys_whoami，并修改Makefile文件，将who.c添加到内核中 在/usr/include/unistd.h中添加__NR_xxx xx，然后编写iam.c和whoami.c 编译内核，gcc编译iam.c和whoami.c - [x] L6 操作系统历史 IBSYS批处理-->OS360多道程序（多进程，作业之间切换调度）-->MULTICS分时系统（多人）-->UNIX-->Linux <font color='red'>多进程图谱（CPU、内存）</font> <font color='red'>文件操作（IO、磁盘、文件）</font> - [x] L7 我们的任务 - 阅读全文 -
