Algorithm
// 暴力解法
func maxArea1(height []int) (result int) {
i := 0
result = 0
for i < len(height) {
k := i + 1
for k < len(height) {
current := (k - i) * min(height[i], height[k])
if current > result {
result = current
}
k++
}
i++
}
return
}
func min(a int, b int) (result int) {
if a < b {
return a
}
return b
}
// 官方双指针解法
func maxArea2(height []int) (result int) {
left := 0
right := len(height) - 1
result = 0
for left < right {
current := (right - left) * min(height[left], height[right])
if current > result {
result = current
}
if height[left] < height[right] {
left += 1
continue
}
if height[left] >= height[right] {
right -= 1
continue
}
}
return
}
Review
10 Common Software Architectural Patterns in a nutshell
文章介绍了一些常用的设计模式的优缺点和使用场景。
TIP
这周开发过程涉及到状态机相关需求，所以了解了fsm相关概念。并使用Go开源fsm库完成了业务需求。
Share
继续学习“操作系统32讲”
L23 段页结合的实际内存管理
虚拟内存
用户角度只能看到分段的虚拟内存，硬件角度虚拟地址映射的是物理内存的页号。操作系统负责虚拟地址到物理地址的转换（ 重定位也就是地址翻译）。
- 首先根据段号+偏移（CS：IP）去段表）找到对应的虚拟地址。CS对应段号，IP对应偏移量。比如CS：IP为1：30，段号找到基址为0x4800，再加上偏移量得到虚拟地址。
段号 基址 长度 保护
0 0x4000 0x0800 R
1 0x4800 0x1400 R/W
2 0xF000 0x1000 R/W
3 0x0000 0x3000 R
- 根据步骤1得到的虚拟地址，然后去页表里面查询得到物理地址。步骤1、2实际都是由MMU自动完成。
操作系统在fork一个进程过程如何实现内存分配和虚实地址映射
- 从虚拟内存中分配一段内存段给新的进程，然后分配对应段表。这里讲的是比较简单的内存分割算法（根据进程ID递增分配内存块）
// 这个函数讲的就是fork进程的时候，把父进程的内存信息copy一份到子进程
int copy_mem(int nr,task_struct *p){ // p就是被fork的进程的pcb
unsigned long new_data_base;
new_data_base = nr * 0x4000000; // 64M*nr nr代表第几个进程，32位操作系统每个进程的内存空间是64M nr*64就是偏移量
set_base(p->ldt[1],new_data_base); // 设置基地址，这里可能是数据段。并且建立段表
set_base(p->ldt[2],new_data_base); // 设置基地址，这里可能是代码段。并且建立段表
}
- 分配物理内存，建立页表。这里因为和父进程共用内存，所以不需要分配新的物理内存，直接建立页表就可以。
32位操作系统的多级页表：
10bits 10bits 12bits
页目录号 页号 offset（页内偏移）
分配物理内存
int copy_mem(int nr,task_struct *p){
unsigned long old_data_base;
old_data_base = get_base(current->ldt[2]);
copy_page_tables(old_data_base, new_data_base, data_limit);
}
// 建立子进程的页表
int copy_page_tables(unsigned long from, unsigned long to, long size){
from_dir = (unsigned long *)((from >> 20) & 0xffc); // 页内偏移为12bits 页号为10bits，先右移22位得到页目录号 每个页目录号对应的页号为4字节 所以需要向左偏移2位 最终就是向右偏移20位
to_dir = (unsigned long *)((to >> 20) & 0xffc);
size = (unsigned long *)(size + 0x3ffffff) >> 22; // 有多个页目录章节
for(; size-->0;from_dir++, to_dir++){ // 建立新的页目录章节的具体页号内容映射
from_page_table = (0xffffff000 & *from_dir);
to_page_table = get_free_page(); // 去物理内存中申请新的内存分配给新的页号
*to_dir = ((unsigned long) to_page_table) | 7;
}
for(;nr-->0;from_page_table++,to_page_table++){ // 拷贝父进程的页号内容到子进程
this_page = *from_page_table; // from_page_table是父进程的内存指针，*from_page_table就是指针指向的内容
this_page &= ~2; // 父子进程共用内存，所以需要设置为只读
*to_page_table = this_page; // 父进程内容给子进程
*from_page_table = this_page; // 内存块修改成只读，所以需要给父进程也重新赋值一下
this_page -= LOW_MEM;
this_page >>= 12;
mem_map[this_page]++;
}
}
L24 内存换入-请求调页
为什么需要内存换入
32位操作系统在用户角度来看，4G的虚拟内存都是可以随意使用的。但是实际的物理内存可能就只有1G或者3G，为了较小的物理内存能够支撑4G的虚拟内存，就引入了内存换入。
用户程序、数据在没有使用的时候存储在磁盘上，在需要用到的时候将需要的数据写入到内存上，这就是内存换入。
如何实现内存换入
- CS：IP查找段表之后，得到虚拟地址。
- MMU拿虚拟地址去查找页表的时候，如果页表上找不到对应的页框号这时候会触发一个缺页中断（page fault）。
- 中断处理程序处理缺页中断的时候，先去磁盘找到对应数据，然后会去内存中get_free_page找到一个空白的内存段并将磁盘中的数据写入到free_page中。
- 中断处理完成之后，继续完成剩下程序逻辑。整个内存换入完成。
L25 内存换出
内存换出常用算法
- FIFO：先入先出算法 会产生较多的缺页次数
- MIN算法：选最远将使用的页淘汰。这个是最优算法，但是无法预测未来哪些页会被访问。
- LRU（least recent used）：最近最长一段时间没有使用的页进行淘汰。最近不常用的页表，一般来说未来也不会被经常使用所以可以优先进行淘汰。这个也符合计算机的局部性现象。
LFU算法的实现
- 使用页码栈来实现，最准确。但是每次地址访问都需要修改栈，实现代价太大。
- 将页组织成循环队列，给每个页加一个引用位（reference bit）。时间轮（clock）算法
- 每次访问一页时，硬件MMU自动设置引用位为1
- 选择淘汰页：触发缺页中断的时候遍历循环队列并扫描引用位，如果引用位是1的时候清0并继续扫描；如果引用位是0的话，就选择该页进行淘汰。 SCR算法（second chance replacement）。
- clock算法的改进
- 缺页中断触发几率很小，同时MMU每次访问页表的时候都会自动把引用位置为1。这样就会导致很大概率下缺页中断处理过程，时间轮上的所有引用位都为1，这时候就会导致每次淘汰的都是最先来的页。最终退化成FIFO。
- 解决方案：引入一个扫描指针。扫描指针不断地定时轮训循环队列并把引用位置为0。扫描指针移动速度比淘汰指针快，这样子实现定时清除引用位。从而防止clock算法退化成FIFO。
