第一个程序

• virtualbox创建虚拟机，虚拟一块.vhd硬盘，写一个asm程序，nasm -f bin 4-2.asm -o 4-2.bin，nasm将asm程序编译为bin二进制文件，可以通过hexView工具查看实际文件。有了vhd虚拟硬盘和bin文件，通过fixvhdwr工具将bin文件写入vhd硬盘的第一个扇区中，此时，启动虚拟机，出现asm字样.代码如下.

  1 2 3 4 5 6 7

  mov ax,0xb800 mov ds,ax mov byte [0x00],'a' mov byte [0x02],'s' mov byte [0x04],'m' times 510 - ($-$$) db 0 dw 0xaa55 ;引导扇区的结束符

8-1源码框架

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

app_start equ 100   ;声明常数，将要从app_start扇区读取用户程序
SECTION mbr align=16 vstart=0x7c00  ; 定义mbr段，16字节对齐，段起始位置0x7c00(绝对物理地址)

; 设置堆栈段
xxx

; 计算用于加载用户程序的逻辑段地址，计算结果为0x10000右移4位,将ds和es寄存器指向0x1000
xxx

; 读取程序的起始部分,di:si一共28位提供硬盘的0x1f3~0x1f6端口将要读取的起始扇区号,同时调用read_hard_disk_0函数。并将读取到的数据加载到ds:0x0000，其中ds已经通过计算得到结果为0x1000.
xxx

; 判断整个程序有多大。在用户程序的前四个字节中定义了程序的总长度，程序总长度是通过段尾字符获得的，获取了总的字节数之后，除以512字节，就可以得到程序占用了几个扇区，ax:dx为总长度，最终dx中存放的是除法之后的余数，ax中存放的是一共占用多少扇区，如果余数为0，说明刚好除尽，用ax-1即可得到结果。如果余数不为零，则进入@l函数，首先判断是否程序刚好只占用一个扇区(ax==0)，如果不是，读取剩余扇区，将cx中的值置为总的扇区数，进入@2函数循环，每次读取一个扇区.

;realloc段，回填段基址,重复调用cac_segment_base,调用完realloc段之后，`jmp far [0x04]`跳转到[0x1000:0x04]内存地址所写的地址，也就是user.asm的start标号

phy_base dd 0x10000  ;用户段被加载的物理起始地址 双字10000

; 填充0字
xxx

dd 0x55aa

8-2源码框架

1
2
3
4

;段重定位表 已经在mbr引导程序中将段表更新了，之后只需要直接调用段表名就可以得到每一个段的实际物理地址

start段
; 重新设置ss，sp，ds设置为用户自己的数据段，ds一定要保留到最后来设置，因为在设置ss，sp时需要用到正确的ds=0x1000.

检测点

• 9.2中 info ivt;显示所有的中断程序的段基址和偏移地址，info ivt [第几个中断向量],查看具体的中断程序的信息。也可以根据xp命令来计算某一个中断程序的入口地址，例如要查看0x70号中断的入口地址，其在中断向量表中的位置是0x1c0，xp/10 0x1c0可以查看70号中断的入口地址。查看之后，不用管低端和高端，直接读取。另一个不用管低端和高端的是u反汇编命令。

  报错信息

• 将8-1，8-2同时写入vhd硬盘时，用bochsdebug调试会出现ata0-0: could not open hard drive image file ‘.vhd’，删除vhd.lock文件即可运行.

15章源码框架

mbr

1
2
3
4
5
6

; 计算gdt所在的段地址
; 分别定义四个段，将其写入gdt表
; 更改cr0的一号位，进入保护模式
; 加载core代码 通过read_hard_disk将其从磁盘写入内存
; 为core代码建立段描述符，尽管core代码在开头已经用不占内存空间的常量定义了，这里是防止以后在除了core代码以外的地方调用core代码。
; 定义构造段描述符的函数make_gdt_descriptor

core

1
2
3
4
5
6

; sys_routine例程段中包含着put_string字符串显示例程。
; allocate_memory函数定义了从一开始分配内存的起始地址，之后，随着用户程序分配内存，该起始地址一直在变化。
; make_gdt_segment函数构造段描述符，但是不实际写入gdt表，在setup_gdt_segment中实际写入gdt表
; load_relocate_program函数中定义了加载用户程序，同时为用户程序构造段描述符
; 所有的函数定义完之后，是首先进入内核程序就开始执行的start标号，最后一行jmp far [0x08]将控制权移交给用户程序，当用户程序执行完毕之后，return一开始执行，回到jmp far指令的下一个标号return_point处
; 实际上，上一点想要解释C语言中调用printf，return等命令之后发生了什么。简单来说，printf和return等命令已经被定义在了core代码中的salt表中，供用户例程调用，256字节用来描述符号名，4字节用来指定偏移量，2字节用来指定段选择子.

P263底部

• 为什么只删除break语句不能求出完整解？

  画出解答树之后，可以看出递归完之后是从最后一层节点继续递归，而不是从头递归，所以需要定义一个数组存储路径。

  P264顶部

• 为什么dp[i]定义为以节点i为终点的最长路径长度，可以求最大dp，却难以求出最优路径？

  因为是从终点递归(也就是矩形最大的开)，不好确定第一位是否是最小值，只有求出了完整的路径之后才能确定最优路径

  P267 Uva1025

• dp的两种定义方式:当dp[i][j]定义为到达状态为时刻i，站台j时，所需要的最少时间。如果某个dp[i][j]=0，可能是搭乘的从0点出发的列车。

  P283 Uva1218

• 将dp[i][2]初始化为INF,也就意味着用INF代表该状态非法。其次，利用代换，将求dp[u][2]的时间复杂度降低为O(n):例如，当计算child节点时,dp[cur][2]=MIN(dp[child0][0]+dp[child1][2]+dp[child2][2])，对于每个child节点都要枚举k次，计算k次，所以原本时间复杂度为O(n^2).但是，一代换,dp[cur][2]=MIN(dp[cur][1]-dp[child0][2]+dp[child0][0]).
• 其次，本题可以既可以递推也可以递归。如果利用递推，需要用栈将节点保存。

  Uva10003

• Uva10003题，刚开始想的是将状态定义为d[i][j]:先切i，最后切j。这样定义状态导致后续状态转移困难。其次，最开始认为切三刀的最优解依赖于切两刀的最优解，这样看也能转化为最优子结构问题，但是如果这样做就会产生书上所说的一个问题，没有顺序规范化。即便是像参考代码一样考虑到了顺序规范化，将dp[i][j]定义为切割点a[i]~a[j]的最优解，也会产生很多细节问题(边界处理).