Lab5: Process

0x00 The Concepts and Syscalls

It’s hard to define what a process is. Usually it is a procedure in which the OS selects an executable file and performs the dynamic execution. During the execution there will be many interaction between the process and the hardware or virtual resources, and we know those are handled by the OS through syscalls. Besides, there are some important syscalls specially made for process management: fork/exec/waitpid:

• fork: When a process (let’s name it A) call fork, the kernel will create a new process (let’s name it B) which is almost identical to A: they have exactly same stack, .text segment or other data segment content, and every registers except a0 which stores the return value of the syscall. They are in different address spaces but the bytes stores in these address space are exactly same at the moment fork returns. The only way a process can figure out whether it is the new process or the old parent is the returen value of fork: 0 for the new born process and pid of child process for the parent. This parent-child relation is very important in unix-like OS.
• exec: This will help us run a new program in the current address space, use it together with fork we can easily create a process that runs a new program.
• waitpid: When a process returns, the memory resources it have consumed cannot be fully recycled through the exit syscall, for eaxmple the current kernel stack. A typical solution for this is to mark the process as zombie, then it’s parent process do the rest recycle work and get the exit status through the waitpid syscall.

0x01 Data Structures for Process

RAII is heavily used to help us safe memory management. For a process, we bind its pid, kernel stack, and address space(MemorySet) to a TaskControlBlock. The TCBs ares stored in a tree formed by the parent-child relations(created through fork&exec) between processes:

pub struct TaskControlBlock {
    // immutable
    pub pid: PidHandle,
    pub kernel_stack: KernelStack,
    // mutable
    inner: UPSafeCell<TaskControlBlockInner>,
}

pub struct TaskControlBlockInner {
    pub trap_cx_ppn: PhysPageNum,
    pub base_size: usize,
    pub priority: usize,
    pub pass: usize,
    pub task_cx: TaskContext,
    pub task_status: TaskStatus,
    pub memory_set: MemorySet,
    pub parent: Option<Weak<TaskControlBlock> >,
    pub children: Vec<Arc<TaskControlBlock> >,
    pub exit_code: i32,
}

Here we use alloc::sync::Weak to wrap the parent pointer so that there will be no cyclic refernces between the parent and it’s child.

Another significant modification from previous chapter is that we split the original task manager module into Processor and TaskManager.
– The Processor module maintains the CPU’s states, including current process and idle task context. In a single-core CPU environment, we only create one gloable instance of Processor.
– The TaskManager stores all Arcs in a BTreeMap, so that we can easily fetch/remove or add/insert tasks(processes) with our scheduler.

pub struct TaskManager {
    ready_queue: BTreeMap<usize, Arc<TaskControlBlock>>,
    scheduler: Box<Scheduler>,
}

impl TaskManager {
    pub fn new() -> Self {
        let stride_scheduler: Scheduler = Scheduler::new();
        Self {
            ready_queue: BTreeMap::new(),
            scheduler: Box::new(stride_scheduler),
        }
    }

    pub fn add(&mut self, task: Arc<TaskControlBlock>) {
        // update pass for stride scheduler
        let mut task_inner = task.inner_exclusive_access();
        task_inner.pass += BIG_STRIDE / task_inner.priority;
        drop(task_inner);
        self.scheduler.insert_task(task.getpid(), task.clone().inner_exclusive_access().pass);
        self.ready_queue.insert(task.getpid(), task);
    }

    pub fn fetch(&mut self) -> Option<Arc<TaskControlBlock>> {
        let next_pid = loop {
            if let Some(next_pid) = self.scheduler.find_next_task() {
                // TODO how about wait state
                if self.ready_queue.contains_key(&next_pid){
                    break next_pid
                }
            } else {
                return None;
            }

        };
        let (_, task) = self.ready_queue.remove_entry(&next_pid).unwrap();
        Some(task)
    }
}

0x02 Process Management

继续阅读“rCore-OS Lab5: Process”

Lab4: Address Space

Address Space is a significant mechanism in modern operating system. By adding an abstract layer between code and physical memory, it frees the developers from the painful memory arrangement work, helping them focus more on their code other than the hardware stuff.

The following figure gives an overview of how Address Space works:

Having Address Space enabled, the codes can only see the Virtual Address. If a process wants to access any address virt_addr, it will be first translated to Physical Address by CPU’s MMU module according to the process’s page table.

0x00 Hardware supports for Multilevel Paging in RISCV

The MMU is disabled by default, thus previously any program are able to access any physical memory. We can enbale the MMU by setting a register named satp:

The above figure shows the meaning of bits in satp:

• MODE controls how the MMU translate address. When MODE = 0 the MMU is disabled, and when ‘MODE’ = 8 the MMU use page table mechanism to translate the address.
• ASID indetifies the address space by id, since we don’t have process implemented yet we just ignore it.
• PPN is the physical page number of the root page table entry.

The address format under page table mechanism consists of two parts: page number and offset:

Each page table entry consists of 3 level virtual page number (vpn) and several flag bits:

With these knowledge we can easily understand how the MMU translates virtual memory address:

TLB

TLB (Translation Lookaside Buffer) works like some kinds of cache, note that we have to use sfence.vma instruction to refresh it after we change satp or any page table entry.

0x01 Address Space of Kernel and User

After satp is enabled, the memory of kernel and user applications are seperated, we need to carefully handle the interaction between different address spaces. In rCore, the designers use a Trampoline to bridge the kernel and usermode applications:

The virtual address of Trampoline is exactly same across each user spaces and the kernel space. Note that there is a guard page between kernel stacks. Those holes in the address space are settled to prevent buffer overflow damage in kernel stack.

The address space of the kernel is illustrated in the following figure:

The permissions here are critical for system security: no page table can be both writable and executable. Besides, we use identical mapping here, so the kernel can read/write any user space memory in an easy way.

In user mode, the address space is quite familiar to us:

We palce the TrapContext just under the Trampoline.

0x02 Multi-tasking with Address Space

__all_traps and trap_return shoud take care of the address space switch. Note that for each task, we should set their TaskContext’s initial ra to trap_return. We don’t have the ra pushed in kernel stack for the first time to run a task so we have to handle this manually.

The syscall call stack is:

syscall: user space ecall -> __all_traps(trampoline) -> trap_handler -> do syscall -> trap_return -> __restore -> user space

The switch process is:
继续阅读“rCore-OS Lab4: Address Space”

声明: 由于经济原因本人已无力继续维护此服务，有愿意接手的人可以点击本行与我联系，谢谢

最近有一些同学反映他们需要大量使用识别工具，但由于种种原因不想或者不能在自己电脑上装客户端，希望能将第三方API集成到Web端。

这个功能我很早就有意识到有需求，但是我还是比较想让大家用MathpixCsharp，因为Web端不支持快捷键，而我个人认为快捷键对于生产力来说非常重要，没有的话体验会很差。但是由于最近我女朋友换了Mac电脑，我意识到有很多MacOS的同学目前是没有办法用MathpixCsharp的，所以我就打算先把这个功能加到Web端，满足更多平台同学的需求。

昨晚抽空先糊了一个勉强能用的界面提供了这项功能，使用示例参考下图：

基本的使用方式跟原来的免费接口是一样的，使用截图工具将要识别的公式截取之后在Web页面粘贴即可。可以参考原版的介绍文章。

新增的付费接口的使用方法

1. 到这个网站购买卡密
2. 在网页中点选 第三方付费接口
3. 将得到的卡密中的APP_ID和APP_KEY分别填入网页中提示填写的两个文本框内
4. 然后截图+粘贴使用即可

其中Uses会显示当前卡密的剩余使用次数。

有任何疑问都可以仔细阅读MathpixCsharp的介绍：http://blog.itewqq.cn/mathpixcsharp-opensource-windows-client/ 和免费版Web app的介绍http://blog.itewqq.cn/image-to-latex-convert-app/

新的版本是临时糊出来的，比较粗糙，有各种问题、意见、建议都欢迎大家到github提issues：https://github.com/itewqq/MathF/issues

另：由于我的前端优化和审美UI设计能力几乎为0，所以如果您对于前端界面有自己的想法，也可以直接修改代码（ https://github.com/itewqq/MathF/blob/master/index.html ），欢迎PR！

题目链接

题意：

有 $m$ 个小朋友，圣诞老人有 $N$ 个咒语，第 $i$ 个咒语施展出来的话，可以给 $[Li,Ri]$ 范围内的小朋友一块糖果，对每个小朋友来说，他得到的糖如果是奇数的话就会happy，否则就会不happy。

现在要求求出当圣诞老人采取某种最优的施展咒语的策略（一些用了一些没用，具体不需要求出来）的时候，最多有多少个小朋友可以happy？

题目保证，每个小朋友最多被 k 个咒语覆盖到。

数据范围： $m \le 10^9$, $N \le 10^5$, $1 \le k \le 8$, $1 \le Li \le Ri \le m$

题解：

(先吐槽下这题竟然2600分，这可是个div2D)

用扫描线的思想来做。

假设有一根竖直的扫描线在横轴上扫过去，那么他只会在每个 $[Li,Ri]$ 段的头尾两端发生状态变化，我们设置这些点为关键点，当我们采取某种特定的策略的时候，两个关键点之间的数据是不会发生变化的。

由于每个点最多被 $k$ 个线段覆盖，我们可以暴力的枚举出来当前扫描到的点的状态，即它被多少种线段覆盖到了，这个状态显然可以用二进制位来表示。由于我们是一个一个关键点找过去的，而两个关键点之间的数据状态仅由前一个点即可确定，所以我们的dp转移只需要考虑前一个点。

具体的转移：设 $dp[i][S]$ 为考虑到了第i个关键点（按从小到大的顺序），覆盖当前点的线段状态为 $S$ 的时候，最优解是多少。

1. 当当前点为某线段的起点时，我们考虑每个 $S$ 中是否包含了第 $i$ 条线段，如果
   • 包含了，那么 $dp[i][S]=dp[i-1][S^(1<<p)]+(i到第i+1个关键点的距离)*(S中二进制位为1的奇偶性)$ ,因为我们相当于加上了新的一段；(其中p为当前线段所应在的二进制位，下同)
   • 没包含，那么$dp[i][S]=dp[i][S]$ $+(i到第i+1个关键点的距离)*(S中二进制位为1的奇偶性)$，等于说我们的扫描线在这一段仍然是按照之前的状态在扫描。
2. 当当前点为某线段的终点时，我们仍然考虑每个 $S$ 中是否包含了第 $i$ 条线段，如果
   • 包含了，由于这条线段到此我们认为结束了，所以这种状态根本不合法，直接设置为$-INF$
   • 没包含，那么$dp[i][S]=max(dp[i-1][S],dp[i-1][S^(1<<p)])$ $+(i到第i+1个关键点的距离)*(S中二进制位为1的奇偶性)$，因为我们前面一段可能选了大，也可能不选更大，我们需要取个最优解。

然后我们可以发现两个转移都有方向性，我们可以用滚动数组忽略掉第一维，也就是说状态数组可以只开 $dp[1<<8]$ 即可。

继续阅读“[DP][扫描线][思维] Codeforces 1313D Happy New Year”