计算的要素第十二章总结

本章是针对Hack OS各个模块的概述及其实现，其中某几个模块实现的算法很有意思，让我们马上开始吧~

1 什么是OS（以Hack OS为例）

以一种对软件友好的方式封装了不同的硬件服务
用不同的函数和抽象数据类型扩展了高级语言。在这个意义上的操作系统与语言的标准程序库的分界线就不那么明显。事实上，某些现代语言（例如Java）就趋向于将很多经典的操作系统服务（比如GUI管理，内存管理，和多任务处理等）连同很多语言拓展一起打包到其标准程序库中，这么做的目的以我的理解是为了屏蔽系统层面的差异（比如C的fopen等）以及减少系统调用（比如Java的内存管理，向内存申请一大片空间，Java NIO等）

2 为什么我们需要OS

计算机是用来解决实际问题的，所以我们构建计算机硬件用来计算，基于硬件我们造了编译器用来写更可读的汇编程序，然后有了用汇编程序写的应用，随着应用程序越来越到，我们需要抽象出能够将控制（硬件和外围设备以及软件）和分配资源的常用功能集一体的概念，它就是Operating System，感兴趣的同学可以看看操作系统的演化。（有时间去研究研究发出来）
计算机系统的基本目标是执行用户程序并以更容易的方式解决用户的问题。

3 数学操作

首先，这里明确的告诉了我下意识想到的通过累加和累减来实现乘除法来操作系统层面是不可行的，原因很简单，效率太低了高达O（n）的输入敏感复杂度会让计算一个100000000000000*10000000000000的人在凳子上坐上几天（只是举个例子，数据不具备代表性），那么就让我们来看一看Hack OS的做法

注：以下所有运算都假定操作数为16位（Hacl硬件规范字长16位）

3.1 乘法

function multiply(x, y) {
    let sum = 0,index = 15;

    while(index > 0) {
        if (y.toString(2).padStart(16,"0").charAt(index) !== "0") {
        	console.log(y, index,y.toString(2).padStart(16,"0"));
             sum = sum + x;
        }
        x = x + x;
       index = index - 1;
    }

    return sum;
}

可以看到实际上乘法就是在模拟我们日常生活中的乘法，通过逐位相乘，并且再每一次乘完以后将被乘数左移一位，迭代这个过程直到遍历完所有位数，在日常生活中我们看到某个算术53*20，当我们处理完5这一位不会再用0去乘20，但是在计算机中你需要一套规则去运算，这套规则在这里就是遍历完操作数的所有位，即便它全是0。

3.2 除法

function divide(x, y) {
    let q,result,flag;

    flag = !((x < 0) ^ (y < 0));

    x = Math.abs(x);
    y = Math.abs(y);
    if(y > x) {
        return 0;
    }
    q = divide(x,y + y);

    if (x - (2 * q * y) < y) {
        result = q + q;
    } else {
        result = q + q + 1;
    }

    return flag ? result : -result;
}

思路也是模仿人除法的过程，选择一个尽可能从x上减去y的最大倍数（假定算式x/y），直到y比x大，这个过程的递归形式如上。

3.3 平方根

function sqrt(x) {
    let y,j,temp,tempQ;

    y = 0;
    j = 7;

    while(j >= 0){
      temp = y + Math.pow(2,j);
      tempQ = temp * temp;
      //avoid overflow
      if((tempQ <= x) & (tempQ > 0)){
        y = temp;
      }
      j = j - 1;
    }
    
    return y;
}

这个算法就是根据y²<= x <(y+1)²，使得y从0开始逐步逼近x使得y满足上述区间

4 内存管理

内存管理很有趣，首先说一说内存管理的背景

4.1 背景

计算机的程序会声明并使用各种类型的变量，包括整数、布尔数等简单的数据类型以及如数组、对象等复杂的数据类型。高级语言的最大优点之一是程序员不必关心内存管理细节：比如为变量分配内存空间；以及当该变量不再使用时，回收为其分配的内存空间。所有关于内存管理的琐碎工作都由编译器、操作系统和虚拟机在后端完成。
不同的变量的内存在程序生命周期中的不同时刻被分配。例如，静态变量在编译期间由编译器为其分配内存，而局部变量则在每个子程序开始运行时被分配在堆栈内。其他变量的内存则是在程序的执行过程中被动态分配，这时候OS就要上了。注意操作系统本身并不自带垃圾回收功能，这是高级语言提供的内存管理手段，比如Java，JVM先向OS请求一大块内存用于程序运行，然后在这块内存中可以“自动内存管理”，本质是在OS层面之上进行内存管理，这样就不用频繁的调用系统的malloc，free了

在OS看来内存其实就是一块大数组（big buffer），当然真实的内存实现我们已经在之前看到过了(多个Register->多个RAM->Memory)。