跳转至

课程笔记

  • 分类于 课程笔记
  • 需要 32 分钟阅读时间

具体数学

具体数学公式小册子

推广一个自己的 github 仓库，期望共同完善。 阅读具体数学电子书籍时，由于经常需要查看某个编号的公式因此产生了这个项目，用于阅读时查阅公式 https://github.com/TheRainstorm/concrete_math_formulas

成套方法

在具体数学 (Concrete Mathematics) 课本中，在解约瑟夫递推方程时，第一次介绍了成套方法 (repertoire method)。之后也使用这种方式求解各种递推方程。相信很多人第一次看到这种方法时都会感觉到不可思议——还能这样？虽然每一步都能看懂，但是就是不知道这种方法是怎么想到的。在查阅了一点资料后，我对该方法有了更多的认识。先说明一点，该方法并不是一种万能方法，实际上要求问题要有线性结构。

参考：linear algebra - Mathematical explanation for the Repertoire Method - Mathematics Stack Exchange

  • 分类于 课程笔记
  • 需要 17 分钟阅读时间

ucore-mips 代码分析

1. Makefile

  1. boot/loader.bin基本就是一个读取 elf 的函数，我们上板使用 pmon 加载 ucore，因此用不到。
  2. obj/ucore-kernel-initrd是一个 elf 文件，特殊之处在于，它的 data 段包含user/_archive目录下的文件（包含一个 test.txt）和$(USER_APP_BINS)（如 sh, ls 等用户程序）的内容。将内核和文件系统打包到了一起。

2. kernel_entry

kern/init/entry.S

  1. 设置了$gp

    定义在链接脚本里，可以通过readelf obj/ucore-kernel-initrd -a|grep _gp来查看其值。参考值（修改了代码编译出的值可能不一样）0x800c7f40

  2. 设置了$sp，启动时用的栈，栈大小为KSTACKSIZE，8KB

    参考值：bootstacktop(0x80068730)，bootstack(0x80066730)

  3. 设置了 Ebase 为__exception_vector。参考值：0x8002b000。__exception_vector 包含了各异常向量地址的入口。

3. kern_init

kern/int/init.c

杂项
tlb_invalidate_all

定义于 kern/include/thumips_tlb.h 和 kern/mm/thumips_tlb.c

tlb_invalidata_all 循环调用 write_one_tlb 清空 tlb 表项 默认 tlb 有 128 项，虽然不会导致错误，但是可以优化

pic_init

定义于 kern/driver/picirq.c pic_init -> write_c0_status 将 Statu 中的 IM 域全置 0，关闭所有中断。 之后可以通过 pic_enable(int irq) 或 pic_disable(int irq) 开关中断

cons_init & clock_init

一个初始化串口，一个初始化时钟中断。

相关宏定义于/kern/include/thumips.h

#define COM1_IRQ        3
#define TIMER0_IRQ       7

clock 需要用到cp0_count和cp0_compare 设置 clock 中断后，每clock.c::TIMER0_INTERVAL=1000000 后会产生一个时钟中断

check_initrd

检查内核是否有 initrd，通过判断是否_initrd_begin == _initrd_end)

kprintf

内核第一次输出信息

const char *message = "(THU.CST) os is loading ...\n\n";
kprintf(message);

kprintf 函数最后调用串口的 cons_putc 输出字符。串口输出字符采用忙等待方式。

kern/lib/stdio.c::kprintf -> kern/lib/stdio.c::vkprintf -> kern/lib/printfmt.c::vprintfmt(cputch, ...)

kern/lib/stdio.c::cputch -> kern/driver/console.c::cons_putc

#!kern/driver/console.c

static void
serial_putc_sub(int c) {
    while (!(inb(COM1 + COM_LSR) & COM_LSR_TXRDY)) {
    }
    outb(COM1 + COM_TX, c);
}

作为对比，用户程序 cprintf

user/lib/stdio.c::cprintf -> user/lib/stdio.c::vcprintf -> user/lib/stdio.c::vprintfmt(cputch, ...)
user/lib/stdio.c::cputch -> user/lib/syscall.c::sys_putc -> syscall(SYS_putc, )
系统调用，进入内核
异常处理程序调用kern/syscall/syscall.c::sys_putc -> kern/lib/stdio.c::kputchar -> cons_putc

用户程序输出每一个字符都会触发一次系统调用

pmm_init
page 结构体
struct Page {
    atomic_t ref;                   // page frame's reference counter
    uint32_t flags;                 // array of flags that describe the status of the page frame
    unsigned int property;          // used in buddy system, stores the order (the X in 2^X) of the continuous memory block
    int zone_num;                   // used in buddy system, the No. of zone which the page belongs to
    list_entry_t page_link;         // free list link
//    swap_entry_t index;             // stores a swapped-out page identifier
    list_entry_t swap_link;         // swap hash link
};

ucore 将物理内存划分成一个一个的页，并使用 Page 结构体数组来管理。一个 Page 项对应一个物理页。

参考 pmm.c::page_init 代码

kprintf("memory map:\n");
kprintf("    [");
printhex(KERNBASE);
kprintf(", ");
printhex(KERNTOP);
kprintf("]\n\n");

maxpa = KERNTOP;
npage = KMEMSIZE >> PGSHIFT;

// end address of kernel
extern char end[];
// put page structure table at the end of kernel
pages = (struct Page *)ROUNDUP_2N((void *)end, PGSHIFT);

KMEMSIZE代表内核管理的物理内存的大小，npage 计算出来为物理页的个数。

end 在链接脚本中定义，为 ucore-kernel-initrd 的结尾。即 ucore 在内核的结尾分配了（直接写）Page 数组的空间，pages 为数组的起始地址。

此时 page 项可以和物理页一一对应起来了

static inline ppn_t
page2ppn(struct Page *page) {
    return page - pages;
}

static inline uintptr_t
page2pa(struct Page *page) {
    return KERNBASE + (page2ppn(page) << PGSHIFT);
}

static inline struct Page *
pa2page(uintptr_t pa) {
    if (PPN(pa) >= npage) {
        panic("pa2page called with invalid pa");
    }
    return &pages[PPN(pa)];
}

static inline void *
page2kva(struct Page *page) {
    return KADDR(page2pa(page));
}

这里强调一下page2kva中KADDR的作用，事实上如果看其定义的话，KADDR(pa) 的值和 pa 是一样的，如下

/* *
 * PADDR - takes a kernel virtual address (an address that points above KERNBASE),
 * where the machine's maximum 256MB of physical memory is mapped and returns the
 * corresponding physical address.  It panics if you pass it a non-kernel virtual address.
 * */
#define PADDR(kva) ({                                                   \
            uintptr_t __m_kva = (uintptr_t)(kva);                       \
            if (__m_kva < KERNBASE) {                                   \
                panic("PADDR called with invalid kva %08lx", __m_kva);  \
            }                                                           \
            __m_kva ;                                         \
        })

/* *
 * KADDR - takes a physical address and returns the corresponding kernel virtual
 * address. It panics if you pass an invalid physical address.
 * */
#define KADDR(pa) ({                                                    \
            uintptr_t __m_pa = (pa);                                    \
            size_t __m_ppn = PPN(__m_pa);                               \
            if (__m_ppn >= npage) {                                     \
                panic("KADDR called with invalid pa %08lx", __m_pa);    \
            }                                                           \
            (void *) (__m_pa);                               \
        })

而之所以需要进行一次转换，主要是保持逻辑上的一致性。因为 CPU 直接发出的地址都是虚拟地址，会经过 MMU 进行虚拟地址转换（一般基于 TLB，而 TLB 基于操作系统管理的页表）。整个转换过程是硬件自动完成的，因此软件基本不用和物理地址打交道（操作系统中涉及到和硬件软硬件协同的部分会涉及到物理地址，如页表中存储的地址是物理地址，当 MIPS 中 tlb refill 异常时，便会读取页表项加载到 TLB 表项中）

因而我们在代码中访问数据时都要使用虚拟地址。

因为这里的整个内核虚拟空间（[KERNBASE, KERNBASE+KMEMSIZE]=[0x8000_0000, 0x8200_0000)）都位于 MIPS 中的 kseg0 段，而该段采用固定地址映射的方式，而不使用 TLB，因此内核访问整个内核虚拟地址空间丝毫不用担心。

这里应该有一个错误

按照定义来说，page2pa 就应该是 (page2ppn(page) << PGSHIFT)，加了 KERNBASE 后反而是虚拟地址了。

不过因为 KADDR 也错了，因此当我们分配了一个空闲物理页 page 后，要获得其虚拟地址

KADDR(page2pa(page))反而没错了

空闲页

空闲地址开始于 Page 数组之后。init_memmap 会调用 pmm_manager 的 init_memmap 函数，用于记录哪些页是空闲的。

uintptr_t freemem = PADDR((uintptr_t)pages + sizeof(struct Page) * npage);
PRINT_HEX("freemem start at: ", freemem);

uint32_t mbegin = ROUNDUP_2N(freemem, PGSHIFT);
uint32_t mend = ROUNDDOWN_2N(KERNTOP, PGSHIFT);
assert( mbegin < mend );
init_memmap(pa2page(mbegin), (mend - mbegin) >> PGSHIFT );
PRINT_HEX("free pages: ", (mend-mbegin)>>PGSHIFT);
PRINT_HEX("## ", sizeof(struct Page));
pmm_manager

物理内存管理其实就是要实现物理空闲页的分配和回收，ucore 定义了 pmm_manager 的结构体，可以认为 C 中实现的类。

关键的两个函数：

struct Page *(*alloc_pages)(size_t n);
void (*free_pages)(struct Page *base, size_t n);

alloc_pages 从空闲页中分配了一段连续的空闲页

而 free_pages 则将指定的一段连续的页重新回收为空闲页

ucore 代码实现了伙伴分配系统 (buddy system)，可以参考其具体实现

页表相关函数

ucore 实现了二级页表

关键函数

pte_t *get_pte(pde_t *pgdir, uintptr_t la, bool create);
struct Page *get_page(pde_t *pgdir, uintptr_t la, pte_t **ptep_store); //根据 pte 的值获得对应的 page
void page_remove(pde_t *pgdir, uintptr_t la);
int page_insert(pde_t *pgdir, struct Page *page, uintptr_t la, uint32_t perm);
struct Page * pgdir_alloc_page(pde_t *pgdir, uintptr_t la, uint32_t perm);
get_pte
pte_t *get_pte(pde_t * pgdir, uintptr_t la, bool create)

函数作用：给定页目录表的虚拟地址，查找虚拟地址 la 对应的页表项 pte。（只要 la 在一个页内，返回的 pte 是相同的） 注：获得的是 pte 项的虚拟地址 过程：

  1. 先计算页目录表中对应 pde 表项的虚拟地址

    pdep = pgdir + PDX(la)

  2. 如果 pde 项有效，即((*pdep)&PTE_P) == 0。直接访问 pde 获得 la 对应二级页表的物理地址。

    PDE_ADDR(*pdep)

  3. 计算二级页表中对应页表项 pte 的物理地址

    (pte_t*)(    PDE_ADDR(*pdep)   ) + PTX(la)

  4. 转换成虚拟地址

    (pte_t*)KADDR(   (uintptr_t)(  (pte_t*)(PDE_ADDR(*pdep))+PTX(la)  )  )

  5. 如果 02 中无效，则需要根据 create 决定是否创建二级页表。（下面代码只考虑了创建情形，并为了突出重点，删减了许多有用的代码）

    struct Page* new_pte = alloc_page();

uintptr_t pa = (uintptr_t)page2kva(new_pte);
*pdep = PADDR(pa);

    最后一行，页表中存储的是物理地址。然而根据之前的分析，我们知道上面代码中的 PADDR(pa) 实际上是虚拟地址。然而我们发现在这样设置之后，下次调用 get_pte 时，获得的 pte 的地址确实是虚拟地址（KADDR 不产生作用）。

page_insert
int page_insert(pde_t *pgdir, struct Page *page, uintptr_t la, uint32_t perm)

作用：将虚拟地址 la 映射到 page 对应的物理页上

步骤：

  1. 根据虚拟地址 la 查找到二级页表项 ptep

  2. 如果原本 ptep 已经映射到另一个物理页上了，则删除该映射（有可能导致回收物理页）

  3. 设置 ptep 映射到新物理页

    *ptep = page2pa(page) | PTE_P | perm;

    由以上代码，可以看到二级页表项中存储的地址其实是虚拟地址。

page_remove
void page_remove(pde_t *pgdir, uintptr_t la) {

作用：解除 pgdir 中虚拟地址 la 的映射

步骤：

  1. 获得 pte

    pte_t *ptep = get_pte(pgdir, la, 0);

  2. 如果ptep != NULL且*ptep & PTE_P，

    struct Page *page = pte2page(*ptep);
page_ref_dec(page);
// and free it when reach 0
if(page_ref(page) == 0){
    free_page(page);
}

  3. 清除映射

    *ptep = 0;
pgdir_alloc_page
struct Page * pgdir_alloc_page(pde_t *pgdir, uintptr_t la, uint32_t perm)

作用：该函数分配一个物理页，并将 la 对应的虚拟页，映射到该物理页

check
check_pgdir
  1. 将虚拟地址 0x0 映射到一个物理页 (随便分配一个 page, p1) 上。
  2. 将虚拟地址 0x1000(PAGESIZE) 映射到一个物理页 (随便分配一个 page, p2)。
  3. 将 0x1000 重新映射到 p1. ...... 主要是检查了 page_insert, page_remove 等函数的正确性。
check_boot_pgdir（tlb refill 处理)

  1. 分配一个物理页，并写入初始值

    struct Page *p;
p = alloc_page();
*(int*)(page2kva(p) + 0x100) = 0x1234;

  2. 将两个虚拟页映射到该物理页上

    assert(page_insert(boot_pgdir, p, 0x100, PTE_W) == 0);
assert(page_ref(p) == 1);
assert(page_insert(boot_pgdir, p, 0x100 + PGSIZE, PTE_W) == 0);
assert(page_ref(p) == 2);

  3. 直接使用虚拟地址访问该物理页，引发 tlb refill 异常

    assert(*(int*)0x100 == 0x1234);

  4. 进入对应异常处理程序

    static void handle_tlbmiss(struct trapframe* tf, int write)
{
  int in_kernel = trap_in_kernel(tf);
  assert(current_pgdir != NULL);
  uint32_t badaddr = tf->tf_vaddr;
  int ret = 0;
  pte_t *pte = get_pte(current_pgdir, tf->tf_vaddr, 0);
  if(pte==NULL || ptep_invalid(pte)){   //PTE miss, pgfault
      kprintf("## pagefault in kernel, badaddr: 0x%x\n", badaddr);
    //tlb will not be refill in do_pgfault,
    //so a vmm pgfault will trigger 2 exception
    //permission check in tlb miss
    ret = pgfault_handler(tf, badaddr, get_error_code(write, pte));
  }else{ //tlb miss only, reload it
    /* refill two slot */
    /* check permission */
    if(in_kernel){
      kprintf("## tlb refill in kernel, badaddr: 0x%x\n", badaddr);
      tlb_refill(badaddr, pte); 
      return;
    }else{
      if(!ptep_u_read(pte)){
        ret = -1;
        goto exit;
      }
      if(write && !ptep_u_write(pte)){
        ret = -2;
        goto exit;
      }
    //kprintf("## refill U %d %08x\n", write, badaddr);
      tlb_refill(badaddr, pte);
      return ;
    }
  }

exit:
  if(ret){
    print_trapframe(tf);
    if(in_kernel){
      panic("unhandled pgfault");
    }else{
      do_exit(-E_KILLED);
    }
  }
  return ;
}

    1. 首先判断是否在内核中发生了异常，这里通过 Status.KSU 位来判断，2'b00 表示 kernel mode，2'b10 表示 user mode。

      bool
trap_in_kernel(struct trapframe *tf) {
  return !(tf->tf_status & KSU_USER);
}

    2. 然后获得 pte

      pte_t *pte = get_pte(current_pgdir, tf->tf_vaddr, 0);

    3. 之后进入 tlb_refill 函数，tlb_refill 执行 tlbwr，从 pte 读取映射的物理页号写入到 tlb 项中。（一次映射两页）

      tlb_replace_random(0, badaddr & THUMIPS_TLB_ENTRYH_VPN2_MASK, 
      pte2tlblow(*pte), pte2tlblow(*(pte+1)));

终端输出

## tlb refill in kernel, badaddr: 0x100
check_boot_pgdir() succeeded!
kmalloc

pmm_init 中还调用了 kmalloc_init。

kmalloc 中主要实现了以下关键函数

void *kmalloc(size_t n);
void kfree(void *objp);

可以看到 kmalloc 函数的参数为字节数，返回值为分配的物理内存的虚拟起始地址。

kmalloc 利用到了 slab 机制

slab 是 Linux 操作系统的一种内存分配机制。其工作是针对一些经常分配并释放的对象，如进程描述符等，这些对象的大小一般比较小，如果直接采用伙伴系统来进行分配和释放，不仅会造成大量的内存碎片，而且处理速度也太慢。而 slab 分配器是基于对象进行管理的，相同类型的对象归为一类 (如进程描述符就是一类)，每当要申请这样一个对象，slab 分配器就从一个 slab 列表中分配一个这样大小的单元出去，而当要释放时，将其重新保存在该列表中，而不是直接返回给伙伴系统，从而避免这些内碎片。

vmm_init

通过内存地址虚拟化，可以使得软件在没有访问某虚拟内存地址时不分配具体的物理理内存，而只有在实际访问某虚拟内存地址时，操作系统再动态地分配物理内存，建立虚拟内存到物理理内存的页映射关系，这种技术称为按需分页（demand paging）。把不不经常访问的数据所占的内存空间临时写到硬盘上，这样可以腾出更更多的空闲内存空间 给经常访问的数据；当 CPU 访问到不不经常访问的数据时，再把这些数据从硬盘读入到内存中。这种技术称为页换入换出 (page in/out)

vma_struct

vma 用于描述进程对虚拟内存的需求

struct vma_struct {
    struct mm_struct *vm_mm; // the set of vma using the same PDT 
    uintptr_t vm_start;      // start addr of vma 
    uintptr_t vm_end;        // end addr of vma
    uint32_t vm_flags;       // flags of vma
    list_entry_t list_link;  // linear list link which sorted by start addr of vma
};

vma 指示了一段连续的虚拟内存空间，不同 vma 通过 list_link 相连，共同表示一个进程的虚拟内存空间。

mm_struct
struct mm_struct {
    list_entry_t mmap_list;        // linear list link which sorted by start addr of vma
    struct vma_struct *mmap_cache; // current accessed vma, used for speed purpose
    pde_t *pgdir;                  // the PDT of these vma
    int map_count;                 // the count of these vma
 void *sm_priv;       // the private data for swap manager
 atomic_t mm_count;
 semaphore_t mm_sem;
 int locked_by;
};

mm_struct 用于管理一系列使用同一个页目录表的 vma 的集合。

进程控制块中包含一个 mm_struct 的指针，用于管理该进程的虚拟内存空间

关键函数
struct vma_struct *find_vma(struct mm_struct *mm, uintptr_t addr);
struct vma_struct *vma_create(uintptr_t vm_start, uintptr_t vm_end, uint32_t vm_flags);
void insert_vma_struct(struct mm_struct *mm, struct vma_struct *vma);
check_pgfault（pagefault 的处理）

  1. 创建 mm_struct

    check_mm_struct = mm_create();

    这里的check_mm_struct为全局变量

  2. 分配[0, PTSIZE]的虚拟内存

    struct vma_struct *vma = vma_create(0, PTSIZE, VM_WRITE); //如果该成 VM_READ，之后在 do_pgfault 便会通不过权限检查。
insert_vma_struct(mm, vma);

  3. 访问 0x100

      uintptr_t addr = 0x100;
  assert(find_vma(mm, addr) == vma);

  int i, sum = 0;
  for (i = 0; i < 100; i ++) {
    *(char *)(addr + i) = i;    //page fault
    sum += i;
  }
  for (i = 0; i < 100; i ++) {
    sum -= *(char *)(addr + i);
  }
  assert(sum == 0);

  4. 触发 tlb refill 异常。（实际为 pagefault，此时页表中没有该映射，因此 tlb 中也没有该项）

    参考之前 tlb refill 异常处理的代码，进入 pgfault_handler

    1. 首先通过判断 check_mm_struct 非空，知道是在执行 check_pgfault 函数，将 mm 设置为 check_mm_struct 2. 在 do_pgfault 中首先调用 find_vma 函数，确定该虚拟地址是有效的 3. 然后检查该地址访问权限是否正确（如果将 4. 都通过了后，调用 pgdir_alloc_page，直接分配一个物理页，并在 mm->pgdir 中插入映射关系。 5. 异常处理完成并返回

  5. 再次触发 tlb refill 异常。（现在页表中存在了该映射，因此进入 tlb_refill 函数）

终端输出

## pagefault in kernel, badaddr: 0x100
## tlb refill in kernel, badaddr: 0x100
check_pgfault() succeeded!

代码

static inline int get_error_code(int write, pte_t *pte)
{
  int r = 0;
  if(pte!=NULL && ptep_present(pte)) //因为 pagefault 的条件 (pte==NULL || ptep_invalid(pte))，这里根本不可能为真
    r |= 0x01;
  if(write)
    r |= 0x02;
  return r;
}

static int
pgfault_handler(struct trapframe *tf, uint32_t addr, uint32_t error_code) {
  extern struct mm_struct *check_mm_struct;
  struct mm_struct *mm;
  if (check_mm_struct != NULL) {
    assert(current == NULL);
    mm = check_mm_struct;
  }
  else {
    if (current == NULL) {
      print_trapframe(tf);
      //print_pgfault(tf);
      panic("unhandled page fault.\n");
    }
    mm = current->mm;
  }
  return do_pgfault(mm, error_code, addr);
}

#! vmm.c

//page fault number
volatile unsigned int pgfault_num=0;
// do_pgfault - interrupt handler to process the page fault execption
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);
  //kprintf("## %08x %08x\n", error_code, addr);

  pgfault_num++;
  if (vma == NULL || vma->vm_start > addr) {
    kprintf("not valid addr %x, and  can not find it in vma\n", addr);
    goto failed;
  }

  switch (error_code & 3) {
    default:
      /* default is 3: write, present */
    case 2: /* write, not present */
      if (!(vma->vm_flags & VM_WRITE)) {
        kprintf("write, not present in do_pgfault failed\n");
        goto failed;
      }
      break;
    case 1: /* read, present */
      kprintf("read, present in do_pgfault failed\n");
      goto failed;
    case 0: /* read, not present */
      if (!(vma->vm_flags & (VM_READ | VM_EXEC))) {
        kprintf("read, not present in do_pgfault failed\n");
        goto failed;
      }
  }

  uint32_t perm = PTE_U;
  if (vma->vm_flags & VM_WRITE) {
    perm |= PTE_W;
  }
  addr = ROUNDDOWN_2N(addr, PGSHIFT);

  ret = -E_NO_MEM;

  // try to find a pte, if pte's PT(Page Table) isn't existed, then create a PT.
  pte_t *ptep=NULL;
  if ((ptep = get_pte(mm->pgdir, addr, 1)) == NULL) {
    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) {
      goto failed;
    }
  }
  else { // if this pte is a swap entry, then load data from disk to a page with phy addr, 
    // map the phy addr with logical addr, trig swap manager to record the access situation of this page
    if(swap_init_ok) {
      panic("No swap!! never reach!!"); 
    }
    else {
      kprintf("no swap_init_ok but ptep is %x, failed\n",*ptep);
      goto failed;
    }
  }
  /* refill TLB for mips, no second exception */
  //tlb_refill(addr, ptep);
  ret = 0;
failed:
  return ret;
}
函数调用

  1. 使用 jal 调用函数，使用 jr ra 返回。使用 a0-a3 传递参数，使用 v0-v1 传递返回值。对于更多的参数，使用栈传递。

  2. 为了防止寄存器的值被覆盖。需要在存储寄存器的值，可以由 caller 或者 callee 来完成。但是只有一方完成时，因为 caller 不知道 callee 会用哪些寄存器，或者 callee 不知道 caller 需要用哪些寄存器。因此就会导致存储不必要的寄存器。MIPS 采用了一种折衷的策略，将寄存器分为 caller-save（如 t0-t7, a0-a3, v0-v1）和 callee-save（如 s0-s7, ra）

  3. fp 寄存器（也是 s8）用于指向栈帧的第一个元素。因为 x86 中提供了 push 和 pop 指令，sp 的位置是变化的，要引用不同变量的值是用 fp 更方便。而 MIPS 中则是在函数的开头手动将 sp 设置，sp 之后的值不会变化，因此 fp 貌似作用不大。

  4. gp 寄存器，用于程序访问全局变量（比如函数的地址）。

    ps. 使用 mipsel-linux-gnu-gcc -S 编译一个简单的函数调用测试代码。不知为什么和上面讲的 caller-save，callee-save 对不上。比如函数开头addiu $sp,$sp,-40，但结果却根本没用上这么大的空间。然后，为什么还会出现sw $a0,40($fp)，即将参数a0写入父函数栈帧的情况。（这个然后 fp 和 sp 始终相等，不知道为什么要去存储 fp

sched_init & proc_init
proc_struct(进程控制块)
struct proc_struct {
    enum proc_state state;                      // Process state
    int pid;                                    // Process ID
    int runs;                                   // the running times of Proces
    uintptr_t kstack;                           // Process kernel stack
    volatile bool need_resched;                 // bool value: need to be rescheduled to release CPU?
    struct proc_struct *parent;                 // the parent process
    struct mm_struct *mm;                       // Process's memory management field
    struct context context;                     // Switch here to run process
    struct trapframe *tf;                       // Trap frame for current interrupt
    uintptr_t cr3;                              // CR3 register: the base addr of Page Directroy Table(PDT)
    uint32_t flags;                             // Process flag
    char name[PROC_NAME_LEN + 1];               // Process name
    list_entry_t list_link;                     // Process link list 
    list_entry_t hash_link;                     // Process hash list
    int exit_code;                              // exit code (be sent to parent proc)
    uint32_t wait_state;                        // waiting state
    struct proc_struct *cptr, *yptr, *optr;     // relations between processes
    struct run_queue *rq;                       // running queue contains Process
    list_entry_t run_link;                      // the entry linked in run queue
    int time_slice;                             // time slice for occupying the CPU
    struct fs_struct *fs_struct;                // the file related info(pwd, files_count, files_array, fs_semaphore) of process
};
tf
struct trapframe {
 uint32_t tf_vaddr; /* coprocessor 0 vaddr register */
 uint32_t tf_status; /* coprocessor 0 status register */
 uint32_t tf_cause; /* coprocessor 0 cause register */
 uint32_t tf_lo;
 uint32_t tf_hi;
 uint32_t tf_ra; /* Saved register 31 */
  struct pushregs tf_regs;
 uint32_t tf_epc; /* coprocessor 0 epc register */
};

tf 记录了

  1. 进程的上下文：32 个通用寄存器的值
  2. epc, status, cause 等 CP0 寄存器

进入异常后，要将 sp 切换到内核栈。对于内核进程来说，就是当前的 sp，而对于用户进程来说，需要从进程控制块中读取 kstack 的地址。

uCore 内核允许嵌套中断。因此为了了保证嵌套中断发⽣生时 tf 总是能够指向当前的 trapframe，uCore 在内核栈上维护了了 tf 的链。

发生中断（异常）时，trap.c::mips_trap 会改变当前进程 current->tf 的值

current->tf = *tf*;

要实现嵌套中断，需要在改变 current->tf 前使用一个 trapframe *otf（局部变量，存储在内核栈中）存下来。之后再将 current->tf 恢复为 otf。

这里提一下，如果一个用户进程发生了异常，在异常处理程序中又发生了一次异常，那么第二次异常时，已经处于了内核模式（在压入 tf 后，调用 mips_trap 之前）。在 ramExcHandle_general 中就不会计算新的 sp

mfc0 k0, CP0_STATUS /* Get status register */
andi k0, k0, KSU_USER/* Check the we-were-in-user-mode bit */
beq k0, $0, 1f  /* If clear, from kernel, already have stack */
kstack

内核栈用于存储中断帧 tf 以及作为进程在内核中执行使用的 sp

对于内核线程，该栈就是运行时的程序使⽤用的栈。而对于普通进程，uCore 在创建进程时分配了了 2 个连续的物理理⻚页作为内核栈的空间。

内核栈位于内核地址空间，并且是不不共享的（每个线程都拥有⾃自⼰己的内核栈），因此不不受到 mm 的管理理，当进程退出的时候，内核能够根据 kstack 的值快速定位栈的位置并进⾏行行回收。

mm

内存管理理的信息，包括内存映射列列表、⻚页表指针等。mm 成员变量量在 lab3 中⽤用于虚存管理理。但在实际 OS 中，内核线程常驻内存，不不需要考虑 swap page 问题，在 lab3 中涉及到了了⽤用户进程，才考虑进程⽤用户内存空间的 swap page 问题，mm 才会发挥作⽤用。

还没看到用户进程的 swap page 代码

创建内核线程
idle

proc_init 函数启动了创建内核线程的步骤。首先当前的执行上下文（从 kern_init 启动至今）就可以看成是 uCore 内核中的一个内线程的上下文。为此，uCore 调用 alloc_proc 函数给当前执行的上下文分配一个进程控制块并在 proc_init 中对它进行相应初始化，将其打造成第 0 个内核线程 --idleproc。

   //alloc_proc
   proc->mm = NULL;    //不需要，所有内核进程公用一个页表
   proc->cr3 = boot_cr3;  //在 pmm_init 中分配为 PADDR(boot_pgdir)

   //proc_init
   idleproc->pid = 0;
   idleproc->state = PROC_RUNNABLE;
   idleproc->kstack = (uintptr_t)bootstack; //在 entry.S 中设置的
   idleproc->need_resched = 1; //表明在 kern_init 后会切换
init(kernel_thread & do_fork)

idle 内核线程主要工作是完成内核中各个子系统的初始化，idle 会调用 kernel_thread 函数创建内核线程 init。

kernel_thread 简单来说为新进程分配了 PCB 空间，和 kstack 空间。

  //proc_init
 int pid = kernel_thread(init_main, NULL, 0);
    if (pid <= 0) {
        panic("create init_main failed.\n");
    }
    initproc = find_proc(pid);
    set_proc_name(initproc, "init");

过程：

  1. kernel_thread 创建内核线程的中断帧，重点在于将 epc 设置为了 kernel_thread_entry，以及设置 a0 和 a1 为 arg 和 fn。还有一点值得注意，status 的 KSU 为内核模式。

    当从 eret 返回后（forkrets -> exception_return），CPU 便会进入 kernel_thread_entry，并以 tf 中指定的寄存器值执行。

    kernel_thread 函数采用了局部变量 tf 来放置中断帧，并把中断帧的指针传递给 do_fork 函数。

    kernel_thread 调用 do_fork 的 stack 参数为 0。在 do_fork->copy_thread 以此来判断是创建内核线程

  2. do_fork 作用是以当前进程为父进程，创建一个子进程，可以根据 clone_flags 决定是否共享 mm。具体主要做了以下一些事情：

    1. 调用 alloc_proc 为子进程分配 PCB 空间

    2. 调用 setup_kstack(proc)分配了内核栈空间（注意这里的 kstack 为空闲页的起始地址，而非栈顶）

    3. 调用 copy_mm，根据 clone_flags 来确定是复制还是共享 mm。（只对用户进程有效，内核线程 mm 都为 NULL）

    4. 调用 copy_thread：将 tf 拷贝到 kstack 的栈顶，设置 tf 中的 sp 为 proc->tf - 32（这里的减 32 应该和之前提到的 MIPS 函数调用规则有关，不管怎样，sp 是位于 kstack 中的）

      将 context 中的 ra 设置为 forkret

    5. 将子进程插入 hash_list 和 proc_list

    6. 调用 wakeup_proc 将进程加入调度队列

int
kernel_thread(int (*fn)(void *), void *arg, uint32_t clone_flags) {
    struct trapframe tf;
    memset(&tf, 0, sizeof(struct trapframe));
    tf.tf_regs.reg_r[MIPS_REG_A0] = (uint32_t)arg;
    tf.tf_regs.reg_r[MIPS_REG_A1] = (uint32_t)fn;
    tf.tf_regs.reg_r[MIPS_REG_V0] = 0;
    //TODO
    tf.tf_status = read_c0_status();
    tf.tf_status &= ~ST0_KSU;
    tf.tf_status |= ST0_IE;
    tf.tf_status |= ST0_EXL;
    tf.tf_regs.reg_r[MIPS_REG_GP] = __read_reg($28);
    tf.tf_epc = (uint32_t)kernel_thread_entry;
    return do_fork(clone_flags | CLONE_VM, 0, &tf);
}

//kern/proc/entry.S
kernel_thread_entry:        # void kernel_thread(void)
  addiu $sp, $sp, -16
  jal $a1
  nop
  move $a0, $v0
  la  $t0, do_exit
  jal $t0 
  nop
  /* never here */

//called by do_fork
static void
copy_thread(struct proc_struct *proc, uintptr_t esp, struct trapframe *tf) {
    proc->tf = (struct trapframe *)(proc->kstack + KSTACKSIZE) - 1;
    *(proc->tf) = *tf;
    proc->tf->tf_regs.reg_r[MIPS_REG_V0] = 0;
    if(esp == 0) //a kernel thread
      esp = (uintptr_t)proc->tf - 32;
    proc->tf->tf_regs.reg_r[MIPS_REG_SP] = esp;
    proc->context.sf_ra = (uintptr_t)forkret;
    proc->context.sf_sp = (uintptr_t)(proc->tf) - 32;
}

// do_fork - parent process for a new child process
//    1. call alloc_proc to allocate a proc_struct
//    2. call setup_kstack to allocate a kernel stack for child process
//    3. call copy_mm to dup OR share mm according clone_flag
//    4. call copy_thread to setup tf & context in proc_struct
//    5. insert proc_struct into hash_list && proc_list
//    6. call wakup_proc to make the new child process RUNNABLE 
//    7. set the 
int
do_fork(uint32_t clone_flags, uintptr_t stack, struct trapframe *tf) {
 int ret = -E_NO_FREE_PROC;
 struct proc_struct *proc;
 if (nr_process >= MAX_PROCESS) {
     goto fork_out;
 }
 ret = -E_NO_MEM;
 //LAB4:EXERCISE2 2009010989
 if ((proc = alloc_proc()) == NULL) {
     goto fork_out;
 }

 proc->parent = current;

 if(setup_kstack(proc)){
     goto bad_fork_cleanup_proc;
 }
 //LAB8:EXERCISE2 2009010989 HINT:how to copy the fs in parent's proc_struct?
 if (copy_fs(clone_flags, proc) != 0) {
     goto bad_fork_cleanup_kstack;
 }
 if (copy_mm(clone_flags, proc)){
     goto bad_fork_cleanup_fs;
 }

 copy_thread(proc, (uint32_t)stack, tf);

 proc->pid = get_pid();
 hash_proc(proc);


 //list_add(&proc_list, &(proc->list_link));
 set_links(proc);

 wakeup_proc(proc);

 ret = proc->pid;

fork_out:
 return ret;

bad_fork_cleanup_fs:
 put_fs(proc);
bad_fork_cleanup_kstack:
 put_kstack(proc);
bad_fork_cleanup_proc:
 kfree(proc);
 goto fork_out;
}
user_main

在 init_main 中，创建了 user_main 线程。

// init_main - the second kernel thread used to create user_main kernel threads
static int
init_main(void *arg) {
 ...
    int pid = kernel_thread(user_main, NULL, 0);
    if (pid <= 0) {
        panic("create user_main failed.\n");
    }

    while (do_wait(0, NULL) == 0) {
        schedule();
    }

    fs_cleanup();
    kprintf("all user-mode processes have quit.\n");
    ...
}

kernel_thread 之前已经分析过了，我们来看 user_main 做了什么

// user_main - kernel thread used to exec a user program
static int
user_main(void *arg) {
    kprintf("in user main, pid: %d\n", current->pid);
    KERNEL_EXECVE(sh);
    panic("user_main execve failed.\n");
}

user_main 调用了KERNEL_EXECVE来加载执行一个用户程序。KERNEL_EXECVE被展开为对 kernel_execve 的调用。

// kernel_execve - do SYS_exec syscall to exec a user program called by user_main kernel_thread
static int
kernel_execve(const char *name, const char **argv) {
    int argc = 0, ret;
    while (argv[argc] != NULL) {
        argc ++;
    }
    //panic("unimpl");
    asm volatile(
      "la $v0, %1;\n" /* syscall no. */
      "move $a0, %2;\n"
      "move $a1, %3;\n"
      "move $a2, %4;\n"
      "move $a3, %5;\n"
      "syscall;\n"
      "nop;\n"
      "move %0, $v0;\n"
      : "=r"(ret)
      : "i"(SYSCALL_BASE+SYS_exec), "r"(name), "r"(argc), "r"(argv), "r"(argc) 
      : "a0", "a1", "a2", "a3", "v0"
    );
    return ret;
}

而 kernel_execve 则是进行了一次系统调用。

kernel_execve -> SYSCALL -> sys_exec -> do_execve

  1. 因为 kernel_execve 就是在内核线程，所以之后进行系统调用，仍然是使用一样的内核栈。

  2. do_execve 做的事情

    int do_execve(const char *name, int argc, const char **argv)

    1. 创建局部变量 local_name, kargv（位于上下文的内核栈中），将参数 name, argv 复制过来。

      kernel_execve 调用时传递了"sh"字符串常量的地址。而该"sh"的地址在 gdb 调试时显示为 0x8002_7ff0，而 local_name 的地址则为 0x81fe_bd20（此时 sp 为 0x81fe_bd00，可以知道 local_name 位于当前函数的栈帧中，而"sh"位于别处）

      copy_string(mm, local_name, name, sizeof(local_name))

copy_kargv(mm, argc, kargv, argv)

      copy_string 函数，作用是先检查访问 src 是否合法（通过 mm），然后将 src 复制到 dst 中。这里的 dst 位于内核空间

      bool copy_string(struct mm_struct *mm, char *dst, const char *src, size_t maxn)

      copy_string 具体代码，if 判断有点复杂，且没有注释，没太看懂。

    2. 读取文件系统，获得文件号，之后传给 load_icode 使用。

      fd = sysfile_open(path, O_RDONLY)

    3. 清空原本的 mm。vma，分配的 Page，页表等等都会被清除。(user 此时是内核进程，因此没有 mm)

       if (mm != NULL) {
        lcr3(boot_cr3);
        if (mm_count_dec(mm) == 0) {
            exit_mmap(mm);
            put_pgdir(mm);
            mm_destroy(mm);
        }
        current->mm = NULL;
    }

    4. 调用 load_icode

      load_icode(fd, argc, kargv)

      调用完 load_icode 后，elf 文件已经被全部加载进内存，并且根据 elf 文件 program header 的内容设置好了 vma，页表等内容。还分配了 USTACK 空间。

  3. load_icode 做的事情

    // load_icode -  called by sys_exec-->do_execve
// 1. create a new mm for current process
// 2. create a new PDT, and mm->pgdir= kernel virtual addr of PDT
// 3. copy TEXT/DATA/BSS parts in binary to memory space of process
// 4. call mm_map to setup user stack, and put parameters into user stack
// 5. setup trapframe for user environment 
static int
load_icode(int fd, int argc, char **kargv)

    1. 创建新的 mm

       struct mm_struct *mm;
    if ((mm = mm_create()) == NULL) {
        goto bad_mm;
    }
    if (setup_pgdir(mm) != 0) {
        goto bad_pgdir_cleanup_mm;
    }

    2. 接下来涉及到对 elf 文件的解析。首先调用 load_icode_read 读取 elf 头 (struct elfhdr32)。然后根据 elfhdr，获得程序头 (struct proghdr) 的文件内偏移 elf->e_phoff、程序头的数量 elf->e_phnum。再通过 for 循环，读取每个程序头 ph。程序头显示了每个段的信息。

      for (phnum = 0; phnum < elf->e_phnum; phnum ++) {
    off_t phoff = elf->e_phoff + sizeof(struct proghdr) * phnum;
    if ((ret = load_icode_read(fd, ph, sizeof(struct proghdr), phoff)) != 0) {
        goto bad_cleanup_mmap;
 }
    ...

      readelf -l obj/user/sh的信息

      Elf 文件类型为 EXEC (可执行文件)
Entry point 0x100033d0
There are 2 program headers, starting at offset 52

程序头：
  Type           Offset   VirtAddr   PhysAddr   FileSiz MemSiz  Flg Align
  ABIFLAGS       0x0141d0 0x100041d0 0x100041d0 0x00018 0x00018 R   0x8
  LOAD           0x010000 0x10000000 0x10000000 0x05010 0x09010 RWE 0x10000

 Section to Segment mapping:
  段节...
   00     .MIPS.abiflags 
   01     .text .MIPS.abiflags .data .bss

    3. 根据每个 ph 的信息，添加 vma。这里用的是 ph->p_memsz。

       vm_flags = 0;
      //ptep_set_u_read(&perm);
    perm |= PTE_U;
    if (ph->p_flags & ELF_PF_X) vm_flags |= VM_EXEC;
    if (ph->p_flags & ELF_PF_W) vm_flags |= VM_WRITE;
    if (ph->p_flags & ELF_PF_R) vm_flags |= VM_READ;
    if (vm_flags & VM_WRITE) perm |= PTE_W; 

    if ((ret = mm_map(mm, ph->p_va, ph->p_memsz, vm_flags, NULL)) != 0) {
        goto bad_cleanup_mmap;
    }

    4. 调用 pgdir_alloc_page 为每个虚拟地址分配物理页，并添加页表映射。调用 load_icode_read 将 elf 文件对应段 (segment) 读取到对应的物理页中。

          off_t offset = ph->p_offset;
    size_t off, size;
    uintptr_t start = ph->p_va, end, la = ROUNDDOWN_2N(start, PGSHIFT);

    end = ph->p_va + ph->p_filesz;
    while (start < end) {
        if ((page = pgdir_alloc_page(mm->pgdir, la, perm)) == NULL) {
            ret = -E_NO_MEM;
            goto bad_cleanup_mmap;
        }
        off = start - la, size = PGSIZE - off, la += PGSIZE;
        if (end < la) {
            size -= la - end;
        }
        if ((ret = load_icode_read(fd, page2kva(page) + off, size, offset)) != 0) {
            goto bad_cleanup_mmap;
        }
        start += size, offset += size;
    }

    5. 设置 bss 段（猜测）

       end = ph->p_va + ph->p_memsz;

    if (start < la) {
        if (start >= end) {
            continue ;
        }
        off = start + PGSIZE - la, size = PGSIZE - off;
        if (end < la) {
            size -= la - end;
        }
        memset(page2kva(page) + off, 0, size);
        start += size;
        assert((end < la && start == end) || (end >= la && start == la));
    }

    while (start < end) {
        if ((page = pgdir_alloc_page(mm->pgdir, la, perm)) == NULL) {
            ret = -E_NO_MEM;
            goto bad_cleanup_mmap;
        }
        off = start - la, size = PGSIZE - off, la += PGSIZE;
        if (end < la) {
            size -= la - end;
        }
        memset(page2kva(page) + off, 0, size);
        start += size;
    }

    6. 映射用户栈空间（添加 vma，当发生 pagefault 时，异常处理程序会自动分配物理页）

       vm_flags = VM_READ | VM_WRITE | VM_STACK;
    if ((ret = mm_map(mm, USTACKTOP - USTACKSIZE, USTACKSIZE, vm_flags, NULL)) != 0) {
        goto bad_cleanup_mmap;
    }

    7. 将函数调用参数压入用户栈中

         uintptr_t stacktop = USTACKTOP - argc * PGSIZE;
    char **uargv = (char **)(stacktop - argc * sizeof(char *));
    int i;
    for (i = 0; i < argc; i ++) {
        uargv[i] = strcpy((char *)(stacktop + i * PGSIZE), kargv[i]);
    }

      上一个步骤已经将 USTACKTOP 添加到了 vma 中。因此在第一次访问用户栈时会触发 pagefault（页表中没有映射关系），操作系统会动态分配 Page。第二次访问会再触发一次 tlb refill，tlb 添加映射关系，之后便可以正常访问了。

    8. 设置 tf。

      1. 将 tf->tf_epc 设置为了 elf->e_entry。因此异常返回时便开始执行 elf 程序。

      3. 在 tf->tf_status 中设置了 KSU_USER，因此从 SYSCALL 返回后，CPU 会转变为用户态。

       struct trapframe *tf = current->tf;
    memset(tf, 0, sizeof(struct trapframe));

    tf->tf_epc = elf->e_entry;
    tf->tf_regs.reg_r[MIPS_REG_SP] = USTACKTOP;
    uint32_t status = read_c0_status();
    status &= ~ST0_KSU;
    status |= KSU_USER;     //变成用户进程
    status |= ST0_EXL;
    tf->tf_status = status;
    tf->tf_regs.reg_r[MIPS_REG_A0] = argc;
    tf->tf_regs.reg_r[MIPS_REG_A1] = (uint32_t)uargv;
调度

执行完 proc_init 后，已经创建好了两个内核线程 idle 和 init，并且当前执行的线程为 proc_init。当 ucore 的所有初始化工作完成后，ucore 执行 kern_init 的最后一个函数 cpu_idle 函数。cpu_idle 会调用 schedule 让出 CPU。

schedule 具体的实现我们可以不关心。我们只需要知道 sched_class_enqueue(proc) 将一个进程放入运行队列 run queue。next = sched_class_pick_next() 从 rq 中找到下一个执行的进程。

当选定需要执行的进程后，proc_run 函数将该进程载入 CPU 执行。

void
cpu_idle(void) {
    while (1) {
        if (current->need_resched) {
            schedule();
        }
    }
}

void
schedule(void) {
    bool intr_flag;
    struct proc_struct *next;
    local_intr_save(intr_flag);
    {
        current->need_resched = 0;
        if (current->state == PROC_RUNNABLE) {
            sched_class_enqueue(current);
        }
        if ((next = sched_class_pick_next()) != NULL) {
            sched_class_dequeue(next);
        }
        if (next == NULL) {
            next = idleproc;
        }
        next->runs ++;
        if (next != current) {
            //kprintf("########################\n");
            //kprintf("c %d TO %d\n", current->pid, next->pid);
            //print_trapframe(next->tf);
            //kprintf("@@@@@@@@@@@@@@@@@@@@@@@@\n");
            proc_run(next);
        }
    }
    local_intr_restore(intr_flag);
}

void
proc_run(struct proc_struct *proc) {
    if (proc != current) {
        bool intr_flag;
        struct proc_struct *prev = current, *next = proc;
        local_intr_save(intr_flag);
        {
          //panic("unimpl");
            current = proc;
            //load_sp(next->kstack + KSTACKSIZE);
            lcr3(next->cr3);
            tlb_invalidate_all();       //标注一下这里的 tlb 清空，待优化
            switch_to(&(prev->context), &(next->context));
        }
        local_intr_restore(intr_flag);
    }
}

proc_run 会调用 switch_to，switch_to 会：

  1. 将当前的 context 存储在 prev->context 中。（注意，context 只包含 s0-s8, sp, gp, ra）
  2. 恢复 next->context
  3. 执行j ra
init 进程执行过程

通过 kernel_thread(init_main, NULL, 0) 创建 init 进程后

  1. cpu_idle 中（idle 进程中），执行 schedule()，此时只有 idle 和 init 两个进程，因此调度到 init 进程执行 proc_run。

  2. 执行 switch_to，kernel_thread 设置了 context 中的 sp, ra。执行 jr ra 后，跳转到 forkret

    // forkret -- the first kernel entry point of a new thread/process
// NOTE: the addr of forkret is setted in copy_thread function
//       after switch_to, the current proc will execute here.
static void
forkret(void) {
    forkrets(current->tf);
}

forkrets:
  addiu sp, a0, -16
  b exception_return
  nop

  3. forkrets->exception_return 从中断返回，弹出中断帧 tf。CPU 便会进入 kernel_thread_entry，并以 tf 中指定的寄存器值执行

  4. kernel_thread_entry 跳转执行$a1 即 init_main

    //kern/proc/entry.S
kernel_thread_entry:        # void kernel_thread(void)
  addiu $sp, $sp, -16
  jal $a1
  nop
  move $a0, $v0
  la  $t0, do_exit
  jal $t0 
  nop
  /* never here */
user_main 的执行过程

  1. 在 init_main 中，创建了 user_main 线程。然后 init_main 执行 do_wait

    // init_main - the second kernel thread used to create user_main kernel threads
static int
init_main(void *arg) {
 ...
    int pid = kernel_thread(user_main, NULL, 0);
    if (pid <= 0) {
        panic("create user_main failed.\n");
    }

    while (do_wait(0, NULL) == 0) {
        schedule();
    }

    fs_cleanup();
    kprintf("all user-mode processes have quit.\n");
    ...
}

  2. do_wait 的作用是等待指定的或者任意一个（传入的 pid 为 0）子线程进入 ZOMBIE 状态，释放子进程的内核栈空间和 PCB 空间。否则，自己进入睡眠状态 SLEEPING，然后调用 schedule()。

    // do_wait - wait one OR any children with PROC_ZOMBIE state, and free memory space of kernel stack
//         - proc struct of this child.
// NOTE: only after do_wait function, all resources of the child proces are free.
int
do_wait(int pid, int *code_store)

  3. schedule 调用到 user_main 线程。和 init 一样，执行到 user_main 函数。

  4. user_main 函数调用了 kernel_execv 函数，实质为一次 SYS_exec 系统调用。

  5. 最后重新分配内核和用户空间，加载了 sh 用户程序。user_main 线程从内核线程变为用户线程。

  6. 用户进程链接脚本 user.ld 指定了 ENTRY(_start)。_start 在 user/libs/initcode.S 中定义。

    _start:
    nop
    la $gp, _gp
    addiu $sp, $sp, -16
    jal umain
    nop

    umain 在 user/libs/umain.c 中定义

    void
umain(int argc, char *argv[]) {
    int fd;
    if ((fd = initfd(0, "stdin:", O_RDONLY)) < 0) {
        warn("open <stdin> failed: %e.\n", fd);
    }
    if ((fd = initfd(1, "stdout:", O_WRONLY)) < 0) {
        warn("open <stdout> failed: %e.\n", fd);
    }
    int ret = main(argc, argv);
    exit(ret);
}
ide_init & fs_init
  • 分类于 课程笔记
  • 需要 7 分钟阅读时间

ucore lab3 总结

目录

  1. x86 中断/异常处理 (tss 和 tf 作用)
  2. 重要函数说明 1. 创建进程 (线程) 2. 调度，运行 3. do_wait & do_exit 4. do_execve 5. 其它系统调用
  3. FAQ 1. 一个进程被创建后如何开始执行？ 2. 一个用户进程如果因为时间片用完而被调度掉后，再次被调度回来时会从哪里继续执行？ 3. 一个进程的完整生命周期？ 4. fork 调用，为什么父进程返回值为 pid，子进程返回值为 0（涉及到用户进程的创建）

总结

实验 3 涉及到的知识点：

  1. x86 中断中 tss 的作用（类似的内核栈，中断帧的概念）
  2. 进程如何创建、执行、切换（do_fork, do_wait, do_exit 等系统调用的设计与实现）
  3. 用户进程的创建、执行过程
  4. 用户 ulib 库 fork, wait, exit 的实现
  • 分类于 课程笔记
  • 需要 4 分钟阅读时间

ucore lab2 总结

概述

回顾实验 1，我觉得需要学习的知识有：

  1. gdb工具的使用
  2. ELF文件的格式，以及 readelf, objdump, objcopy 工具的使用（查看各个 section，查看符号表）
  3. x86 汇编基础（通用寄存器，段寄存器，EIP，EFLAG 等），GCC内联汇编格式（AT&T 格式）
  4. x86 内存分段机制（GDT 表，段描述符）
  5. x86中断处理机制（IDT 表，中断向量 -> 中断处理程序）
  6. 操作系统启动过程（BIOS->bootloader(第一扇区)->Kernel 各阶段做的事情）

而做完实验 2 后，我觉得需要学习的知识有：

  1. BIOS 探测物理内存，Kernel 打开分页时自带一个页表
  2. 二级页表进行虚拟地址转换
  3. 物理内存管理 之 空闲块(以页为单位) 管理（Page 数据结构和物理页的对应，空闲块链表 free_list，FirstHit 分配连续的物理页）
  4. 虚拟内存管理 之 有效虚拟页（表示一个程序可能使用的虚拟地址段，vma, mm 数据结构）
  5. 导致PageFault的原因（1. pte=0 即从来没有被加载过，2. 被 swap out, 3. 访问权限错误）
  6. FIFO 页替换算法实现（page struct 增加 pra_page_link, pra_vaddr，mm->sm_priv(pra_list_header) 记录最近使用的页序列；swap_manager）

以下介绍一些难点

  • 分类于 课程笔记
  • 需要 1 分钟阅读时间

编译原理总结

目前我眼中的计算机层次

  • 计算机体系结构（RTL 级设计，流水线，缓存，多发射）
  • ISA（访存模式，中断/异常）
  • 汇编语言（寄存器 + 内存空间）
  • 高级语言（编译器）
  • 操作系统（内核：进程调度，同步与死锁，内存管理：页表，文件系统 应用：桌面系统，浏览器）

编译器各阶段

  1. 词法分析：解析源代码文件，输出记号流。 记号即指一个有独立意义的“单词”。空白字符便一般不包含意义，故可以省略。 这些单词一般可分类为：标识符，常数（整数，浮点数），字符常量，字符串， 操作符，界符，关键字。

  2. 语法分析：分析记号流，输出程序的逻辑结构，如语法分析树（或 AST 树） 一种语言的语法规则可以被文法产生式完全定义。 文法一般包括表达式的定义，各种语句的定义（if, while, for），变量声明， 函数定义等。

  • 分类于 课程笔记
  • 需要 2 分钟阅读时间

RISC-V 报告

author: 计科卓越班 袁福焱 20174260

0. 导言

RISC-V 是 21 世纪诞生的一种完全开放的计算机精简指令集，可应用于小到嵌入式系统大到高性能处理器等广泛领域。RISC-V 充分汲取了许多指令集的实践经验，具有非常多的优点。并且它完全开放，采用 BSD 开源协议——全世界任何公司、大学、个人都可以自由免费地使用 RISC-V 指令集构建自己的系统。

本报告第一部分讲述 RISC-V 的几个主要特点与优势，第二部分介绍 RISC-V 的目前已构建建的生态系统。最后一部分，谈论 RISC-V 在推动开源硬件中起到的作用。

1. RISC-V 的特点

1.1 指令集模块化

以往的指令集为了实现兼容，往往采用增量扩展的方法。即新的处理器不仅要实现新的扩展，还必需要实现过去所有的扩展。如典型的 x86 架构，其中许多指令早已失效，但为了兼容性却必须实现，这导致硬件实现变得越来越复杂。RISC-V 按照功能将指令集分为很多个模块。其中 I 模块为基础整型指令集，这是 RISC-V 要求必须实现的指令集，并且永远不会发生改变。只要实现了该指令集便可以运行完整的基于 RISC-V 的软件。这样，RISC-V 在扩展时便不再会像 x86 那样背上沉重的历史包裹。编译器也可以在保证兼容的基础上，根据已实现的扩展，选择性地生成更高效的代码。

1.2 回避以往的设计缺陷

目前主流的指令集有 x86, ARM, MIPS 等。其中 x86 为复杂指令集 (RISC)，于 1978 年诞生。而 ARM, MIPS 为精简指令集 (RISC)，都是 1986 年诞生的。从计算机体系结构的发展上来看，RISC 由于简洁性，能够更加充分地利用现代微体系结构中的流水线、分支预测、cache 等技术，因此比 CISC 更加高效。因此，诞生于 21 世纪 (2004) 的 RISC-V，必然也是精简指令集。并且，由于有了前面指令的经验，RISC-V 吸收了以往指令集的优点，并回避了以往指令集的一些缺陷。优点如，RISC-V 有 32 个通用寄存器，有专门的 0 寄存器。使用专门的移位指令来处理移位操作。使用 load/store 指令访问内存。跳转指令不使用条件码。缺陷则如，RISC-V 废弃了 MIPS 中的分支延迟槽 (有利于架构和实现的分离)，立即数只进行有符号扩展，算数运算不抛出异常 (通过软件判断)，更规整的指令格式（源及目的字段位置固定），整数乘除法可选 (简化了基础实现)。

1.3 完全开放

RISC-V 采用 BSD 开源协议，任何人都可以自由免费地使用 RISC-V。其他指令集如 x86 是完全闭源的，只有 intel 和 AMD 等少数公司能够基于 x86 架构生产产品。而 ARM 和 MIPS 都采用授权的方式，通过卖授权的方式盈利，其中 ARM 的授权费则十分昂贵。RISC-V 如今由 RISC-V 基金会维护，任何公司只要愿意每年支付一笔会员费即可成为会员，会员可以参与到 RISC-V 之后标准的制定中。RISC-V 也因此真正成为一个开放的指令集，不会因为任何一个公司的起伏而受到影响。

2. RISC-V 的生态

以下内容引用自开放指令集与开源芯片进展报告-v1p1

2011 年，加州大学伯克利分校发布了开放指令集 RISC-V，并很快建立起一个开源软硬件生态系统。截止 2019 年 1 月，已有包括 Google、NVidia 等在内的 200 多个公司和高校在资助和参与 RISC-V 项目。其中，部分企业已经开始将 RISC-V 集成到产品中。例如全球第一大硬盘厂商西部数据（Western Digital）最近宣布将把每年各类存储产品中嵌入的 10 亿个处理器核换成 RISC-V；Google 利用 RISC-V 来实现主板控制模块；NVidia 也将在 GPU 上引入 RISC-V 等。此外，国内阿里巴巴、华为、联想等公司都在逐步研究各自的 RISC-V 实现；上海市将 RISC-V 列为重点扶持项目；印度政府也正在大力资助基于 RISC-V 的处理器项目，使 RISC-V 成为了印度的事实国家指令集。

由此可见，RISC-V 国内外的兴起使得目前 RISC-V 的生态已经比较完善了。

3. 之于构建开放硬件生态的意义

2019 年度国际计算机体系结构旗舰会议 ISCA 于 6 月在美国亚利桑那州凤凰城召开，会议的主题即是“面向下一代计算的敏捷开放硬件（Agile and Open Hardware for Next-Generation Computing）”。由此可见开放硬件，敏捷开发已成为未来的趋势。而 RISC-V 则刚好成为这趋势中不可或缺的一环。

目前开源硬件开发中面临着 4 个关键问题 (Yungang Bao, Chinese Academy of Sciences, The Four Steps to An Open-Source Chip Design Ecosystem)：

  1. 开放的指令集 ISA/开源 IPs/开源 Socs
  2. 硬件描述语言 Lanuages/开源的 EDA 工具
  3. 验证和仿真 Vertification/Simulation
  4. OS/Complier

RISC-V 便处于第一环中，

虽然目前每个环节都还未完全解决，但我们可以相信，在未来，开发硬件可以像开发一个软件一样。充分利用已开源的资源，用户只需要定制 10% 以内的代码，便可以以月为单位开发出客制化的硬件系统。

4. 参考资料

大道至简——RISC-V 架构之魂（上）

大道至简——RISC-V 架构之魂（中）

大道至简——RISC-V 架构之魂（下）

开放指令集与开源芯片进展报告-v1p1（2019-02-22 更新）

远景研讨会纪要–面向下一代计算的开源芯片与敏捷开发

  • 分类于 课程笔记
  • 需要 1 分钟阅读时间

非对齐指令总结

1 大端与小端

  • 大端：数据的高位位于内存的低地址，数据的地位位于内存的高地址。
  • 小端：与大端相反。

事实上大端更符合人的思维，因为在写一个数字时人们更习惯从高位写到低位，且高位是写在左边的。而这可以直接和内存的“图像”对应，而小端则需要把每个字的字节地址颠倒一下才可以。 例如，一个 32 位的整数 0xffeeddcc，在内存里的存储情况如下。（非对齐，起始地址为 0x01）

大端: 0 1 2 3 0x00 00ffeedd 0x01 cc556677 小端: 3 2 1 0 0x00 eeddcc00 0x01 776655ff ps.假设除去该整数存储的空间，字节地址与存储的十六进制数对应，即地址为 0x01 存 11，0x05 存 55，这点用来突出字节地址是多少。

2 非对齐指令

instruction lwl/swl, lwr/swr usage lwl t0, offset(s0)

其中的 left，与 shift left 的“左”都表示数据的高位。right 则表示数据的低位。

lwl 表示将内存对应地址所在的字（align_address，即抹掉地址低两位对应地址）的数据低位复制到寄存器数据的高位。寄存器其它部分不变。

swl 则表示将寄存器的数据高位复制到内存对应数据低位。其它部分不变。 即 lwl/swl 寄存器数据高位↹内存数据低位 lwr/swr 寄存器数据低位↹内存数据高位

1 从#1 中读取该整数实例

大端 lwl s0, 0(1) lwr s0, 3(1) 小端 lwr s0, 0(1) lwl s0, 3(1)

将整数以图中所示存储到内存中只需将 lw*改为 sw*。

可以以此定义非对齐加载、存储伪指令， 如 uld(rd, rb) 表示非对齐 load，加载内存[rb+3:rb]的数据， uld(rd, rb)=> lwl rd, 0(rb) lwr rd, 3(rb) （可能 uld 是加载 8 字节，待确认）

2 关于 load/store 多少字节

n 为地址低 2 位，n=addr[1:0] 大端 lwl/swl 4-n lwr/swr n+1 小端 lwr/swr 4-n lwl/swl n+1

  • 分类于 课程笔记
  • 需要 3 分钟阅读时间

操作系统第 7 章 作业 死锁

1、

Consider the traffic deadlock depicted in follow figure.

deadlock car

a. Show that the four necessary conditions for deadlock indeed hold in this example. b. State a simple rule for avoiding deadlocks in this system.

  • a. 1. mutual exclusion: 每条道路都只能让一个方向的车通行，且车之间不可能穿透而过。 2. hold and wait: 四个方向的车辆都占有一条道路，并等待另一方向的车露出空隙。 3. no preemption: 每个方向的车都必须等待另一个方向的车主动倒车，无法强迫。 4. circular wait：每个方向的车互相等待，形成一个环。
  • b. 安排一位交警选择并指挥一个方向的车让出道路。

2、

Consider a system consisting of four resources of the same type that are shared by three processes, each of which needs at most two resources. Show that the system is deadlock free.

答：反证法，假设形成了死锁。则由每个进程最多需求 2 个资源实例，和死锁必要条件中的 3，4 点可知，唯一的情形是：三个进程各自占有一个资源且等待另一个资源，并形成了一个环。而在该情况下，剩余的一个资源导致死锁不会发生。

3、

Consider a system consisting of m resources of the same type being shared by n processes. Resources can be requested and released by processes only one at a time. Show that the system is deadlock free if the following two conditions hold:

  • a. The maximum need of each process is between 1 and m resources.
  • b. The sum of all maximum needs is less than m + n.

$ a. \sum_{i=1}^n Max_i < m+n $ $ b. Max_i \geq 1 for all i $ $ c. Need_i = Max_i − Allocation_i $

If there exists a deadlock state then: $ d. \sum_{i=1}^n Allocation_i = m $

$ a,b,c,d \Rightarrow \sum_{i=1}^n Need_i < n $

This implies that there exists a process $ P_i $ such that $ Need_i = 0 $. Since $ Max_i >= 1 $, it follows that $ P_i $ has at least one resource, the deadlock can't maintain.

4、

Consider the following snapshot of a system:

PID AL. MAX
A B C D A B C D
P0 0 0 1 2 0 0 1 2
P1 1 0 0 0 1 7 5 0
P2 1 3 5 4 2 3 5 6
P3 0 6 3 2 0 6 5 2
P4 0 0 1 4 0 6 5 6
AV.
A B C D
1 5 2 0

(p.s. AL.= Allocated:, AV.= Available)

Answer the following questions using the banker's algorithm: a. What is the content of the matrix Need? b. Is the system in a safe state? c. If a request from process $ P_1 $ arrives for (0,4,2,0), can the request be granted immediately?

  • a | PID | need | | | | | --- | --- | - | - | - | | | A | B | C | D | | P0 | 0 | 0 | 0 | 0 | | P1 | 0 | 7 | 5 | 0 | | P2 | 1 | 0 | 0 | 2 | | P3 | 0 | 0 | 2 | 0 | | P4 | 0 | 6 | 4 | 2 |
  • b 由银行家算法可知是安全的，序列\(<0,2,1,3,4>\)为安全序列。
  • c 假设满足，则$ Need_{P_1} =(0,11,7,0) \(，序列\) <0,2,3,4,1> $为安全序列，故可立即满足。

5、

Consider a system with four processes$ P_1, P_2, P_3$ and $ P_4 $, and two resources, $ R_1, R_2 $ respectively. Each resource has two instances. Furthermore:

$ P_1 $ allocates an instance of $ R_2 $ , and requests an instance of $ R_1 $ ; $ P_2 $ allocates an instance of $ R_1 $ , and doesn’t need any other resource; $ P_3 $ allocates an instance of $ R_1 $ and requires an instance of $ R_2 $ ; $ P_4 $ allocates an instance of $ R_2 $ , and doesn’t need any other resource. Answer the following questions:

a. Draw the resource allocation graph. b. Is there a cycle in the graph? If yes name it. c. Is the system in deadlock? If yes, explain why. If not, give a possible sequence of executions after which every process completes.

  • a. 略
  • b. 存在
  • c. 不是，$ $
  • 分类于 课程笔记
  • 需要 2 分钟阅读时间

操作系统第六章作业 进程同步

1. What is the meaning of the term busy waiting?

当一个进程位于临界区时，任何其它试图进入临界区的进程都必须在代码中不断地循环。

2. What is the meaning of the term spinlocks?

自旋锁是一种会造成忙等的信号量，在进程等待锁时还需不断运行，占用 cpu 资源。

3. Explain the deadlock and give an example

若干个进程竞争系统资源，最后每个进程都必须得在其它进程释放资源时才能改变状态，因而无法改变状态，造成死锁。 如以下程序在 A，B 同时运行时造成死锁。 A:

wait(S)
wait(Q)
...
signal(S)
signal(Q)

B:

wait(Q)
wait(S)
...
signal(S)
signal(Q)

4

Servers can be designed to limit the number of open connections. For example, a server may wish to have only N socket connections at any point in time. As soon as N connections are made, the server will not accept another incoming connection until an existing connection is released. Explain how semaphores can be used by a server to limit the number of concurrent connections. (6.8)

初始化计数型信号量 connection=N

wait(connection)
//do something
signal(connection)

5. What operations can be performed on a semaphore? List them and explain the means of semaphore values

wait() 和 signal() 操作。 信号量可分为计数信号量与二进制信号量。计数信号量值域不受限制，代表系统受限资源的数量。 二进制信号量的值只能为 0 或 1，可表示对临界区的访问权（只能有一个进程位于临界区）。

6. How does the signal() operation associated with monitors differ from the corresponding operation defined for semaphores? (6.16)

当没有进程等待时，信号量的 signal() 会对信号量的值加一，而管程里的 signal() 则不会进行任何操作。

7

A uniprocessor system concurrently executes 2 processes ($ P_A, P_B $). Two Semaphores $ Mutex_R_a $ and $ Mutex_R_b $ are added in mutual accessing the critical section and synchronizing between $ P_A $ and $ P_B $ . Please read following program segment carefully and answer the questions:

(1) What are initial values for $ Mutex_R_a $ and $ Mutex_R_b $ . (2) Is it possible to cause deadlock? Please state your reason. Semaphore $ Mutex_R_a $, $ Mutex_R_b $ ;

Void P_A ( ){
    while(true){
        Wait(Mutex_Ra );
        ......
        Wait(Mutex_Rb );
        ......
        Signal(Mutex_Ra );
        ......
        Signal(Mutex_Rb );
    }
}

Void P_B ( ){
    while(true){
        Wait(Mutex_Rb );
        ......
        Wait(Mutex_Ra );
        ......
        Signal(Mutex_Rb );
        ......
        Signal(Mutex_Ra );
    }
}

答： (1) $ Mutex_R_a = Mutex_R_b = 1$ (2) 当 P_A 和 P_B 同时到达时，两个进程都会执行第一句，接着便会由于$ Mutex_R_a = Mutex_R_b = 0$而陷入死锁。

8

设有一个可以装 A、B 两种物品的仓库，其容量有限 (为 N),但要求仓库中 A、B 两 种物品的数量满足下述不等式： $$ -M≤A 物品数量-B 物品数量≤N $$ 其中 M 和 N 为正整数。另外，还有一个进程消费 A 和 B，一次取一个 A 与 B 组装成 C。 试用信号量和 P、V 操作描述 A、B 两种物品的入库和出库 (组装成 C) 过程。

答： 设 nA, nB 分别为 A 物品，B 物品数量，二进制信号量 mutex，初始值为 1。

A 入库进程：

wait(mutex)
nA++
if(nA <= N && -M <= nA-nB <= N)
    A入库
else
    nA--
signal(mutex)

B 入库进程：

wait(mutex)
nB++
if(nB <= N && -M <= nA-nB <= N)
    B入库
else
    nB--
signal(mutex)

C 出库进程：

wait(mutex)
if(nA>0 && nB>0)
    nA--;nB--
    C出库
signal(mutex)

changed:

semaphore initiation:
    muxtex = 1
    empty  = N
    delta  = M
    nA = nB = 0
progress A:
do{
    P(empty)
    P(mutex)
        A in
    V(mutex)
    V(nA)
    V(delta)
}while(true)

progress B:
do{
    P(empty)
    P(delta)
    P(mutex)
        B in
    V(mutex)
    V(nB)
}while(true)

progress C:
do{
    P(nA)
    P(nB)
    P(mutex)
        C out
    V(mutex)
    V(empty)
    V(empty)
}while(true)
  • 分类于 课程笔记
  • 需要 2 分钟阅读时间

操作系统第五章作业 CPU 调度

5.1. Why is it important for the scheduler to distinguish I/O-bound programs from CPU-bound programs?

对于长期调度程序，知道进程是 IO 约束的还是 CPU 约束的之后，便可以按照一定比例组合被调度的进程，使得 CPU 和 IO 设备都会一直处于负载状态，从而提高资源的使用率。 对于短期调度（CPU 调度），IO 约束的进程 CPU 区间都比较短，而 CPU 越苏进程则比较长，因而根据最短作业优先准则，可以优先调度 IO 约束进程。

5.2. Discuss how the following pairs of scheduling criteria conflict in certain settings

  • a. CPU utilization and response time CPU 利用率与上下文交换频率成负相关，而响应时间与之成正相关，故冲突。
  • b. Average turnaround time and maximum waiting time 为了减小平均周转时间，通常会采用短作业优先算法，而这会令长作业的等待时间增大。
  • c. I/O device utilization and CPU utilization 为了提高 I/O 设备的利用率，需要优先执行 IO bound 进程，因为 IO 约束的进程 CPU 区间短，因而导致频繁的上下文交换，因而降低 CPU 效率。

5.4 Consider the following set of processes, with the length of the CPU-burst time given in milliseconds

Process Burst Time Priority
$ P_1 $ 10 3
$ P_2 $ 1 1
$ P_3 $ 2 3
$ P_4 $ 1 4
$ P_5 $ 5 2

The processes are assumed to have arrived in the order $ P_1,P_2,P_3,P_4,P_5 $, all at time 0.

  • a. Draw four Gantt charts illustrating the execution of these processes using FCFS , SJF , a nonpreemptive priority (a smaller priority number implies a higher priority), and RR (quantum = 1) scheduling. 1. FCFS $ P_1 $ (10)       | $ P_2 $(1)   | $ P_3 $(2)   | $ P_4 \((1)   |\) P_5 $ (5)     --- | --- | --- | --- | --- 2. SJF $ P_2 $(1)   | $ P_4 $(1)   | $ P_3 $(2)   | $ P_5 $ (5)     | $ P_1 $ (10)       --- | --- | --- | --- | --- 3. nopreemptive priority $ P_2 $(1)   | $ P_5 $ (5)     | $ P_1 $ (10)       | $ P_3 $(2)   | $ P_4 $(1)   --- | --- | --- | --- | --- 4. Round Robin $ P_1 $| $ P_2 $ | $ P_3 $ | $ P_4 $ |$ P_5 $ | $ P_1 $| $ P_3 $ | $ P_5 $ | $ P_1 $ |$ P_5 $ | $ P_1 $ | $ P_5 $ | $ P_1 $ | $ P_5 $ | $ P_1 $ | $ P_1 $ | $ P_1 $ | $ P_1 $ | $ P_1 $ | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
  • b. What is the turnaround time of each process for each of the scheduling algorithms in part a?
      FCFS SJF nopreemptive priority RR
    $ P_1 $ 10 19 16 19
    $ P_2 $ 11 1 1 2
    $ P_3 $ 13 4 18 7
    $ P_4 $ 14 2 19 4
    $ P_5 $ 19 9 6 14
  • c. What is the waiting time of each process for each of the scheduling algorithms in part a?
      FCFS SJF nopreemptive priority RR
    $ P_1 $ 0 9 6 9
    $ P_2 $ 10 0 0 1
    $ P_3 $ 11 2 16 5
    $ P_4 $ 13 1 18 3
    $ P_5 $ 14 4 1 9
    sum 48 16 41 27
    - d. Which of the schedules in part a results in the minimal average waiting time (over all processes)?

    答：SJF with 3.2 ms

5.10 Explain the differences in the degree to which the following scheduling algorithms discriminate in favor of short processes

  • a. FCFS
  • b. RR
  • c. Multilevel feedback queues

答：

  • FCFS 哪个先到哪个优先，因此对待短进程和长进程是平等的。
  • RR 给每个进程分配相同的时间片，因此也是平等的。
  • 对于一种典型的多级反馈队列算法（有三个队列，前两个使用 RR 算法，时间片分别为 8ms，16ms，第三个使用 FCFS 算法，队列间使用抢占式优先级算法），短作业都会处于前面的队列，以此短作业的优先级更高。

5. Please prove: SJF gives the minimum average waiting time for a given set of processes to arrive at the same time

假设 CPU 按照一定顺序执行这些进程，每个进程 CPU 区间分别为$ t_1,t_2,\dots,t_n $。（非抢占） 则平均等待时间为： $$ \overline t = \frac{1}{n}\sum_{i=1}^n{(i-1)t_i} $$ 由排序不等式知$ t_1,t_2,\dots,t_n $降序时最短，即 SJF 算法。

6. What is Processor Affinity? What is load balancing? What is the relationship between the two?

处理器亲和性指在多处理器调度算法中，由于 cache miss 的代价比较高，应该努力让一个进程在一个处理器上运行。 而负载平衡指将工作负载平均分配到每个处理器上，从而保持每个处理器使用率都比较高。 因此当一个处理器负载较高时，负载平平衡策略会倾向让负载分配到多个处理器上，而处理器亲和则倾向保持该状态。 因此这两种策略有矛盾的关系。

  • 分类于 课程笔记
  • 需要 1 分钟阅读时间

操作系统第三章 作业

4.1

Provide two programming examples in which multithreading does not provide better performance than a single-threaded solution.

1) 任何“线性”执行的程序（后面的程序严重依赖前面执行的结果），这类程序即使使用多线程，每个线程都会阻塞其它线程的执行，因此并不会有更好的性能。

2) 只执行单一任务的程序。多线程对于浏览器，字处理软件等多任务软件是有用的。如浏览器可以在接收网络数据时同时刷新页面。但对于只执行单个任务的程序，便没有必要。

4.2

Describe the actions taken by a thread library to context switch between user-level threads.

用户级线程库的代码都存在于用户空间，因此调用库中的函数会导致一个本地调用而不是系统调用。因为线程主要包括寄存器的值和栈，因此上下文切换会涉到寄存器和栈状态的保存和恢复。

4.3

Under what circumstances does a multithreaded solution using multiple kernel threads provide better performance than a single-threaded solution on a single-processor system?

1）一个应用程序分为许多不同的部分。如网页浏览器有一个线程用于显示图像和文本，另一个用于从网络接收数据。 2）一个应用程序需要执行多个相似的任务。如网页服务器可能要处理上千个客户并发请求网页。

4.4

Which of the following components of program state are shared across threads in a multithreaded process?

  • a. Register values
  • b. Heap memory
  • c. Global variables
  • d. Stack memory

答：b,c

4.8

Consider a multiprocessor system and a multithreaded program written using the many-to-many threading model. Let the number of user-level threads in the program be more than the number of processors in the system. Discuss the performance implications of the following scenarios.

a. The number of kernel threads allocated to the program is less than the number of processors.

b. The number of kernel threads allocated to the program is equal to the number of processors.

c. The number of kernel threads allocated to the program is greater than the number of processors but less than the number of user-level threads.

答：当内核线程小于处理器数目时，因为用户线程只能通过内核线程访问处理器，因此会有一些处理器处于“围观”状态。当内核线程刚好等于处理器时，处理器的效率相对于 a 会提高，然而当一个线程执行了阻塞系统调用时，其它用户线程就无法使用该内核进程，c 的情况则弥补了这一点，当一个用户线程阻塞时可以被其它用户线程替换，因此处理器效率最高。

  • 分类于 课程笔记
  • 需要 1 分钟阅读时间

操作系统第三章 作业

3.1

Describe the differences among short-term, medium-term, and long-term scheduling.

  • 短期调度 从内存中的就绪队列里选择一个进程执行。执行最为频繁，为保证执行时间短，因而调度算法不能太复杂。
  • 长期调度 也称为工作调度，决定从磁盘中将哪些进程放入内存。因为执行很不频繁，所以可以使用更复杂的调度算法，从而使内存中进程的 CPU 使用和 I/O 使用更均衡，资源利用率更高。
  • 中期调度 有交换的机制，即将进程从内存中移除，并在适当时间再次将其调入内存。这有助于动态改善进程组合，使 CPU 和 I/O 使用更均衡。

3.2

Describe the actions taken by a kernel to context-switch between processes.

进程间的上下文切换，即切换到另一个进程时需要保留当前进程的状态并恢复另一进程的状态。这些状态可以用 PCB 即进程控制块表示，包含进程状态，程序计数器，CPU 寄存器等信息。上下文切换时，主要执行一个状态保存和状态恢复过程，可能还要执行一些体系结构有关的操作比如清除 cache 等。

3.A

Consider a computer with N processors in a multiprocessor configuration.

a. How many processes can be in each of the Ready, Running, and Waiting states at one time? 答：若干个就绪阶段，不超过 N 个执行阶段，若干个等待阶段。 b. What is the minimum number of processes that can be in each of the Ready, Running, and Waiting states at one time? 答：最少当然都是 0 个？

3.B

Please explain the five states of a process.

  • new: 进程刚被创建时，处于此阶段。如 linux 中 fork 系统调用创建新进程时。
  • ready: 进程执行等待被分配到 CPU 中执行。
  • run: 进程正在被执行。
  • waiting: 进程由于需要等待 I/O 等设备的数据，而不能执行，被放置对应设备的等待队列中。
  • terminated: 进程执行结束，正在释放进程的 PCB。

3.C

what is the role of PCB in OS? What information is contained in PCB? 操作系统对进程的创建、删除、调度都是通过对 PCB 的操作来完成的。 PCB 包含：

  • 进程状态
  • 程序计数器
  • cpu 寄存器
  • cpu 调度信息：如进程优先级，调度队列指针等。
  • 内存管理信息：基址，页表或段表等。
  • accounting info: cpu 时间时间，时间界限，进程数等。
  • I/O 状态信息：分配的 I/O 列表，打开的文件列表等待。

3.D

When a process is created, the operating system needs to be done?

  • 给新进程分配物理和逻辑资源（CPU 时间，内存，文件，I/O 设备，可来自操作系统或继承父进程资源）
  • 传递初始化数据

3.E

Please list the differences between message passing system and shared memory system.

  • 共享内存系统基本只能在同一台计算机（可多核）两进程传递信息，而信息传递系统既可以是同一台计算机也可以是通过网络连接的不同计算机间进程传递信息。
  • 共享内存系统只需为进程分配共享内存，通信由进程负责，而信息传递系统需要操作系统参与进行进程间的信息传递。
  • 分类于 课程笔记
  • 需要 1 分钟阅读时间

操作系统第二章 作业

2.2

List five services provided by an operating system that are designed to make it more convenient for users to use the computer system. In what cases it would be impossible for user-level programs to provide these services? Explain.

1 程序执行 服务：操作系统将程序装载入内存并执行程序。 若使用用户程序提供该服务，则很有可能带来安全隐患，因为应用程序可能会装载非法程序。

2 I/O 操作 服务：系统提供方便操作 I/O 设备的方法。 若使用用户程序提供该服务，在多用户系统中，应用程序可能会窃取其它用户存储在硬盘里的数据。

3 文件系统操作 服务：提供文件的，创建、删除、搜索、获取信息方法，并提供访问权限管理。 同样，应用程序可能会非法访问文件。

4 通信 服务：提供进程间的相互通信。（同一计算机内的不同进程或通过网络链接的不同计算机的进程） 同样，应用程序可能会非法窃听其它应用的信息。

5 错误检测 服务：对于发生在硬件上或用户程序中的错误，操作系统采取适当的处理措施。 若使用应用程序提供该服务，则应用程序在编写时需要考虑所有可能的错误，这是不现实的。

2.5

What are the five major activities of an operating system in regard to file management?

  • 文件的创建和删除
  • 文件的打开和关闭
  • 文件的读、写、重定位
  • 读取文件属性和设置文件属性
  • 文件的权限管理

2.8

What are the two models of interprocess communication? What are the strengths and weaknesses of the two approaches?

1 共享内存 (shared-memory model) 优点：

  • 速度快
  • 访问数据方便

缺点：

  • 不易进行数据的保护和同步

2 消息 (message-passing model) 优点：

  • 不必避免冲突
  • 计算机间通信时，更容易实现

缺点：

  • 大量数据传输时，速度慢
  • 分类于 课程笔记
  • 需要 1 分钟阅读时间

操作系统第一章 作业

1.3

Under what circumstances would a user be better off using a timesharing system rather than a PC or single-user workstation? 答：当计算机性能足够强大的时候，采用分时系统可以让计算机同时地，快速地，为许多用户解决复杂的问题，并使得计算资源得到充分的利用。此时若让每个用户使用 pc 机去解决问题会需要很久，而给使用工作站成本又太高。

1.5

Describe the differences between symmetric and asymmetric multiprocessing. What are three advantages and one disadvantage of multiprocessor systems? 答：

  1. 区别：
  • 对称多处理器中的每个核对于程序来讲是完全相同的，而非对称多处理的每个核都有自己擅长处理的特定的计算任务，是不同的。
  • 对称多处理器中的每个核都可以进行 I/O 操作，而非堆成中多处理中，有一个主核控制其它从核，通常只有主核执行 I/O 操作。
  1. 优缺点：

  • 优点：

    1. 利用了并行性，增加了系统的吞吐量。
    2. 因为不同 cpu 共享外设，大容量存储和电源等资源，因此更加经济。
    3. 因为即使一个 cpu 出了问题，整个系统仍可以正常工作，因此更加可靠。

  • 缺点：

    1. 需要编程人员编写并行性的程序才能发挥效果，增加编程工作量。

1.10

What is the purpose of interrupts? What are the differences between a trap and an interrupt? Can traps be generated intentionally by a user program? If so, for what purpose? 答：

  1. 中断的目的：
  • 使用中断访问 I/O 机制，可以消除 cpu 对 I/O 设备的轮询，减少 cpu 的等待时间。
  • 通过中断更容易对外设进行响应，如按下键盘会产生一个中断，计算机处理这个中断便会跳转到响应处理程序。
  1. 中断是硬件产生的，陷阱（trap）是软件产生的。
  2. 可以，如软件需要进行系统调用时。
  • 分类于 课程笔记
  • 需要 3 分钟阅读时间

计算机组成原理 第一章作业

教材：计算机组成原理：软硬件接口 第 5 版 (mips 版) 时间：2019/09/08

Exercise 1.2

  1. a: "Assembly lines in automobile manufacturing" -> "Performance via Pipelining"
  2. b: "Suspension bridge cables" -> “Dependability via Redundancy”
  3. c: "Aircraft and marine navigation systems that incorporate wind information" -> “Performance via Prediction”
  4. d: "Express elevators in buildings" -> “Performance via Parallelism”
  5. e: "Library reserve desk" -> “Hierarchy of Memories”
  6. f: "Increasing the gate area on a CMOS transistor to decrease its switching time" -> “Make the Common Case Fast”
  7. g: "Adding electromagnetic aircraft catapults (which are electrically-powered as opposed to current steam-powered models), allowed by the increased power generation off ered by the new reactor technology" -> “Design for Moore’s Law”
  8. h: "Building self-driving cars whose control systems partially rely on existing sensor systems already installed into the base veh icle, such as lane departure systems and smart cruise control systems" -> “Use Abstraction to Simplify Design”

Exercise 1.3

以 C 语言为例：     编译     汇编      链接 $ 源代码 \Longrightarrow 汇编语言 \Longrightarrow 目标代码 \Longrightarrow 机器代码$

  • 编译：通过编译器，读取源程序（字符流），对之进行词法和语法的分析，将高级语言指令转换为功能等效的汇编代码的过程。
  • 汇编：通过汇编器将汇编语言代码翻译成目标机器指令的过程。
  • 链接：将有关的目标文件彼此相连接，也即将在一个文件中引用的符号同该符号在另外一个文件中的定义连接起来，使得所有的这些目标文件成为一个能够被操作系统装入执行的统一整体。

Exercise 1.4

a) $ frame size = 1280 \times 1024 \times 3 \times 8bit = 3.75MB $ b) $ time = \frac{ 1280 \times 1024 \times 3 \times 8bit }{100 \times 10^{6} bit} \approx 0.31s $

Exercise 1.5

1.5.1

设\(I\)为指令数，\(t\)为 cpu 执行时间，\(f\)为时钟频率，则： $$ I = \frac{t \cdot f}{CPI} $$ $ I_{p1} = {1 \times 3 \over 1.5} = 2G 条$ $ I_{p2} = {1 \times 2.5 \over 1} = 2.5G 条$ $ I_{p3} = {1 \times 4 \over 2.2} \approx 1.82G 条$

1.5.2

设$ C $为时钟数，则：

$ C_{p1} = 10 \times 3 = 30G $ $ I_{p1} = {30 \over 1.5} = 20G $

$ C_{p2} = 10 \times 2.5 = 25G $ $ I_{p2} = {25 \over 1} = 25G $

$ C_{p3} = 10 \times 4 = 40G $ $ I_{p3} = {40 \over 2.2} \approx 18.2G $

1.5.3

(1) $ t = \frac{I \cdot CPI}{f} $ (2) $ (1-0.3)t = \frac{I \cdot (1+0.2)CPI}{f'} $

$ 由\frac{(1)}{(2)} \Rightarrow \frac{clock rate'}{clock rate} = {(1+0.2) \over (1-0.3)} = 1.71$

Exercise 1.6

1.6.1

令$ p_i $为一条指令占总指令的比例，则对于平均 CPI，有： $$ \overline {CPI} = \sum_{i=1}^nCPI_i \cdot p_i $$ 对于 P1：$ \overline {CPI} = 0.1\times 1 + 0.2\times 2 + 0.5\times 3 + 0.2\times 3 = 2.5 $ 对于 P2：$ \overline {CPI} = 2 $

1.6.2

对于 P1，时钟数：$ C = \frac{1.0 \times 10^6}{2.5} = 4\times 10^5 $ 对于 P2，时钟数：$ C = \frac{1.0 \times 10^6}{2} = 5\times 10^5 $

Exercise 1.7

a)

设$ T \(为时钟周期，\) t \(为程序执行时间，\) I $为指令数，则： $$ CPI = \frac{t}{I \cdot T} $$ $ \overline {CPI_A} = \frac{1.1s}{1.0 \times 10^9 \times 1 ns} = 1.1$ $ \overline {CPI_B} = \frac{1.5s}{1.2 \times 10^9 \times 1 ns} = 1.25$

b)

设$ f = \frac{1}{T} $，利用上述公式，得： $$ \frac{CPI_A}{CPI_B} = \frac{I_B \cdot T_{PB}}{I_A \cdot T_{PA}}\ \Rightarrow \frac{1.1}{1.25} = \frac{1.2 f_{PA}}{1.0 f_{PB}}\ \Rightarrow \frac{f_{PA}}{f_{PB}} = 0.733 $$ 答：处理器 A 的时钟频率为处理器 B 的 0.733 倍

c)

仍假设 cpu 时钟周期为 1ns，$ t_{new} = 6.0 \times 10^8 \times 1.1 \times 1ns = 0.66s $

对于 A: $ 加速比 = (1.1 - 0.66)/1.1 = 40\% $ 对于 B：$ 加速比 = (1.5 - 0.66)/1.5 = 29.3\% $

Exercise 1.8

1.8.1

设 P 为功耗，C 为负载电容，V 为电压，f 为开关频率，动态功耗公式： $$ P = C \cdot U^2 \cdot f $$ $ C_{Pentium 4} = \frac{90}{1.25^2 \times 3.6 \times 10^6} = 16 \mu F$ $ C_{Core i5} = \frac{40}{0.9^2 \times 3.4 \times 10^6} \approx 14.5 \mu F$

1.8.2

$ 设 p1 为静态功耗占总功耗的比例，p2 为静态功耗相对于动态功耗的比例。 $

$ Pentium 4: p1 = 10/100 = 10\%, p2 = 10/90 = 11.1\%$ $ Core i5: p1 = 30/70 = 42.9\%, p2 = 30/40 = 75\%$

1.8.3

\[ P_总 = P_动 + P_静 = C \cdot U^2 \cdot f + I \cdot U$$ $ 因为 I 不变，设变化后的电压为 U'，t = \frac{U'}{U},则： $ $$ P_总' = P_动 \cdot \left( \frac{U'}{U} \right)^2 + P_静 \cdot \left( \frac{U'}{U} \right) \\ \Rightarrow P_总' = P_动 \cdot t^2 + P_静 \cdot t \]

对于 P4： $ 90 = 90t^2 + 10t \Rightarrow t \approx 0.946 $ 对于 i5: $ 63 = 40t^2 + 30t \Rightarrow t \approx 0.935$ 答：对于 P4，电压降为原来的$ 94.6\% \(，对于 i5，电压降为原来的\) 93.5\% $