Embryo!

进程模块 —— 雏形

在确定好设计理念之后，我们就需要来具体实现 OS 的进程系统了。我希望它作为一个模块挂载到 OS 下，这样抽象成模块存在，就可以易于安装、分离与运行。

既然它作为一个独立模块存在，那么它对主 AI 应当只暴露一些公开的接口，所以首先，我们需要设计它暴露的公开接口是什么。这样，即便后来我们换了或者是优化了具体的实现细节，只要公开的接口相同，其他的代码就不用跟着更换。

在此之前，需要先定义一些之前公开的涉及到的类型和常量：

/**
 * 公开的原子函数返回值
 */

/** 下一次执行时, 仍然从当前原子函数重复执行 */
export const OK_STOP_CURRENT = "ok_stop_current"
/** 下一次执行时, 从当前原子函数下一条继续执行 */
export const OK_STOP_NEXT = "ok_stop_next"
/** 下一次执行时, 从指定 Tag 开始继续执行 */
export const OK_STOP_CUSTOM = "ok_stop_custom"
/** 错误, 在下一 tick 重启运行该进程 */
export const STOP_ERR = "stop_err"

/**
 * 特殊的原子函数返回值
 */

/** 阻塞进程 */
const STOP_STUCK = "stop_stuck"

/** 普通原子函数返回值 */
type AtomicFuncReturnCode = OK | typeof OK_STOP_CURRENT | typeof OK_STOP_NEXT | [typeof OK_STOP_CUSTOM, string] | [typeof STOP_ERR, string]
/** 可阻塞的原子函数返回值 */
type StuckableAtomicFuncReturnCode = OK | typeof STOP_STUCK

/**
 * 原子函数定义
 */

/** 原子函数 */
type AtomicFunc = () => AtomicFuncReturnCode | StuckableAtomicFuncReturnCode
/** Tag + 原子函数 */
type AtomicFuncWithTag = [string, AtomicFunc]
/** 条件跳转: "JUMP" + 条件 + Tag */
type AtomicJump = ["JUMP", () => boolean, string]

/** 原子函数描述器, 用于构建进程时 */
type AtomicFuncDescriptor = (AtomicFunc | AtomicFuncWithTag | AtomicJump)[]

现在还没涉及到阻塞的锁、信号量和管程，所以暂且不写，留待以后补充。

接下来，我们需要在进程模块主文件内部来具体定义：

/**
 * 进程模块
 * 
 * 特别的, 暂时我们不允许 kill 进程. 如果引入 kill 进程, 会
 * 牵涉到权限控制等一系列尚未定义的方面.
 */
export interface ProcessModule {
    /**
     * 创建进程
     * @param descriptor 进程具体流程
     * @param description 进程简要描述
     * @returns 进程 Id
     */
    createProc(descriptor: AtomicFuncDescriptor, description: string): ProcId
    /**
     * 在当前 tick 运行一次
     * 
     * 注意: 本函数每 tick 只能运行一次, 否则会报错.
     * 所以, 请在其他功能模块创建完进程后, 再执行.
     * 
     * 注意: 本函数在运行中, 如果有新的进程被创建, 新
     * 的进程也会被执行.
     */
    tick(): void
}

/**
 * 进程
 * 不对外公开
 */
class Process {
    /** 进程号 */
    pid: ProcId
    /** 
     * 进程文字描述
     * 我设定为强制要求, 因为可读的文字描述有利于
     * 监控与调试
     */
    description: string
    /** 进程具体流程 */
    descriptor: AtomicFuncDescriptor
    /** 记录当前进程运行到的原子函数行数 */
    pc: number
    /** Tag 到对应原子函数行数的映射 */
    tagDict: {[tag: string]: number}
    /** 
     * 进程状态: 就绪, 阻塞, 运行
     * 结束状态被省去, 因为进程一旦消亡, 则不会被中断, 
     * 直至处理结束进程的函数结束
     */
    state: "Ready" | "Stuck" | "Running"

    constructor(
        pid: ProcId, 
        description: string, 
        descriptor: AtomicFuncDescriptor
    ) {
        this.pid = pid
        this.description = description
        this.descriptor = descriptor

        // 初始化当前 PC
        this.pc = 0
        // 计算 Tag 到对应原子函数行数的映射
        this.tagDict = {}
        this.descriptor.forEach((value, index) => {
            // 检查属于 AtomicFuncWithTag
            if ( Array.isArray(value) && value.length === 2 )
                this.tagDict[value[0]] = index
        })
        // 初始化状态
        this.state = "Ready"

        // 检查跳转的 Tag 都存在
        for (const desc of this.descriptor) {
            if ( Array.isArray(desc) && desc.length === 3 )
                assertWithMsg(desc[2] in this.tagDict, `在检查进程 ${this} 时发现未识别的跳转后标签 ${desc[2]}`)
        }
    }
    
    toString() {
        return `[Proc ${this.pid}: ${this.description}]`
    }
}

在之后, 锁、信号量和管程会作为进程模块的子模块附加在内。因为他们需要访问进程的私有属性和方法。

📃 Interface 模块内部实现

在 Interface 模块内部，我们需要实现一些私有属性和方法。

/**
 * 进程模块的具体实现
 * Process Module Implementation (PMI)
 * 
 * 特点:
 *  - 在这个实现当中, 同一时刻, 只有一个进程可以运行 (不使用异步函数)
 */
export class PMI implements ProcessModule {
    /** 当前正在运行的进程 Id, 用于内部阻塞原子函数识别进程 */
    static #currentProcId: number = -1
    /** 断言正在运行的进程 Id, 用于检查 */
    static #assertCurrentProcId(id: number, task: string) {
        if ( !(id in this.#procDict) )
            throw `在${task}中, 发现正在运行的进程 Id 为 ${this.#currentProcId}, 找不到应当处于进行态的进程 Id ${id}`
        else
            assertWithMsg( this.#currentProcId === id, `在${task}中, 发现正在运行的进程 Id 为 ${this.#currentProcId}, 但是进程 ${this.#procDict[id]} 的状态为运行态` )
    }
    /** 就绪进程 Id 队列 */
    static #processIdReadyQueue: number[] = []
    /** 阻塞进程 Id 队列 */
    static #processIdStuckQueue: number[] = []
    /** 映射进程 Id 到进程实体 */
    static #procDict: {[ id: number ]: Process} = {}

    /** 可用的进程 Id 链表 */
    static #idLinkList: number[] = [ ...Array(MAX_PROC_ID).keys() ]
    /** 获得下一个进程 Id */
    static #getProcId(): number {
        // 无可用的进程 Id
        if ( PMI.#idLinkList.length === 0 )
            throw "Error: 无可用进程 Id";
        
        // 返回进程 Id 链表中第一个可用 Id
        return PMI.#idLinkList.shift()
    }

    /**
     * 阻塞进程, 不对外暴露
     */
    static #stuckProc(id: number) {
        // 找不到进程 id
        if ( !(id in this.#procDict) )
            throw `Error: 无法找到进程 ${id} 以阻塞`
        
        const proc = this.#procDict[id]
        const state = proc.state

        if ( state === "Ready" ) {
            // 阻塞就绪进程
            // 从就绪进程 Id 队列中删去
            _.pull(this.#processIdReadyQueue, id)
        } else if ( state === "Running" ) {
            // 阻塞运行中进程
            // 确认当前只有一个进程正在运行
            // 并且为正被阻塞的进程
            this.#assertCurrentProcId(id, "阻塞")
            // 重置正在运行的进程 Id
            this.#currentProcId = -1
        } else if ( state === "Stuck" ) {
            throw `Error: 进程 ${proc} 已经处于阻塞态, 无法再次被阻塞`
        }
        // 调整状态为阻塞
        proc.state = "Stuck"
        // 将进程 Id 加入阻塞进程 Id 队列中
        this.#processIdStuckQueue.push(id)
    }

    /**
     * 将进程从阻塞态唤醒到就绪态
     * 
     * 注意: 考虑到群惊效应, 进程可能被唤醒多次. 因此, 若
     * 进程出于就绪态, 不会报错. 但是因为同一时间只有一个
     * 运行的进程, 而自己不能唤醒自己, 会报错.
     */
    static #wakeUpProc(id: number) {
        // 找不到进程 id
        if ( !(id in this.#procDict) )
            throw `Error: 无法找到进程 ${id} 以唤醒`
        
        const proc = this.#procDict[id]
        const state = proc.state

        if ( state === "Ready" )  {
            // 已经处于就绪的进程
            // 无需处理
        } else if ( state === "Stuck" ) {
            // 唤醒阻塞中进程
            // 从阻塞进程 Id 队列中删除
            _.pull(this.#processIdStuckQueue, id)
            // 将进程 Id 加入就绪进程 Id 队列中
            this.#processIdReadyQueue.push(id)
        } else if ( state === "Running" ) {
            // 唤醒运行中进程
            throw `Error: 运行中的进程 ${proc} 无法再次被唤醒`
        }
        // 调整状态为就绪
        proc.state = "Ready"
    }

    /** 
     * 销毁进程, 不对外暴露
     * @todo 给未释放的锁, 信号量或管程提出警告
     */
    static #destroyProc(id: number) {
        // 找不到进程 id
        if ( !(id in this.#procDict) )
            throw `Error: 无法找到进程 ${id} 以结束`
        
        const proc = this.#procDict[id]
        const state = proc.state

        if ( state === "Ready" ) {
            // 销毁就绪进程
            // 从就绪进程 Id 队列中删去
            _.pull(this.#processIdReadyQueue, id)
        } else if ( state === "Running" ) {
            // 销毁运行中进程
            // 确认当前只有一个进程正在运行
            // 并且为正被销毁的进程
            this.#assertCurrentProcId(id, "销毁")
            // 重置正在运行的进程 Id
            this.#currentProcId = -1
        } else if ( state === "Stuck" ) {
            // 销毁阻塞进程
            // 从阻塞进程 Id 队列中删去
            _.pull(this.#processIdStuckQueue, id)
        }
        
        // 从映射中删去实体
        delete this.#procDict[id]
        // 归还进程 Id
        this.#idLinkList.push(id)
    }

    createProc(descriptor: AtomicFuncDescriptor, description: string) {
        const id = PMI.#getProcId()
        const proc = new Process(id, description, descriptor)

        // 将进程注册到映射表中
        PMI.#procDict[id] = proc
        // 将新创建的进程加入到就绪队列当中
        PMI.#processIdReadyQueue.push(id)

        return id
    }
    /** 记录上一次调用 tick 的 Game.time 以保证每 tick 只能执行一次 tick */
    static #lastTick: number = -1

    tick() {
        // 检验为本 tick 第一次调用
        assertWithMsg(PMI.#lastTick === -1 || PMI.#lastTick !== Game.time, `进程模块在 ${Game.time} 被重复调用 tick 函数`)
        // 校验当前没有正在运行的进程
        assertWithMsg(PMI.#currentProcId === -1, `进程模块在 tick 开始时, 发现已有正在运行的进程 Id ${PMI.#currentProcId}`)
        // 创建临时就绪进程 Id 队列
        const processIdReadyQueue = []

        while ( PMI.#processIdReadyQueue.length !== 0 ) {
            // 从就绪队列 Id 中出队头 Id
            const id = PMI.#processIdReadyQueue.shift()
            const proc = PMI.#procDict[id]

            // 修改状态
            PMI.#currentProcId = id
            proc.state = "Running"

            // 运行进程
            // 这个不作为 Process 的成员函数存在, 
            // 是因为要访问进程模块的私有成员
            while ( true ) {
                // 进程执行结束
                if (proc.pc >= proc.descriptor.length) {
                    PMI.#destroyProc(id)
                    break
                }
                // 获得当前原子函数描述
                const desc = proc.descriptor[proc.pc]

                if (Array.isArray(desc) && desc.length === 3) {
                    // 条件跳转
                    const condition = desc[1]()

                    if ( condition )
                        proc.pc = proc.tagDict[desc[2]]
                    else
                        proc.pc++
                } else {
                    // 取得原子函数
                    let atomicFunc: AtomicFunc = null
                    if (Array.isArray(desc) && desc.length === 2) atomicFunc = desc[1]
                    else atomicFunc = desc

                    const returnCode = atomicFunc()
                    if (returnCode === OK) {
                        // 顺序执行下一条原子函数
                        proc.pc++
                    } else if (returnCode === "ok_stop_current") {
                        // 主动停止, 仍然从本条原子函数开始
                        proc.state = "Ready"
                        processIdReadyQueue.push(id)
                        // 复原状态
                        PMI.#currentProcId = -1
                        break
                    } else if (returnCode === "ok_stop_next") {
                        // 主动停止, 从下一条原子函数开始
                        proc.pc++
                        // 特殊情况: 进程结束
                        if ( proc.pc >= proc.descriptor.length )
                            PMI.#destroyProc(id)
                        else {
                            proc.state = "Ready"
                            processIdReadyQueue.push(id)
                            // 复原状态
                            PMI.#currentProcId = -1
                        }
                        break
                    } else if (returnCode === "stop_stuck") {
                        // 阻塞, 下次仍然从同一条原子函数开始执行
                        PMI.#stuckProc(id)
                        break
                    } else if (Array.isArray(returnCode) && returnCode[0] === "stop_err") {
                        // 错误, 资源的释放应当在进程内部完成
                        // 在下一 tick 重启运行该进程
                        proc.state = "Ready"
                        processIdReadyQueue.push(id)
                        proc.pc = 0
                        // 输出错误信息
                        log(LOG_ERR, `运行进程 ${proc} 时, 遇到错误: ${returnCode[1]}`)
                        // 复原状态
                        this.#currentProcId = -1
                        break
                    } else if (Array.isArray(returnCode) && returnCode[0] === "ok_stop_custom") {
                        // 复原状态
                        PMI.#currentProcId = -1

                        // 主动停止, 从特定 Tag 处开始
                        const tag = returnCode[1]
                        if (!(tag in proc.tagDict))
                            throw `Error: 在执行进程 ${proc} 的过程中, 无法跳转到标签 ${tag}`
                        
                        proc.state = "Ready"
                        proc.pc = proc.tagDict[tag]
                        processIdReadyQueue.push(id)
                        break
                    }
                }
            }
        }

        // 将进程模块的就绪进程 Id 队列指向临时变量
        PMI.#processIdReadyQueue = processIdReadyQueue
        // 更新上一次调用函数的时间
        PMI.#lastTick = Game.time
    }
}

锁的实现是进程同步机制中最简单的一个。它只需要实现acquire 和 release 两个方法。

但是因为这牵涉到进程的阻塞与唤醒，所以它不能作为一个独立模块存在，而是作为进程模块的子模块存在。

首先，我们定义锁类实体。

/** 随机生成一个锁的 Id */
const getLockId = () => generate_random_hex(8)

/**
 * 锁类实体
 * 不对外公开
 */
class Lock {
    /** 锁 Id */
    lockId: string
    /** 持有锁的进程 Id */
    holder: ProcId
    /** 请求锁而阻塞的进程 Id 列表 */
    stuckList: ProcId[]
    constructor(lockId: string) {
        this.lockId = lockId
        this.holder = null
        this.stuckList = []
    }
}

接下来，我们需要定义锁模块的接口，并加到进程模块中去。

/**
 * 锁模块
 */
interface LockModule {
    /** 创建一个新锁 */
    createLock(): string
    /** 销毁一个锁 */
    destroyLock(lockId: string): void
    /** 获得一个锁, 只能在进程流程中运行使用 */
    acquireLock(lockId: string): StuckableAtomicFuncReturnCode
    /** 释放一个锁, 只能在进程流程中运行使用 */
    releaseLock(lockId: string): OK
}

注意: 在这个实现当中，锁模块中的获得与释放只能在进程流程中使用, 不可在其他地方使用。因为他们需要通过正在运行的进程 Id 来确认是哪个进程正在尝试获得或者是释放锁。这样并不保险，所以我们可以换一个写法，让进程流程在描述时使用字符串指明想要获得锁，然后在创建进程过程中编译进程描述，替换为真实函数，但是就有点儿复杂了，没有必要，我们注意一下就可以了。

注意: 锁的销毁需要手动销毁。因为进程模块在执行过程中，无法判断锁是否不再被使用。因为进程中可能存在控制结构等。

在进程模块中加入管理锁的部分：

/** 映射锁 Id 到锁实体 */
static #lockDict: {[id: string]: Lock} = {}
/** 映射进程 Id 到使用过的锁 Id, 用于进程销毁时, 检测销毁锁 */
static #proc2Lock: {[id: ProcId]: string[]} = {}
/** 实例上的锁模块 */
lock: LockModule

static #lockCreateLock() {
    const id = getLockId()
    this.#lockDict[id] = new Lock(id)
    return id
}

static #lockDestroyLock(lockId: string) {
    // 如果 lock 不存在
    if ( !(lockId in this.#lockDict) )
        throw `Error: 无法找到锁 ${lockId} 以销毁`
    
    const lock = this.#lockDict[lockId]
    // 当锁销毁时, 会唤醒所有阻塞的进程
    for (const pid of lock.stuckList)
        this.#wakeUpProc(pid)

    delete this.#lockDict[lockId]
}

static #lockAcquireLock(lockId: string): StuckableAtomicFuncReturnCode {
    // 如果 lock 不存在 (可能已经销毁)
    if ( !(lockId in this.#lockDict) )
        return OK
    
    const lock = this.#lockDict[lockId]
    const pid = this.#currentProcId
    // 正在运行的进程不存在
    if ( pid === -1 )
        throw `Error: 在获得锁 ${lockId} 时, 无法找到正在运行的进程`
    
    // 如果正有进程持有锁
    if (lock.holder !== null) {
        assertWithMsg(!lock.stuckList.includes(pid), `锁 ${lockId} 的阻塞列表中包含 ${this.#procDict[pid]}, 该进程却又想获得锁`)
        lock.stuckList.push(pid)
        return STOP_STUCK
    }
    
    // 进程持有锁
    lock.holder = pid
    return OK
}

static #lockReleaseLock(lockId: string) {
    // 如果 lock 不存在 (可能已经销毁)
    if ( !(lockId in this.#lockDict) )
        return OK
    
    const lock = this.#lockDict[lockId]
    const pid = this.#currentProcId
    // 正在运行的进程不存在
    if ( pid === -1 )
        throw `Error: 在释放锁 ${lockId} 时, 无法找到正在运行的进程`
    
    // 释放的进程不持有锁
    if (lock.holder !== pid)
        throw `Error: 进程 ${this.#procDict[pid]} 不持有锁 ${lockId}, 但是却期望释放`
    
    // 重置持有进程
    lock.holder = null
    // 群惊阻塞进程
    for (const id of lock.stuckList)
        this.#wakeUpProc(id)
    // 重置阻塞进程 Id 列表
    lock.stuckList = []
    return OK
}

constructor() {
    // 创建锁子模块
    // 这里之所以采用这种写法, 是因为如果所有相关函数都在
    // 进程模块下, 不太美观. 不如整理到一个子模块下, 但是
    // 子模块又需要访问进程模块的私有属性和方法, 因此采用
    // 共有匿名函数对私有方法包装.
    this.lock = {
        createLock: () => PMI.#lockCreateLock(), 
        destroyLock: (lockId: string) => PMI.#lockDestroyLock(lockId), 
        acquireLock: (lockId: string) => PMI.#lockAcquireLock(lockId), 
        releaseLock: (lockId: string) => PMI.#lockReleaseLock(lockId)
    }
}

Okay，到目前为止，我们的进程模型大略已经完成了，下面需要一些简单的测试。

🚥 信号集的实现

信号集需要实现Swait 和 Ssignal 。而信号集依赖于信号量。实际上，我们只要实现了一个个的信号量，就可以实现信号集。

但是因为这牵涉到进程的阻塞与唤醒，所以它不能作为一个独立模块存在，而是作为进程模块的子模块存在。

首先我们定义信号量类：

/** 随机生成一个信号量的 Id */
const getSignalId = () => generate_random_hex(8)

/**
 * 信号量类实体
 * 不对外公开
 */
class Signal {
    /** 信号量 Id */
    signalId: string
    /** 因该信号量而阻塞的进程 Id 列表 */
    stuckList: ProcId[]
    /** 信号量值 */
    value: number
    constructor(signalId: string, value: number) {
        this.signalId = signalId
        this.stuckList = []
        this.value = value
    }
}

接下来，我们需要定义信号量模块的接口，并加到进程模块中去。

/**
 * 信号量模块
 */
interface SignalModule {
    /** 
     * 创建一个新信号量
     * @param value 初始值
     */
    createSignal(value: number): string
    /** 销毁一个信号量 */
    destroySignal(signalId: string): void
    /** 等待一个信号量集 */
    Swait(...signals: {signalId: string, lowerbound: number, request: number}[]): StuckableAtomicFuncReturnCode
    /** 激活一个信号量集 */
    Ssignal(...signals: {signalId: string, request: number}[]): StuckableAtomicFuncReturnCode
}

注意: 在这个实现当中，信号量模块中的获得与释放只能在进程流程中使用, 不可在其他地方使用。因为他们需要通过正在运行的进程 Id 来确认是哪个进程正在尝试获得或者是激活信号集。这样并不保险，所以我们可以换一个写法，让进程流程在描述时使用字符串指明想要获得信号集，然后在创建进程过程中编译进程描述，替换为真实函数，但是就有点儿复杂了，没有必要，我们注意一下就可以了。

注意: 信号量的销毁需要手动销毁。因为进程模块在执行过程中，无法判断信号量是否不再被使用。因为进程中可能存在控制结构等。

接下来，我们在进程模块中具体添加信号量子模块：

/** 映射信号量 Id 到信号量实体 */
static #signalDict: {[id: string]: Signal} = {}
/** 实例上的信号量模块 */
signal: SignalModule

static #signalCreateSignal(value: number) {
    const id = getSignalId()
    this.#signalDict[id] = new Signal(id, value)
    return id
}

static #signalDestroySignal(signalId: string) {
    if ( !(signalId in this.#signalDict) )
        throw `Error: 无法找到信号量 ${signalId} 以销毁`
    
    const signal = this.#signalDict[signalId]
    // 当信号量销毁时, 会唤醒所有阻塞的进程
    for (const pid of signal.stuckList)
        this.#wakeUpProc(pid)
    signal.stuckList = []
    
    delete this.#signalDict[signalId]
}

static #signalSwait(...signals: {signalId: string, lowerbound: number, request: number}[]): StuckableAtomicFuncReturnCode {
    const pid = this.#currentProcId
    // 正在运行的进程不存在
    if ( pid === -1 )
        throw `Error: 在获得信号集 ${signals.map(o => o.signalId)} 时, 无法找到正在运行的进程`
    
    for (const signalDescriptor of signals) {
        const signal = this.#signalDict[signalDescriptor.signalId]
        // 找不到信号量 (可能已经销毁)
        if (!signal) continue
        if (signal.value < signalDescriptor.lowerbound) {
            assertWithMsg(!signal.stuckList.includes(pid), `信号量 ${signal.signalId} 的阻塞列表中包含 ${this.#procDict[pid]}, 该进程却又想获得信号量`)
            signal.stuckList.push(pid)
            return STOP_STUCK
        }
    }

    for (const signalDescriptor of signals) {
        const signal = this.#signalDict[signalDescriptor.signalId]
        // 找不到信号量 (可能已经销毁)
        if (!signal) continue
        signal.value -= signalDescriptor.request
    }
    return OK
}

static #signalSsignal(...signals: {signalId: string, request: number}[]): StuckableAtomicFuncReturnCode {
    const pid = this.#currentProcId
    // 正在运行的进程不存在
    if ( pid === -1 )
        throw `Error: 在激活信号集 ${signals.map(o => o.signalId)} 时, 无法找到正在运行的进程`
    
    for (const signalDescriptor of signals) {
        const signal = this.#signalDict[signalDescriptor.signalId]
        // 找不到信号量 (可能已经销毁)
        if (!signal) continue
        signal.value += signalDescriptor.request
        for (const id of signal.stuckList)
            this.#wakeUpProc(id)
        signal.stuckList = []
    }
    
    return OK
}

constructor() {
    // ...
    // 创建信号量子模块
    this.signal = {
        createSignal: (value: number) => PMI.#signalCreateSignal(value), 
        destroySignal: (signalId: string) => PMI.#signalDestroySignal(signalId), 
        Swait: (...signals: {signalId: string, lowerbound: number, request: number}[]) => PMI.#signalSwait(...signals), 
        Ssignal: (...signals: {signalId: string, request: number}[]) => PMI.#signalSsignal(...signals)
    }
}

信号集的实现十分关键，我们后边资源管理模块也要依赖信号集来实现。