commit f148949be8629ca1f694f1a80fd723730b1598d0
parent 6504fcbd2a58307ea90494226a6d63dbdc91fd75
Author: Alex Balgavy <alex@balgavy.eu>
Date: Wed, 6 Oct 2021 15:26:53 +0200
AOS: paging & multiprocessing
Diffstat:
4 files changed, 137 insertions(+), 0 deletions(-)
diff --git a/content/aos-notes/_index.md b/content/aos-notes/_index.md
@@ -8,3 +8,5 @@ title = 'Advanced OS'
- [Managing physical memory](managing-physical-memory)
- [Page tables](page-tables)
- [User mode](user-mode)
+- [Paging](paging)
+- [Multiprocessing](multiprocessing)
diff --git a/content/aos-notes/multiprocessing.md b/content/aos-notes/multiprocessing.md
@@ -0,0 +1,73 @@
++++
+title = 'Multiprocessing'
++++
+# Multiprocessing
+## Process creation
+### Fork
+fork: creates new child process by duplicating calling process
+
+Simple part:
+- duplicate task: copy most info, with exceptions (e.g. PID)
+- allocate and initialize new kernel stack: setup `thread_info`, copy trap frame and update
+- and copy some other stuff
+
+`copy_mm`:
+- duplicate descriptor of address space of parent (`mm` descriptor): copy basic info, initialize empty address space (new page directory)
+- duplicate address space: copy VMA info, page tables, and fix up page table entries
+ - `MAP_SHARED`: share page frames
+ - `MAP_PRIVATE (R)`: share page frames
+ - `MAP_PRIVATE (R/W)`: copy-on-write page frames
+ - shared memory: permissions of VMA are identical to permissions of PTE
+ - COW: permissions of VMA are RW, permissions of PTE are read-only
+ - duplicate page frme and remap new private copy into faulting PTE on demand
+
+COW: copy on write, share the same resource until one copy is written to, at which point you duplicate the resource.
+- `MAP_PRIVATE` file pages - dedupes binary pages
+- `MAP_PRIVATE` anonymous forked pages - dedupes pages in process hierarchy
+- `MAP_PRIVATE` anonymous forked pages - dedupes zero pages for unrelated processes
+
+### Exec
+Executes program pointed by filename.
+
+implementation:
+- input and permission checking
+- load binary headers in memory
+- find binary format
+- flush old resources:
+ - reinit `task_struct` and empty `mm`
+ - flush VMAs, page tables, page frames
+- load binary (binary-format specific)
+ - parse headers and sections
+ - create corresponding VMAs (data, text, stack, etc.)
+ - update `%rsp` and `%rip` in trap frame
+ - `%rsp` is top of user stack
+ - `%rip`: program entry point for statically linked, dynamic linker's entry point for dynamically linked
+ - page tables initially empty
+ - even binary files are demand paged
+ - PF handler maps them from cache using COW-based strategy
+
+## Scheduling
+easy version:
+- hardware raises periodic timer interrupts
+- timer interrupt handler invokes simple scheduler
+- simple scheduler
+ - FIFO scheduling queue
+ - enqueue interrupted process at tail
+ - dequeue process at heat and run on CPU
+
+## IPC
+communications, sync, signals
+
+Shared mem:
+- System V: get/create shmem segment by key, attach/detach
+
+semaphores:
+- counter shared across processes
+- atomic wait (decrement), release (increment) if val >= -sem\_op
+
+message queue:
+- mailbox with senders and receivers
+- get/create queue by key & permission
+- block if queue full (on send) or empty (on receive)
+
+POSIX: uses names instead of keys, thread safety, ref counting, shmem is file oriented
diff --git a/content/aos-notes/paging/index.md b/content/aos-notes/paging/index.md
@@ -0,0 +1,62 @@
++++
+title = 'Paging'
++++
+
+# Paging
+## Page faults
+Special kind of exception, IV 14.
+
+Types:
+- invalid: access to invalid address (e.g. write to RO page)
+- major (slower): valid, but page not in memory (e.g. file, swapped pages)
+- minor (faster): valid, page in memory
+
+Kernel page fault:
+- invalid:
+ - on kernel address: oops (panic/recovery)
+ - on user address: checks (copy to/from user)
+- major: kernel memory is paged out (not on Linux, e.g. in Windows)
+- minor: lazy allocations (e.g. old vmalloc)
+
+User page fault:
+- could be anything
+
+Page fault information:
+- cr2 register has faulting virtual address
+- error code on stack has:
+ - bunch of reserved bits
+ - P: PTE present bit set (so page present, maybe fault caused by some other problem)
+ - W: write access
+ - U: user access (so we were in user eecution)
+ - R: PTE had reserved bits set
+ - I: faulted while trying to fetch instruction
+
+VMA:
+- contiguous virtual region with given properties (bit flags)
+- anonymous: no file
+- stored in red-black tree (for efficiency) and linked list (for traversing in order)
+
+
+
+Demand paging:
+- new pages are not mapped onto physical memory
+- on first access, process page faults
+- kernel assigns page frame to process, creates PTE, resumes execution
+
+VMA operations:
+- mmap: maps new region in adress space
+ - find fitting hole in memory map, creates and links new VMA (in simplest case)
+- munmap: unmaps region in address space
+ - unlinks and deletes VMA (in simplest case), removes mapped page frames, removes allocated page tables, flushes TLB
+- mprotect: changes region's protection bits
+ - update VMA protection (in simplest case), update affected PTEs
+- madvise: give kernel advice on region, like `MADV_DONTNEED` (unmap page frames), `MADV_WILLNEED` (read ahead page frames)
+- find and split: when you work on a part of a VMA (might even split one into three parts)
+- merge: merge any adjacent VMAs with same properties (flags)
+
+Transparent Huge Pages (THP)
+- kernel transparently allocates THP when possible
+- map: allocate compound pages (physically contiguous pages) and map as THPs
+- collapse: replace some regular pages with THP
+- split: split THP into number of regular pages
+- compact: memory compaction to allocate compound pages
diff --git a/content/aos-notes/paging/vma-diagram.png b/content/aos-notes/paging/vma-diagram.png
Binary files differ.
