Mar

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) $$ ...

OS : lab0课下基础 1. Linux Command cat命令用于拼接文件并输出到标准输出，也可以用于查看单个文件内容。 拼接文件并输出到标准输出，cat file1 file2将文件2的内容拼接到文件1的后边输出到标准输出 查看单个文件内容，cat file 常用：使用cat命令拼接文件重定向输出到文件中 cat file1 file2 > newfile head查看文件的首部内容 head -n <n>显示文件的前n行内容 tail查看文件的尾部内容 tail -n <n>显示文件的后n行内容 tail -f <n>文件增长时，输出后续添加的数据 ps命令用于显示当前进程状态（process status） ps -e显示所有进程 ps -f 显示全部信息 kill用于向进程发送信号，不止于终止进程 kill -9强制杀死进程 sudo超级用户权限执行命令 sudo command mkdir递归建立目录：-p参数 mkdir -p dir/inner 2.有关文本处理 1. vim /<word>文件下寻找名为<word>的字符串 :%s/<word1>/<word2>/g，全文中寻找<word1>字符串，并将该字符串取代为<word2> [n] yy，复制游标所在的一行或n行，用p/P可以粘贴 [n] dd，删除游标所在的一行或n行，用p/P可以粘贴（类似于剪切） p粘贴在光标下一行，P粘贴在光标上一行 u:undo ctrl + Q块选，通过移动光标可以选中块，实现更加便捷的操作，例如删去段首的注释，为段首增加空格等。 d剪切选中文本 y复制选中文本 p粘贴选中文本 u复原 }选中光标下一个段落 {选中光标上一个段落 2. grep grep(global regular expression)命令用于查找文件中符合条件的字符串或正则表达式。主要用于查找 ...

OO第一单元第二次作业 0.题目需求分析 0.1 概念分析 本次作业在第一次作业的基础上添加了指数函数和自定义函数，其中 需要支持嵌套多层括号 新增指数因子，指数函数括号内部包含任意因子 新增自定义函数因子，自定义函数的表达式会给出且其中不会调用其他自定义函数 本次迭代表达式架构上的改变 支持前导0的十进制带符号整数 因子 变量因子，x 幂函数 一般形式：x^非负整数 省略形式：指数为1，x 指数函数：特指以e为底数的指数函数，表示为exp(<因子>)等 一般形式：exp(<因子>)^指数，注：该指数为exp()整体的指数 exp()的指数为非负整数 **省略形式：**指数为1时，写为exp(<因子>) 自定义函数 自定义函数中不会调用其他自定义函数，定义类似于 f(x,y,z) = 表达式（可能不全部包含x,y,z这三个变量） f,g,h是函数的函数名，本次作业中的自定义函数名只包括f,g,h即最多只有三个自定义函数 x,y,z是函数的形参，形参个数为1~3个，且同一函数定义中不会出现重复使用的形参 函数表达式为关于形参的表达式 函数调用的形式为f(因子，因子，因子)，例如f(x^2),g(exp(x^2),exp(x)),h(1,0,-0)，因子为函数调用中的实参，包含任意一种因子 注意：函数定义中不允许出现自定义函数，但是函数调用中的实参可以是自定义函数 常数因子 表达式因子 项 表达式 ​ 关于去括号要求中的**“必要的括号”** 指数函数调用时必要的一层括号exp() 指数函数对应的嵌套因子为不带指数的表达式因子时，该因子两侧必要的一层括号，例如 exp((x+1)^2)中(x+1)中的括号是不合法的，需要展开为不带指数的形式exp((x^2+2*x+1)) 0.2 表达式架构图 大致保留之前的架构，新增指数函数因子类和自定义函数因子类 1.处理流程分析 1.1 字符串预处理 由于自定义函数的引入，可以新增去除,后不必要的+ 1.2 语义分析 1.2.1 Lexer ​ 本次作业中，新增了EXP,F,G,H,COMMA(逗号)等token，需要增加识别功能。 1.2.2 Parser 1.2.2.1 parseExp ​ 在Parser类中新建一个方法parseExp，当我们读到的token为EXP时调用该方法进行解析。首先对括号内的因子进行解析，再对括号外的指数进行解析。 $$ exp()^n \space | \space exp() $$ public Factor parseExp() { // exp(<factor>)^<num> | exp(<factor>) // lexer : exp -> pos = pos + 4 already into the ( // 读到RP时接着往后读看有没有指数 int pow = 1;//默认指数为1 Factor innerFactor = parseFactor(); if (lexer.getCurTokenType() == TokenType.POW) { // 后面有指数 } return new Exp(innerFactor, pow); } 1.2.2.2 parseFunc 1.2.2.2.1 Definer ​ 为了成功地解析自定义函数，我们首先定义出Definer类，他的主要作用是处理自定义函数的定义以及调用。（相当于parseFunc的slave）其中定义出两个HashMap ...