开发日记和无聊琐碎

前言

现在内存管理的方法都是非连续内存管理，也就是结合段机制和分页机制

段机制

段地址空间

• 进程的段地址空间由多个段组成，比如代码段、堆栈段和符号表段等等

• 段对应一个连续的内存“块”

• 不同段在物理内存中是分散的二维结构

段访问

前言

虚拟内存是计算机系统内存管理的一种技术。它使得应用程序认为它拥有连续的可用的内存（一个连续完整的地址空间），而实际上，它通常是被分隔成多个物理内存碎片，还有部分暂时存储在外部磁盘存储器上，在需要时进行数据交换。

覆盖和技术

• 覆盖

依据程序逻辑结构，将程序划分为若干功能相对独立的模块；将不会同时执行的模块共享同一块内存区域

但是由于需要程序员来划分功能模块和确定模块之间的覆盖关系，所以增加了编程难度，并且也增加了执行时间

• 交换

交换技术和覆盖技术讨论的不一样的是，交换技术讨论的是当前内存足够当前的单个程序运行的内存，但是对于多道程序可能会有运行内存不够的情况

实现方法可以将暂时不能运行的程序放到外存当中，再运行时来执行换入换出操作

虚拟内存

在装载程序时，只将当前指令执行需要的部分页面或段装入内存，指令执行中需要的指令或数据不在内存（称为缺页）时，处理器通知操作系统将相应的页面调入内存，操作系统将内存中暂时不同的页面保存到外存

虚拟内存在页机制的基础上，也就是增加了请求调页和页面置换

• 当用户程序要装载到内存运行时，只装入部分页面，就启动程序运行
• 进程在运行中发现有需要的代码或数据不在内存时，则向系统发出缺页异常请求
• 操作系统在处理缺页异常时，将外存中相应的页面调入内存，使得进程能继续运行

页表项结构

• 驻留位：表示该页是否在内存
• 修改位：表示在内存中的该页是否被修改过
• 访问位：表示该页面是否被访问过（读或写）
• 保护位：表示该页的允许访问方式

缺页中断处理

1. 在内存中有空闲物理页面时，分配一物理页帧f，转第5步；
2. 依据页面置换算法选择将被替换的物理页帧f，对应逻辑页q
3. 如q被修改过，则把它写回外存；
4. 修改q的页表项中驻留位置为0；
5. 将需要访问的页p装入到物理页面f
6. 修改p的页表项驻留位为1,物理页帧号为f；
7. 重新执行产生缺页的指令

页面置换

刚刚在上面说到当发生缺页中断的时候，可能当前已经没有了空闲的物理页了，那就需要进行页面置换

局部页面置换算法

置换的页面仅限于当前进程占用的物理页面内

• 先进先出算法
  维护一个记录所有位于内存中的逻辑页面链表，链表元素按驻留内存的时间排序，链首最长，链尾最短，出现缺页时，选择链首页面进行置换，新页面加到链尾

• 最近最久未使用算法
  缺页时，计算内存中每个逻辑页面的上一次访问时间，选择上一次使用到当前时间最长的页面

  最近最久未使用算法实现一般有两种方法：

  1. 页面链表
     系统维护一个按最近一次访问时间排序的页面链表，访问内存时，找到相应页面，并把它移到链表之首，缺页时，置换链表尾节点的页面
  2. 活动页面栈
     访问页面时，将此页号压入栈顶，并栈内相同的页号抽出，缺页时，置换栈底的页面

• 时钟置换算法
  在页表项中增加访问位，描述页面在过去一段时间的内访问情况，各页面组织成环形链表，指针指向最先调入的页面，访问页面时，在页表项记录页面访问情况，缺页时，从指针处开始顺序查找未被访问的页面进行置换

• 最不常用算法
  缺页时，置换访问次数最少的页面，访问页面时，访问计数加1

全局页面置换算法

置换的页面包括所有可用的物理页面内

• 工作集置换算法
  当前时刻前τ个内存访问的页引用是工作集，τ被称为窗口大小，访存链表：维护窗口内的访存页面链表，访存时，换出不在工作集的页面；更新访存链表，缺页时，换入页面；更新访存链表

• 缺页率置换算法
  访存时，设置引用位标志，缺页时，计算从上次缺页时间tlast 到现在tcurrent 的时间间隔，如果 tcurrent – tlast>T, 则置换所有在[tlast , tcurrent ]时间内没有被引用的页，如果tcurrent – tlast ≤ T, 则增加缺失页到工作集中

缺页中断代码实现

当启动分页机制以后，如果一条指令或数据的虚拟地址所对应的物理页框不在内存中或者访问的类型有错误（比如写一个只读页或用户态程序访问内核态的数据等），就会发生页访问异常

和之前说的普通的中断一样，由CPU发送一个中断信号，然后到最后是由trap_dispatch进行分发处理

1
2
3
4
5
6

case T_PGFLT:  //page fault
    if ((ret = pgfault_handler(tf)) != 0) {
        print_trapframze(tf);
        panic("handle pgfault failed. %e\n", ret);
    }
    break;

其中最重要的就是处理缺页异常的函数

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

int
do_pgfault(struct mm_struct *mm, uint32_t error_code, uintptr_t addr) {
    int ret = -E_INVAL;
    struct vma_struct *vma = find_vma(mm, addr);

    pgfault_num++;
    if (vma == NULL || vma->vm_start > addr) {
        cprintf("not valid addr %x, and  can not find it in vma\n", addr);
        goto failed;
    }
    //check the error_code
    switch (error_code & 3) {
    default:
            /* error code flag : default is 3 ( W/R=1, P=1): write, present */
    case 2: /* error code flag : (W/R=1, P=0): write, not present */
        if (!(vma->vm_flags & VM_WRITE)) {
            cprintf("do_pgfault failed: error code flag = write AND not present, but the addr's vma cannot write\n");
            goto failed;
        }
        break;
    case 1: /* error code flag : (W/R=0, P=1): read, present */
        cprintf("do_pgfault failed: error code flag = read AND present\n");
        goto failed;
    case 0: /* error code flag : (W/R=0, P=0): read, not present */
        if (!(vma->vm_flags & (VM_READ | VM_EXEC))) {
            cprintf("do_pgfault failed: error code flag = read AND not present, but the addr's vma cannot read or exec\n");
            goto failed;
        }
    }
    
    uint32_t perm = PTE_U;
    if (vma->vm_flags & VM_WRITE) {
        perm |= PTE_W;
    }
    addr = ROUNDDOWN(addr, PGSIZE);

    ret = -E_NO_MEM;

    pte_t *ptep=NULL;
    
    if ((ptep = get_pte(mm->pgdir, addr, 1)) == NULL) {
        cprintf("get_pte in do_pgfault failed\n");
        goto failed;
    }
    
    if (*ptep == 0) { // if the phy addr isn't exist, then alloc a page & map the phy addr with logical addr
        if (pgdir_alloc_page(mm->pgdir, addr, perm) == NULL) {
            cprintf("pgdir_alloc_page in do_pgfault failed\n");
            goto failed;
        }
    }
    else { // if this pte is a swap entry, then load data from disk to a page with phy addr
           // and call page_insert to map the phy addr with logical addr
        if(swap_init_ok) {
            struct Page *page=NULL;
            if ((ret = swap_in(mm, addr, &page)) != 0) {
                cprintf("swap_in in do_pgfault failed\n");
                goto failed;
            }    
            page_insert(mm->pgdir, page, addr, perm);
            swap_map_swappable(mm, addr, page, 1);
            page->pra_vaddr = addr;
        }
        else {
            cprintf("no swap_init_ok but ptep is %x, failed\n",*ptep);
            goto failed;
        }
   }
   ret = 0;
failed:
    return ret;
}

• 首先查找此地址是否在某个VMA的地址范围内和根据errorcode看是否满足正确的读写权限
• 如果在此范围内并且权限也正确，这认为这是一次合法访问，但没有建立虚实对应关系
• 如果都不是就是需要进行页的换入操作

页面置换机制代码实现

页面置换这里采用了最简单的FIFO算法

其中最重要的两个函数是_fifo_map_swappable和_fifo_swap_out_victim

1
2
3
4
5
6
7

static int _fifo_map_swappable(struct mm_struct *mm, uintptr_t addr, struct Page *page, int swap_in) {        
    list_entry_t *head=(list_entry_t*) mm->sm_priv;   
    list_entry_t *entry=&(page->pra_page_link);          
    assert(entry != NULL && head != NULL);   
    list_add(head, entry); //将最近用到的页面添加到次序队尾  
    return 0;   
}

它的主要作用是将最近被用到的页面添加到算法所维护的次序队列

1
2
3
4
5
6
7
8
9
10
11
12
13

static int  
_fifo_swap_out_victim(struct mm_struct *mm, struct Page ** ptr_page, int in_tick) {       
    list_entry_t *head=(list_entry_t*) mm->sm_priv;          
    assert(head != NULL);      
    assert(in_tick==0);
    list_entry_t *le = head->prev;  //用le指示需要被换出的页             
    assert(head!=le);  
    struct Page *p = le2page(le, pra_page_link);//le2page宏可以根据链表元素获得对应的Page指针p      
    list_del(le);      //将进来最早的页面从队列中删除      
    assert(p !=NULL);       
    *ptr_page = p; //将这一页的地址存储在ptr_page中
    return 0; 
}

_fifo_swap_out_victim()函数是用来查询哪个页面需要被换出，它的主要作用是用来查询哪个页面需要被换出

前言

最近接了一个外包项目再加上填一些之前立的flag，发现好像很久没有发博客了。现在编译原理操作系统算法方面都还有大坑没有填，加上离实习越来越近，应用层方面的学习也要加强了，但反倒是压力越大越想摸鱼

之前暑假的时候跟着书上写过一个玩具操作系统，然后之后还翻了一下Linux0.11一起写了一个系列的博客，但是还是觉得认识的太浅薄，然后最近发现清华大学的一个操作系统课程，就跟着了。准备用博客来记录一下，虽然会和之前的那个系列有些重复，但是也算是加强巩固了

BIOS

对于所有寄存器开机时都有各自的初始值，在X86中，CS和EIP寄存器分别是F000H,0000FFF0H，所以X86开机执行的第一条指令就是位于这个位置的指令，一般这条指令都是长跳转指令，从这里跳到BIOS程序的起始位置。

BIOS的工作是硬件自检和初始化，并且读取该设备的第一扇区，并且转交CPU控制权

bootloader

由BIOS加载的第一扇区一般放的都是bootloader，bootloader的工作就是

搭这个实验环境主要是为了学习Linux-0.11的代码，那就需要修改代码再次编译来验证自己的想法。主要的实验环境来自实验楼，但是在那上面毕竟不方便，所以就以实验楼上的为基础在自己的虚拟机上搭建一个环境。

主要的实验环境和Linux-0.11的源代码已经打包在我的github上了：Linux0.11-Lab

项目地址：Regex in Python

前两篇已经完成的写了一个基于NFA的正则表达式引擎了，下面要做的就是更近一步，把NFA转换为DFA，并对DFA最小化

DFA的定义

对于NFA转换为DFA的算法，主要就是将NFA中可以状态节点进行合并，进而让状态节点对于一个输入字符都有唯一的一个跳转节点

所以对于DFA的节点就含有一个nfa状态节点的集合和一个唯一的标识和对是否是接收状态的flag

项目地址：Regex in Python

在看一下之前正则的语法的 BNF 范式

1
2
3
4
5

group ::= ("(" expr ")")*
expr ::= factor_conn ("|" factor_conn)*
factor_conn ::= factor | factor factor*
factor ::= (term | term ("*" | "+" | "?"))*
term ::= char | "[" char "-" char "]" | .

上一篇构造了 term 的简单 NFA

构造复杂的 NFA

factor

根据上面的factor ::= (term | term ("*" | "+" | "?"))*，先进行 term 的 NFA 的生成，然后根据词法分析器来判断要进行哪个 factor 的 NFA 的构造

1
2
3
4
5
6
7
8

def factor(pair_out):
    term(pair_out)
    if lexer.match(Token.CLOSURE):
        nfa_star_closure(pair_out)
    elif lexer.match(Token.PLUS_CLOSE):
        nfa_plus_closure(pair_out)
    elif lexer.match(Token.OPTIONAL):
        nfa_option_closure(pair_out)

前言

项目地址：Regex in Python

开学摸鱼了几个礼拜，最近几天用Python造了一个正则表达式引擎的轮子，在这里记录分享一下。

实现目标

实现了所有基本语法

1
2
3
4
5
6

st = 'AS342abcdefg234aaaaabccccczczxczcasdzxc'
pattern = '([A-Z]+[0-9]*abcdefg)([0-9]*)(\*?|a+)(zx|bc*)([a-z]+|[0-9]*)(asd|fgh)(zxc)'

regex = Regex(st, pattern)
result = regex.match()
log(result)

更多示例可以在github上看到

前言

从一开始的引导程序到现在的文件系统已经有十篇了，算是自己对操作系统的学习的一个笔记，原本是想结合自己之前写的玩具操作系统FragileOS，但是之后就转到了结合Linux 0.11的代码去写这个笔记。

因为现在是马上开学了，后劲不足，也有点焦虑，所以这个系列写得非常乱。没有之前那个从零写编译器的系列学习笔记写得顺畅，收获也没有那么多。所以之后开学后可能会打算再读一下Linux 0.11的源码。

前言

这个应该是这个系列的尾声了，一个完整的操作系统可能最主要的也就是分成这几大模块：进程管理、内存管理和文件系统。计算机以进程为基本单位进行资源的调度和分配；而与用户的交互，基本单位则是文件

生磁盘

文件正是对生磁盘的抽象

磁盘的组成

一个磁盘由多个盘面串联而成，而一个盘面又被分为磁道，磁道又由扇区组成。

磁盘的访问单元就是扇区，一个扇区为512字节

前言

在多进程的运行环境下，进程是并发执行的，不同进程间存在着不同的相互制约关系。为了协调进程之间的相互制约关系，达到资源共享和进程协作，避免进程之间的冲突，引入了进程同步的概念。

临界资源

多个进程可以共享系统中的各种资源，但其中许多资源一次只能为一个进程所使用，我们把一次只允许一个进程使用的资源成为临界资源。
对临界资源的访问，必须互斥的进行。每个进程中，访问临界资源的那段代码成为临界区。