rcore-os Blog
0%

Posted on Edited on In

Chapter 8-2

Introduction

We will develop exclusion mechanism previously mentioned.

Beside construction, we need to abstract possible situation of data sharing. A usual native thought is a thread want to modify one thing but due to thread switch, the data is already modified and we get wrong result. So based on this, we want a operation to be Atomic, which means the operation excluding others. Now we can alleviate this restriction and generalize this.

Generalization:

  • Allow multiple but finite thread can join one atomic operation.
  • Allow condition of atomic operation.

Before such generalization, we want a way to represent atomic operation. We call the content of this operation Critical Section, and multiple threads operations in indeterminate time sequence Race Condition. So the basic problem of data sharing push us to identify multiple different operations by different threads, we can’t restrict data because the problem is on modification by threads, we need to Lock operations!

So, it there’s a lock sharing by threads, each threads can declare Lock it!, and no other threads can access this thread again.

Now, back to our generalization. If this lock has a bound of access number, many can access until reaching a bound. That’s also a reasonable design, we call this Semaphore; If this lock has a signal which one thread can send it to others to allow others to access it, That’s also a reasonable design, we call this Condition Variable.

If the real minimal sharing thing is Lock rather than data, we can discard so called data problem, and focus on lock itself, each threads can do anything in this lock and excluding others.

Design

No matter which kinds of lock, this is shared among threads.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
pub struct ProcessControlBlock {
    // immutable
    pub pid: PidHandle,
    // mutable
    inner: UPSafeCell<ProcessControlBlockInner>,
}
pub struct ProcessControlBlockInner {
    ...
    pub lock_list: Vec<Option<Arc<Lock>>>,
}

pub struct Lock {
    pub inner: UPSafeCell<LockInner>,
}
pub struct LockInner {
	pub data: ...
    pub wait_queue: VecDeque<Arc<TaskControlBlock>>,
}

In such design, one lock can push one thread to wait_queue to stop it, and pop front to start it. data is a generalization for various locks.

Then, in one process, it owns many locks used in various conditions, one can easily take it as a generalization of many data(actually nothing related to real data) we want to share.

Basic Lock

Now, we want to construct a basic lock allowing simple lock, unlock operation.

1
2
3
4
pub trait Mutex: Sync + Send {
    fn lock(&self);
    fn unlock(&self);
}

Usually, there’s U-level, M-level, S-level implementation. First, we gonna try first one easily, knowing the heuristic design of M-level, and extend basic thought to S-level.

U-level

A naive approach is to declare a global boolean indicating block state. lock will wait if the boolean is true and try to set it to true, and unlock will set it to false to release.

1
2
3
4
5
6
7
8
9
10
static mut mutex :i32 = 0;

fn lock(mutex: i32) {
    while (mutex);
    mutex = 1;
}

fn unlock(mutex: i32){
    mutex = 0;
}

However, that’s wrong! We can’t construct lock by things we want to lock! Threads can jump in any instructions and break it! That’s means we can’t do it in U-level? We should ponder further in real situation, imagine two threads modify one thing in nearly same time, if we could set two global state in a operation that excluding each other(for example, one state set to 1 and another state set to 0), then only one operation can really be implemented and we can check this condition, allow it to get the lock.

1
2
3
4
5
6
7
8
9
10
11
12
static mut flag : [i32;2] = [0,0]; // 哪个线程想拿到锁？
static mut turn : i32 = 0;         // 排号：轮到哪个线程? (线程 0 or 1?)

fn lock() {
    flag[self] = 1;             // 设置自己想取锁 self: 线程 ID
    turn = 1 - self;            // 设置另外一个线程先排号
    while ((flag[1-self] == 1) && (turn == 1 - self)); // 忙等
}

fn unlock() {
    flag[self] = 0;             // 设置自己放弃锁
}

Now analyze the code, we find that no matter which flag is 1, or both 1, indicating certain thread want to get lock, turn will be a excluding state to flag, which means if another thread modify turn in same time, the turn can only be in one of the state and only one thread can get the lock.

M-level

Is there any predefined operation in instructions that is atomic? Then we can use it as a lock. The answer is Yes, in RISC-V, it’s:

  • AMO: Atomic memory operation
  • LR/SC: Load Reserved/Store Conditional

AMO: will read the value in memory and write new value, then store the old value to target register(s.t. amoadd.w rd, rs2, (rs1)).

LR/SC: LR will read memory and store in target register, and leave the addr of this memory, then SC could check the addr and write data to this addr, output a condition(0/1) to target register.(s.t. lr.w rd, (rs1), sc.w rd, rs2, (rs1))

We can use it to implement a atomic function:

1
2
3
4
5
6
7
8
9
10
# RISC-V sequence for implementing a TAS  at (s1)
li t2, 1                 # t2 <-- 1
Try: lr  t1, s1          # t1 <-- mem[s1]  (load reserved)
        bne t1, x0, Try     # if t1 != 0, goto Try:
        sc  t0, s1, t2      # mem[s1] <-- t2  (store conditional)
        bne t0, x0, Try     # if t0 !=0 ('sc' Instr failed), goto Try:
Locked:
        ...                 # critical section
Unlock:
        sw x0,0(s1)         # mem[s1] <-- 0

Here the logic of Try is mem[s1] would be zero if it’s unlocked, and would be non-zero if it’s locked. So, Try will compare t1 and x0, actually mem[s1] and 0, if equal to zero, then try to store t2 into s1, if succeed, it will compare it again for the output signal t0 and x0, actually the output signal and 0, if succeed, it will jump out otherwise repeat.In this process, if the write operation failed, t0 would be non-zero, and repeat in Try.

If we want to Unlock, we write x0 to s1 to set mem[s1] to zero. Which is the unlocked state.

S-level

Then we could take the function to rust and package it. A simple refactor is when we in repetition loop, we yield, and give CPU to others.

Now, for any kinds of locks, we could apply it to our structure.

First, when we create a lock, we create and push it to list or set in empty element.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// os/src/syscall/sync.rs
pub fn sys_mutex_create(blocking: bool) -> isize {
    let process = current_process();
    let mutex: Option<Arc<dyn Mutex>> = if !blocking {
        Some(Arc::new(MutexSpin::new()))
    } else {
        Some(Arc::new(MutexBlocking::new()))
    };
    let mut process_inner = process.inner_exclusive_access();
    if let Some(id) = process_inner
        .mutex_list
        .iter()
        .enumerate()
        .find(|(_, item)| item.is_none())
        .map(|(id, _)| id)
    {
        process_inner.mutex_list[id] = mutex;
        id as isize
    } else {
        process_inner.mutex_list.push(mutex);
        process_inner.mutex_list.len() as isize - 1
    }
}

When we call lock, we should provide corresponding id of the lock, if it’s already locked, we push to wait_queue, else we lock it and goes on.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// os/src/syscall/sync.rs
pub fn sys_mutex_lock(mutex_id: usize) -> isize {
    let process = current_process();
    let process_inner = process.inner_exclusive_access();
    let mutex = Arc::clone(process_inner.mutex_list[mutex_id].as_ref().unwrap());
    drop(process_inner);
    drop(process);
    mutex.lock();
    0
}
// os/src/sync/mutex.rs
impl Lock for MutexBlocking {
    fn lock(&self) {
        let mut mutex_inner = self.inner.exclusive_access();
        if ... {
            mutex_inner.wait_queue.push_back(current_task().unwrap());
			// ... other operations
            drop(mutex_inner);
            block_current_and_run_next();
        } else {
			// ... other operations
        }
    }
}

Same reverse operation:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// os/src/syscall/sync.rs
pub fn sys_mutex_unlock(mutex_id: usize) -> isize {
    let process = current_process();
    let process_inner = process.inner_exclusive_access();
    let mutex = Arc::clone(process_inner.mutex_list[mutex_id].as_ref().unwrap());
    drop(process_inner);
    drop(process);
    mutex.unlock();
    0
}
// os/src/sync/mutex.rs
impl Mutex for MutexBlocking {
    fn unlock(&self) {
        let mut mutex_inner = self.inner.exclusive_access();
		// ... other operation
		if ... {
			if let Some(waking_task) = mutex_inner.wait_queue.pop_front() {
				add_task(waking_task);
			}
		}
    }
}

Semaphore

It’s simple, we only need to switch boolean to number and check the bound. So, the initiated count is the bound, if one thread access, it will minus one, and release, add one. We only need to check positive or negative.

Apply our structure:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
pub fn up(&self) {
    let mut inner = self.inner.exclusive_access();
    inner.count += 1;
    if inner.count <= 0 {
        if let Some(task) = inner.wait_queue.pop_front() {
            add_task(task);
        }
    }
}

pub fn down(&self) {
    let mut inner = self.inner.exclusive_access();
    inner.count -= 1;
    if inner.count < 0 {
        inner.wait_queue.push_back(current_task().unwrap());
        drop(inner);
        block_current_and_run_next();
    }
}

If the initiated count equal to 1, we back to mutex!, which indicates sole thread access!

Actually, we could use it for synchronization operation, we set count to 0, if one thread access, it will be blocked, and another thread will could release and add one to count, then the original thread finally could access. Then the second thread will always be advanced to first one.

Here, the first is always advanced to second.

1
2
3
4
5
6
7
8
9
10
11
12
13
const SEM_SYNC: usize = 0; //信号量ID
unsafe fn first() -> ! {
    sleep(10);
    println!("First work and wakeup Second");
    semaphore_up(SEM_SYNC); //信号量V操作
    exit(0)
}
unsafe fn second() -> ! {
    println!("Second want to continue,but need to wait first");
    semaphore_down(SEM_SYNC); //信号量P操作
    println!("Second can work now");
    exit(0)
}

Conditional Variable

If we want one thread owns the ability of release lock for others, we need the CondVar. We have to dispatch operation in wait_queue, if one thread signal others, it will pop out a thread, which means trigger it You are free!. And if one thread wait, it will push itself to queue to wait, The unlock and lock is important because in wait operation, it allow other thread to modify condition, but it should be after of the push operation, in case that the signal is before the push, then we can never receive the signal again! We won’t encapsulate condition check to CondVar because it should leave to user to design it, we only leave out interface for user.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
pub fn signal(&self) {
	let mut inner = self.inner.exclusive_access();
	if let Some(task) = inner.wait_queue.pop_front() {
		add_task(task);
	}
}
pub fn wait(&self, mutex: Arc<dyn Mutex>) {
    let mut inner = self.inner.exclusive_access();
    inner.wait_queue.push_back(current_task().unwrap());
    drop(inner);
    mutex.unlock();                 
    block_current_and_run_next();
    mutex.lock();
}

However, if condition check is leave out to user, we can’t ensure the condition be violated due to data sharing, so usually we need to append mutex lock for this section.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
static mut A: usize = 0;   //全局变量

const CONDVAR_ID: usize = 0;
const MUTEX_ID: usize = 0;

unsafe fn first() -> ! {
    sleep(10);
    println!("First work, Change A --> 1 and wakeup Second");
    mutex_lock(MUTEX_ID);
    A=1;
    condvar_signal(CONDVAR_ID);
    mutex_unlock(MUTEX_ID);
    ...
}
unsafe fn second() -> ! {
    println!("Second want to continue,but need to wait A=1");
    mutex_lock(MUTEX_ID);
    while A==0 {
        condvar_wait(CONDVAR_ID, MUTEX_ID);
    }
    mutex_unlock(MUTEX_ID);
    ...
}

We can see that if A=1, second won’t wait repeatly, and goes out.

Posted on Edited on In

Day-1

Component Kernel

Based on experiment, we will construct kernel in increment by demand.

  • UniKernel: Single S-Level, App is within kernel.

Each kernel instance can be considered as a construction based on unikernel.

  • MacroKernel: Manage U-Level with support on multiple apps, process management etc…
  • Hypervisor: Virtual state with restricted communication between U-level and S-level.

Aceros Design

1
2
3
graph TD
    App <--> Runtime
    Runtime <--> HAL

The design of Aceros is simple, first HAL(axhal) is the abstraction of hardware to initiation trap, stack, MMU, registers based on various architectures. Then Runtime(ax*) will be classified as many components to support various environments, like net, task, fs etc…

Each arrow is reversible, in boot, it will be from bottom to top to initiate App. Then when App call something, it will be from top to bottom to evoke functionality.

In real situation, we choose thing based on features. 

1
2
3
4
5
6
7
8
graph TD
	App --> axstd
	axstd --> |axfeat| aceros_api
	aceros_api --> axruntime
	axruntime -->|alloc| axalloc
	axruntime --> axhal
	axruntime -->|irq| irq
	axruntime -->|multitask| axtask

Posted on Edited on In

Day-2

Paging

We delve into paging.

Example

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/// Physical address for pflash#1
const PFLASH_START: usize = 0x2200_0000;

#[cfg_attr(feature = "axstd", no_mangle)]
fn main() {
    // Makesure that we can access pflash region.
    let va = phys_to_virt(PFLASH_START.into()).as_usize();
    let ptr = va as *const u32;
    unsafe {
        println!("Try to access dev region [{:#X}], got {:#X}", va, *ptr);
        let magic = mem::transmute::<u32, [u8; 4]>(*ptr);
        println!("Got pflash magic: {}", str::from_utf8(&magic).unwrap());
    }
}

PFlash is the simulation of flash memory of qemu. When qemu boot, it will automatically load file to fixed MMIO, and can be directly accessed.

Paging: feature = ["paging"] is the way to evoke virtual memory management tu support MMIO. Located in axruntime.

The workflow would be:

  • qemu fdt: from 0x0c00_0000 to 0x3000_0000. Construct the space of device.
  • SBI: from 0x8000_0000 to 0x8020_0000. RISC-V Supervisor Binary Interface, it construct a interface for programming language to manipulate device level things.
  • Kernel Image: from 0x8020_0000. _skernel contains S-level things like static data, code etc… _ekernel is user thing.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#[link_section = ".data.boot_page_table"]
static mut BOOT_PT_SV39: [u64; 512] = [0; 512];

unsafe fn init_boot_page_table() {
    // 0x8000_0000..0xc000_0000, VRWX_GAD, 1G block
    BOOT_PT_SV39[2] = (0x80000 << 10) | 0xef;
    // 0xffff_ffc0_8000_0000..0xffff_ffc0_c000_0000, VRWX_GAD, 1G block
	// shift 10 bits to store flags
    BOOT_PT_SV39[0x102] = (0x80000 << 10) | 0xef;
}

unsafe fn init_mmu() {
    let page_table_root = BOOT_PT_SV39.as_ptr() as usize;
    satp::set(satp::Mode::Sv39, 0, page_table_root >> 12);
    riscv::asm::sfence_vma_all();
}

Each entry of page table will map 1G(0x4000_0000) memory. From 0x8000_0000 to 0xc0000_0000 at pgd_idx = 2 to 0xffff_ffc0_8000_0000 to 0xffff_ffc0_c000_0000 at pgd_idx = 102. This will map to a bigger range.

Task

Example

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
let worker = thread::spawn(move || {
	println!("Spawned-thread ...");

	// Makesure that we can access pflash region.
	let va = phys_to_virt(PFLASH_START.into()).as_usize();
	let ptr = va as *const u32;
	let magic = unsafe {
		mem::transmute::<u32, [u8; 4]>(*ptr)
	};
	if let Ok(s) = str::from_utf8(&magic) {
		println!("Got pflash magic: {s}");
		0
	} else {
		-1
	}
});

Each task will be in concurrency and dispatched by strategy. If it’s blocked, it will be moved to wait_queue to wait. If it’s ready, it will be moved to run_queue which is scheduler to be dispatched.

Message Communication

Example

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
let q1 = Arc::new(SpinNoIrq::new(VecDeque::new()));
let q2 = q1.clone();

let worker1 = thread::spawn(move || {
    println!("worker1 ...");
    for i in 0..=LOOP_NUM {
        println!("worker1 [{i}]");
        q1.lock().push_back(i);
        // NOTE: If worker1 doesn't yield, others have
        // no chance to run until it exits!
        thread::yield_now();
    }
    println!("worker1 ok!");
});

let worker2 = thread::spawn(move || {
    println!("worker2 ...");
    loop {
        if let Some(num) = q2.lock().pop_front() {
            println!("worker2 [{num}]");
            if num == LOOP_NUM {
                break;
            }
        } else {
            println!("worker2: nothing to do!");
            // TODO: it should sleep and wait for notify!
            thread::yield_now();
        }
    }
    println!("worker2 ok!");
});

Cooperative Scheduling: Each tasks kindly yield themselves or exit otherwise it will block everyone because the power of CPU occupation is ownned by each tasks.

Preemptive Scheduling: Each tasks will be automatically suspended by external condition: No lock, no device access; inner condition: run out of current time slice. We can use a disable_count to record this, even for multiple condition restriction, we can sum them up.

1
2
3
4
5
6
7
8
axhal::irq::register_handler(TIMER_IRQ_NUM, || {
    update_timer();
    #[cfg(feature = "multitask")]
    axtask::on_timer_tick();
});

// Enable IRQs before starting app
axhal::arch::enable_irqs()

on_timer_tick will be trigger in time slice. When time ticker ticks, run_queue will check and suspend task if possible.

We can make it more dynamic. Which means each task has priority and during the implementation of cpu, each task has a vruntime to be dynamically adjusted by init_vruntime + (delta/weight(nice)) where delta and nice are dynamic adjustment number. delta will be incremented by timer, weight(nice) is actually the priority of the task. We ensure that task with lowest vruntime will be placed at top.

Posted on Edited on In

Day-4

Hypervisor

A physical computer system can build multiple virtual computer system with its own virtual resources. Just like apps in U-level, each virtual system will consider themselves uniquely occupies these resources.

Emulator like a interpretor to stimulate a virtual system while in loose demand of efficiency.

Hypervisor will execute most instructions directly as a isomorphism of the stimulated virtual system to gain a huge efficiency.

*I type: Each virtual OS is equal on hardware.
*II type: Virtual OS is on host OS.

Each instance as Guest(OS Image) be loaded on our host os kernel.

Design

Only focus on hypervisor(I type).

Levels are extended, because we need to separate host and guest, so U-Level become U, VU-Level. So does the kernel level because we need to separate host, the hypervisor and guest, the virtual OS. So S-Level become HS, VS-Level.

Communication

Instructions will be implemented in communication of HS and VS, when there’s a sbi-call, VS will communicate HS to implement.

In hstatus of RISC-V, design the virtualization mode:

SPV: the source of HS or VS, which determines the sret to VU or U.
SPVP: the permission of modification of memory that HS to V.

We need to store guest context and host context, then switch between ret(VM-Exit) and sret. We implement this by run_guest and guest_exit which both is the other’s reverse.

Timer will be injected to sbi-call by setting a virtual clock in VS, when set timer, we clear timer of guest and set timer of host; when interrupt, we set clear timer of host and set timer of guest waiting for next request of timer.

Memory will be separated based on guest and host too. GVA will be a map of GPA as guest memory. However, HPA take responsibility of handle GPA as the virtualization process.

Dev will record each start vaddr and when VM-Exit of PageFault, it will findvmdevs.find(addr) and call handle_mmio for corresponding request.

Posted on Edited on In

Day-3

Device

In common, devices can be separated to FS, Net, Dispaly.

1
2
3
4
5
6
7
8
9
10
11
12
13
/// A structure that contains all device drivers, organized by their category.
#[derive(Default)]
pub struct AllDevices {
    /// All network device drivers.
    #[cfg(feature = "net")]
    pub net: AxDeviceContainer<AxNetDevice>,
    /// All block device drivers.
    #[cfg(feature = "block")]
    pub block: AxDeviceContainer<AxBlockDevice>,
    /// All graphics device drivers.
    #[cfg(feature = "display")]
    pub display: AxDeviceContainer<AxDisplayDevice>,
}

Devices will be initiated in axruntime, where axdriver module will be loaded to seek each device and mount drivers.

In qemu, virtio-mmio will send request to probe driver response otherwise return 0 as non-driver.

Block Driver

Block driver provide interface to write and read block providing IO operations and perennial storage.

Aceros use module axfs, with definition of interface vfs, and concrete implementation of ramfs and devfs.

Monolith

In U-Level, we will separate kernel memory and user memory, allowing user context used for process.

The basic logic would be construct new user space,load file to it and initiate user stack, then spawn user task with app_entry.

The top of page root would be shared as kernel space, and below would be independent as user space.

In user space separation, many kinds of resources can’t be shared as global resources, rather the demand of TaskExt as a reference to those independent resources owned by each user apps.

In TaskInner, we store the ptr of TaskExt by macro declaration of such type.

1
2
3
4
struct AxTask {
    ...
    task_ext_ptr: *mut u8
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/// Task extended data for the monolithic kernel.
pub struct TaskExt {
    /// The process ID.
    pub proc_id: usize,
    /// The user space context.
    pub uctx: UspaceContext,
    /// The virtual memory address space.
    pub aspace: Arc<Mutex<AddrSpace>>,
}

// It will expanded as a trait implmentation of reference to ptr as the `TaskExt` type.
def_task_ext!(TaskExt)

pub fn spawn_user_task(aspace: Arc<Mutex<AddrSpace>>, uctx: UspaceContext) -> AxTaskRef {
    let mut task = TaskInner::new(
        || {
            let curr = axtask::current();
            let kstack_top = curr.kernel_stack_top().unwrap();
            ax_println!(
                "Enter user space: entry={:#x}, ustack={:#x}, kstack={:#x}",
                curr.task_ext().uctx.get_ip(),
                curr.task_ext().uctx.get_sp(),
                kstack_top,
            );
            unsafe { curr.task_ext().uctx.enter_uspace(kstack_top) };
        },
        "userboot".into(),
        crate::KERNEL_STACK_SIZE,
    );
    task.ctx_mut()
        .set_page_table_root(aspace.lock().page_table_root());
    task.init_task_ext(TaskExt::new(uctx, aspace));
    axtask::spawn_task(task)
}

NameSpace

To reuse resources, we will construct a axns_resource section in compilation to form a global namespace. Each will be shared by Arc::new().

If there’s a demand of uniqueness, we will allocate space and copy them.

Page Fault

We could implement lazy allocation of user space memory. We register PAGE_FAULT for our function and call handle_page_fault for AddrSpace.

1
2
3
4
5
6
7
8
9
10
impl AddrSpace
pub fn handle_page_fault(...) -> ...
        if let Some(area) = self.areas.find(vaddr) {
            let orig_flags = area.flags();
            if orig_flags.contains(access_flags) {
                return area
                    .backend()
                    .handle_page_fault(vaddr, orig_flags, &mut self.pt);
            }
        }

MemoryArea has two way:

  • Linear: direct construct map relation of memory based on physical contiguous mmemory.
  • Alloc: only construct null-map, and call handle_page_fault to really allocate memory.

User App

ELF is the default format of many apps. Kernel take the responsibility to load app to correct region.

Notice the offset of file and virtual space may be different due to optimization of ELF.

In order to load apps from linux, we will construct a Posix Api given interface mimic to linux.

Posted on Edited on

起点

十多年前的一个下午，我坐在电脑前，刷完了所有周常任务。游戏公会里最后一位成员下线回老家吃饭。连续在线十几个小时后，我退出游戏、关掉电源，一股巨大的空虚感突然涌上心头。

我毕业于青岛一所专科院校计算机专业，从达内培训班结业后，进入一家对日外包公司，维护着1995年开发的VB6.0程序。在青岛，月薪三千元省吃俭用才能勉强度日。我总觉得自己的能力不止于此，人生不该是这副模样。

想要改变却毫无方向，既缺资源又缺机会。

后来在网上翻帖，听说《计算机程序设计艺术》是计算机领域的圣经。这位没有方向的年轻人，决定啃下这部巨著。它的作者是图灵奖得主、算法领域先驱、被誉为”算法之父”的Donald E. Knuth。为配合本书，作者甚至专门编写了配套教材《具体数学》。我买来这本书，却只坚持读了一天就放弃了。

找不到《具体数学》的公开课，偶然发现其目录与离散数学相似。得知清华大学在学堂在线开设《组合数学》课程，我立即报名并完成学习。同时在知乎了解到，若想补充编译原理知识，可学习《SICP》，便买来这本书跟着上古录像学了前三章。

这两门课让我获得薪资六倍的offer，从青岛搬到上海加入创业公司。如今从业十余年，从外包程序员到前端/全栈工程师，再到系统架构师，甚至担任过CTO。相较于起点，这或许算得上逆袭。

但命运的齿轮究竟何时开始转动？

是关闭游戏感到空虚的那个下午？还是买下《具体数学》翻开扉页的那天？

都不是。我始终认为，命运的齿轮真正转动始于报名《组合数学》课程的那一刻。

现在问参加操作系统训练营的同学们：你们是否已感受到命运齿轮开始转动？

通关攻略

当今社会被资本构建的信息茧房笼罩，每天被Python编程课广告轰炸，甚至上万的AI课程、数千元的知识星球…所谓大厂高P讲师们坐享时代红利，利用信息不对称收割韭菜，教材却是东拼西凑、充斥大量错误和误导的八股文。

而一流大学的优质课程免费开放却鲜为人知。恭喜诸位突破信息茧房，本次训练营依托清华大学操作系统课程，配有专业师资团队。

登录官网可见先修要求：

  • Rust语言基础
  • 计算机组成与设计
  • RISC-V 汇编特权指令集

但作为注重实践的训练营，最终考核是完成操作系统实现并在QEMU验证。还有一些官网未提及的隐藏门槛：

  • Git：是否熟练掌握commit/checkout/branch/merge/rebase等操作？
  • Linux：是否有使用经验并熟悉常用命令？
  • 英语：能否阅读英文文档（即使借助翻译工具）？
  • 编码与调试：是否具备万行代码经验，能否将代码拆分到多个函数和文件？
  • 网络：是否能无障碍访问国际互联网，并为开发工具配置代理或镜像源？
  • 提问：能否精准描述问题并明确所需帮助？

每项技能至少需要10小时学习投入。若缺少其中任何一项，实验过程中将需要付出更多时间精力来补足。

总结

感谢陈渝、向勇、石磊等教授开设课程，感谢李明老师推广宣传，感谢助教团队的付出。这门课程：

  • 于国：培养操作系统人才，助力科技自立自强
  • 于民：促进教育公平，让教育资源匮乏地区的学生获得一流课程
  • 于我：这个专科生终于能与985/211学生站在同一起跑线。过去总抱怨命运不公，如今证明自己的机会就在眼前——我只需全力以赴。

Posted on Edited on In

2025OS训练营一阶段记录

说明一下，我是提前为训练营做准备，所以记录时间比开营要早，毕竟以我这种基础不笨鸟先飞怕跟不上哈哈。

3.12

今天开始学Rust，之前对这个语言也没咋接触过，但是之前学过点go，都是函数式编程，应该有相通处吧。

我找了经验贴都说看course.rs的Rust圣经，于是按照提示搭建了下环境，我用的是ubuntu20.04，装起环境没有碰到什么问题。还跟着作者用vscode，装了几个推荐的插件。

了解了cargo 跑了下helloworld，之前写c++的，每次都被环境折腾的不行，找不到的包还要自己手动编译，而且是win环境下…不会写makefile还要用cmake，这东西更新还快，每种库外部文件导入方式还不一样，可能被折磨习惯了觉得这很正常。原来现在的编程语言能做到这么厉害，不仅不用自己编译，手动导入，连库的可用性也会检测。而且rust还有媲美c++的性能，太厉害了！编译的方式也非常简单，toml的依赖方式也比任何语言的依赖方式都要简单。Rust 原生支持 UTF-8 编码的字符串，可以很容易的使用世界各国文字作为字符串内容，再也不用被msvc的字符集问题折腾了。{}作为占位符，数字、字符串、结构体都能打印。rust有很好的链式编程特性，标准库的函数熟练运用起来应该非常方便优雅。

第一章变量绑定与解构。变量默认不可变 ：Rust变量默认不能修改，必须加mut才能变成可变变量。这个设计挺特别的，一开始不习惯但确实能避免很多意外修改的bug。变量遮蔽：可以用同名变量覆盖之前的变量，实际上是创建了新变量。和mut的区别在于会创建新内存空间，还能用来改变变量类型。解构赋值 ：可以从元组、结构体等复杂类型中提取值赋给变量，写法很简洁。常量 ：用const声明，必须指定类型，命名习惯是全大写加下划线。命名规范 ：下划线开头的变量名可以避免未使用变量的警告。

整体感觉Rust的变量系统设计得很严谨，虽然开始有点不习惯，但这些特性确实能写出更安全的代码。特别是默认不可变这个设计，强迫开发者想清楚哪些变量真的需要修改。

第二章基本类型。基本类型与c++没什么差别，特别的就是单元类型 () ，其唯一的值也是 ()。rust编译器必须在编译期知道我们所有变量的类型，但这不意味着需要为每个变量指定类型，它可以根据变量的值和上下文中的使用方式来自动推导出变量的类型，在某些情况下，它无法推导出变量类型，需要手动去给予一个类型标注。在整数上，在release 模式构建时，Rust 不检测溢出。相反，当检测到整型溢出时，Rust 会按照补码循环溢出（two’s complement wrapping）的规则处理，也有一些函数用来检查溢出。在处理浮点数计算时要相当注意。NaN为数学上为定义，与之交互都会成为NaN。

我注意到range for i in 1..=5这样的方式非常有意思和方便，还可以用字母。Rust 拥有相当多的数值类型. 需要熟悉这些类型所占用的字节数，这样就知道该类型允许的大小范围以及选择的类型是否能表达负数。类型转换必须是显式的. Rust 永远也不会偷偷把你的 16bit 整数转换成 32bit 整数。

Rust 的函数体是由一系列语句组成，最后由一个表达式来返回值，需要区分语句和表达式，表达式总要返回值，分号结尾的是语句。

当用 ! 作函数返回类型的时候，表示该函数永不返回，这种语法往往用做会导致程序崩溃的函数。

3.13

今天学习基础第三章所有权和借用。为了解决内存安全问题，rust提出所有权概念，所有权三条规则：Rust 中每一个值都被一个变量所拥有，该变量被称为值的所有者；一个值同时只能被一个变量所拥有，或者说一个值只能拥有一个所有者；当所有者（变量）离开作用域范围时，这个值将被丢弃(drop)。

1
2
let x = 5;
let y = x;

这段代码并没有发生所有权的转移，原因很简单： 代码首先将 5 绑定到变量 x，接着拷贝 x 的值赋给 y，最终 x 和 y 都等于 5，因为整数是 Rust 基本数据类型，是固定大小的简单值，因此这两个值都是通过自动拷贝的方式来赋值的，都被存在栈中，完全无需在堆上分配内存。

1
2
let s1 = String::from("hello");
let s2 = s1;

当 s1 被赋予 s2 后，Rust 认为 s1 不再有效，因此也无需在 s1 离开作用域后 drop 任何东西，这就是把所有权从 s1 转移给了 s2，s1 在被赋予 s2 后就马上失效了。其实类似于c++里的move。如果不想夺取原有的所有权可以使用clone（），rust基本类型自带clone属性。

Rust通过借用(Borrowing) 获取变量的引用，称之为借用。引用分为可变引用和不可变引用，区别就是可不可变，这种限制的好处就是使 Rust 在编译期就避免数据竞争，两个或更多的指针同时访问同一数据，至少有一个指针被用来写入数据，没有同步数据访问的机制。可变引用和不可变引用不可以同时存在，可变引用可以同时存在一个，不可变引用可以同时存在多个。

基础第四章复合类型。&s[0..len]切片操作很方便得用到string，字节序等，0..len为range类，左闭右开，在处理字节流时要注意，汉字在utf8占三个字节。字符串字面量也是个切片。

元组是由多种类型组合到一起形成的，因此它是复合类型，元组的长度是固定的，元组中元素的顺序也是固定的。可以通过以下语法创建一个元组：

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

变量 tup 被绑定了一个元组值 (500, 6.4, 1)，该元组的类型是 (i32, f64, u8)，元组是用括号将多个类型组合到一起，可以使用模式匹配或者 . 操作符来获取元组中的值。

用模式匹配解构元组：

1
let (x, y, z) = tup;

struct结构体和c语言类似，访问字段用 . ,初始化实例时，每个字段都需要进行初始化，初始化时的字段顺序不需要和结构体定义时的顺序一致。结构体中具有所有权的字段转移出去后，将无法再访问该字段，但是可以正常访问其它的字段，

结构体必须要有名称，但是元组结构体的字段可以没有名称，例如：

1
2
struct Color(i32, i32, i32);
let origin = Point(0, 0, 0);

元组结构体在你希望有一个整体名称，但是又不关心里面字段的名称时将非常有用。

如果想在结构体里包含一个引用，必须声明生命周期。可以为结构体添加debug属性，实现fmt函数用来自定义打印结构体信息。

枚举类比大多语言要强大，每个元素可以是结构体包含不同信息，

1
2
3
4
5
6
enum Message {
    Quit,
    Move { x: i32, y: i32 },
    Write(String),
    ChangeColor(i32, i32, i32),
}

Option 枚举用于处理空值，在其它编程语言中，往往都有一个 null 关键字，当null 异常导致程序的崩溃时我们需要处理这些 null 空值。Rust 吸取了众多教训，决定抛弃 null，而改为使用 Option 枚举变量来表述这种结果。Option 枚举包含两个成员，一个成员表示含有值：Some(T), 另一个表示没有值：None，定义如下：

1
2
3
4
enum Option<T> {
    Some(T),
    None,
}

其中 T 是泛型参数，Some(T)表示该枚举成员的数据类型是 T，换句话说，Some 可以包含任何类型的数据。

在 Rust 中，最常用的数组有两种，第一种是速度很快但是长度固定的 array，第二种是可动态增长的但是有性能损耗的 Vector，在本书中，我们称 array 为数组，Vector 为动态数组。数组的三要素：长度固定、元素必须有相同的类型、依次线性排列。声明方式：

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

3.14

今天学习基础第五章流程控制和第六章模式匹配。流程控制就是for … in while loop很容易。模式匹配还是对c++er比较新颖。match的用法和switch相似，强大的点在于可以同时解构内容如：

1
2
3
4
5
6
match action {
            Action::Say(s) => {
                println!("{}", s);
            },
            _ => {},
       }

if let 相当于单个匹配的match，同样用于获取并解构。

matches!，它可以将一个表达式跟模式进行匹配，然后返回匹配的结果 true or false。

match 和 if let 都可以触发变量遮蔽，就是可以同名变量优先使用当前作用于下的，在处理时很方便。

Option解构在rust经常用到，返回结果要么是Some（T），要么是None，在处理时解构处理不同情况非常强大。

解构方式还有个while let ，可以循环处理解构，数组和元组也可以用对应的结构来解构，_可以用来忽略这个位置的变量，匹配的范围同样可以使用range。

基础第七章方法。可以使用impl 对struct enum实现方法，方法公开需前置pub，方法的函数如若调用结构体的内容需要第一个参数位self，一般情况时&self，在需要对结构体内容更改时为&mut self，当然也可以不是引用，self转让所有权到方法里。在函数里没有结构体的引用时（关联函数）需要使用结构体：：来访问，否则一概使用 . 来访问。impl 内部也可以声明变量、常量等。impl 可以多次进行实现。

第八章泛型与特征。在 Rust 中，泛型参数的名称可以任意起，但是出于惯例都用 T ，使用泛型参数，有一个先决条件，必需在使用前对其进行声明：

1
fn largest<T>(list: &[T]) -> T {

该泛型函数的作用是从列表中找出最大的值，其中列表中的元素类型为 T。首先 largest<T> 对泛型参数 T 进行了声明，然后才在函数参数中进行使用该泛型参数 list: &[T] ，函数 largest 有泛型类型 T，它有个参数 list，其类型是元素为 T 的数组切片，最后，该函数返回值的类型也是 T。

T 可以是任何类型，但不是所有的类型都能进行比较，编译器建议我们给 T 添加一个类型限制：使用 std::cmp::PartialOrd 特征（Trait）对 T 进行限制。

有时候，编译器无法推断你想要的泛型参数，这时候需要显式地来声明。

1
2
3
4
5
6
7
fn create_and_print<T>() where T: From<i32> + Display {
    let a: T = 100.into(); // 创建了类型为 T 的变量 a，它的初始值由 100 转换而来
    println!("a is: {}", a);
}
fn main() {
    create_and_print::<i64>();
}

结构体和枚举的泛型

1
2
3
4
5
6
7
8
9
10
11
12
13
enum Option<T> {
    Some(T),
    None,
}
struct Point<T,U> {
    x: T,
    y: U,
}
impl<T> Point<T> {
    fn x(&self) -> &T {
        &self.x
    }
}

方法中使用泛型：使用泛型参数前要提前声明：impl<T>，这样 Rust 就知道 Point 的尖括号中的类型是泛型而不是具体类型。注意，这里的 Point<T> 不再是泛型声明，而是一个完整的结构体类型，因为我们定义的结构体就是 Point<T> 而不再是 Point。除了结构体中的泛型参数，还能在该结构体的方法中定义额外的泛型参数，就跟泛型函数一样：

1
2
3
4
5
6
7
8
impl<T, U> Point<T, U> {
    fn mixup<V, W>(self, other: Point<V, W>) -> Point<T, W> {
        Point {
            x: self.x,
            y: other.y,
        }
    }
}

const泛型：[i32; 3] 和 [i32; 2] 确实是两个完全不同的类型，因此无法用同一个函数调用，const 泛型，也就是针对值的泛型可以用于处理数组长度的问题：

1
2
3
4
5
6
7
8
9
fn display_array<T: std::fmt::Debug, const N: usize>(arr: [T; N]) {
    println!("{:?}", arr);
}
fn main() {
    let arr: [i32; 3] = [1, 2, 3];
    display_array(arr);
    let arr: [i32; 2] = [1, 2];
    display_array(arr);
}

const fn，即常量函数。通常情况下，函数是在运行时被调用和执行的。然而，在某些场景下，我们希望在编译期就计算出一些值，以提高运行时的性能或满足某些编译期的约束条件。例如，定义数组的长度、计算常量值等。有了 const fn，我们可以在编译期执行这些函数，从而将计算结果直接嵌入到生成的代码中。

特征trait：如果不同的类型具有相同的行为，那么我们就可以定义一个特征，然后为这些类型实现该特征。定义特征是把一些方法组合在一起，目的是定义一个实现某些目标所必需的行为的集合。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
pub trait Summary {
    fn summarize(&self) -> String;
}
pub struct Post {
    pub title: String, // 标题
    pub author: String, // 作者
    pub content: String, // 内容
}

impl Summary for Post {
    fn summarize(&self) -> String {
        format!("文章{}, 作者是{}", self.title, self.author)
    }
}

pub struct Weibo {
    pub username: String,
    pub content: String
}

impl Summary for Weibo {
    fn summarize(&self) -> String {
        format!("{}发表了微博{}", self.username, self.content)
    }
}

关于特征实现与定义的位置，有一条非常重要的原则：如果你想要为类型 A 实现特征 T，那么 A 或者 T 至少有一个是在当前作用域中定义的！ 例如可以为上面的 Post 类型实现标准库中的 Display 特征，这是因为 Post 类型定义在当前的作用域中。同时也可以在当前包中为 String 类型实现 Summary 特征，因为 Summary 定义在当前作用域中.

特征中定义具有默认实现的方法，这样其它类型无需再实现该方法，或者也可以选择重载该方法.

使用特征作为函数参数：

1
2
3
pub fn notify(item: &impl Summary) {
    println!("Breaking news! {}", item.summarize());
}

impl Summary顾名思义，它的意思是 实现了Summary特征 的 item 参数。

如果想要强制函数的两个参数是同一类型只能使特征约束来实现：

1
pub fn notify<T: Summary>(item1: &T, item2: &T) {}

泛型类型 T 说明了 item1 和 item2 必须拥有同样的类型，同时 T: Summary 说明了 T 必须实现 Summary 特征。

多重约束:除了单个约束条件，可以指定多个约束条件，

1
pub fn notify(item: &(impl Summary + Display)) {}

除了上述的语法糖形式，还能使用特征约束的形式：

1
pub fn notify<T: Summary + Display>(item: &T) {}

特征约束，可以让我们在指定类型 + 指定特征的条件下去实现方法,也可以有条件地实现特征，例如，标准库为任何实现了 Display 特征的类型实现了 ToString 特征。

可以通过 impl Trait 来说明一个函数返回了一个类型，该类型实现了某个特征：

1
2
3
4
5
fn returns_summarizable() -> impl Summary {
    Weibo {
        。。。
    }
}

这种 impl Trait 形式的返回值，在一种场景下非常非常有用，那就是返回的真实类型非常复杂，你不知道该怎么声明时。

#[derive(Debug)] ：是一种特征派生语法，被 derive 标记的对象会自动实现对应的默认特征代码，继承相应的功能。例如 Debug 特征，它有一套自动实现的默认代码，当你给一个结构体标记后，就可以使用 println!("{:?}", s) 的形式打印该结构体的对象。

再如 Copy 特征，它也有一套自动实现的默认代码，当标记到一个类型上时，可以让这个类型自动实现 Copy 特征，进而可以调用 copy 方法，进行自我复制。

总之，derive 派生出来的是 Rust 默认给我们提供的特征，在开发过程中极大的简化了自己手动实现相应特征的需求，当然，如果你有特殊的需求，还可以自己手动重载该实现

特征对象

1
2
3
pub trait Draw {
    fn draw(&self);
}

只要组件实现了 Draw 特征，就可以调用 draw 方法来进行渲染。假设有一个 Button 和 SelectBox 组件实现了 Draw 特征：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
pub struct Button {
    pub width: u32,
    pub height: u32,
    pub label: String,
}

impl Draw for Button {
    fn draw(&self) {
        // 绘制按钮的代码
    }
}

struct SelectBox {
    width: u32,
    height: u32,
    options: Vec<String>,
}

impl Draw for SelectBox {
    fn draw(&self) {
        // 绘制SelectBox的代码
    }
}
fn draw1(x: Box<dyn Draw>) {
    // 由于实现了 Deref 特征，Box 智能指针会自动解引用为它所包裹的值，然后调用该值对应的类型上定义的 `draw` 方法
    x.draw();
}

fn draw2(x: &dyn Draw) {
    x.draw();
}

此时，还需要一个动态数组来存储这些 UI 对象：

1
2
3
pub struct Screen {
    pub components: Vec<?>,
}

特征对象**指向实现了 Draw 特征的类型的实例，也就是指向了 Button 或者 SelectBox 的实例，这种映射关系是存储在一张表中，可以在运行时通过特征对象找到具体调用的类型方法。

  • draw1 函数的参数是 Box<dyn Draw> 形式的特征对象，该特征对象是通过 Box::new(x) 的方式创建的
  • draw2 函数的参数是 &dyn Draw 形式的特征对象，该特征对象是通过 &x 的方式创建的
  • dyn 关键字只用在特征对象的类型声明上，在创建时无需使用 dyn
1
2
3
pub struct Screen {
    pub components: Vec<Box<dyn Draw>>,
}

其中存储了一个动态数组，里面元素的类型是 Draw 特征对象：Box<dyn Draw>，任何实现了 Draw 特征的类型，都可以存放其中。

再来为 Screen 定义 run 方法，用于将列表中的 UI 组件渲染在屏幕上：

1
2
3
4
5
6
7
impl Screen {
    pub fn run(&self) {
        for component in self.components.iter() {
            component.draw();
        }
    }
}

泛型是在编译期完成处理的：编译器会为每一个泛型参数对应的具体类型生成一份代码，这种方式是静态分发，因为是在编译期完成的，对于运行期性能完全没有任何影响。与静态分发相对应的是动态分发(dynamic dispatch)，直到运行时，才能确定需要调用什么方法。

3.15

第九章集合类型

使用 Vec::new 创建动态数组

1
let v: Vec<i32> = Vec::new();

这里，v 被显式地声明了类型 Vec<i32>，这是因为 Rust 编译器无法从 Vec::new() 中得到任何关于类型的暗示信息，因此也无法推导出 v 的具体类型：

1
2
let mut v = Vec::new();
v.push(1);

此时，v 就无需手动声明类型，因为编译器通过 v.push(1)，推测出 v 中的元素类型是 i32，因此推导出 v 的类型是 Vec<i32>。

如果预先知道要存储的元素个数，可以使用 Vec::with_capacity(capacity) 创建动态数组，这样可以避免因为插入大量新数据导致频繁的内存分配和拷贝，提升性能

还可以使用宏 vec! 来创建数组，与 Vec::new 有所不同，前者能在创建同时给予初始化值：

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

同样，此处的 v 也无需标注类型，编译器只需检查它内部的元素即可自动推导出 v 的类型是 `Vec

跟结构体一样，Vector 类型在超出作用域范围后，会被自动删除：

1
2
3
4
{
    let v = vec![1, 2, 3];
    // ...
} // <- v超出作用域并在此处被删除

当 Vector 被删除后，它内部存储的所有内容也会随之被删除。

同时借用多个数组元素 遇到同时借用多个数组元素的情况

1
2
3
4
let mut v = vec![1, 2, 3, 4, 5];
let first = &v[0];
v.push(6);
println!("The first element is: {first}")；

此时编译器报错。数组的大小是可变的，当旧数组的大小不够用时，Rust 会重新分配一块更大的内存空间，然后把旧数组拷贝过来。这种情况下，之前的引用显然会指向一块无效的内存。

1
2
3
4
5
6
7
8
use std::collections::HashMap;

// 创建一个HashMap，用于存储宝石种类和对应的数量
let mut my_gems = HashMap::new();

// 将宝石类型和对应的数量写入表中
my_gems.insert("红宝石", 1);
my_gems.insert("蓝宝石", 2);

3.16

第十章生命周期。

借用检查：为了保证 Rust 的所有权和借用的正确性，Rust 使用了一个借用检查器(Borrow checker)来检查程序的借用正确性。

函数中的生命周期：

1
2
3
4
5
6
7
8
9
10
11
12
13
fn longest(x: &str, y: &str) -> &str {
    if x.len() > y.len() {
        x
    } else {
        y
    }
}
--------
 --> src/main.rs:9:33
  |
9 | fn longest(x: &str, y: &str) -> &str {
  |               ----     ----     ^ expected named lifetime parameter // 参数需要一个生命周期
  |

编译器无法知道该函数的返回值到底引用 x 还是 y ，因为编译器需要知道这些，来确保函数调用后的引用生命周期分析。在存在多个引用时，编译器有时会无法自动推导生命周期，此时就需要手动去标注，通过为参数标注合适的生命周期来帮助编译器进行借用检查的分析。

生命周期标注：生命周期的语法以 ' 开头，名称往往是一个单独的小写字母，大多数人都用 'a 来作为生命周期的名称。 如果是引用类型的参数，那么生命周期会位于引用符号 & 之后，并用一个空格来将生命周期和引用参数分隔开

1
2
3
&i32        // 一个引用
&'a i32     // 具有显式生命周期的引用
&'a mut i32 // 具有显式生命周期的可变引用

一个生命周期标注，它自身并不具有什么意义，因为生命周期的作用就是告诉编译器多个引用之间的关系。例如，有一个函数，它的第一个参数 first 是一个指向 i32 类型的引用，具有生命周期 'a，该函数还有另一个参数 second，它也是指向 i32 类型的引用，并且同样具有生命周期 'a。此处生命周期标注仅仅说明，这两个参数 first 和 second 至少活得和’a 一样久，至于到底活多久或者哪个活得更久，我们都无法得知：

1
fn useless<'a>(first: &'a i32, second: &'a i32) {}

函数签名中的生命周期标注

1
2
3
4
5
6
7
fn longest<'a>(x: &'a str, y: &'a str) -> &'a str {
    if x.len() > y.len() {
        x
    } else {
        y
    }
}
  • 和泛型一样，使用生命周期参数，需要先声明 <'a>
  • x、y 和返回值至少活得和 'a 一样久（因为返回值要么是 x，要么是 y）

该函数签名表明对于某些生命周期 'a，函数的两个参数都至少跟 'a 活得一样久，同时函数的返回引用也至少跟 'a 活得一样久。实际上，这意味着返回值的生命周期与参数生命周期中的较小值一致：虽然两个参数的生命周期都是标注了 'a，但是实际上这两个参数的真实生命周期可能是不一样的（生命周期 'a 不代表生命周期等于 'a，而是大于等于 'a）。在通过函数签名指定生命周期参数时，并没有改变传入引用或者返回引用的真实生命周期，而是告诉编译器当不满足此约束条件时，就拒绝编译通过。

因此 longest 函数并不知道 x 和 y 具体会活多久，只要知道它们的作用域至少能持续 'a 这么长就行。

该例子证明了 result 的生命周期必须等于两个参数中生命周期较小的那个:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
fn main() {
    let string1 = String::from("long string is long");
    let result;
    {
        let string2 = String::from("xyz");
        result = longest(string1.as_str(), string2.as_str());
    }
    println!("The longest string is {}", result);
}
error[E0597]: `string2` does not live long enough
 --> src/main.rs:6:44
  |
6 |         result = longest(string1.as_str(), string2.as_str());
  |                                            ^^^^^^^ borrowed value does not live long enough
7 |     }

在上述代码中，result 必须要活到 println!处，因为 result 的生命周期是 'a，因此 'a 必须持续到 println!。

结构体中的生命周期：

1
2
3
struct ImportantExcerpt<'a> {
    part: &'a str,
}

ImportantExcerpt 结构体中有一个引用类型的字段 part，因此需要为它标注上生命周期。结构体的生命周期标注语法跟泛型参数语法很像，需要对生命周期参数进行声明 <'a>。该生命周期标注说明，结构体 ImportantExcerpt 所引用的字符串 str 生命周期需要大于等于该结构体的生命周期

生命周期消除：尽管我们没有显式的为其标注生命周期，编译依然可以通过。其实原因不复杂，编译器为了简化用户的使用，运用了生命周期消除大法。

三条消除规则：

编译器使用三条消除规则来确定哪些场景不需要显式地去标注生命周期。其中第一条规则应用在输入生命周期上，第二、三条应用在输出生命周期上。若编译器发现三条规则都不适用时，就会报错，提示你需要手动标注生命周期。

  1. 每一个引用参数都会获得独自的生命周期

    例如一个引用参数的函数就有一个生命周期标注: fn foo<'a>(x: &'a i32)，两个引用参数的有两个生命周期标注:fn foo<'a, 'b>(x: &'a i32, y: &'b i32), 依此类推。

  2. 若只有一个输入生命周期（函数参数中只有一个引用类型），那么该生命周期会被赋给所有的输出生命周期，也就是所有返回值的生命周期都等于该输入生命周期

    例如函数 fn foo(x: &i32) -> &i32，x 参数的生命周期会被自动赋给返回值 &i32，因此该函数等同于 fn foo<'a>(x: &'a i32) -> &'a i32

  3. 若存在多个输入生命周期，且其中一个是 &self 或 &mut self，则 &self 的生命周期被赋给所有的输出生命周期

    拥有 &self 形式的参数，说明该函数是一个 方法，该规则让方法的使用便利度大幅提升。

3.17

方法中的生命周期：

1
2
3
4
5
6
7
8
9
struct ImportantExcerpt<'a> {
    part: &'a str,
}

impl<'a> ImportantExcerpt<'a> {
    fn level(&self) -> i32 {
        3
    }
}
  • impl 中必须使用结构体的完整名称，包括 <'a>，因为生命周期标注也是结构体类型的一部分！
  • 方法签名中，往往不需要标注生命周期，得益于生命周期消除的第一和第三规则

静态生命周期：生命周期 'static，拥有该生命周期的引用可以和整个程序活得一样久。

字符串字面量是被硬编码进 Rust 的二进制文件中，因此这些字符串变量全部具有 'static 的生命周期：

1
let s: &'static str = "就是活得久，嘿嘿";

Rust 中的错误主要分为两类：

  • 可恢复错误，通常用于从系统全局角度来看可以接受的错误，例如处理用户的访问、操作等错误，这些错误只会影响某个用户自身的操作进程，而不会对系统的全局稳定性产生影响
  • 不可恢复错误，刚好相反，该错误通常是全局性或者系统性的错误，例如数组越界访问，系统启动时发生了影响启动流程的错误等等，这些错误的影响往往对于系统来说是致命的

Rust 提供了 panic! 宏，当调用执行该宏时，程序会打印出一个错误信息，展开报错点往前的函数调用堆栈，最后退出程序。

当出现 panic! 时，程序提供了两种方式来处理终止流程：栈展开和直接终止。

其中，默认的方式就是 栈展开，这意味着 Rust 会回溯栈上数据和函数调用，因此也意味着更多的善后工作，好处是可以给出充分的报错信息和栈调用信息，便于事后的问题复盘。直接终止，顾名思义，不清理数据就直接退出程序，善后工作交与操作系统来负责。

对于绝大多数用户，使用默认选择是最好的，但是当你关心最终编译出的二进制可执行文件大小时，那么可以尝试去使用直接终止的方式，例如下面的配置修改 Cargo.toml 文件，实现在 release 模式下遇到 panic 直接终止：

1
2
[profile.release]
panic = 'abort'

panic后如果是 main 线程，则程序会终止，如果是其它子线程，该线程会终止，但是不会影响 main 线程。

*Result<T, E> *是一个枚举类型，定义如下：

1
2
3
4
enum Result<T, E> {
    Ok(T),
    Err(E),
}

泛型参数 T 代表成功时存入的正确值的类型，存放方式是 Ok(T)，E 代表错误时存入的错误值，存放方式是 Err(E)，

不想使用 match 去匹配 Result<T, E>以获取其中的 T 值，因为 match 的穷尽匹配特性，你总要去处理下 Err 分支。有个办法简化这个过程就是 unwrap 和 expect。它们的作用就是，如果返回成功，就将 Ok(T) 中的值取出来，如果失败，就直接 panic。expect 跟 unwrap 很像，也是遇到错误直接 panic, 但是会带上自定义的错误提示信息，相当于重载了错误打印的函数.

1
2
let f = File::open("hello.txt").unwrap();
let f = File::open("hello.txt").expect("Failed to open hello.txt");

错误传播：

1
fn read_username_from_file() -> Result<String, io::Error>
  • 该函数返回一个 Result<String, io::Error> 类型，当读取用户名成功时，返回 Ok(String)，失败时，返回 Err(io:Error)
  • File::open 和 f.read_to_string 返回的 Result<T, E> 中的 E 就是 io::Error

3.18

  • 项目(Package)：可以用来构建、测试和分享包
  • 工作空间(WorkSpace)：对于大型项目，可以进一步将多个包联合在一起，组织成工作空间
  • 包(Crate)：一个由多个模块组成的树形结构，可以作为三方库进行分发，也可以生成可执行文件进行运行
  • 模块(Module)：可以一个文件多个模块，也可以一个文件一个模块，模块可以被认为是真实项目中的代码组织单元

包 Crate

对于 Rust 而言，包是一个独立的可编译单元，它编译后会生成一个可执行文件或者一个库。

一个包会将相关联的功能打包在一起，使得该功能可以很方便的在多个项目中分享。例如标准库中没有提供但是在三方库中提供的 rand 包，它提供了随机数生成的功能，只需要将该包通过 use rand; 引入到当前项目的作用域中，就可以在项目中使用 rand 的功能：rand::XXX。

同一个包中不能有同名的类型，但是在不同包中就可以。例如，虽然 rand 包中，有一个 Rng 特征，可是依然可以在自己的项目中定义一个 Rng，前者通过 rand::Rng 访问，后者通过 Rng 访问，不会存在引用歧义。

项目 Package

由于 Package 就是一个项目，因此它包含有独立的 Cargo.toml 文件，以及因为功能性被组织在一起的一个或多个包。一个 Package 只能包含一个库(library)类型的包，但是可以包含多个二进制可执行类型的包。

库 Package

1
2
3
4
5
6
7
$ cargo new my-lib --lib
     Created library `my-lib` package
$ ls my-lib
Cargo.toml
src
$ ls my-lib/src
lib.rs

如果你试图运行 my-lib，会报错：

1
2
$ cargo run
error: a bin target must be available for `cargo run`

原因是库类型的 Package 只能作为三方库被其它项目引用，而不能独立运行，只有之前的二进制 Package 才可以运行。

与 src/main.rs 一样，Cargo 知道，如果一个 Package 包含有 src/lib.rs，意味它包含有一个库类型的同名包 my-lib，该包的根文件是 src/lib.rs。

模块

  • 使用 mod 关键字来创建新模块，后面紧跟着模块名称
  • 模块可以嵌套，这里嵌套的原因是招待客人和服务都发生在前厅，因此我们的代码模拟了真实场景
  • 模块中可以定义各种 Rust 类型，例如函数、结构体、枚举、特征等
  • 所有模块均定义在同一个文件中

模块树为模块的嵌套结构，他们都有一个根模块 crate。如果模块 A 包含模块 B，那么 A 是 B 的父模块，B 是 A 的子模块。

想要调用一个函数，就需要知道它的路径，在 Rust 中，这种路径有两种形式：

  • 绝对路径，从包根开始，路径名以包名或者 crate 作为开头
  • 相对路径，从当前模块开始，以 self，super 或当前模块的标识符作为开头

Rust 出于安全的考虑，默认情况下，所有的类型都是私有化的，包括函数、方法、结构体、枚举、常量，是的，就连模块本身也是私有化的。父模块完全无法访问子模块中的私有项，但是子模块却可以访问父模块、父父..模块的私有项。

模块可见性不代表模块内部项的可见性，模块的可见性仅仅是允许其它模块去引用它，但是想要引用它内部的项，还得继续将对应的项标记为 pub。

当外部的模块项 A 被引入到当前模块中时，它的可见性自动被设置为私有的，如果你希望允许其它外部代码引用我们的模块项 A，那么可以对它进行再导出。使用 pub use 即可实现。

引入第三方包中的模块，关于如何引入外部依赖：

修改 Cargo.toml 文件，在 [dependencies] 区域添加一行：rand = "0.8.3"

3.21-3.24 rustlings

关于rustlings，系统学过rust后几乎没有难题，所以我在6号一天就完成了70多道，前两天在熟悉github classroom和rustlings的自检方式。

Posted on Edited on In

2025OS训练营三阶段记录

4.7-4.8

这两天看了石磊老师的unikernel讲解视频，完成了彩色print和hashmap的任务。

unikernel我是第一次听说，用组件化的方式来实现操作系统，可以对应用定制轻量化的运行环境，相当于操作系统与应用一体，比较适合嵌入式和轻量虚拟化场景。arceos就不像rcore那样是面向教学的了，而是更偏向于实际应用，我查看了toml，操作系统的组件几乎都是依赖导入，刚开始有些搞不清楚这些包的具体用途。

彩色print的实现很简单，在格式化前加入蓝色字符标注即可实现。

hashmap的实现我一开始考虑的是nostd环境是否还需要我来实现对内存分配器，但是后来仔细看过arceos里有实现默认的对内存分配。我的实现内存分配依赖的vec，用vec作为hashmap的底层数据结构，实现起来相对容易，对于通过测例来说还是足够的。

4.9-4.12

这几天在琢磨lab1的挑战题，不愧是挑战题，花了目前最久的时间。题目规范很好，只需要实现规定的部分就可以。内容是要实现一个字节内存分配器来让这个测试达到最大迭代次数。这个测试用例是重点，他是循环分配32+i到2的14次方+i的内存，这个i就是迭代次数，每次迭代会把每一轮偶数次数的分配空间给释放掉，所以每次都有一部分内存不会被释放，即这个挑战有理论最大值。用例的分配用的是vec，vec根据rust的实现每次分配在空间不够时都是要扩容当前一倍的空间的。挑战的分数是i的次数要大于170，因为170是算法tlsf的结果。我对tlsf、buddy算法的实现都手动实现测试了一遍，逐步理清了我的实现思路。

每次分配的偶数情况都会被释放，那直接对偶数情况的内存分配给固定的内存池，比如32 index为0，那分配32+Max的内存池，这个max就是最大i值，中修改max来得到i最大值。对于奇数的情况我使用了最简单的线性分配方法，应为当时想的是每次技术分配的都不会释放，所以不会有间隙，其实不是。这个探索的过程我发现分配的大小没有按照我的想法分配到对应的位置，于是我就打印了每次分配的内存的大小，我发现有几个固定值96，192，386这些数字不符合每次请求的内存大小，猜测应该是对其的要求分配的。所以对这个情况进行处理，直接计数进行跳过。但是效果到64又出现问题，分析发现32涨到96，与固定值96的分配打乱了奇偶计数的顺序，所以对全局分配96的大小进行计数，同样跳过一个固定位次的96分配。同理128在涨到192时也会触发，32在涨到192又会触发。对这些情况都做处理，得到了189的分数，折腾了三天，也总算有个结果，即便我知道这不是最佳答案。

其实问题在于我认为奇数的分配是没有空隙的，其实vec的分配策略，扩容的空间都是浪费了，如果要提升，就要在奇数合并块时，通过某种策略找出未使用的扩容区域，就可以真做到最大限度利用空间，达到无空隙。

这个题目刚开始觉得是个算法题，但其实也让我对内存分配的理解更加的深入。

4.13

今天实现的是bump内存分配策略，同时兼顾页分配和字节分配，通过上次挑战题的考验，这道题相当简单了。而且题目要求也很低，我的实现就是对分配器维护一个左右标签记录已经分配的区域，左为字节分配器的使用位置，右为页面分配器的使用位置。字节分配采用线性分配，每次分配查看左标签内还有没有空余，没有就移动左标签扩容。释放只处理与左标签邻近的地址，将左标签剪去分配的内存大小。右标签则是每次分配页面大小，维护是扩容则减，释放则加。

其实对与这道题的测试用例很松，维护好左右分配标签就可以过。

4.14

今天实现了rename，其实有个最简单的方法就是拷贝删除用来重新创建该文件。

正规做法需要先改下依赖的路径为本地，再将rename实现，arceos的文件系统依赖于虚拟文件系统，根据它的结构找到mata文件即可修改文件名。

4.15

mmap操作需要先理解静态分配，其实很简单，我们平时用到的动态分配就是请求了就立即分配内存空间给用户，静态则是在请求时返回成功，再用到时访问内存会触发pagefault，这个时候再分配内存。mmap需要做到文件映射，本来文件读入内存需要先经过内核空间再到用户空间，mmap在静态分配地址后，手动映射到用户空间，再将文件直接读取到这个物理地址，实现了无拷贝操作。

实现时检查参数有效性，转换传进来的flags格式，获取当前任务的地址空间即可转换给定的虚拟地址为物理地址，使用mapalloc对内存大小完成映射，注意flag要加上USER，因为是要映射到用户空间。通过fd找到文件节点后直接读入到得到的物理内存处，完成映射。

4.16

虚拟化这个题，看过了视频后，有了老师给的提示还是非常容易的。虚拟机在执行到某个位置触发了系统异常，那肯定要在traphandler里找，返汇编后，看到有非该特权级的指令执行出发了异常指令，那就将pc指针步进继续执行，然后代替处理复制操作，后面的错误访问内存也一样，代替执行赋值后设置pc继续执行内核。

总结

三阶段做的这些题远远不够理解arceos，所以在做完后我确定在虚拟化上下功夫，仔细研究这一块的代码。

Posted on Edited on In

2025OS训练营二阶段记录

3.18-3.21

这段时间是在开营前，我在用rcorebook学习，这几天完成了ch1-ch3的学习。

ch1

环境配置：我用的是ubuntu20.04，按照教程来配置还是相当容易的，没有碰到什么问题。

个人基础：我是在寒假接触自制操作系统的，看的一本书叫做《操作系统真象还原》，这本书用c语言和汇编实现了一个x86的32的操作系统。书的内容很多，对于基础盲区也讲解很全，作者从MBR到Bios、bootloader再到用显存来实现print，操作系统的必要组件。所以我学起来还没那么吃力。

riscv我没有接触过，有一些x86的汇编先不系统学习还是可以看得懂的，毕竟rcore没有涉及太多汇编内容。

rust的编译工具安装、编译方便在开始都让我非常惊喜。内核的第一条指令涉及到一个linker.ld，这个文件就是链接脚本，通过分析内容可以很容易理解程序的内存分布，首先是固定的内存入口，其次是 .data .bss .rodata等段的排布很清晰。

简单学习了下gdb调试和远程连接，反编译反汇编工具。

第一次接触rust的外部链接extern “C”，使用声明函数的方式来找到链接脚本确定的内存区域起始符号。

rustsbi这个东西真的很方便，当然也是riscv架构的标准。像打印字符这种函数都实现在里面，要不然需要用汇编来自己实现。对sbi进行封装后很容易就能实现write函数和print宏。

ch2

这一章是写一个批处理系统，系统在运行前就明确了所有要运行的app，这些app都按顺序执行直到最后一道，然后系统panic结束。应用的内存地址都是在运行前要手动计算确定的。riscv架构从大到小分为0，1，2，3四个特权级，还提供了ecall，eret用来切换特权级。这个批处理系统分成了用户态和内核态，ecall就是用来从用户态进入内核态，eret用来返回用户态。ecall属于riscv规定的一种异常，而操作系统属于在riscv的s模式特权级，在用户态ecall就会触发陷入机制进入s模式特权级，用sret来返回u特权级。进入s模式后会调用二进制接口，也称为系统调用。

系统调用的意义在于很多操作交给用户来做非常不安全，系统稳定性难以保证，所以需要划分出内核态用户态，内核根据需求做出安全的系统调用操作。

程序的入口准确来说是_start就是linker里的start符号位置，这里我们不能使用原生架构编译工具，而是使用交叉工具链，所以rust std内容都用不了，main函数也不能完成作为程序入口的作用。在rust声明外部链接符号就要在link操作的宏。

创建系统调用的触发接口，使用内敛汇编调用ecall传入系统调用号和参数，在操作系统就会捕捉异常，判断类型为ecall后根据对应系统调用号即可处理系统调用，完成系统调用后返回用户态。

这里的测试没有实现具体的系统调用，而是用了linux相同的系统调用好在linux环境进行测试，测试正常。

rcore写了build.rs用来构建linker.ld链接脚本，app需要使用路径方式进行导入，每个app的入口地址和执行顺序挂钩。使用的测试用例是在linux系统调用环境下编译的，编译的结果是elf的，需要使用工具来将elf转换成bin二进制文件。在设计上rcore创建了UnSafeCell用来在单核上可以安全使用全局可变借用。

load_app根据固定的标号入口地址来从内存里找到app的代码段，加载到APP_BASE_ADDR，这个地址是个固定值。

1
2
3
4
5
6
批处理操作系统为了建立好应用程序的执行环境，需要在执行应用程序之前进行一些初始化工作，并监控应用程序的执行，具体体现在：
当启动应用程序的时候，需要初始化应用程序的用户态上下文，并能切换到用户态执行应用程序；
当应用程序发起系统调用（即发出 Trap）之后，需要到批处理操作系统中进行处理；
当应用程序执行出错的时候，需要到批处理操作系统中杀死该应用并加载运行下一个应用；
当应用程序执行结束的时候，需要到批处理操作系统中加载运行下一个应用（实际上也是通过系统调用 sys_exit 来实现的）。
这些处理都涉及到特权级切换，因此需要应用程序、操作系统和硬件一起协同，完成特权级切换机制。

系统调用和异常都涉及到了切换特权级，特权级的切换最重要的就是保存上下文。因为不管是trap还是异常都是停止执行当前的程序，转去执行系统调用或者异常处理，这时候就需要保存当前应用的寄存器环境，这个就是上下文，将这些寄存器按固定顺序保存到用户栈，在ret时再逆顺序恢复寄存器。

1
2
3
4
sstatus 的 SPP 字段会被修改为 CPU 当前的特权级（U/S）。
sepc 会被修改为 Trap 处理完成后默认会执行的下一条指令的地址。
scause/stval 分别会被修改成这次 Trap 的原因以及相关的附加信息。
CPU 会跳转到 stvec 所设置的 Trap 处理入口地址，并将当前特权级设置为 S ，然后从Trap 处理入口地址处开始执行。

这些是riscv用到的硬件辅助寄存器。

rcore使用汇编实现了alltrap和restore，用来保存和恢复寄存器，需要注意sp寄存器，sp寄存器的值用到sscratch，这个寄存器用来交换内核栈sp值，还要注意处理当前执行的位置。

traphandler中根据scause的结果，对不同的异常进行处理，包括ecall，runnext等操作。

ch3

这一章要创建一个多道程序处理系统，需要实现分时调用就必须要将应用都加载到内存，这也意味着也要为当前每个应用都分配独立栈空间。所以不能像上节一样都加载到base地址，需要确保应用占用的空间不会重叠。切换任务必然也要保存上下文，与系统调用不同的是，任务切换的操作保存寄存器恢复寄存器都是在用户态。rcore根据sbi实现了gettime，设定计时器后，计时器到时触发异常，traphandler捕捉到后执行任务切换操作。

任务切换最重要的是switch操作，在执行之前已经将下个任务的栈顶地址保存起来，保存当前寄存器环境后，导入下个任务的寄存器环境。yeild操作为计时器中断触发切换任务的系统调用。

3.24-3.25

关于trace的系统调用实现,需要判断request来实现不同功能. 在request为0时:需要将id转换成const u8 再解引用,再转换为isize返回;在request为1时:要将id转换成mut u8,再将data转换成u8,复制给id转换后指针的解引用,返回0;

当request为2时: 想要获取每个任务的某个系统调用次数,并且考虑到批处理系统会进行任务切换,所以在切换到其他任务时也要保存着其他刮起的人物的调用次数,所以我就在syscall/mod.rs中实现了个全局变量SYSCALL_COUNT,类型为Mutex<BTreeMap<usize, BTreeMap<usize, usize>>>,Mutex包裹是因为他是全局变量(rust的要求? 按理说批处理单进程用不到锁,但是我编译没过就加上了.),外层BTree key为app_id,value为内层BTree,内层BTree为(sys_id, count).这样就可以通过app_id来得到所有系统调用的次数.syscall_count方法在syscall里用来计数,insert_syscall_count为当前任务初始化记录,已有记录则返回,delete_syscall_count在进程退出时删除记录,get_syscall_count就用来在sys_trace里获取当前任务的系统调用次数.

3.25-3.26

在sys_get_time和sys_trace实现最主要的是将虚拟地址转换成物理地址,因为内核不能访问应用的虚拟地址.sys_get_time首先获取应用虚拟页表,将ts转换成虚拟地址,记录偏移,通过页表转换后可以得到对应的物理页表项,将表项加上偏移就得到了对应ts的物理地址,然后转换成mut指针,将获取的timeval复制给该地址.判断跨页是要在ts地址上加上timeval长度得到截至地址,与start%Pagesize后判断是否相等,不相等则要处理跨页,还是计算出物理地址分别在对应部分拷贝该部分的数据.

sys_trace相比上次只需要处理0,1的情况,要想办法通过虚拟地址读取或写入,同样转换为物理地址就可以将其转换成指针.在获取物理页表项时要注意判断页表项的有效性 可读性 可写性.

mmap就是要为应用程序申请一块动态区域,这个就要在memset上处理,本来我是准备将内存加入areas的,但是在写unmap时判断vpn来删除有些困难,就考虑重新为mmap的内存重新建立映射结构.处理时就是要几个点注意,1:判断port是否全0或者无效位有非0, 2:判断start是否页表对齐,没有对齐就返回, 3:PTEFlags不仅要加上port的标志,还需要有效位V和用户位U, 4:计算虚拟页表起始地址,然后对每个页循环遍历, 5: 判断虚拟页表有效性,有效则返回(mapped), 6: 申请物理页建立映射.

unmap要判断虚拟页表无效性,然后循环遍历每个vpn在虚拟页表中被unmap,并移除mmap_set对应项.

3.26-3.28

关于spawn,相比fork就是不要复制父进程的内存布局,将传进来的字符串指针转换成string,通过这个名字获取应用elf_data,后面就对TCB进行初始化,和TCB::new一样,注意三点,父进程设置为当前进程;将该进程加入父进程的child列表;将该进程加入运行队列.

关于stride,我定义了两个常量BASE_STRIDE=91,BIG_STRIDE=99991.在TCBinner里加入两个量:pass=0,prio=1,封装updatepass:

pass += (BASE_STRIDE / prio) % BIG_STRIDE

留出相关接口.再到run_task调用updatepass, 在fatch里对ready_queue取出最小pass的TCB.

3.28-3.30

关于link，与linux的ln命令类似，对文件创建链接相当于在操作系统层面增加个INode，但是磁盘里共用统一片块，那相当于拥有相同的inode编号，我们先通过原文件名称获取编号，已知所有文件都在根目录。找到编号后就可以得到块位置id和offset，在创建inode时需要。接下来修改目录项，需要先扩展目录项的存储区域，后写入目录项。返回一个新的inode。

关于unlink，通过name找到根节点后计算目录项数目，循环读取根节点每个文件对比名称，找到index后，把末尾的目录项换到index处，减小目录大小。

stat就连两个项需要获取，ino就是blockid，nlink需要通过块位置来对目录里所有文件的块位置进行比较，相同计数加1.在返回时我和gettime的处理一样，将虚拟地址转换成物理地址后再转换成可变指针，将stat结构体指针放进去。

3.30-4.3

这节还挺费劲的。刚开始看了很久没发现是银行家算法，不知道如何来抽象这些资源。

首先就是清楚是要以每个进程为单位来进行资源管理，所以在pcb inner里添加了死锁检测模块。模块数据一维为线程tid，二维为资源rid，模块需要实现几个功能，isunsafe就是银行家算法用来查看当前状态是否安全，tryallocate在检查unsafe同时通过tid和rid处理减小available和need，增加allocation；setneed需要在设置资源前调用，在分配失败时会保留，在分配成功会减小。release在up时增加available和减小allocation；检测开关只需要设置enabled。在创建线程和创建资源时需要更新数据结构，在添加一个线程时会为二维结构添加资源数的全为0的向量，在添加mutex时avail则push 1，sem则push 初始化值。在down时首先判断是否打开了检测，打开了就首先setneed，然后判断unsafe如果不安全则直接返回dead，安全则尝试分配（会失败），然后调用down；up时判断检测打开之后就调用release，release判断了当前分配数是否为0。

Posted on Edited on In

Lab1

3.28

完成 Rust 语言练习

Lab2

4.7

risc-v知识欠缺，花费大量时间浏览 risc-v 手册。

完成 Lab1

学习 第四章 Rust 中的动态内存分配，地址空间， SV39 多级页面管理机制（上）。

成果：

初步了解risc-v多级分页机制。

4.10

完成 Lab2, 选做了 Lazy 分配策略。

大部分时间花在了 Lazy 策略初始化不分配内存上，通过查看多个函数的调试输出，完善了mmap申请的虚拟页表和物理页表映射结构上的设计。

4.11

开始 Lab3：spawn, 迁移 Lab2 中的工作。

spawn 功能非常简单，记得最后要添加到 manager 中。

4.15 总结

rcore 的文档很详细，通过读文档已经能对 rcore 很清晰的了解了，之后做实验也不存在太大的困难。选做题只做了 mmap lazy 策略。

Lab3

4.17

做完第二个小测验，发现没有安装 riscv-linux-musl-gcc， ArchLinux 中这个包在 AUR 中可以找到，riscv64-gnu-toolchain-musl-bin^AUR^, 也可以在 github 上找到相应的二进制文件 riscv-gnu-toolchain/releases

4.23

完成 Lab3, 选做题花费的时间多了些，主要是卡在了最后一个点上，费了一番功夫才完成了。现在回想起来感觉是因为是在晚上3，4点脑子不清醒，今天下午就顺利很多。
题目难度本身不大，第三阶段需要对项目的结构有一定的了解，不然会不知道要找的模块在哪里。