2024秋冬季训练营第四阶段总结-戴志强

2024 秋冬季开源操作系统训练营

导学阶段

这个阶段主要是介绍 linux 和 github的基本操作。

基础阶段-Rust 编程

在这个阶段，学员将深入学习 Rust 编程语言的基础知识和高级特性。主要内容包括 Rust 的语法结构、内存管理机制、并发编程和错误处理等。

📖

学习经历： 完成110题并上传，关于所有权的特性还不是特别熟练，特别是在数据结构比较复杂的情况下比如一个Rc指针 包含一个Vec，在这种多层所有权的情况下容易出错，还需多多练加强。

笔记：

Rust编程 基础知识

梳理后

变量与可变性:

使用 let 声明变量

let x = 5;

默认不可变（一旦赋值，不可修改）

意义：防止意外的数据修改和并发问题

如何可变？使用 mut 关键字

let mut x = 5;

常量声明

使用 const 而不是 let

声明值只能为 常量表达式

（即，不可以是只能在程序运行时才能计算出的值）

const THREE_HOURS_IN_SECONDS: u32 = 60 * 60 * 3;

基本数据类型-原生类型（primitives）

标量类型

有符号整数 (signed integers) : i8, i16, i32, i64, i128 和 isize （指针宽度）

无符号整数 (unsigned integers) : u8

浮点数 (floating point): f32, f64

char (字符) : 单个 Unicode 字符，如 ‘a’

bool (布尔型) : 只能是 true 或 false

单元类型 (unit type) : ()。

复合类型

数组 (array) : 如 [1, 2, 3]

元组 (tuple) : 如 (1, true)

元组 (tuple)

把一个或多个其他类型的值组合进一个复合类型

长度固定（声明后长度不变）

let tup: (i32, f64, u8) = (500, 6.4, 1);

如何获取单个值？

1. 使用点号 (.) 加值的索引

2. 使用模式匹配 (pattern matching) 来解构 (destruction) 元组值

   let tup = (500, 6.4, 1);
   let (x, y, z) = tup;
   println!("The value of y is: {y}");

数组 (array)

在栈上分配，单个内存块

声明

1. 直接声明

   let a = [1, 2, 3, 4, 5];

2. 指定元素类型和元素数量

   let a: [i32; 5] = [1, 2, 3, 4, 5];

3. 指定初始值和元素个数

   let a = [3; 5];

使用

使用索引来访问

函数

声明

使用 fn 关键字来声明

fn main() {
    println!("Hello, world!");
    another_function();
}
fn another_function() {
    println!("Another function.");
}

if 表达式

loop 循环

循环标签

改变 break 或 continue 的作用对象

while 循环

for 循环

所有权概念

变量作用域与变量隐藏

函数参数的所有权

函数返回值

引用与借用

可变引用

String

String slice

结构体

元组结构体

Vector

定义

可变长数组，只能存储相同类型的值

使用

Vec::new() 可以新建空 vector

let v: Vec<i32> = Vec::new();
//这个 Vec<i32> 可以不加

vec! 宏，会根据我们提供的值来创建一个新的 vector

let v = vec![1, 2, 3];

使用 push 可以向 vector 中增加元素

hashmap

定义

HashMap<K, V> 类型储存了一个键类型为 K 对应一个值类型为 V 的映射

其通过一个 哈希函数（hashing function）来实现映射，决定如何将键和值放入内存中

使用

可以使用 new 来创建

使用 insert 增加元素

使用 get 方法来从 hashmap 中获取值

use std::collections::HashMap;
let mut scores = HashMap::new();
scores.insert(String::from("Blue"), 10);
scores.insert(String::from("Yellow"), 50)

第二节

枚举 enum

枚举 Option

定义

enum Option<T>{
    None,
    Some(T),
}

使用

用 unwrap() 获取内部值

作用域 scope

就是作用范围吧

同一个作用域不能有两个相同名称的项 → C++ 中的变量名冲突

（可以使用一下工具来解决名称冲突？？？）

模块系统 the module system

模块系统可以将 crate 中的代码分组和封装，提高可读性和重用性

包 Packages

Cargo 的一个功能，允许构建、测试和分享 crate

包是提供一系列功能的一个或者多个 crate , 包含一个 Cargo.toml 文件

Crates

一个模块的树形结构，它形成了库或二进制项目

crate 是 Rust 在编译时最小的代码单位，有两种形式：二进制项和库

crate root 是一个源文件，是 crate 的根模块

crate 的约定

src/main.rs 是一个与包同名的二进制 crate 的 crate 根

src/lib.rs 是一个与包同名的库 crate 的 crate 根

src/bin 目录下的每个文件都会被编译成一个独立的二进制 crate

模块 Modules 和 use

允许你控制作用域和路径的私有性

use 关键字

可以在一个作用域内创建一个项的快捷方式，减少长路径的重复

类似于 Java 的导包？

as 关键字

配合 use 使用，就是给快捷方式重命名

一些调用项的方式

//例如 xxx 模块的 yyy 子模块下定义了一个 zzz
crate::xxx::yyy::zzz;

use crate::xxx::yyy::zzz;//之后就可以直接使用 zzz 了

use crate::xxx::yyy::zzz as z;

私有和公有

默认所有内容私有

pub 关键字

可以将模块或模块内的项标记为公开的

模块树

crate 根文件 (src/lib.rs 或 src/main.rs) 是 crate 模块结构的根，也是名为 crate 的隐式模块的根

在 crate 根文件中，可以声明新的模块

使用 mod 关键字和花括号或分号

mod a_module {
    //something...
}

如何寻找

内联（以大括号结尾时）

在文件 src/xxx.rs

在文件 src/xxx/mod.rs

在其它文件中，可以定义子模块

使用 mod 关键字和花括号或分号，并在以父模块命名的目录中寻找子模块代码

模块树可以用来展示 crate 中的模块层次结构，以及模块之间的父子和兄弟关系

路径 path

一个命名项（结构体、函数或模块等）的方式

绝对路径 absolute path

以 crate 根 (root) 开头的全路径

对于外部 crate 的代码，是以 crate 名开头的绝对路径

对于当前 crate 的代码，则以字面值 crate 开头

相对路径 relative path

从当前模块开始，以 self, super 或当前模块的标识符开头

绝对路径和相对路径都后跟一个或多个由双冒号分割的标识符

专业阶段- OS设计实现

📖 **学习经历：**本阶段的学习过程非常有启发性。作为我初次接触操作系统的经历，它帮我对操作系统的成功地祛魅，让我认识到其本质不过是一个为了实现提供用户态程序访问系统资源的接口以及对整个系统资源管理的 复杂程序。同时，详细的v3指导书也给我补充许多基础知识，让我对操作系统学习更有信心。

🤔

联想 ：操作系统的运行是被隐藏起来的，给用户态程序提供了资源调用接口。而人的意识也是直接嵌入在生物机体上，通过生物神经系统间接地获取对身体地掌控权力。从人类个体到整个社会也是如此，个人嵌入在社会运行的某一环节中，并且他通过这种方式来实现和获得自身，同时又通过整个社会的隐藏环节来获取权力。

第三章：多道程序与分时多任务系统

ch3 要求我们完成的任务具体要求如下：

• 实现系统调用 sys_task_info，系统调用号为 410
• 该系统调用需要返回当前任务的以下信息：
  • 任务状态（必定为 Running）
  • 任务使用的系统调用及其调用次数
  • 系统调用时刻距离任务第一次被调度时刻的时长（单位ms）
• 使用 TaskInfo 结构体来存储这些信息
• 系统调用成功时返回 0，失败时返回 -1
• 注意：调用 sys_task_info 本身也会被计入系统调用次数

思路：

sys_task_info 需要三个信息，我们一个一个来，

任务状态：第一个是任务状态，这个实现起来比较简单，甚至因为在这个系统里，查询的是当前任务的状态，因此 TaskStatus 一定是 Running。

系统调用时刻距离任务第一次被调度时刻的时长：我们需要的这个时长等于 当前时刻减去第一次被调度的时刻，当前时刻很好获取，利用get_time_ms()函数就可以直接获取，而另外一个 则需要为任务控制块添加新的字段 ，用于记录第一次被调度的时长，这样我们就可以通过任务管理器直接地获取某任务初次调用时刻了。

任务使用的系统调用及其调用次数:我的方法和提示里给出地方法相同 因为系统调用号一定小于 500，所以直接使用一个长为 MAX_SYSCALL_NUM=500 的数组做桶计数。同样也直接在 任务控制块中添加 数组，实现把各个任务的系统调用次数数组与该任务绑定。在此之后，我们直接到系统调用前syscall/mod.rs:syscall 增加相应任务的相应系统调用类型的调用次数即可。

最后我们直接创建一个TaskInfo类型保存如上三种数据，并利用sys_task_info中的*mut类型参数，把Taskinfo的内容传回用户态即可完成该功能。

总的来说作为第一个任务，用来熟悉内核编程，还算比较简单。

问答题-lab1

第四章：地址空间

ch4要求我们完成的具体内容如下：

重写 sys_get_time 和 sys_task_info
引入虚存机制后，原来内核的 sys_get_time 和 sys_task_info 函数实现就无效了。请你重写这个函数，恢复其正常功能。
mmap 和 munmap 匿名映射 mmap 在 Linux 中主要用于在内存中映射文件， 本次实验简化它的功能，仅用于申请内存。
请实现 mmap 和 munmap 系统调用，mmap 定义如下： fn** sys_mmap(start: usize, len: usize, port: usize) -> isize - syscall ID：222 - 申请长度为 len 字节的物理内存（不要求实际物理内存位置，可以随便找一块），将其映射到 start 开始的虚存，内存页属性为 port
参数：
start 需要映射的虚存起始地址，要求按页对齐
len 映射字节长度，可以为 0
port：第 0 位表示是否可读，第 1 位表示是否可写，第 2 位表示是否可执行。其他位无效且必须为 0
返回值：执行成功则返回 0，错误返回 1
说明： 为了简单，目标虚存区间要求按页对齐，len 可直接按页向上取整，不考虑分配失败时的页回收。
可能的错误： start 没有按页大小对齐 - port & !0x7 != 0 (port 其余位必须为0) - port & 0x7 = 0 (这样的内存无意义) - [start, start + len) 中存在已经被映射的页 - 物理内存不足

思路：

我们先说sys_get_time和sys task_info 这两个函数的重写：

首先我们来说说为什么这两个函数会失效，在ch3中我们的系统调用 利用*mut类型指针来将数据直接地写入用户态中的地址，但是在ch4中，我们将用户态和内核态都分别做了不同的地址映射，这导致我们没办法像ch3那样直接利用_ts来写入数据，因为ch4中传入的是用户态中的虚拟地址，必须借助页表机制，将虚拟地址转换为物理地址，来修改。获取 time 和 TaskInfo的步骤和之前ch3中提到的方式类似。

需要注意的是，我们写入的数据结构可能存在如下所示的跨页的问题，

/// YOUR JOB: get time with second and microsecond /// HINT: You might reimplement it with virtual memory management. /// HINT: What if [TimeVal] is splitted by two pages ?

所以我们不能把数据一次性全部写入，这里我选择的办法是将数据转换为字节数组 并依次写入。

mmap和unmmap:

首先来说mmap：

mmap需要实现的是将一段虚拟地址进行页面映射，想要实现这个功能，我们需要在进程的地址空间中加入添加新的页面映射，而该系统正好提供了为地址空间提供了insert_framed_area方法，用于插入新的逻辑段，这样的话情况就会变得很简单。

首先我们根据可能的错误对函数给出的参数进行对应的判断，并且通过port得到MapPermission。

if _start % PAGE_SIZE != 0 || _port & !0x7 != 0 || _port & 0x7 == 0 {
return -1;

}
let portpomis = Portpomiss::from_bits_truncate(_port as u8);
let mut flag:MapPermission=MapPermission::empty();
flag|=MapPermission::U;
if portpomis.contains(Portpomiss::R){
     flag|=MapPermission::R;
}
if portpomis.contains(Portpomiss::W){
     flag|=MapPermission::W;
}
if portpomis.contains(Portpomiss::X){
    flag|=MapPermission::X;
}

之后我们检查虚拟页面是否已经被映射过

for vpn in vpn_range {
    if let Some(pte) = inner.tasks[cur].memory_set.translate(vpn) {
        if pte.is_valid() {
            return -1;
        }
    }
}

最后我们直接添加页面映射

inner.tasks[id].memory_set.insert_framed_area(_start, _end, port);

问答题-lab2

第五章：进程及进程管理

ch5要求我们具体完成的内容如下:

spawn 系统调用定义( 标准spawn看这里 )：

`fn sys_spawn(path: *const u8) -> isize`

• syscall ID: 400
• 功能：新建子进程，使其执行目标程序。
• 说明：成功返回子进程id，否则返回 -1。
• 可能的错误：
  • 无效的文件名。
  • 进程池满/内存不足等资源错误。

TIPS：虽然测例很简单，但提醒读者 spawn 不必 像 fork 一样复制父进程的地址空间。

stride 调度算法

算法描述如下:

(1) 为每个进程设置一个当前 stride，表示该进程当前已经运行的“长度”。另外设置其对应的 pass 值（只与进程的优先权有关系），表示对应进程在调度后，stride 需要进行的累加值。

1. 每次需要调度时，从当前 runnable 态的进程中选择 stride 最小的进程调度。对于获得调度的进程 P，将对应的 stride 加上其对应的步长 pass。
2. 一个时间片后，回到上一步骤，重新调度当前 stride 最小的进程。

可以证明，如果令 P.pass = BigStride / P.priority 其中 P.priority 表示进程的优先权（大于 1），而 BigStride 表示一个预先定义的大常数，则该调度方案为每个进程分配的时间将与其优先级成正比。证明过程我们在这里略去，有兴趣的同学可以在网上查找相关资料。

其他实验细节：

• stride 调度要求进程优先级 ≥2，所以设定进程优先级 ≤1 会导致错误。
• 进程初始 stride 设置为 0 即可。
• 进程初始优先级设置为 16。

为了实现该调度算法，内核还要增加 set_prio 系统调用

思路：

我们先说spawn系统调用:

就如同TIPS一样，我们不需要复制父进程的地址空间，

pub fn sys_spawn(_path: *const u8) -> isize {
    trace!(
        "kernel:pid[{}] sys_spawn NOT IMPLEMENTED",
        current_task().unwrap().pid.0
    );
    let current_task = current_task().unwrap();
    let token =current_user_token();
    let path = translated_str(token, _path);
    let tcb=Arc::new(TaskControlBlock::new(get_app_data_by_name(path.as_str()).unwrap()));
    let mut inner=tcb.inner_exclusive_access();
    let mut pin=current_task.inner_exclusive_access();
    inner.parent=Some(Arc::downgrade(&current_task));
    pin.children.push(tcb.clone());
    drop(inner);
    let pid = tcb.pid.0 as isize;
    add_task(tcb);
    pid
}

我们直接用 app_data来创建TaskControlBlock而跳过了复制父进程的地址空间，并将他连接到父进程的子进程上，这样才能在sys_waitpid中被遍历到。然后把他加入任务管理器。就可以通过测试。

stride 调度算法：

时间原因暂未实现..

问答题-lab3

第六章：文件系统与I/O重定向

ch6要求我们具体完成的内容如下:

硬链接

硬链接要求两个不同的目录项指向同一个文件，在我们的文件系统中也就是两个不同名称目录项指向同一个磁盘块。

本节要求实现三个系统调用 sys_linkat、sys_unlinkat、sys_stat 。

linkat：

syscall ID: 37功能：创建一个文件的一个硬链接， linkat标准接口 。Ｃ接口： int linkat(int olddirfd, char* oldpath, int newdirfd, char* newpath, unsigned int flags)Rust 接口： fn linkat(olddirfd: i32, oldpath: *const u8, newdirfd: i32, newpath: *const u8, flags: u32) -> i32参数：olddirfd，newdirfd: 仅为了兼容性考虑，本次实验中始终为 AT_FDCWD (-100)，可以忽略。flags: 仅为了兼容性考虑，本次实验中始终为 0，可以忽略。oldpath：原有文件路径newpath: 新的链接文件路径。说明：为了方便，不考虑新文件路径已经存在的情况（属于未定义行为），除非链接同名文件。返回值：如果出现了错误则返回 -1，否则返回 0。可能的错误链接同名文件。

unlinkat:

syscall ID: 35功能：取消一个文件路径到文件的链接, unlinkat标准接口 。Ｃ接口： int unlinkat(int dirfd, char* path, unsigned int flags)Rust 接口： fn unlinkat(dirfd: i32, path: *const u8, flags: u32) -> i32参数：dirfd: 仅为了兼容性考虑，本次实验中始终为 AT_FDCWD (-100)，可以忽略。flags: 仅为了兼容性考虑，本次实验中始终为 0，可以忽略。path：文件路径。说明：注意考虑使用 unlink 彻底删除文件的情况，此时需要回收inode以及它对应的数据块。返回值：如果出现了错误则返回 -1，否则返回 0。可能的错误文件不存在。

fstat:

syscall ID: 80功能：获取文件状态。Ｃ接口： int fstat(int fd, struct Stat* st)Rust 接口： fn fstat(fd: i32, st: *mut Stat) -> i32参数：fd: 文件描述符st: 文件状态结构体#[repr(C)]
#[derive(Debug)]
pub struct Stat {
/// 文件所在磁盘驱动器号，该实验中写死为 0 即可 pub dev: u64,
/// inode 文件所在 inode 编号 pub ino: u64,
/// 文件类型 pub mode: StatMode,
/// 硬链接数量，初始为1 pub nlink: u32,
/// 无需考虑，为了兼容性设计 pad: [u64; 7],
}

/// StatMode 定义：bitflags! {
pub struct StatMode: u32 {
const NULL = 0;
/// directory const DIR = 0o040000;
/// ordinary regular file const FILE = 0o100000;
}
}

我们先来实现fstat:

fstat需要我们先得到三个位置信息分别是

/// inode 文件所在 inode 编号 pub ino: u64,
/// 文件类型 pub mode: StatMode,
/// 硬链接数量，初始为1 pub nlink: u32,

inode 文件所在 inode 编号：

在rcore系统的内核中，似乎没有提供能直接从OSinode得到inode id的接口，所以有两种办法，一种是去修改Easy-fs，另有一种方法是在OSinode被创建的时候给他们分配id。在这里我使用的是后者。

在OSinode结构体中添加如下结构体

pub struct Ino{ link:u32, ino:u64, }

然后再每次打开文件之后对OSinode 使用一个bitmap来分配 id，在文件关闭时用bitmap来回收id；

bitmap在 easyfs中的bitmap.rs有相应实现。我们只需要利用bitmap的alloc和dealloc来实现id的分配和回收。

其中文件类型，可以通过使用 read_disk_inode 获取 inode 对应的 DiskInode 的只读引用，并从中读取相关信息即可。

最后是硬链接数量，该信息显然需要结合link 与 unlink来维护，我们在link时通过刚刚所分配的id，来进行映射即可

ITOS.get_mut(&op).unwrap().link+=1;

ps:ITOS是一个BTreeMap 可以通过文件名来获取或者修改对应的 Ino结构体。

我们再来实现link与unlink:

首先我们刚刚已经为文件进行了id的分配，我们继续利用先前所分配的id，进行管理。

首先我储存了新的名字和磁盘块原名之间的映射，在文件open与close前，将输入的名字（如果已经被映射）替换为原名来实现两个不同名称目录项指向同一个磁盘块。

如下：

if unsafe {
UMAP2.contains_key(&path1)
}{
{
        path = unsafe { UMAP2 [&path1].clone()};

    }
}
else {
    path =path1;
}

unlink的逻辑也与link类似，通过用BTreeMap的remove方法将映射删除。
但是要特别注意的是，当link为0时，我们需要回收inode id

let  c= unsafe { ITOS .get_mut(&name).unwrap()};
if c.link>0{ 
        c.link-=1;
       }
       else{
         let fd=unsafe { UMAP1.get(&name).unwrap() };
         let bind=current_task().unwrap();
         let inner=bind.inner_exclusive_access().fd_table[*fd].clone().unwrap();
         inner.clear();

       }

向前兼容：

唯一要注意的点就是在spawn 中，我们需要用ch6新建立的文件系统来获取应用数据，而不是像ch4一样用translated_str方法直接获取应用数据。

let Some(app_inode) = open_file(path.as_str(), OpenFlags::RDONLY)

向前兼容的其他方面都与先前类似。

问答题-lab4

第八章：并发

ch8要求我们具体完成的内容如下:

死锁检测

目前的 mutex 和 semaphore 相关的系统调用不会分析资源的依赖情况，用户程序可能出现死锁。 我们希望在系统中加入死锁检测机制，当发现可能发生死锁时拒绝对应的资源获取请求。 一种检测死锁的算法如下：

定义如下三个数据结构：

• 可利用资源向量 Available ：含有 m 个元素的一维数组，每个元素代表可利用的某一类资源的数目， 其初值是该类资源的全部可用数目，其值随该类资源的分配和回收而动态地改变。 Available[j] = k，表示第 j 类资源的可用数量为 k。
• 分配矩阵 Allocation：n * m 矩阵，表示每类资源已分配给每个线程的资源数。 Allocation[i,j] = g，则表示线程 i 当前己分得第 j 类资源的数量为 g。
• 需求矩阵 Need：n * m 的矩阵，表示每个线程还需要的各类资源数量。 Need[i,j] = d，则表示线程 i 还需要第 j 类资源的数量为 d 。

算法运行过程如下：

1. 设置两个向量: 工作向量 Work，表示操作系统可提供给线程继续运行所需的各类资源数目，它含有 m 个元素。初始时，Work = Available ；结束向量 Finish，表示系统是否有足够的资源分配给线程， 使之运行完成。初始时 Finish[0..n-1] = false，表示所有线程都没结束；当有足够资源分配给线程时， 设置 Finish[i] = true。
2. 从线程集合中找到一个能满足下述条件的线程

1Finish[i] == false; 2Need[i,j] ≤ Work[j];

若找到，执行步骤 3，否则执行步骤 4。

1. 当线程 thr[i] 获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行:

1Work[j] = Work[j] + Allocation[i, j]; 2Finish[i] = **true**;

跳转回步骤2

1. 如果 Finish[0..n-1] 都为 true，则表示系统处于安全状态；否则表示系统处于不安全状态，即出现死锁。

出于兼容性和灵活性考虑，我们允许进程按需开启或关闭死锁检测功能。为此我们将实现一个新的系统调用： sys_enable_deadlock_detect 。

enable_deadlock_detect：

• syscall ID: 469
• 功能：为当前进程启用或禁用死锁检测功能。
• C 接口： int enable_deadlock_detect(int is_enable)
• Rust 接口： fn enable_deadlock_detect(is_enable: i32) -> i32
• 参数：
  • is_enable: 为 1 表示启用死锁检测， 0 表示禁用死锁检测。
• 说明：
  • 开启死锁检测功能后， mutex_lock 和 semaphore_down 如果检测到死锁， 应拒绝相应操作并返回 -0xDEAD (十六进制值)。
  • 简便起见可对 mutex 和 semaphore 分别进行检测，无需考虑二者 (以及 waittid 等) 混合使用导致的死锁。
• 返回值：如果出现了错误则返回 -1，否则返回 0。
• 可能的错误
  • 参数不合法
  • 死锁检测开启失败

思路：

要为锁机制实现死锁检测，关键在于如何维护相关状态，并在检测前构造出合适的资源分配结构。我们可以从mutex开始：每个线程最多只需要一把锁，因为线程只有在获取所需的锁资源后才能继续执行，若没有锁资源可用，线程将会被阻塞。因此，为每个线程分配一个 mutex_need 变量，用来记录当前线程所需的锁的 id。

除此之外，我们还需要维护一个 mutex_allocation 向量，记录线程当前已获得但未释放的锁资源的 id。当线程调用 sys_mutex_lock(mutex_id) 请求锁时，在实际获取锁前，我们将当前线程的 mutex_need 设置为 mutex_id。当线程成功获得锁时，将 mutex_id 加入 mutex_allocation 向量，并将 mutex_need 置为空。这里可以使用 usize::MAX 来表示空值，也可以使用 Option 类型，后者更为优雅。

当线程调用 sys_mutex_unlock(mutex_id) 释放锁时，在实际释放锁前，首先查找并移除 mutex_allocation 向量中对应的 mutex_id 元素。

通过这种方式，我们能够在死锁检测之前，根据维护的信息构建出 Available、Allocation 和 Need 数据结构，进而使用银行家算法判断当前系统是否处于不安全状态。信号量的实现方式大致相同，但由于信号量的数量不再是二值的，因此线程的资源分配向量需要记录每个信号量的数量。我们可以用 <sem_id, cnt> 这样的二元组来表示，或者也可以使用 cnt 个 sem_id 元素。在这里，我采用前者。

此外，信号量还可以为负数，负值的绝对值表示资源的提前“透支”数量。在银行家算法中，Available[i][j] 不应为负值，若出现负数，应视为 0 处理。

fn deadlock_check(available: Vec<usize>, allocation: Vec<Vec<usize>>, need: Vec<Vec<usize>>) -> bool {
        // n: thread count  m: resources count
        let (n, m) = (allocation.len(), allocation[0].len());
        let mut work = available;
        let mut finish = vec![false; n];
        loop {
            let mut idx = usize::MAX;
            for i in 0..n {
                let mut flag = true;
                if finish[i] {
                    continue;
                }
                for j in 0..m {
                    if need[i][j] > work[j] {
                        flag = false;
                        break;
                    }
                }
                if flag {
                    idx = i;
                    break;
                }
            }
            // has found a thread meet the requirement
            if idx != usize::MAX {
                for j in 0..m {
                    work[j] += allocation[idx][j];
                }
                finish[idx] = true;
            } else {
                break;
            }
        }
        finish.iter().all(|&x| x)
    }

问答题-lab5

---