第十二章操作系统

导读

在前面的章节中，我们构建了完整的计算机系统：从硬件到虚拟机，从编译器到高级语言。本章将完成这个软件栈的最后一块拼图——操作系统。

操作系统是计算机系统的核心软件，它管理硬件资源，为应用程序提供公共服务。在Nand2Tetris中，我们实现了一个简单的操作系统，为Jack程序提供运行时支持。

通过本章的学习，你将理解操作系统的基本功能，掌握内存管理、I/O处理等核心技术，并为Jack程序提供完整的运行时环境。

核心概念详解

12.1 操作系统概述

操作系统是管理计算机硬件和软件的系统软件。

操作系统的功能

进程管理：创建、调度和终止进程

内存管理：分配和回收内存

文件系统：管理文件和目录

设备管理：控制I/O设备

用户接口：提供命令行或图形界面

Jack操作系统的简化

Jack操作系统是一个极简的操作系统：

没有进程管理(单任务)
简单的内存管理
基本的I/O支持
面向Jack程序的运行时库

12.2 内存管理

内存管理是操作系统的核心功能之一。

内存布局

Hack计算机的内存布局：

0-15        : 预定义变量(SP, LCL, ARG, THIS, THAT)
16-255      : 符号表(编译器使用的变量)
256-2047    : 堆栈
2048-16383  : 堆(动态分配)
16384-24575 : 屏幕内存
24576       : 键盘内存

堆管理

堆用于动态内存分配：

jack

var Array arr;
let arr = Array.new(10);  // 从堆中分配内存

内存分配算法

Jack操作系统使用简单的首次适应算法：

jack

class Memory {
    field int heapStart, heapEnd;
    field int freeList;
    
    constructor Memory new() {
        let heapStart = 2048;
        let heapEnd = 16384;
        let freeList = heapStart;
        // 初始化空闲链表
        return this;
    }
    
    function Array alloc(int size) {
        // 在空闲链表中查找足够大的块
        // 如果找到，分割并返回
        // 否则返回null
    }
    
    function void deAlloc(Array obj) {
        // 将块返回到空闲链表
        // 合并相邻的空闲块
    }
}

内存分配实现

jack

function Array alloc(int size) {
    var int block, prev, next, blockSize;
    
    let block = freeList;
    let prev = 0;
    
    while (block != 0) {
        let blockSize = Memory.peek(block);
        
        if (blockSize >= size) {
            // 找到合适的块
            if (blockSize > size + 2) {
                // 分割块
                let next = block + size + 1;
                Memory.poke(next, blockSize - size - 1);
                Memory.poke(block, size);
                
                // 更新空闲链表
                if (prev != 0) {
                    Memory.poke(prev + 1, next);
                } else {
                    let freeList = next;
                }
                Memory.poke(next + 1, Memory.peek(block + 1));
            } else {
                // 使用整个块
                if (prev != 0) {
                    Memory.poke(prev + 1, Memory.peek(block + 1));
                } else {
                    let freeList = Memory.peek(block + 1);
                }
            }
            
            return block + 1;  // 返回数据区域
        }
        
        let prev = block;
        let block = Memory.peek(block + 1);
    }
    
    return null;  // 没有足够的内存
}

12.3 字符串处理

String类提供字符串操作功能。

String类结构

jack

class String {
    field int maxLength;
    field int length;
    field Array chars;
    
    constructor String new(int maxLen) {
        let maxLength = maxLen;
        let length = 0;
        let chars = Array.new(maxLen);
        return this;
    }
    
    method void dispose() {
        do chars.dispose();
        do Memory.deAlloc(this);
    }
    
    method int length() {
        return length;
    }
    
    method int charAt(int index) {
        return chars[index];
    }
    
    method void setCharAt(int index, char c) {
        let chars[index] = c;
    }
    
    method void appendChar(char c) {
        if (length < maxLength) {
            let chars[length] = c;
            let length = length + 1;
        }
    }
}

字符串操作实现

jack

method void eraseLastChar() {
    if (length > 0) {
        let length = length - 1;
    }
}

method int intValue() {
    var int value, i, digit;
    let value = 0;
    let i = 0;
    
    while (i < length) {
        let digit = chars[i] - 48;  // '0' = 48
        let value = value * 10 + digit;
        let i = i + 1;
    }
    
    return value;
}

method void setInt(int value) {
    var int i, digit;
    
    // 清空字符串
    let length = 0;
    
    if (value = 0) {
        do appendChar('0');
    } else {
        if (value < 0) {
            do appendChar('-');
            let value = -value;
        }
        
        // 提取数字(逆序)
        var Array temp;
        let temp = Array.new(10);
        let i = 0;
        
        while (value > 0) {
            let digit = value - (value / 10) * 10;
            let temp[i] = digit + 48;  // 转换为字符
            let value = value / 10;
            let i = i + 1;
        }
        
        // 逆序添加到字符串
        let i = i - 1;
        while (i >= 0) {
            do appendChar(temp[i]);
            let i = i - 1;
        }
        
        do temp.dispose();
    }
}

12.4 输出处理

Output类提供屏幕输出功能。

屏幕映射

屏幕是512×256像素的黑白显示器：

每个内存字控制32个水平像素
内存地址16384-24575映射到屏幕
0表示黑色，1表示白色

Output类实现

jack

class Output {
    static int cursorRow, cursorCol;
    
    function void init() {
        let cursorRow = 0;
        let cursorCol = 0;
    }
    
    function void moveCursor(int row, int col) {
        let cursorRow = row;
        let cursorCol = col;
    }
    
    function void printChar(char c) {
        // 在光标位置绘制字符
        do Screen.drawChar(c, cursorRow, cursorCol);
        
        // 移动光标
        let cursorCol = cursorCol + 8;  // 假设字符宽度为8
        if (cursorCol > 504) {
            let cursorCol = 0;
            let cursorRow = cursorRow + 11;  // 假设字符高度为11
        }
    }
    
    function void printString(String s) {
        var int i, length;
        let i = 0;
        let length = s.length();
        
        while (i < length) {
            do printChar(s.charAt(i));
            let i = i + 1;
        }
    }
    
    function void printInt(int i) {
        var String s;
        let s = String.new(10);
        do s.setInt(i);
        do printString(s);
        do s.dispose();
    }
    
    function void println() {
        let cursorRow = cursorRow + 11;
        let cursorCol = 0;
    }
    
    function void backspace() {
        if (cursorCol > 0) {
            let cursorCol = cursorCol - 8;
            // 清除字符
            do Screen.drawChar(' ', cursorRow, cursorCol);
        }
    }
}

12.5 键盘处理

Keyboard类提供键盘输入功能。

键盘映射

键盘通过内存地址24576访问：

没有按键时，值为0
有按键时，值为按键的ASCII码或特殊键码

特殊键码

129  : 删除键
130  : 左箭头
131  : 上箭头
132  : 右箭头
133  : 下箭头
137  : Home键
139  : End键
140  : Page Up
141  : Page Down
143  : Insert键

Keyboard类实现

jack

class Keyboard {
    function char keyPressed() {
        return Memory.peek(24576);
    }
    
    function char readChar() {
        var char c;
        
        // 等待按键
        while (keyPressed() = 0) {
            // 空循环
        }
        
        let c = keyPressed();
        
        // 等待释放
        while (keyPressed() != 0) {
            // 空循环
        }
        
        return c;
    }
    
    function String readLine(String message) {
        var String input;
        var char c;
        
        do Output.printString(message);
        let input = String.new(50);
        
        let c = readChar();
        while (~(c = 130)) {  // 不是回车键
            if (c = 129) {  // 删除键
                do input.eraseLastChar();
                do Output.backspace();
            } else {
                do input.appendChar(c);
                do Output.printChar(c);
            }
            let c = readChar();
        }
        
        do Output.println();
        return input;
    }
    
    function int readInt(String message) {
        var String input;
        var int value;
        
        let input = readLine(message);
        let value = input.intValue();
        do input.dispose();
        
        return value;
    }
}

12.6 屏幕绘图

Screen类提供图形绘图功能。

绘图原语

jack

class Screen {
    function void clearScreen() {
        var int i;
        let i = 16384;
        
        while (i < 24576) {
            Memory.poke(i, 0);
            let i = i + 1;
        }
    }
    
    function void setColor(boolean color) {
        // 设置绘图颜色(0=黑，1=白)
        // 实际实现需要保存当前颜色
    }
    
    function void drawPixel(int row, int col) {
        var int address, bit;
        
        // 计算内存地址
        let address = 16384 + (row * 32) + (col / 16);
        
        // 计算位位置
        let bit = col % 16;
        
        // 设置位
        Memory.poke(address, Memory.peek(address) | (1 << bit));
    }
    
    function void drawLine(int row1, int col1, int row2, int col2) {
        // 使用Bresenham算法绘制直线
        var int dx, dy, x, y, stepX, stepY, err;
        
        let dx = col2 - col1;
        let dy = row2 - row1;
        
        if (dx < 0) { let dx = -dx; }
        if (dy < 0) { let dy = -dy; }
        
        if (col1 < col2) { let stepX = 1; } else { let stepX = -1; }
        if (row1 < row2) { let stepY = 1; } else { let stepY = -1; }
        
        let err = dx - dy;
        let x = col1;
        let y = row1;
        
        while (~(x = col2)) {
            do drawPixel(y, x);
            
            let err = err * 2;
            if (err > -dy) {
                let err = err - dy;
                let x = x + stepX;
            }
            if (err < dx) {
                let err = err + dx;
                let y = y + stepY;
            }
        }
        
        do drawPixel(row2, col2);
    }
    
    function void drawRectangle(int row1, int col1, int row2, int col2) {
        var int i;
        
        // 绘制四条边
        do drawLine(row1, col1, row1, col2);  // 上边
        do drawLine(row2, col1, row2, col2);  // 下边
        do drawLine(row1, col1, row2, col1);  // 左边
        do drawLine(row1, col2, row2, col2);  // 右边
    }
    
    function void drawCircle(int row, int col, int radius) {
        var int x, y, d;
        
        let x = 0;
        let y = radius;
        let d = 1 - radius;
        
        while (x <= y) {
            do drawPixel(row + y, col + x);
            do drawPixel(row + y, col - x);
            do drawPixel(row - y, col + x);
            do drawPixel(row - y, col - x);
            do drawPixel(row + x, col + y);
            do drawPixel(row + x, col - y);
            do drawPixel(row - x, col + y);
            do drawPixel(row - x, col - y);
            
            if (d < 0) {
                let d = d + 2 * x + 3;
            } else {
                let d = d + 2 * (x - y) + 5;
                let y = y - 1;
            }
            let x = x + 1;
        }
    }
}

12.7 数学库

Math类提供数学运算功能。

Math类实现

jack

class Math {
    function int abs(int x) {
        if (x < 0) {
            return -x;
        }
        return x;
    }
    
    function int multiply(int x, int y) {
        var int result, i;
        let result = 0;
        let i = 0;
        
        while (i < y) {
            let result = result + x;
            let i = i + 1;
        }
        
        return result;
    }
    
    function int divide(int x, int y) {
        var int quotient, remainder;
        let quotient = 0;
        let remainder = x;
        
        while (remainder >= y) {
            let remainder = remainder - y;
            let quotient = quotient + 1;
        }
        
        return quotient;
    }
    
    function int min(int x, int y) {
        if (x < y) {
            return x;
        }
        return y;
    }
    
    function int max(int x, int y) {
        if (x > y) {
            return x;
        }
        return y;
    }
    
    function int sqrt(int x) {
        var int result, guess;
        
        if (x = 0) {
            return 0;
        }
        
        let result = x;
        let guess = 1;
        
        while (guess < result) {
            let result = guess;
            let guess = (guess + x / guess) / 2;
        }
        
        return result;
    }
}

12.8 系统服务

Sys类提供系统级服务。

Sys类实现

jack

class Sys {
    function void init() {
        // 初始化操作系统
        do Memory.init();
        do Output.init();
        do Screen.clearScreen();
    }
    
    function void wait(int duration) {
        var int i;
        let i = 0;
        
        while (i < duration) {
            let i = i + 1;
        }
    }
    
    function void halt() {
        while (true) {
            // 无限循环
        }
    }
    
    function void error(int errorCode) {
        do Output.printString("Error: ");
        do Output.printInt(errorCode);
        do Output.println();
        do halt();
    }
}

12.9 程序启动

Jack程序的启动过程：

系统初始化(Sys.init)

调用Main.main

程序执行

程序结束(Sys.halt)

启动代码

jack

class Sys {
    function void init() {
        do Memory.init();
        do Output.init();
        do Screen.clearScreen();
        
        // 调用主程序
        do Main.main();
        
        // 程序结束
        do halt();
    }
}

12.10 操作系统架构

完整的Jack操作系统架构：

Jack OS
├── Memory (内存管理)
│   ├── alloc
│   └── deAlloc
├── String (字符串处理)
│   ├── new
│   ├── appendChar
│   └── ...
├── Array (数组支持)
│   ├── new
│   └── dispose
├── Output (输出处理)
│   ├── printChar
│   ├── printString
│   └── printInt
├── Keyboard (键盘处理)
│   ├── keyPressed
│   ├── readChar
│   └── readLine
├── Screen (屏幕绘图)
│   ├── drawPixel
│   ├── drawLine
│   └── drawCircle
├── Math (数学运算)
│   ├── multiply
│   ├── divide
│   └── sqrt
└── Sys (系统服务)
    ├── init
    ├── wait
    └── halt

重要知识点

知识点1：内存分配策略

常见的内存分配策略：

首次适应：从空闲链表头部开始查找
最佳适应：查找最小的足够大的块
最坏适应：查找最大的块
下次适应：从上次分配的位置继续查找

知识点2：垃圾回收

垃圾回收自动回收不再使用的内存：

引用计数：跟踪每个对象的引用数
标记-清除：标记活动对象，清除未标记对象
复制回收：将活动对象复制到新区域

知识点3：I/O缓冲

I/O缓冲提高I/O效率：

单缓冲：使用一个缓冲区
双缓冲：使用两个缓冲区交替
循环缓冲：使用环形缓冲区

知识点4：设备驱动

设备驱动控制硬件设备：

轮询：定期检查设备状态
中断：设备主动通知CPU
DMA：直接内存访问，不经过CPU

知识点5：系统调用

系统调用是应用程序请求操作系统服务的接口：

进程控制：创建、终止进程
文件操作：打开、读取、写入文件
设备管理：请求I/O操作
信息维护：获取系统信息

常见误区

误区1：认为操作系统很复杂

实际上，基本的操作系统原理并不复杂。通过Nand2Tetris，我们可以理解操作系统的核心概念。

误区2：忽视内存管理

内存管理是操作系统的核心功能。内存泄漏、碎片化等问题会严重影响系统性能。

误区3：不理解I/O的复杂性

I/O操作涉及硬件细节，是操作系统中最复杂的部分之一。

误区4：认为操作系统是一成不变的

操作系统在不断演进。从批处理到分时系统，从单任务到多任务，操作系统在不断发展。

误区5：忽视安全性

操作系统必须保护系统资源，防止未授权访问。安全性是操作系统设计的重要考虑。

实践应用

实践1：实现内存管理器

jack

class Memory {
    static int heapStart;
    static int heapEnd;
    static int freeList;
    
    function void init() {
        let heapStart = 2048;
        let heapEnd = 16384;
        let freeList = heapStart;
        
        // 初始化空闲链表
        Memory.poke(freeList, heapEnd - heapStart - 1);  // 块大小
        Memory.poke(freeList + 1, 0);  // 下一个块为空
    }
    
    function Array alloc(int size) {
        var int block, prev, next, blockSize;
        
        let block = freeList;
        let prev = 0;
        
        while (block != 0) {
            let blockSize = Memory.peek(block);
            
            if (blockSize >= size) {
                // 找到合适的块
                if (blockSize > size + 2) {
                    // 分割块
                    let next = block + size + 1;
                    Memory.poke(next, blockSize - size - 1);
                    Memory.poke(block, size);
                    
                    // 更新空闲链表
                    if (prev != 0) {
                        Memory.poke(prev + 1, next);
                    } else {
                        let freeList = next;
                    }
                    Memory.poke(next + 1, Memory.peek(block + 1));
                } else {
                    // 使用整个块
                    if (prev != 0) {
                        Memory.poke(prev + 1, Memory.peek(block + 1));
                    } else {
                        let freeList = Memory.peek(block + 1);
                    }
                }
                
                return block + 1;
            }
            
            let prev = block;
            let block = Memory.peek(block + 1);
        }
        
        return 0;  // 没有足够的内存
    }
    
    function void deAlloc(Array obj) {
        var int block, prev, next;
        
        let block = obj - 1;  // 块头
        
        // 找到插入位置
        let prev = 0;
        let next = freeList;
        
        while ((next != 0) & (next < block)) {
            let prev = next;
            let next = Memory.peek(next + 1);
        }
        
        // 插入块
        Memory.poke(block + 1, next);
        if (prev != 0) {
            Memory.poke(prev + 1, block);
        } else {
            let freeList = block;
        }
        
        // 合并相邻块
        if ((next != 0) & (block + Memory.peek(block) + 1 = next)) {
            Memory.poke(block, Memory.peek(block) + Memory.peek(next) + 1);
            Memory.poke(block + 1, Memory.peek(next + 1));
        }
        
        if ((prev != 0) & (prev + Memory.peek(prev) + 1 = block)) {
            Memory.poke(prev, Memory.peek(prev) + Memory.peek(block) + 1);
            Memory.poke(prev + 1, Memory.peek(block + 1));
        }
    }
}

实践2：实现完整的String类

jack

class String {
    field int maxLength;
    field int length;
    field Array chars;
    
    constructor String new(int maxLen) {
        let maxLength = maxLen;
        let length = 0;
        let chars = Array.new(maxLen);
        return this;
    }
    
    method void dispose() {
        do chars.dispose();
        do Memory.deAlloc(this);
    }
    
    method int getMaxLength() {
        return maxLength;
    }
    
    method int length() {
        return length;
    }
    
    method int charAt(int index) {
        return chars[index];
    }
    
    method void setCharAt(int index, char c) {
        let chars[index] = c;
    }
    
    method void appendChar(char c) {
        if (length < maxLength) {
            let chars[length] = c;
            let length = length + 1;
        }
    }
    
    method void eraseLastChar() {
        if (length > 0) {
            let length = length - 1;
        }
    }
    
    method int intValue() {
        var int value, i, digit;
        let value = 0;
        let i = 0;
        
        while (i < length) {
            let digit = chars[i] - 48;
            let value = value * 10 + digit;
            let i = i + 1;
        }
        
        return value;
    }
    
    method void setInt(int value) {
        var int i, digit;
        var Array temp;
        
        let length = 0;
        
        if (value = 0) {
            do appendChar(48);  // '0'
        } else {
            if (value < 0) {
                do appendChar(45);  // '-'
                let value = -value;
            }
            
            let temp = Array.new(10);
            let i = 0;
            
            while (value > 0) {
                let digit = value - (value / 10) * 10;
                let temp[i] = digit + 48;
                let value = value / 10;
                let i = i + 1;
            }
            
            let i = i - 1;
            while (i >= 0) {
                do appendChar(temp[i]);
                let i = i - 1;
            }
            
            do temp.dispose();
        }
    }
    
    method String getNew(int size) {
        // 创建新字符串
        var String newStr;
        let newStr = String.new(size);
        return newStr;
    }
}

实践3：实现完整的Output类

jack

class Output {
    static int cursorRow;
    static int cursorCol;
    
    function void init() {
        let cursorRow = 0;
        let cursorCol = 0;
    }
    
    function void moveCursor(int row, int col) {
        let cursorRow = row;
        let cursorCol = col;
    }
    
    function void printChar(char c) {
        do Screen.drawChar(c, cursorRow, cursorCol);
        let cursorCol = cursorCol + 8;
        
        if (cursorCol > 504) {
            let cursorCol = 0;
            let cursorRow = cursorRow + 11;
            
            if (cursorRow > 245) {
                do scroll();
                let cursorRow = 245;
            }
        }
    }
    
    function void printString(String s) {
        var int i, len;
        let i = 0;
        let len = s.length();
        
        while (i < len) {
            do printChar(s.charAt(i));
            let i = i + 1;
        }
    }
    
    function void printInt(int i) {
        var String s;
        let s = String.new(10);
        do s.setInt(i);
        do printString(s);
        do s.dispose();
    }
    
    function void println() {
        let cursorRow = cursorRow + 11;
        let cursorCol = 0;
        
        if (cursorRow > 245) {
            do scroll();
            let cursorRow = 245;
        }
    }
    
    function void backspace() {
        if (cursorCol > 0) {
            let cursorCol = cursorCol - 8;
            do Screen.drawChar(32, cursorRow, cursorCol);  // 空格
        }
    }
    
    function void scroll() {
        var int i, j;
        
        // 向上滚动一行
        let i = 16384;
        while (i < 24544) {  // 24576 - 32
            Memory.poke(i, Memory.peek(i + 32));
            let i = i + 1;
        }
        
        // 清除最后一行
        let i = 24544;
        while (i < 24576) {
            Memory.poke(i, 0);
            let i = i + 1;
        }
    }
}

实践4：实现完整的Screen类

jack

class Screen {
    static boolean currentColor;
    
    function void init() {
        let currentColor = true;
    }
    
    function void clearScreen() {
        var int i;
        let i = 16384;
        
        while (i < 24576) {
            Memory.poke(i, 0);
            let i = i + 1;
        }
    }
    
    function void setColor(boolean color) {
        let currentColor = color;
    }
    
    function void drawPixel(int row, int col) {
        var int address, bit, value;
        
        let address = 16384 + (row * 32) + (col / 16);
        let bit = col % 16;
        
        let value = Memory.peek(address);
        if (currentColor) {
            let value = value | (1 << bit);
        } else {
            let value = value & ~(1 << bit);
        }
        Memory.poke(address, value);
    }
    
    function void drawLine(int row1, int col1, int row2, int col2) {
        var int dx, dy, x, y, stepX, stepY, err, e2;
        
        let dx = col2 - col1;
        let dy = row2 - row1;
        
        if (dx < 0) { let dx = -dx; }
        if (dy < 0) { let dy = -dy; }
        
        if (col1 < col2) { let stepX = 1; } else { let stepX = -1; }
        if (row1 < row2) { let stepY = 1; } else { let stepY = -1; }
        
        let err = dx - dy;
        let x = col1;
        let y = row1;
        
        while (~(x = col2)) {
            do drawPixel(y, x);
            
            let e2 = err * 2;
            if (e2 > -dy) {
                let err = err - dy;
                let x = x + stepX;
            }
            if (e2 < dx) {
                let err = err + dx;
                let y = y + stepY;
            }
        }
        
        do drawPixel(row2, col2);
    }
    
    function void drawRectangle(int row1, int col1, int row2, int col2) {
        var int i;
        
        // 填充矩形
        let i = row1;
        while (i <= row2) {
            do drawLine(i, col1, i, col2);
            let i = i + 1;
        }
    }
    
    function void drawCircle(int row, int col, int radius) {
        var int x, y, d;
        
        let x = 0;
        let y = radius;
        let d = 1 - radius;
        
        while (x <= y) {
            do drawPixel(row + y, col + x);
            do drawPixel(row + y, col - x);
            do drawPixel(row - y, col + x);
            do drawPixel(row - y, col - x);
            do drawPixel(row + x, col + y);
            do drawPixel(row + x, col - y);
            do drawPixel(row - x, col + y);
            do drawPixel(row - x, col - y);
            
            if (d < 0) {
                let d = d + 2 * x + 3;
            } else {
                let d = d + 2 * (x - y) + 5;
                let y = y - 1;
            }
            let x = x + 1;
        }
    }
}

实践5：实现完整的Math类

jack

class Math {
    function int abs(int x) {
        if (x < 0) {
            return -x;
        }
        return x;
    }
    
    function int multiply(int x, int y) {
        var int result, i;
        let result = 0;
        
        if (x < 0) {
            let x = -x;
            let y = -y;
        }
        
        let i = 0;
        while (i < y) {
            let result = result + x;
            let i = i + 1;
        }
        
        return result;
    }
    
    function int divide(int x, int y) {
        var int quotient, remainder;
        
        if (y = 0) {
            do Sys.error(1);  // 除零错误
        }
        
        let quotient = 0;
        let remainder = Math.abs(x);
        let y = Math.abs(y);
        
        while (remainder >= y) {
            let remainder = remainder - y;
            let quotient = quotient + 1;
        }
        
        if ((x < 0) & (y > 0)) { let quotient = -quotient; }
        if ((x > 0) & (y < 0)) { let quotient = -quotient; }
        
        return quotient;
    }
    
    function int min(int x, int y) {
        if (x < y) {
            return x;
        }
        return y;
    }
    
    function int max(int x, int y) {
        if (x > y) {
            return x;
        }
        return y;
    }
    
    function int sqrt(int x) {
        var int result, guess;
        
        if (x <= 0) {
            return 0;
        }
        
        let result = x;
        let guess = 1;
        
        while (guess < result) {
            let result = guess;
            let guess = (guess + x / guess) / 2;
        }
        
        return result;
    }
}

实践6：编写测试程序

jack

class Main {
    function void main() {
        var Array arr;
        var int i, sum;
        
        do Sys.init();
        
        // 测试内存分配
        let arr = Array.new(10);
        
        // 填充数组
        let i = 0;
        while (i < 10) {
            let arr[i] = i * i;
            let i = i + 1;
        }
        
        // 计算总和
        let sum = 0;
        let i = 0;
        while (i < 10) {
            let sum = sum + arr[i];
            let i = i + 1;
        }
        
        // 输出结果
        do Output.printString("Sum of squares: ");
        do Output.printInt(sum);
        do Output.println();
        
        // 测试字符串
        var String s;
        let s = String.new(20);
        do s.appendChar('H');
        do s.appendChar('e');
        do s.appendChar('l');
        do s.appendChar('l');
        do s.appendChar('o');
        
        do Output.printString("String: ");
        do Output.printString(s);
        do Output.println();
        
        // 测试数学运算
        do Output.printString("5 * 3 = ");
        do Output.printInt(Math.multiply(5, 3));
        do Output.println();
        
        do Output.printString("sqrt(16) = ");
        do Output.printInt(Math.sqrt(16));
        do Output.println();
        
        // 清理
        do arr.dispose();
        do s.dispose();
        
        do Output.printString("Press any key to halt...");
        do Keyboard.readChar();
        
        do Sys.halt();
        return;
    }
}

本章小结

本章我们实现了Jack操作系统，为Jack程序提供完整的运行时支持。

核心要点回顾

内存管理：使用空闲链表管理堆内存，支持动态分配和回收。

字符串处理：String类提供字符串创建、修改和转换功能。

输出处理：Output类提供字符、字符串和整数的屏幕输出。

键盘处理：Keyboard类提供键盘输入功能，支持字符和字符串读取。

屏幕绘图：Screen类提供像素、直线、矩形和圆形的绘图功能。

数学运算：Math类提供基本的数学运算功能。

系统服务：Sys类提供初始化、等待和终止等系统服务。

关键技能掌握

理解操作系统的基本功能
掌握内存管理的原理和实现
能够实现I/O处理
理解系统调用的概念
能够为高级语言提供运行时支持

与前面章节的联系

本章完成的操作系统是整个Nand2Tetris项目的最后一块拼图：

第一到三章：构建硬件基础(逻辑门、ALU、时序电路)
第四到五章：构建计算机体系结构和机器语言
第六章：构建汇编器
第七到八章：构建虚拟机
第九到十一章：构建编译器
第十二章：构建操作系统

学习建议

理解整体：从整体上理解操作系统的功能和架构

关注细节：内存管理、I/O处理等细节决定系统质量

动手实践：亲手实现操作系统的各个组件

测试验证：使用各种测试程序验证操作系统的正确性

通过本章的学习，你已经完成了整个Nand2Tetris项目。从最基本的逻辑门到完整的操作系统，这是一个了不起的成就。你不仅理解了计算机系统的各个层面，更掌握了从简单到复杂、从具体到抽象的系统化设计方法。

这种自底向上的学习方法让你深入理解了计算机系统的本质。从硬件到软件，从机器语言到高级语言，从编译器到操作系统，每一层抽象都建立在前一层的基础之上。这种层次化的设计思想是计算机科学的核心思想之一。

现在，你拥有了完整的知识体系，可以进一步探索更复杂的计算机系统。无论是深入研究硬件架构，还是探索操作系统原理，或是学习编译器设计，你都已经有了坚实的基础。

第十二章 操作系统

导读

核心概念详解

12.1 操作系统概述

操作系统的功能

Jack操作系统的简化

12.2 内存管理

内存布局

堆管理

内存分配算法

内存分配实现

12.3 字符串处理

String类结构

字符串操作实现

12.4 输出处理

屏幕映射

Output类实现

12.5 键盘处理

键盘映射

特殊键码

Keyboard类实现

12.6 屏幕绘图

绘图原语

12.7 数学库

Math类实现

12.8 系统服务

Sys类实现

12.9 程序启动

启动代码

12.10 操作系统架构

重要知识点

知识点1：内存分配策略

知识点2：垃圾回收

知识点3：I/O缓冲

知识点4：设备驱动

知识点5：系统调用

常见误区

误区1：认为操作系统很复杂

误区2：忽视内存管理

误区3：不理解I/O的复杂性

误区4：认为操作系统是一成不变的

误区5：忽视安全性

实践应用

实践1：实现内存管理器

实践2：实现完整的String类

实践3：实现完整的Output类

实践4：实现完整的Screen类

实践5：实现完整的Math类

实践6：编写测试程序

本章小结

核心要点回顾

关键技能掌握

与前面章节的联系

学习建议

第十二章操作系统