Operating Systems from scratch - Part 2

Explore the binary number system (base-2) with 0 and 1, learn powers of two and 2^n numbers with n bits, and see how dividing by one bit supports memory management.

Explore the basics of memory management, from CPU registers and RAM to the role of memory as instructions and data, with word size, addressing, and the address and data buses.

Explore how address space defines the collection of addresses, distinguishing physical and logical address spaces in RAM. Learn how contiguous and non-contiguous allocation place process addresses in memory.

Variable partitioning, also called dynamic partitioning, allocates memory without fixed partitions, sizing partitions to each process to avoid internal fragmentation; it enables flexible multiprogramming but introduces external fragmentation.

Discover how variable partitioning and RAM holes are managed using first-fit, next-fit, best-fit, and worst-fit memory allocation algorithms, with linked list or bitmap tracking.

Analyze how first-fit and best-fit allocate 300, 25, 125, and 50 kb processes in a variable-partition ram, and explain how external fragmentation can prevent allocation.

Explore memory allocation strategies like next-fit, first-fit, best-fit, and worst-fit, and how holes and external fragmentation in RAM affect allocation outcomes.

Explore how first-fit, best-fit, next-fit, and worst-fit memory allocation respond to different request orders, highlighting external fragmentation and the dependence on memory structure.

Apply the best-fit allocation under fixed partitioning to four partitions (4, 8, 20, 2 KB), place P1–P7, and determine that P7 completes at time unit 19.

Explore how binary addressing maps to real-world structures using streets, houses, and floors, revealing how 4-bit addresses organize 16 bytes across partitions in a byte-addressable RAM.

Explain binary addressing concepts by analyzing a 4 GB RAM with fixed partitioning into 64 partitions, addressing 2^32 bytes with 32-bit addresses and 6-bit partition plus 26-bit byte within partition.

Explore why paging and segmentation solve memory management challenges in operating systems. Compare fixed and dynamic partitions, internal and external fragmentation, and how paging enables non-contiguous allocation.

Learn how operating systems move from contiguous to non-contiguous allocation, and how paging solves non-contiguous storage using base registers and the distinction between logical and physical addresses.

Explore how paging solves non-contiguous allocation by using a page table to map process pages to fixed-size frames, enabling the CPU to access memory efficiently.

Explain paging with a concrete example, showing how a four-page process fits into RAM frames via a per-process page table, highlighting frames, physical and logical address space, and noncontiguous allocation.

Understand paging through example that shows how a cpu uses a page table base register to translate a logical address into a physical address and fetch a byte from RAM.

Explain paging with an example, showing how a 24-bit logical address becomes a 34-bit physical address via a 7-bit page number and 17-bit offsets, using a page table and MMU.

Revisit internal fragmentation in paging, showing it can occur when the process size is not a multiple of the page size or when the page table is smaller than a page, while paging avoids external fragmentation.

Determine the logical address length by the ceiling of log base 2 of the space in bytes; 16 bytes require 4 bits, 15 bytes require 4 bits.

Compute ram size as 2^(m-n) frames times 2^n bytes per frame, giving 2^m bytes. Relate processes to paging: 2^l pages with 2^k bytes per page yield total size 2^(l+k) bytes.

Explore how p-bit logical addresses and a page size of 2^q bytes in a byte-addressable system yield 2^(p-q) pages and a process size of 2^p bytes.

Compute 16-bit logical and physical addresses for a 64 kb space with 2 kb pages, deriving 11-bit offsets and 5-bit frame numbers, yielding a 32-entry page table of 5-bit entries (20 bytes).

Solve a paging problem in a byte-addressable system with 256 kb logical space and 1 mb physical space, deriving 18-bit logical addresses, 20-bit physical addresses, and a 64-byte page table.

The logical address space is 2^21 bytes with a 10-bit page offset, giving 11-bit page numbers, 2^10-byte pages. With 2^8 frames, the page table holds 2^11 entries of 8 bits.

Solve a paging problem in a byte-addressable system with 256 MB physical space and 1 MB logical space. Derive 28-bit physical addresses, 20-bit logical addresses, and a 12-bit page offset.

Analyze paging calculations for a byte-addressable system with a 2^12-byte page, 2^10 pages, and 2^9 frames, yielding 22-bit logical and 21-bit physical addresses and a 1152-byte page table.

Explore paging with 2^15 byte pages and 2^7 pages, revealing a 22-bit logical address, a 2^22 byte space, and 31-bit physical addresses via a 16-bit frame number.

The RAM stores frames for pages and the CPU uses a page table base address. Indexing the page table via the memory management unit yields the physical address.

Explore why multilevel paging is needed when a page table grows larger than a frame, reducing fragmentation and managing non-contiguous memory efficiently.

Learn how logical addresses are translated to physical addresses using paging, including page tables, page table base registers, and frame numbers, contrasting contiguous allocation with multilevel paging.

Compare single level paging with multi-level paging, showing how contiguous versus noncontiguous process layouts affect memory accesses to page tables and data.

Introduce multilevel paging to handle non-contiguous process pages by using level 0 and level 1 page tables stored in RAM frames, with pointers, simple indexing, and awareness of internal fragmentation.

Learn how multilevel paging uses page number and page offset to reach the correct frame, scaling from single to two-level page tables via base address.

explains how a 5-bit logical address splits into a 3-bit page offset and a 2-bit page number, resolved by a two-level page table with 2-entry pages.

Analyze a 64-bit address space with 1 MB pages and 4-byte page table entries to compute innermost and next-level page table sizes for multilevel paging.

Explore multilevel paging concepts, including three levels of page tables, address split, and memory access costs, highlighting fragmentation and the n+1 rule for fetching a byte.

Solve a 48-bit address space with 16 KB pages using three-level paging, yielding 2^34 pages and a 14/12/12/10 bit split to access a byte in four memory accesses.

Analyze a multilevel paging problem by deriving a 72-bit logical address, 2^44 pages, and a two-level page table with 2^18 first-level entries and a 2^26 second-level page, highlighting internal fragmentation.

solve multilevel paging for a 72-bit logical address space with a 30-bit page offset, splitting 42 bits into 27 and 15 for a two-level page table.

Derives the 8 gb logical address space in a two-level paging system with an outer 8 kb page table and 8-byte entries.

The lecture analyzes a three-level paging system, derives 2^10 outer page table entries, 2^20 level-two page table entries, and 2^30 level-one entries, yielding an 8 tb address space.

solve a single-level paging problem by computing 2^10 page table entries from an 8 KB outer page table with 8-byte entries, yielding a process size of 2^23 bytes.

Understand the compulsory frame number field in a page table entry that maps pages to frames, and explore optional fields like the referenced bit and basic page replacement ideas.

Explains present/absent and dirty bits in page tables, how page faults and hits occur, and how RAM, hard disk, and page replacement (LRU) manage modified pages.

Learn how protection bits define a page's access, distinguishing read-only, write-only, and read-write states using two bits, with 00 for read-only, 01 for write-only, and 10 for read-write.

Analyze page table entries, where the frame number indicates the page location, and reference bit, dirty bit, protection bit, and present bit describe usage, access rights, modification, and RAM residency.

The dirty bit in a page table entry signals whether a page was modified and must be written back during page replacement, avoiding unnecessary writes to disk and saving time.

derive a 24-bit page table entry for an 8 kb page system with 32-bit addresses, containing dirty bit, present bit, three permission bits, and frame number, yielding a 36-bit address.

Compute the page table size in a 32-bit, byte-addressable system with 4 KB pages and 4-byte entries, showing that 2^20 entries yield 2^22 bytes or 4 MB.

Determine the maximum page table entry size for a 4 MB logical space with 4 KB pages under single-level paging, yielding 4 bytes.

Using a 4 gb logical address space and 4 mb pages, determine the maximum page table entry size for single-level paging as 4 kb.

Determine the minimum page size for single-level paging given a 256 KB logical address space and 4-byte page table entries, establishing 1024 bytes. Smaller page sizes require multi-level paging.

Explain locality of reference and virtual memory, showing how the cpu uses only a few pages at a time to boost degree of multiprogramming, via ram frames and disk storage.

Explore how virtual memory increases multiprogramming and cpu efficiency, enabling execution of processes larger than ram by loading only the needed pages.

Explain average memory access time in a single-level paging system, comparing RAM hits (about 10 ns) with page faults (about 5010 ns), yielding 510 ns per byte fetch.

Explore two logical methods to calculate average memory access time (amat) using page table, ram, and disk access; both yield a consistent 510 ns result.

Explore average memory access time for a two-level paging system with 10 ns ram and 1000 ns disk, 90% page hit rate, yielding 1030 ns and 130 ns.

With n levels of paging, accessing a byte requires n+1 memory accesses: n for page tables and one for data. For 9 levels, hits and faults average around 200 ns.