Time sharing: a policy for processes to take turn to use the CPU.
Hardware has a timer to send interrupts to the OS.
Scheduling: choose process to run.
Isolation: avoid process access other processes’ data.
File descriptor: an integer that maps to a file.
Unix philosophy: everything is a file.
Kernel maintains a file descriptor table.
0: stdin, 1: stdout, 2: stderr
Week 2
fork(): create a new process.
exec(): replace memory of the current process.
It doesn’t clear file descriptor.
Pipe: redirect one process’ output into another process input.
parent: write to p[1], close p[0], p[1]
child: close stdin, duplicate p[0] close p[0], p[1]
Week 3
leave: special instruction in x86, which return the old ebp.
Why do we need stack frames? They are not strictly required, but it is good to have them.
Stack contains return addresses of caller function.
eax, edx: the return value.
ebp(frame pointer): points to the base of the frame.
variables:
Global variables: initialized(data section), uninitialized(BSS).
Dynamic variables: allocated on Heap memory.
Local variables: stack.
Week 4
Linking: combines multiple object files into an executable or a library.
Pros
We can write our programs in modules.
Faster code compilation, since we only need to re-compile changed source files and link them to the final target.
Space efficient, since we can share common code.
Loading: load executable into memory.
Relocation: merge sections of each object files into multiple sections in the final executable. Resolve any unknown memory addresses.
ELF format
Program header table: used by loader to load each segments into memory.
Section header table: used by linker to link code and data sections together.
Statically linked: library is linked into the executable, which makes the size of the file larger.
Dynamically linked: library is loaded at runtime, which makes the size of the file smaller.
Position independent code(PIC): generate code in such a way that it can work no
matter where it is located in the address space.
Add additional layer of indirection for all references to global data, imported functions.
Global Offset Table(GOT): a table, which maintains by the linker, that stores the addresses of variables.
Week 5
How to share one memory across multiple processes?
Relocation: process 1 starts from 0x00, process 2 starts from 0x1100.
This works but it lacks isolation. One process can easily access other processes’ memory.
How can we enforce isolation?
Software: SFI(Software Fault Isolation) works, but it has performance overhead.
Hardware: segmentations add base addresses, which are maintained by the hardware, for each process. Hardware has a special register to keep an index into the table.
Global Descriptor Table: an array of segments(base and size) and access control flags.
GDT register points to the address of GDT in physical address.
Linear address(named by Intel): physical address = base(logical address) + offset(effective address)
Each process has a private GDT.
What if one process needs more memory and the increased memory section overlaps with another process?
Move the other process to another memory address, or swap it to disk. Both solutions are inefficient.
Paging is an alternative solution for segmentation.
Instead of seeing memory as a contiguous area, OS treats them as multiple pages that map to frames on physical memory.
Each process has its own page table(page table directory and page tables).
Implementation for Paging
Array
Array of arrays(Page table)
Week 6
copy-on-write: OS only copies page tables only when one of parent, child writes.
What kind of services might disable page table?
Databases
In-memory key-value stores
Does OS flush TLB after context-switching?
A tagged TLB can tag process id to avoid flushing TLB. Greater performance.
System boot
Week 7
System boot
Intel ME powers first and reads initialization code from BIOS chip.
One of the logical processor is chosen as Bootstrap processor(BSP). Others will become application processors.
BSP starts reading instructions in the BIOS chip.
BSP starts without DRAM. Custom assembly code that uses no stack.
System Management Mode: OS cannot access this region of memory. No way to disable this.
BIOS ends by loading a boot loader.
(xv6) BIOS starts executing instructions at address 0x7c00.
Outline of the boot sequence:
Setup segmentation(data and code)
Switch to protection mode(16 to 32 bits)
Load GDT(global descriptor table)
Setup stack(part of C runtime)
Load kernel from disk(ELF)
Jump to kernel entry(set page as 4KB and setup page directory)
Setup page table
Setup high address stack 0x7c00 grows towards 0x0000
Jump to main
Page table has two entries to map to the kernl
#1: 0x0:0x4MB
#2: 0x80000000:0x8040000
Hardware wants the page table directory in register cr3.
Week 8
Why do we need the first page table entry? 0x0:0x4MB
After enabling page table, the kernel will continue executing on virtual address.
If we don’t map the first page table, it will crash after enabling paging.
Linker script specifies the memory address of each section.
Enforce isolation so that user processes cannot access each other and the kernel.
(xv6) Each process will have a 2GB user memory and 2GB kernel memory.
How to implement a memory allocator?
A bitmap that refers to pages. 0: available page, 1: not available page.
Maintain a free page lists.
(xv6) There is an area of free memory after the kernel end where we can use to allocate kernel page table.
Map a region of virtual memory into page tables.
Start at 2GB, iterate memory by page, allocate page directory and pages, map pte with repected physcial address.
Lowest 12 bits of the page table entry are used as modes.