Posts

OO第二单元第二次作业 [toc] 0.题目新增需求 乘客不再固定电梯接送，设计电梯调度策略 增加RECEIVE输出，避免自由竞争策略 增加RESET请求，时长1.2s，在RESET期间电梯处于静默状态(不可以开关门、移动、RECEIVE等)，重置电梯 1.处理流程分析 1.1 电梯调度策略 ​ 在本次作业中，需要设计将乘客分配给合适的电梯的调度器(补第五次作业偷的懒)，我的设计中选择将调度器作为一个线程实现，输入线程与调度器线程交互，调度器线程与六个电梯线程交互。对于单个电梯运行的策略我保留了第五次作业的LOOK算法，对于多部电梯的分配策略，我选择了性价比较高的调参方法，性价比体现在代码量较少的同时能够拿到比较好的性能分数。UML时序图如下 1.1.1 UML时序图 1.1.2 调参算法 ​ 所谓调参算法其实就是选取几个有关电梯的指标，给这些指标赋予合适的参数，为每部电梯计算出得分，选择得分最高的电梯进行分配。我选取的指标有电梯接到该乘客需要走的距离，电梯中人数，电梯等待队列中人数，电梯容量，电梯速度。 距离：这里距离的计算是不准确的，没有找出电梯运行的上确界或下确界，即没有找出电梯运行到哪里就可以转向，而是同一按照1/11处理 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 private int getDistance(int fromFloor,int toFloor,int curFloor,boolean direction) { int distance = 0; int flow = (direction) ? 1 : -1; if ((toFloor - fromFloor) * flow > 0) { // 乘客移动方向与电梯当前移动方向相同 if ((fromFloor - curFloor) * flow >= 0) { // 电梯沿当前方向能接到乘客 distance = abs(fromFloor - curFloor); } else { if (flow == 1) { distance = 20 - curFloor + fromFloor; } else { distance = 20 + curFloor - fromFloor; } } } else { if (flow == 1) { distance = 22 - curFloor - fromFloor; } else { distance = curFloor + fromFloor - 2; } } return distance; } 电梯状态：电梯状态这个参数实际上是电梯容量、电梯中人数、电梯等待队列中人数三个量经过调参得来的，可以适当增加电梯等待队列中人数的权重，避免给一部性能好的电梯分配太多乘客，这样的性能可能还不如大家都运行 ...

OS:lab3课下基础 1.进程 由于没有实现线程，本实验中进程既是基本的分配单元，也是基本的执行单元 1.1 进程控制块 ​ 进程控制块(Process Control Block)是用来管理进程的数据结构，可以记录进程的变化过程，记录进程的外部特征。PCB是系统感知进程存在的唯一标志，进程与PCB是一一对应的。在MOS中，PCB定义为一个Env结构体 1 2 3 4 5 6 7 8 9 10 11 struct Env { struct Trapframe env_tf; // saved context (registers) before switching LIST_ENTRY(Env) env_link; // intrusive entry in 'env_free_list' u_int env_id; // unique environment identifier u_int env_asid; // ASID of this env u_int env_parent_id; // env_id of this env's parent u_int env_status; // status of this env Pde *env_pgdir; // page directory TAILQ_ENTRY(Env) env_sched_link; // intrusive entry in 'env_sched_list' u_int env_pri; // schedule priority }; env_tf : 在发生进程调度，或当陷入内核时，会将当时的进程上下文环境保存在env_tf变量中 ...

OS:lab2实验报告 Thinking 2.1 **在编写的C程序中，指针变量中存储的地址被视为虚拟地址，还是物理地址？MIPS汇编程序中lw和sw指令使用的地址被视为虚拟 地址，还是物理地址？ ** 在编写的C程序中，指针变量中存储的地址为虚拟地址 汇编程序中lw，sw发送的也是虚拟地址 Thinking 2.2 请从可重用性的角度，阐述用宏来实现链表的好处 使用宏定义对链表操作进行封装，可以实现代码的复用，即减少了工作量，也提高了程序的可读性 请你查看实验环境中的 /usr/include/sys/queue.h，了解其中单向链表与循环链表的实现，比较它们与本实验中使用的双向链表，分析三者在插入与删除操作上的性能差异 对于单向链表，由于它只能获得每一项的后面一项，因此在删除时需要遍历整个链表；同样，如果是在某一项的前面插入，也需要从head开始遍历这个链表。但是如果是“在某一项之后插入”，单项链表可以直接进行该操作。 对于循环链表，因为它仍然是单向的，所以在“删除”、“某一项之前插入”、“某一项之后插入”三个操作的性能和单项链表相同。但是，由于循环链表首尾相连，同时维护了一个指向尾项的指针，因此它可以直接在尾部插入。 对于双向链表，因为它可以直接获得某一项的前后两项，所以无论是“删除”还是“在某一项前或后插入”都可以以O(1)的开销实现。但是，双向链表没有维护指向尾部的指针，因此无法直接将某一项插入链表尾部，如要实现该操作还需要遍历整个链表。 Thinking 2.3 选择Page_list正确的展开结构 C struct Page_list{ struct { struct { struct Page *le_next; struct Page **le_prev; } pp_link; u_short pp_ref; }* lh_first; } Thinking 2.4 请阅读上面有关TLB的描述，从虚拟内存和多进程操作系统的实现角度，阐述ASID的必要性。 操作系统会给每一个进程分配一个页表，每个页表都有自己的虚拟地址空间，而同一虚拟地址在不同地址空间中通常映射到不同的物理地址。如果没有ASID来区分当前虚拟地址是在哪个进程中使用，则可能会将该虚拟地址映射到错误的物理地址。(每一个进程都有自己的虚拟地址空间4G，ASID可以区分不同进程同一虚拟地址转换成物理地址的方法) 请阅读 MIPS 4Kc 文档《MIPS32® 4K™ Processor Core Family Software User’s Manual》的 Section 3.3.1 与 Section 3.4，结合 ASID 段的位数，说明 4Kc中可容纳不同的地址空间的最大数量 ASID有8位，即最多可以有$2^8$个地址空间（进程数量） Thinking 2.5 tlb_invalidate 和 tlb_out 的调用关系是怎样的？ ...

OS:lab2课下基础 一.物理内存管理 1.虚拟地址映射到物理地址 在MIPS-4Kc上，软件访存虚拟地址会先被MMU(Memory Management Unit) 映射到物理地址，随后使用物理地址来访问内存或其他外设 ​ 虚拟地址空间中的四个部分 kseg0：存放内核代码与数据 将虚拟地址的最高位清0得到物理地址 通过Cache访存 0x8000_0000 - 0x9fff_ffff kseg1：访问外设 将虚拟地址的最高三位清0得到物理地址 不通过Cache访存 0xa000_0000 - 0xbfff_ffff kuseg：用户程序代码与数据 通过TLB转换成物理地址 通过Cache访存 0x0000_0000 - 0x7fff_ffff 2.内核程序启动 lab1中内核启动后跳转到mips_init函数，lab2中在mips_init中增加三个函数 在建立内核管理机制时，实验中都通过kseg0访问内存 2.1 mips_detect_memory 探测硬件可用内存，并对一些和内存管理相关的变量进行初始化 void mips_detect_memory(u_int _memsize) { /* Step 1: Initialize memsize. */ memsize = _memsize; /* Step 2: Calculate the corresponding 'npage' value. */ /* Exercise 2.1: Your code here. */ npage = memsize / PAGE_SIZE; printk("Memory size: %lu KiB, number of pages: %lu\n", memsize / 1024, npage); } memsize对应总物理内存对应的字节数 npage对应总物理页数 PAGE_SIZE是mmu.h中定义的宏，大小是4096，即每个物理页面的大小为4096字节 2.2 mips_vm_init alloc 在建立起页式内存管理机制之前，使用alloc进行内存空间的分配 ...

OO第二单元第一次作业 [toc] 0. 前置知识 0.1 进程与线程 计算机中，我们把一个任务称作一个进程(Process) 在一个进程中，还包含一个至多个子任务，称为线程(Thread) 进程与线程是包含关系，一个进程中可以包含多个线程 线程内执行顺序确定，线程间执行顺序由操作系统调度，无法确定 tips:此单元作业中不要使用调试，会影响线程，转为使用打印调试法 0.1.1 创建新线程 Java语言中内置了多线程支持，当Java程序启动的时候，实际上是启动了一个JVM进程，然后JVM启动主线程来执行main方法，在main方法中我们可以启动其他线程 继承Thread类 从Thread类派生一个自定义类，覆写run方法 public class myThread extends Thread { @Override public void run() { // ... } } 实现Runnable接口 实现Runnable接口，重写run方法 public class myRunnable implements Runnable { @Override public void run() { //... } } 创建一个新线程 Thread t = new myThread(); Thread t = new Thread(new myRunnable) 启动新线程 t.start() 注：start()方法会在内部自动调用实例的run方法，直接调用run()方法不会创建新线程 线程入口run()方法的模版 public void run(){ try{ while(true){ if(has new task) { //... } else { break; } } //do something to finish } catch(InterruptedException e){ //该线程被调用interrupt //... } //do something to finish } 0.1.2 线程的状态 在Java程序中，一个线程对象只能调用一次start()方法启动新线程，并在新线程中执行run()方法，一旦run()方法执行结束，线程就结束了 ...

OS第二次理论作业 1.多道程序的存储管理 空间的分配：分区式分配，将内存分为一些大小相等或不等的分区，每个应用程序占用一个或几个分区，操作系统占用其中一个分区 1.1 固定（静态）式分区分配 当系统初始化时，把存储空间划分为若干个任意大小的区域，然后将这些区域分配给每个用户作业 将内存划分为若干个固定大小的连续分区 分区大小相等：多个相同程序的并发执行 分区大小不等：多个小分区，适量的中等分区，少量的大分区 优点：易于实现，开销小 缺点：内碎片造成浪费，分区总数固定，限制了并发执行的程序数目 采用的数据结构：分区表——记录分区的大小和使用情况 1.1.1 单一队列分配方式 ​ 需要加载程序时，选择一个当前闲置且容量足够大的分区进行加载，即多个用户程序排在一个共同的队列中等待分区 1.1.2 多队列分配方式 ​ 防止单一队列造成的小程序占用大分区的情况，采用多个队列，每个分区一个队列，程序按照大小排在相应的队列中，即小分区排队的都是小程序，大分区排队的都是大程序 1.2 可变（动态）式分区分配 可变式分区：分区的边界可以移动，即分区的大小可变 优点：没有内碎片 缺点：有外碎片 1.2.0 内碎片与外碎片 内碎片：分配给作业的存储空间中未被利用的部分，如固定分区中存在的碎片 内碎片其实已经被分配出去了，只是没有被利用，在作业完成后会得到释放 外碎片：系统中无法利用的小的空闲分区，如分区与分区之间存在的碎片，动态分区管理会产生外部碎片 消除外部碎片的方法：紧凑技术 1.2.1 位图表示法 给每个分配单元赋予一个字位，用来记录该分配单元是否闲置。字位取值为0表示单元闲置，取值为1表示已被占用 空间成本固定，不依赖于程序中的程序数量 时间成本低，操作简单，直接修改位图值 没有容错能力：无法确定是为1还是因错误变为1 1.2.2 链表表示法 将分配单元按照是否闲置链接起来 空间成本取决于程序的数量 例如空闲链表，将内存中空闲的区域以链表的形式穿起来 时间成本：链表扫描速度较慢，还要进行链表项的插入删除和修改 有一定容错能力，链表有被占空间和闲置空间的表项，可相互验证 1.3 基于顺序搜索的分配算法 First Fit：每个空白区按其在存储空间中地址递增的顺序连载一起，在为作业分配存储区域时，从这个空白区域链的始端开始查找，选择第一个足以满足请求（够大）的空白块 Next Fit：把存储空间中的空白区构成一个循环链，每次为存储请求查找合适的分区时，总是从上次查找结束的地方开始，只要找到一个足够大的空白区，就将他划分后分配出去 Best Fit：为一个作业选择分区时，总是寻找其大小最接近于作业所要求的存储区域 Worst Fit：为作业选择存储区域时，总是寻找最大的空白区 2.页式内存管理 从方便管理物理内存的角度考虑 2.1 程序、进程和作业 程序：程序是静止的，是存放在磁盘上的可执行文件 进程：进程是动态的，进程包括程序的程序处理对象（数据），是系统分配资源的基本单位，分为系统进程和用户进程，进程有生命周期 作业：作业是用户需要计算机完成的某项任务，是要求计算机所做工作的集合，一个作业可以有多个进程 2.2 分页式存储管理 把一个逻辑地址连续的程序分散存放到若干不连续的内存区域内，充分利用内存空间，逻辑上相邻的页，物理上不一定相邻 页：在页式存储管理系统中，把每个作业的地址空间分成一些大小相等的片，称之为页 存储块（页框）：把主存的存储空间也分成与页面大小相同的片，这些片称为存储块或页框 ...

OS : lab1 实验报告 Thinking 1.1 **尝试分别使用实验环境中的原生x86工具链(gcc、ld、readelf、objdump 等)和 MIPS 交叉编译工具链（带有 mips-linux-gnu 前缀），重复其中的编译和解析过程，观察相应的结果，并解释其中向objdump传入的参数 的含义。 ** objdump传入参数的含义 参数 含义 -d 将代码段反汇编 反汇编那些应该还有指令机器码的section -D 与 -d 类似，但反汇编所有section -S 将代码段反汇编的同时，将反汇编代码和源代码交替显示，源码编译时需要加-g参数，即需要调试信息 -C 将C++符号名逆向解析 -l 反汇编代码中插入源代码的文件名和行号 -j section: 仅反编译所指定的section，可以有多个-j参数来选择多个section objdump-DS 要反汇编的目标文件名 > 导出文本文件名 -DS表示反汇编并将反汇编代码和源代码交替显示 使用原生x86工具链进行编译并查看反汇编 git@22373362:~/compile $ gcc -c hello.c -o hello.o git@22373362:~/compile $ objdump -DS hello.o > x86_log 如下图（部分） 使用MIPS交叉编译工具链进行编译 git@22373362:~/compile $ mips-linux-gnu-gcc -c hello.c -o mips_hello.o git@22373362:~/compile $ mips-linux-gnu-objdump -DS mips_hello.o > mips_log Thinking1.2 **尝试使用我们编写的readelf程序，解析之前在target目录下生成的内核ELF文件。 ** ...

OS ：lab1课下基础 1. 操作系统的启动 : boot 1.1 概述 ​ 将硬件初始化的相关工作称为bootloader程序，将bootloader程序放在非易失存储器中(ROM/FLASH)，将操作系统内核放在磁盘中。 将硬件初始化相关工作从操作系统中抽离出来放在bootloader中实现。实现了硬件启动和软件启动的分离。即由bootloader实现硬件启动，操作系统内核实现软件启动，这样负责硬件启动的指令不多，需要的存储空间不大，可以存在容量较小的ROM或FLASH中 bootloader在硬件初始化之后，需要为软件启动（操作系统内核的功能）做准备，将内核镜像从存放他的存储器（例如磁盘）中读到RAM中。bootloader需要将内核镜像加载到内存中，就可以选择用哪一个内核镜像进行加载，实现多重开机的功能，在一个硬件上选择运行不同的操作系统。 bootloader划分了硬件启动和软件启动的边界，bootloader主要负责硬件启动相关工作，操作系统内核专注于软件启动以及对用户提供服务的工作。简化操作系统的开发和移植。 1.2 bootloader ​ bootloader需要正确地找到内核并加载执行。bootloader的实现依赖于CPU的体系结构，分为stage1，stage2两个部分。 1.3 QEMU中操作系统的启动 ​ QEMU已经提供了bootloader的引导功能，支持加载ELF格式的内核。启动流程被简化为加载内核到内存，之后跳转到内核的入口。 2. ELF 2.1 编译链接 ​ 我们知道源代码文件需要经过编译链接两个阶段才能变成可执行文件来运行。 编译-c：源代码被翻译为二进制指令，得到目标文件 链接：将多个目标文件链接为可执行文件 将编译好的目标文件反汇编：objdump指令 objdump -DS <要反汇编的目标文件名> > <导出文本文件名> ​ 以简单的代码为示例 #include<stdio.h> int main() { printf("hello,world!\n"); return 0; } ​ 这里我们知道，头文件中只包含函数的声明，而不包括函数的定义，因此在预处理阶段（替换头文件、宏定义过程）只会将printf替换为他的声明。最后在链接阶段才会替换为printf的实现。即在编译的最后，链接器将所有的目标文件链接在一起，将 之前未填写的地址等信息填上，形成最终的可执行文件，这就是链接的过程 2.2 ELF ​ ELF是一种文件格式，即Executable and Linkable Format。ELF是Unix系统中一种常见的文件格式，包括可重定位文件(relocatable)，可执行文件(executable)，共享对象文件(shared object)。其中可重定位文件即为我们熟悉的.o文件，后两种文件都需要对.o文件进行链接才能产生。 2.2.1 段和节 段：segment 节：section ELF 官方文档中对于section segment的解释 所谓section与segment是同一数据的两种视图 左侧是链接视图：使用section进行链接 右侧是执行视图：使用segment运行 每个segment中包含一个或多个section 节头表(Section header table)：包含程序中各个节(section)的信息，在程序编译链接时使用 ...

OS-lab0 实验报告 Thinking 0.1 执行命令cat Modified.txt，观察其结果和第一次执行 add 命令之前的 status 是 否一样，并思考原因。 ​ 不一样。第一次执行add命令之前的status是未跟踪文件。第二次执行cat命令的status为尚未暂存以备提交的变更，并提示修改：README.txt。原因是第一次时，文件未被add过，即为未跟踪文件(Untracked file)，第二次查看status时，README.txt已经被add过，即已经放入暂存区，故只提示修改。 Thinking 0.2 思考一下箭头中的add thefile、stage thefile和 commit分别对应的是Git里的哪些命令呢？ **add the file : git add && git commit ** **stage the file : git add ** **commit : git commit ** Thinking 0.3 代码文件print.c 被错误删除时，应当使用什么命令将其恢复？ 可以使用git checkout -- print.c 关于git checkout -- <file>:在工作区中对多个文件进行多次修改后，若还未执行git add，可以使用本命令将工作区恢复成原样 代码文件 print.c 被错误删除后，执行了 git rm print.c 命令，此时应当 使用什么命令将其恢复 git reset HEAD print.c ...

OO第一单元第三次作业 0. 题目需求 ​ 本次作业在上次作业的基础上主要增加了求导因子，同时自定义函数表达式中允许调用已经定义过的表达式。 求导因子(归结在因子中)，求导因子形式为dx(表达式)，含义为对表达式中的x求导，其中可以出现多次求导的情况，但是自定义函数表达式中不会出现求导算子 ==关于求导的形式化表述== 求导算子 -> ‘dx’ 求导因子 -> 求导算子 空白项 ‘(’ 空白项 求导因子 空白项 ‘)’ | 求导算子 空白项 ‘(’ 空白项 表达式 空白项 ‘)’ 注意：求导算子内部可能有表达式，应该调用parseExpr 注：形式化表述中允许了多层求导的情况，例如， dx(dx(x)) ==可能用到的求导公式== $$ I.f(x)\space =\space c\space ,f'(x)\space = \space 0 $$$$ II.f(x)\space = \space x^n,f'(x) = nx^{n-1} $$$$ III. f(x)\space = \space exp(x),f'(x) \space = \space exp(x) $$$$ IV.[f(g(x))]'\space = \space f'(g(x))g'(x) $$$$ V.[f(x)g(x)]' \space = \space f'(x)g(x) + f(x)g'(x) $$ ==因子->变量因子|常数因子|表达式因子|求导因子== ...