EinNiemand's Blog

高级搜索树 伸展树 局部性：刚被访问过的数据，极有可能很快地再次被访问 BST 的局部性 时间：刚被访问过的节点，极有可能很快地再次被访问 空间：下一将要访问的节点，极有可能就在刚被访问过节点的附近 对于 AVL 的连续 m≫nm \gg nm≫n 次查找，共需 O(mlog⁡n)O(m\log n)O(mlogn) 利用局部性加速：BST 的节点一旦被访问，随即调整到树根 单层伸展 节点 v 一旦被访问，随即被推送至根 自下而上，逐层旋转 旋转次数呈周期性的算术级数（周期访问所有节点） 每一周期结构会复原，累计 Ω(n2)\Omega(n^2)Ω(n2) ，分摊 Ω(n)\Omega(n)Ω(n) 双层伸展 反复考察祖孙三代 g = parent(p), p = parent(v), v 根据他们的相对位置，经 两次旋转，使 v 上升两层，成为子树根 zig-zag 操作本身就是平衡的，效果很好 对于 zig-zig，先 p 后 g 只会拉长和移动访问路径，无法改善树的整体结构；而先 g 后 p 则能够“折叠”和“打散”访问路径 zig...

Shell挑战性任务 任务要求 本次挑战性任务是在 lab6 实现的 MOS Shell 基础上继续实现新的功能。 实现功能 具体内容参考任务说明。（各测试点间无依赖关系） 关于shell 在 MOS 中，进程是一个很重要的概念，我们需要清楚 MOS 在运行的过程中存在哪些进程、这些进程之间的关系是什么，这有助于我们完成 shell 的相关任务。 比如，当我们启动 shell 时，它的 main 函数构成了一个新的进程。这个主进程主要负责完成命令的读取（readline）等工作（这个进程从 mosh 被打开到结束也都是不会被 free 的），不断有新的进程被 fork 出来通过调用runcmd去执行命令。在runcmd中，则首先调用parsecmd解析命令的参数。 parsecmd通过返回argc表明完成对命令和参数的解析，或者递归调用parsecmd进行更复杂的解析工作。在这个过程中，主要通过gettoken和_gettoken对字符串命令进行拆解。 解析完成后，又会调用spawn函数加载对应的可执行文件、fork 新的进程并设置跳转入口，以执行对应的命令。spawn会返回这个...

lab6实验报告 思考题 Thinking 6.1 示例代码中，父进程操作管道的写端，子进程操作管道的读端。如果现在想让父进程作为“读者”，代码应当如何修改？ 12345678910111213141516171819202122232425262728293031#include <stdio.h>#include <unistd.h>int fildes[2];// fildes[0]读端 fildes[1]写端char buf[100];int status;int main() { status = pipe(fildes); if (status == -1) { printf("error in pipe!\n"); } switch(fork()) { case -1: break; case 0: /* 子进程 - 作为管道的写者 */ close(fi...

lab5实验报告 思考题 Thinking 5.1 如果通过 kseg0 读写设备，那么对于设备的写入会缓存到 Cache 中。这是一种错误的行为，在实际编写代码的时候这么做会引发不可预知的问题。请思考：这么做这会引发什么问题？对于不同种类的设备（如我们提到的串口设备和 IDE 磁盘）的操作会有差异吗？可以从缓存的性质和缓存更新的策略来考虑。 当程序需要读取设备的数据时，若数据已经被写入了Cache，则会从Cache中直接读取，而此时若外部设备的数据发生变化，则会产生错误的行为。 Thinking 5.2 查找代码中的相关定义，试回答一个磁盘块中最多能存储多少个文件控制块？一个目录下最多能有多少个文件？我们的文件系统支持的单个文件最大为多大？ 1234567891011121314151617181920212223// Bytes per file system block - same as page size#define BLOCK_SIZE PAGE_SIZE//...#define FILE_STRUCT_SIZE 256struct File { ...

lab4实验报告 思考题 Thinking 4.1 思考并回答下面的问题： 内核在保存现场的时候是如何避免破坏通用寄存器的？ 系统陷入内核调用后可以直接从当时的 $a0-$a3 参数寄存器中得到用户调用 msyscall 留下的信息吗？ 我们是怎么做到让 sys 开头的函数“认为”我们提供了和用户调用 msyscall 时同样的参数的？ 内核处理系统调用的过程对 Trapframe 做了哪些更改？这种修改对应的用户态的变化是什么？ 通过include/stackframe.h中的SAVE_ALL宏，用$k0,$k1寄存器将其他通用寄存器保存到内核栈上。 可以，不过在陷入内核态时已经将$a0-$a3寄存器中的值保存到了内核栈中，一般来说直接从内核栈中获取这些参数的值。 根据MIPS\mathcal{MIPS}MIPS调用规范，调用msyscall时，syscall_*已经将调用参数存入了$a0-$a3寄存器和用户栈中；进一步，陷入内核调用后，将用户进程上下文环境保存进内核栈中。因此，函数sys_*可以使用到所需要的参数。 12345678void do_sy...

正向建模与开发 正向建模与开发是指从需求分析开始，通过逐步细化需求，创建模型，并最终开发出软件的过程。这种方法强调从抽象到具体、从概念到实现的系统性过程。 而本单元正式所使用 UML（Unified Modeling Language）建模语言则是贯彻上述理念的一个很好的工具。在之前几个单元的设计中，我们虽然已经开始对 UML 有一些接触，但只是局限于用它来对每单元最后的迭代结果进行总结分析。既然有没有 UML 我们都或好或坏地完成了架构设计任务，那为什么还要花时间来接触这样一门建模语言呢？ 面向对象本质上定义了一个抽象语言系统 词汇：对象、属性、操作、活动、流程、状态…… 语法：对象间连接、对象与数据间连接、对象与操作间连接、属性与操作间连接、属性与活动间连接、操作与状态间连接…… 我们作为面向对象的初学者，通过 oopre + oo 算是品尝了一番迭代开发的滋味，也许不必在意用这样的语言组成的话语会向别人传达什么信息，只要自己代码写得痛快并且能够理解就行。但也许未来我们可能会面对越来越复杂、迭代不止的软件开发任务，或者与他人进行合作开发；这个时候若还是看了眼需求埋头就写、...

前言——唉，JML 本单元的主题为基于规格的层次化设计，相较于前两个单元的问题抽象与分解、并发程序设计，这单元的难度算是降低了不少吧——所有的方法与接口都由JML\mathcal{JML}JML规格给出，只需要根据约定、将功能一一实现即可（暂不考虑程序性能的前提下）。 在我看来，其实不用太纠结于JML\mathcal{JML}JML这里有什么毛病，那里有什么毛病，虽然有时看起来确实很滑稽（比如由于其形式化的描述，费了老半天劲写出来的东西自然语言一句话就讲明白了），最主要的一点还是去感受契约式设计的魅力（见仁见智把）。 规格设计者（架构师）基于规格和需要实现的业务，定义一个类所需管理的数据及其需要满足的约束和实现不同作用的方法；而程序员则遵循对每个对象和方法的要求，只需聚焦于具体方法的实现。当然在保证没有二义性的前提下，JML\mathcal{JML}JML大篇大篇的数理逻辑表述确实又臭又长（所以这学期助教们对用于教学的JML的简化工作确实挺好的）。不过JML\mathcal{JML}JML这样的形式化的表述，在另一方面确实有利于对代码进行各种验证和测试： pre-conditio...

同步块与锁 在本单元的设计中，考虑到对性能的影响不大（请求数量级为10210^2102），以及为了更简单地保证共享资源时的线程安全，绝大部分情况下我是用synchronized给方法加锁（即锁住对应实例）。 其余部分为了实现其他的互斥操作或者线程同步操作，如将进行重置操作后的乘客“遣返”回主请求队列、进行影子电梯模拟、双轿厢离开交换楼层时通知另一个轿厢，则会使用synchronized (...) {}进行上锁。 需要注意的是，后者加锁方式必须仔细考虑获取锁的时候是否会造成死锁问题，也可以使用ReentrantLock的tryLock()方法避免这一问题，此处先按下不表。 总之，在进行多线程同步设计时，需要对线程间的协作和资源的共享情况有一个清醒的认知。 架构设计迭代 hw5 基本思路 主要采用了生产者-消费者设计模式，一方面输入线程InputThread不断“生产”请求，另一方面将这些请求经由调度器Dispatcher分发给一个合适的电梯线程Elevator去处理。 由于这次作业指定了每个乘客乘坐的电梯，故最开始没有单独设计Dispatcher，直接分给对应的电梯就好了。 12...

前言 随着第三次作业的强测结果公布，这一单元的学习也接近了尾声。从开始的迷茫和手足无措，到最后可以拿出一份层次清晰、结构完整代码，我开始对作业所要求的层次化设计思想有了一定感觉，也体会到编写代码时各个类之间做到有效协同、职责分派之后带来的高效和美观。这些也离不开许多同学在讨论区的想法分享和往年学长学姐的经验总结。下面我将以我的学习总结和心得体会为第一单元的学习画上一个句号。 程序架构分析 得益于课程组大力提倡的递归下降法和实验课提供的demo，以及同学在讨论区的各式各样的想法分享，我能够在开始时就采用一个比较优秀的架构，所以本单元迭代过程中基本没有大的重构。因此关于代码架构的分析就以hw3的代码为主了。 整体架构 首先根据题目的形式化表述，可以很自然地建出Expr -> Term -> Factor这样一个结构，而其中Factor又可以根据不同情况建立不同子类。将读入经过预处理之后，在使用递归下降的方法就可以清晰地将表达式解析开来。 接下来对于表达式的展开主要借鉴了zyt同学的思路，从由若干基本单元组成的多项式的输出结果出发，考虑将从原始表达式解析出来的东西化归为统...

MIPS汇编 一些常用宏 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960# 程序结束.macro end li $v0, 10 syscall.end_macro#--------------------------# 输入Integer.macro readInt(%d) li $v0, 5 syscall move %d, $v0.end_macro#--------------------------# 输出Interger.macro printInt(%d) li $v0, 1 move $a0, %d syscall.end_macro#--------------------------# 输出字符串（包括换行和空格）# 值得一提的是，最好只使用".asciiz&...