build a computer week 12

终于完成了build a computer系列的最后几章了，最终所有的project全部都通过了。

真心感觉这个过程比较艰难，这个project是该系列课程里面最后的一个toy project了，主要部分为一个非常简单的OS系统的源代码的实现，其实代码实现并不难，因为大部分算法都可以在网上找到，但是细节处理非常容易出错，写代码很爽，也就3天的时间完成了大概也就将近1000行的代码，但是调试确实花了非常多的时间来完成，主要是因为部分细节确实实现比较坑爹，不太好弄，但是终于还是调通和实现了，感觉这种业务代码的实现也就是搬砖的活，还是写算法，刷题来的爽，因为算法的大部分问题思考的时间很多，写代码实际上非常容易实现，现在越来越喜欢类似的深度思考，需要花时间来解决的数学和技术难题，而不是拼命搬砖。所有的实现代码最终放在github上，p12-jackos.
终于完成全部的build a modern computer系列课程了，课程真的是太有趣了，我想做事有始有终，以前给自己定的flag是一定要完成这个课程，陆陆续续刷了大概有6个月的时间，才把整个系列的part1,part2课程完成了。本课程最有意思的是该课程讲出了计算机模型的本质，非常推荐国外这种化繁为简的教育理念和教育方法，通过现象可以看到本质，只需要实现最基本的OS的核心，非常低的门槛就可以将学生代入计算机的伟大世界中，了解计算的本质和基本原理，真心替两位教授点赞，看到资料介绍，本课程陆陆续续开发了近五年才最终完成了如此精品的课程。我想兴趣才是最好的老师，虽然学习这门课程花了很大的精力和很多的时间，但是学习完成之后，仍然会对本课程回味许多。

project

本章节的project主要是实现操作系统的部分核心内容，俗称造轮子。本次需要造的轮子如下：

Math:数学计算部分，包含最基本的乘法，除法，开方，乘方，取模运算等;
String: 字符串部分，主要包括字符类的基本功能，字符串转换，等等基本操作;
Array: 数组的管理，数组的管理，主要包括数组构造和删除；
Output: 字符或者数字的输出模块；
Screen: 最基本的图形显示部分，包含最基本的图形显示部分，比如像素、直线、圆、矩形的显示；
Keyboard:键盘的输入读取控制。
Memory: 基本的内存管理部分。
Sys：系统管理，包括系统的初始化和完成。

Math

整个math部分完成了乘法、除法、开方、乘方、取模、取绝对值运算，其中最难的还是乘法和除法以及开方的实现。

multiply:乘法利用了二进位的特定来进行实现，实现其实比较简单，算法时间复杂度为$O(lgn)$，每次测试二进制位i是否为1，如果为1，则减去相应的值即可，利用位运算非常容易实现。
divide: 除法部分稍微复杂点，我们提前减去利用算法的特性实现即可，时间复杂度为$O(lgn)$.
sqrt: 开方的实现方法有很多种，这个实现思路就很多了，最简单的利用二分查找实现即可，还可以利用牛顿法，或者逼近法，课程中给出的解法则利用左右边界的逼近法。
$$
y^{2} \le x \le (y+1)^{2}
$$

Memory

本节实现了非常简单的内存管理模块，堆的管理实现比较简单，也没有太大的难度，常见的两种办法为first fit和best fit,关于具体的内存管理的实现算法有许多成熟的论文或者开源的代码可以参考，不过基本上也没有什么太大的难度。在本章中是实现了简单的first fit算法，简单的链表实现即可，对于老鸟来说非常简单的实现，当然对于快速的缓存来说一般都是采用将内存划分为固定字节的块，避免繁琐的查找。

Screen

该小节实现了基本的图形显示界面的实现，比如实现了最基本的矩形，圆形，点，直线的代码实现。

pixel:对于点的实现比较简单，由于内存的字长为16位，我们直接采用16位掩码的方式，来快速的对显存部分实现读取和写入。
line：line的部分就实现稍微复杂点，如果我们直接利用求斜率的方法则需要用到除法和乘法，非常耗时。在此利用加法和减法来实现快速的判别实现直线的点的计算。当然实现的过程中我们需要将直线分为3中类型，
- 水平直线：即与x轴平行的直线，此时我们即可以快速的利用显存的16位带宽，一次性可以写入连续的16位，来加速写入显存的速率。
- 垂直直线: 此时的无法计算斜率，但是我们只需要连续填入即可，利用基本的几何知识即可实现。
- 普通直线: 我们则利用如下算法来实现相关代码，非常巧妙的加减法判断即可。
rectangle:此时我们则利用画水平线的方式，快速的实现即可。
circle:画圆的方式则比较容易实现，就是快速的画水平直线即可,当然如下的算法可以稍微改进一下，每次画两条直线，即可减少开方的计算，毕竟开方的计算非常耗时。

Output

输出部分主要为整个系统的字符输出和显示。整个系统中给所有的字符完成一种最基本的字符定义和类型，从中我们可以窥探到字符集的实现。本质为我们将每一种字符都进行位图编辑，每次输出字符时，我们显示该字符的实际的位图即可，这个起始非常容易实现。

printChar：打印字符的实现，所有的字符都采用11x8的位图来实现，因此非常的简单。我们每次输出字符时只需要定位到相应的起始位置，在显存中写入该字符的位图即可。
printInt:这个即将整形转换为字符串，然后再输出即可，比较麻烦的地方是处理负数的问题。

Keyboard

读取和控制键盘，对键盘的输入进行读取和显示，这部分的实现起始非常简单，从键盘的i/o地址出，读取写入的字符然后显示相应的字符即可。

keypressed：从键盘读取一个输入字符，判断读取的循环即可

String

string的处理则非常简单，因为只需要基本的函数即可，没啥太大难度，也没有多少难点需要阐述的。

Array

array部分就更简单了，申请size长度的数组即为从堆中申请相应长度的空间即可。

Sys

sys系统部分，主要重点需要注意的为系统初始化部分，题目中给的完全可能是错误的，首先第一个需要初始化的应该是memory部分，因为其他模块都可能需要用到memory部分的功能。具体的初始流程如下即可：

function void init() {
    do Memory.init();
    do Math.init();
    do Screen.init();
    do Output.init();
    do Keyboard.init();
    do Main.main();
    do Sys.halt();
    return;
}

总结

起始总的来说，这个project相比其他几个project都容易许多，但是许多需要注意的细节：

对于数学的部分：这部分需要非常快速的效率来实现，所以非常需要快的数学方法来化简直接的方法，从而提高效率，否则后续容易出现程序执行效率不高的问题。
对于图形部分的实现，如何继续改进则需要仔细的思考，特别是圆形的实现还需要非常多的优化。
其余的部分感觉基本上就是cround，没有特别多的理论需要思考和实现的。

project

本周的project感觉还是非常复杂的project，虽然很简单，但是要不出错还是需要非常注意细节的实现。
代码实现：poj12.

欢迎关注和打赏，感谢支持！

关注我的博客: http://mikemeng.org/
关注我的知乎：https://www.zhihu.com/people/da-hua-niu
关注我的微信公众号: 公务程序猿

Tags: 公开课学习

← 【CSAPP】 lab4 【build a computer】 project 11 →

扫描二维码，分享此文章

【build a computer】 project 12

build a computer week 12

project

Math

Memory

Screen

Output

Keyboard

String

Array

Sys

总结

project