＜Introduction to algorithms＞笔记

Part4 高级设计和分析技术

part1-3中学习的普遍应用的算法思想和技术如下:

• 分治法 divide and conquer
• 随机化 randomize
• 递归求解 recursion

在面对一个计算问题时, 一般的直接解法是暴力破解,即穷举法.从一定意义上讲,所有的最优化问题都可以通过穷举法来解决,但是这在时间上是不可接受的.要更高效的求解问题, 需要学习对高效算法的设计分析技术
所有的高效算法都是为了加快速度:

1. 动态规划:保存子问题的解,以备重复使用
2. 贪心算法:用局部最优解来求全局最优解
3. 平摊分析是用来分析算法的工具,它本身并不是一种算法.

• 动态规划 dynamic programming

  • 动态规划通常应用于最优化问题,即要做出一组选择以达到一个最优解时.在做选择的同时,经常出现同样形式的子问题.关键技术是存储这些子问题每一个的解,以备它重复出现.

• 贪心算法 greedy algorithm

  • 贪心算法通常也是应用于最优化问题,该算法的思想是以局部最优的方式来做每一个选择.采用贪心算法可以比动态规划更快地得出一个最优解,但是关键是不容易判断贪心算法所得到的是否真的是最优解.

• 平摊分析 amortized analysis

  • 平摊分析是一种用来分析执行一系列类似操作的算法的工具.在一个操作序列中,不可能每一个都以其已知的最坏情况运行,某些操作的代价高些,而其它的低一些.平摊分析不分别计算每一次操作的代价确定一系列代价的界,而是对整个操作序列的真实代价限界.

hw4 lazy page allocation

目标

OS可以使用页表硬件的技巧之一是 堆内存的懒惰分配.当进程需要更多的内存的时候,调用malloc()函数申请更多的堆内存,底层系统调用sbrk实际完成这个工作.sbrk系统调用分配物理内存,并映射到进程的虚拟地址.但是有的进程会一次申请大量的内存,但是又可能根本用不到,比如稀疏数组(sparse array).所以说复杂的内核涉及会将实际的allocation的工作推迟到应用程序尝试使用该页面的时候,即发生了page fault,然后再进行实际的分配. -

Part1 删除’sbrk’的内存分配

任务

从sbrk(n)系统调用实现中删除页分配,实现为sysproc.c中的sys_sbrk()函数.sbrk(n)系统调用将进程的内存大小增加n个字节,然后返回新分配区域的开始地址.

hw3 xv6 system calls

目标

在[hw1 boot pc]的基础上,学习xv6的系统调用:

• 运用xv6的系统调用
• 修改xv6 kernel, 添加新系统调用

Part1: 系统调用追踪

任务

修改systemcall.c,在进行系统调用时,打印出系统调用的名字和返回值.实现后,在xv6启动时是打印如下内容:

1 2 3 4 5 6 7

... fork -> 2 exec -> 0 open -> 3 close -> 0 $write -> 1 write -> 1

Lab2 内存管理

摘要

• 内存管理有两个组件:

1. 第一个组件是内核的物理内存分配器，因此内核可以分配内存并稍后释放它。.分配器将以4096个字节为单位进行操作，称为页面。代码要实现维护记录哪些物理页面是空闲的，哪些被分配的数据结构以及共享每个分配的页面的进程数量,另外还将编写例程以分配和释放内存页面。
2. 第二个组件是虚拟内存，它将内核和用户软件使用的虚拟地址映射到物理内存中的地址。 当指令使用内存，咨询一组页表时，x86硬件的内存管理单元（MMU）执行映射。 lab2根据提供的规范修改JOS以设置MMU的页表。

• lab1分为三部分

1. part1: 物理页面管理 physical page management
2. part2: 虚拟内存 virtual memory
3. part3: 内核地址空间 kernel address space

＜Introduction to algorithms＞笔记

Part3: 数据结构

1. 动态集合:随着时间改变而变化
2. 关键字(keyword) -> 全序集(排序)
3. 基本操作

   • search(S, k)
   • insert(S, x)
   • delete(S, x)
   • maximum/minimum(S)
   • successor/predecessor(S, x)