oo-Unit3
前言经过了上一单元电梯的折磨,我个人感觉这次的JML相比之下还是比较容易的吧
架构设计容器的选择本次单元作业的绝大多数指令都是通过id来寻找对应的tag,Person还有Meessage。
以Person为例,如果把所有的Person都放在一个List容器里,那么我们每次查找都需要遍历一遍容器,算法复杂度为O(n),很容易出现TLE。
所以我选择了HashMap作为存储容器,将id作为键值,这样可以保证每次查询都能以O(1)的复杂度完成。
算法设计由于本单元的各个方法之间相对独立,所以我就逐个分析一下我优化的方法。
第一次作业
第一次作业中呢,有三个较为复杂的方法:isCircle,queryBlockSum和queryTripleSum。那首先就单纯看JML我们可以看到queryBlockSum是二重for循环,queryTripleSum是三重for循环。这种O(n^2)及以上的时间复杂度肯定是不行的,所以我们可以通过并查集和随时维护来进行降低时复杂度。
并查集首先我的并查集中有三个容器: parent存放每个节点的根节点,rank存放每个节点的秩,graph存放与每个节点直接 ...
OS-lab3
一、思考题Thinking 3.1请结合 MOS 中的页目录自映射应用解释代码中e->env_pgdir[PDX(UVPT)] = PADDR(e->env_pgdir) | PTE_V的含义。
答:
PDX(UVPT)是得出UVPT所处的页目录号,即UVPT处于第PDX(UVPT)个页目录项所映射的4MB空间,因此页目录也被第PDX(UVPT)映射,然后将该页目录号所对应的的页目录项映射为页目录的物理基地址,并且加上权限位。
页目录基地址:
UVPT+UVPT>>10
映射到页目录的页目录项的基地址:
UVPT+UVPT>>10+UVPT>>20
该页表项处于第几个页目录项:
(UVPT>>20) >> 2 = UVPT>>22 = PDX(UVPT)
Thinking 3.2elf_load_seg以函数指针的形式,接受外部自定义的回调函数map_page。 请你找到与之相关的 data 这一参数在此处的来源,并思考它的作用。没有这个参数可不可以?为什么?
答:
data是传 ...
oo-Unit2
前言又是三周的oo,终于结束了电梯的单元。
第二单元的编程难度和debug难度对我个人而言都远高于第一单元,真的是好费劲,不过不管咋样,也还算是顺利结束了这一单元的学习吧。
下面,我将分别对这三次作业进行分析。
第一次作业题目描述 我们要模拟的电梯系统是一个类似北京航空航天大学新主楼的电梯系统,楼座内有多部电梯,电梯可以在楼座内1-11层之间运行。系统从标准输入中读入乘客请求信息(起点层,终点楼层),请求调度器会根据此时电梯运行情况(电梯所在楼层,运行方向等)将乘客请求合理分配给某部电梯,然后被分配请求的电梯会经过上下行,开关门,乘客进入/离开电梯等动作将乘客从起点层运送到终点层。
基本思路第一次作业还算比较容易,只需要根据生产者-消费者模型,构建输入池,请求池,调度线程以及电梯线程,并编写策略类实现电梯运行策略即可。
具体实现
在整体构建上,我是参考上机实验中的代码框架,进行对应的修改。
在策略选择上,我根据往年学长经验选择了LOOK策略,在性能上强于ALS算法。
在调度上,由于第一次有具体电梯的编号,所以只需根据这些编号将总请求池的请求分到对应六个电梯的分请求池中 ...
OS-lab2
一、思考题Thinking 2.1请根据上述说明,回答问题:
在编写的 C 程序中,指针变量中存储的地址被视为虚拟地址,还是物理地址?
MIPS 汇编程序中 lw 和 sw 指令使用的地址被视为虚拟地址,还是物理地址?
答:
虚拟地址。自身所写的程序的指针储存地址为映射到进程地址空间的偏移地址,不同进程地址空间是相互隔离的,不同进程两个值相同的指针对应的真实内存是不同的
虚拟地址。其地址为32位而物理地址为64位
Thinking 2.2请思考下述两个问题:
从可重用性的角度,阐述用宏来实现链表的好处。
查看实验环境中的 /usr/include/sys/queue.h,了解其中单向链表与循环链表的实现,比较它们与本实验中使用的双向链表,分析三者在插入与删除操作上的性能差异。
答:
简化代码量
复杂宏大量调用简单宏可重用性强,可读性强,易于维护
单向链表
对于单纯的插入和删除操作只有O(1)的时间复杂度,但是对于任意第 i 个元素的插入和删除操作来说,则需要从头遍历一遍故而时间复杂度会上升到O(n);
双向链表
对于任意第 i 个元素的插入和删除操作时间复杂度 ...
OS-lab1
思考题Thinking 1.1请阅读 附录中的编译链接详解,尝试分别使用实验环境中的原生 x86 工具链(gcc、ld、readelf、objdump 等)和 MIPS 交叉编译工具链(带有mips-linux-gnu前缀),重复其中的编译和解析过程,观察相应的结果,并解释其中向 objdump 传入的参数的含义。
答:
通过阅读附录A.3,我们可以看到一个简单的printf("Hello World!")是怎么一步步预处理,编译,链接并最终变成可执行文件的。因为我们想找到printf到底是在哪里被插入到程序中的,所以我们每次只用gcc执行一次操作,同时使用objump进行反汇编。通过找到汇编语言中callq位置并观察其调用函数的地址来判断该阶段printf是否插入程序中。
为了使机器码转换回汇编代码,我们使用objdump -参数 要反汇编的目标文件名 > 导出文本文件名命令进行反汇编,那我们先来介绍一下objump相关参数的含义:
-S :用于在反汇编的输出中插入源代码。
-D :用于在每条指令前面添加对应的机器码。通常 -D 参数会结合 -S 参数一 ...
OO第一单元总结
前言在三周的磕磕绊绊中,也算是顺利完成了oo第一单元的三次作业。面对久仰大名的oo,虽说的确很累,但也收获良多。
第一次作业题目描述读入一个包含加、减、乘、乘方以及括号(其中括号的深度至多为 1 层)的单变量表达式,输出恒等变形展开所有括号后的表达式。
需求如下:
处理括号
处理指数
计算加,减,乘
化简合并得到结果
基本思路对于输入的一个表达式,我主要分为两步进行处理:
第一步:解析表达式,得到后缀表达式
第二步:计算后缀表达式,得到结果
具体实现
首先我对输入的表达式进行了一波预处理,主要就干了两件事:去空格,连续的加减号变成一个符号
然后,开始解析表达式,我在课程组在training中提供的递归下降算法的代码基础上,根据题目要求做了稍微修改,得到后缀表达式(不得不说,课程组给的代码真是救大命)
这里要提一句,由于第一次作业经验不足,我将指数在解析表达式阶段处理,也就是解析时读到一个^,就将前面的式子乘对应指数遍,比如我读到(x+1)^3,我就会处理成(x+1)*(x+1)*(x+1),一个^还好,一旦指数嵌套,由于我存的时候没有化简合并,就会有爆时间和爆内存的风险,也是导致 ...
OS-lab0
一、思考题Thinking 0.1 :Git的状态转换思考下列有关 Git 的问题:
在前述已初始化的 ~/learnGit 目录下,创建一个名为 README.txt 的文件。执 行命令 git status > Untracked.txt(其中的 > 为输出重定向,我们将在 0.6.3 中 详细介绍)。
在 README.txt 文件中添加任意文件内容,然后使用 add 命令,再执行命令 git status > Stage.txt。
提交 README.txt,并在提交说明里写入自己的学号。
执行命令 cat Untracked.txt 和 cat Stage.txt,对比两次运行的结果,体会 README.txt 两次所处位置的不同。
修改 README.txt 文件,再执行命令 git status > Modified.txt。
执行命令 cat Modified.txt,观察其结果和第一次执行 add 命令之前的 status 是 否一样,并思考原因。
答:
本思考题主要探讨的问题为Git中的四种状态转换关系,如下图
第一次查看状态时重 ...
OS预习
Linux基础目录操作
cd
用法:cd 目录
作用:切换到该目录(类似于打开文件夹)
cd /:/ 代表根目录,即Linux文件系统的最顶层cd ~:~当前用户主目录,对于一般用户,主目录是/home/用户名;如果当前用户是系统管理员(root)用户,主目录是/rootcd /etc/test:切换到etc目录下的test目录(可以理解为打开test文件夹)
cd test:cd命令支持相对路径,如果系统在etc目录,可以输入cd test直接访问test目录
cd .:.表示当前目录cd ..:..表示上一级目录cd -:-表示上一次访问的目录
ls
用法:ls [选项] [目录] ([]代表可有可无)
作用:列出目录中的文件
常用选项:
-a:显示隐藏的文件(文件名以 . 开头的文件)
-l:每行只列出一个文件
mkdir
用法:mkdir 目录
作用:创建一个新目录
pwd
用法:pwd [选项]
作用:输出当前目录的绝对路径
rmdir
用法:rmdir [选项] 目录
作用:删除一个空的目录。注意:只能是空目录
文件操作文件操作的对象是几乎所有 ...
单片机——蓝桥杯备赛
蓝桥杯比赛指定单片机跟51单片机差不多,可以通过淘宝国信长天购买。
本次学习跟着b站小蜜蜂老师的视频
使用的相关软件为 keil4 和 STC-ISP
相关软件使用keil4作用是编写代码和编译
STC-ISP的作用是将keil4得到的16进制码下载到我们的板子上
keil4使用
选一个位置存代码,新建文件夹
打开keil4,顶栏选择Project,再选择第一个New Project,找到刚才建的文件夹,自己写一个项目名,然后在Atmel中找到AT89C52
新建c文件,保存在刚才建的项目文件夹中
在左侧项目栏中右键项目文件夹,找到add什么那个,然后把建的c文件加进去
改成16进制输出
写代码,编译
STC-ISP使用
点打开程序文件,打开要下载到板子上的.hex文件
点下载/编程
按板子上的下载按钮完成下载
下面我们实现各个元件的控制
各个基本元件控制LED指示灯的控制在蓝桥杯指定单片机上已经有了诸多外设,传感器等等,板子的内部电路固定。所以需要通过特定的电路来对电路原件做相应的控制,而不像大一的电子设计课一样需要自己连线,可以自己定每条线插在哪个口。
电路部分板子 ...