2026-09-09

MATH371

Record one interesting problem

You have a 6 by 6 chess plate. Place 6 rooks that they can’t attack each other. Can’t place column 1,2 at row 1,2; Can’t place at column 3,4 at row 3,4; Can’t place at column 5,6 at row 5,6.

Initially I thought to put them into 3 blocks with two rows of each to apply Inclusion-Exlusion. But this is a wrong idea. Situation such as row 1 and 6 placed in wrong is not included in our calculation.

The correct way of doing In-Ex is to do case study. Assuming we make this number of rooks in wrong intensively,

0. $6!$
1. $6*2*5!$
2. $3*2*4!+3*2^2*2^2*4!$
3. $2^3*2^3*3!+3*2^2*2^2*3$
4. $3*2^5*2!+3*2^2*2!$
5. $3*2*2^3*1!$
6. $2^3$

Now we have a proper way to do counting, that is to use poly. The idea I described above is not totally wrong.. : )

Since it can be grouped, there should be methods to express the counting efficiently, consider these three cases in a group if we group each two rows together,

0 rook placed in wrong, 1 situation for the forbidden area

1 rook placed in wrong, 4 situations (first row 2choice+ second row 2chioce= 4)

2 rooks placed in wrong, 2situations

Consider this poly,

The degree tells the number of rooks placed in wrong,

So the coefficent of this poly would be the thing we want..,

One template problem..

Given that $2\le x_i\le 5$, how many int solutions?

Okay, same as..,

Now be carefule, what you need to do is to exclude $x_i\ge 4$, if you exclude $x_i\ge 3$ you will get a negative number…

OS

有个东西叫 VM

我们的process永远触碰不到物理地址，他只能看到自己有很多，很多很多的VM，这样是有好处的喵！防止冲突的发生，以及随之而来的一些权限问题！

通过VM这层中间架构，我们就可以加入各种权限控制在中间了喵！

贪婪的process

一般我们抽象出data,code,stack,heap这几个process具备的要素，他们分别位于process的VM的不同部位。

用Segmentation。因为base+bound太直接。我们需要满足process的内需求增长，stack和heap都会需求更多的空间，如果把他们放在一起，必然会预开很多浪费的空间。那么segmentation，我们分别把各个部分存一个地方，然后开一个电话簿segment table存一下他们的信息。

但是，这还是会造成各种external fragment和internal fragment.

我们想到了Paging

Paging 和他的L1L2L3

我们明确一个事实喵！VM会很大，因为process的内存需求要增长的喵！所以要给多一点喵！

由于stack 和 heap的特殊增长方向，一般我们把stack塞在高地址，把heap塞在低地址，注意这里的地址是VM而不是物理地址哦。那么中间势必有很多浪费，而paging和hierarchical data structures则理论化地降低了这种浪费。

具体思路是，我们把一团VM和在一起叫一个page，我们接下来拿4KB当一个page的大小举例。我们每次做mapping的时候都按照page的大小链接。规定从地址0开始这么干，则你会发现VM的最后12位($2^{12}$B=4KB)和物理地址的最后12位是一样的。这个就叫offset，所以我们处理VA到PA的时候可以直接把最后log(page)的地址砍下来用。

然后我们来处理这个浪费的问题喵！最典型的例子就是stack和heap中间会有很多很多的空，这些我们都不需要，所以我们尽量不去给这些VM做mapping喵！于是我们使用hierarchical structres喵！

给VM做规定，我们定义一个39bit VM address为9bit(L1)+9bit(L2)+9bit(L3)+12bit。我们每次做翻译只做L1->L2，L2->L3 L3->物理地址的翻译喵！具体是什么意思呢喵？比如我找这个地址喵

(11)(22)(33)(44) ，我们直接转成10进制方便理解喵，应该是按bit取的喵。

那么我们按照这个process的L1page table搜索11喵。找到11喵！这个table会告诉我们11开头的VM应该在L2层的哪里存储着喵！

我们现在到L2层了。我们在L2的table里找22，没找到喵。那么我们新建一个L3table喵！我们把这个L2table的entry指向这个table喵。我们现在就算将功补过了喵！

那么我们来到L3层了喵。找33，没找到喵，由于我们在L3层了，直接去物理地址上开一个frame(物理硬件上我们叫frame以便于和page区分)，然后指向这个frame喵。

offset直接拿来用喵！那么我们就找到这个物理地址了喵！

形象地说，这就是一个动态开点线段树。

在xv6里面，一般一个entry是64B，就是8Byte，那么$2^9*8B=2^{12}B$刚好是一个Page大小喵！所以在这套规则下，一个page table的大小卡位一个page的大小，终于不用担心浪费空间了喵！

需要注意的是，这里的L1 L2 L3都是cache，不是我们说的page structure，我们的page structure都在Page table这个格子里喵，实现全是在VM上实现的，本身占据了虚拟内存喵！

还有两个趣味小问答。

第一个是1，因为可以为空，那就一个satp指向的根节点

第二个是N，因为不知道。

看起来很有用的东西：）

下面是ai写的笔记喵，上课给我听昏头了喵，

Memory management is mainly about how the OS manages memory and gives processes a safe, convenient view of memory.

A process uses virtual addresses (VA). Hardware, with help from the OS, translates VA → physical addresses (PA). Virtual memory provides isolation, protection, sharing, and a convenient address space for each process.

For memory allocation, malloc() asks for a region of memory and returns a pointer; free(ptr) returns it. The allocator needs some data structure to track free memory, commonly a free list. A free list stores the address and size of free chunks.

Two important problems are:

• External fragmentation: free memory is split into many small chunks. There may be enough total free memory, but no single contiguous chunk is large enough.
• Internal fragmentation: an allocator gives a chunk larger than requested, wasting space inside the allocated chunk.

Common allocator mechanisms include:

• Splitting: divide a large free chunk when a smaller allocation is requested.
• Coalescing: merge adjacent free chunks after free().
• Metadata: extra information stored with an allocation, such as its size, pointers, or a magic number. This lets free(ptr) determine the size of the allocation even though the caller only provides a pointer.

The distinction between policy and mechanism is important. Policy decides what should happen; mechanism provides how it is implemented. For example, choosing which process runs next is policy, while queues and context switches are mechanisms.

For virtual memory, a simple approach is base and bounds:

PA = Base + VA

The hardware first checks:

VA < Bound

If the check fails, an exception occurs. This provides relocation and protection, but the process needs a contiguous physical region and can suffer from fragmentation.

Segmentation improves this by dividing a process into logical segments such as Code, Data, Heap, and Stack. Each segment has its own:

Base
Bound
Permissions (R/W/X)

A virtual address contains a segment ID and an offset:

VA = Segment ID + Offset

The segment table identifies the segment, checks the offset and permissions, and then computes:

PA = Segment.Base + Offset

Segmentation allows different segments to be placed independently and can support sharing. However, segments are variable-sized, so external fragmentation remains a problem.

Paging solves much of this problem by using fixed-size units. Virtual memory is divided into pages, and physical memory is divided into equally sized frames.

Instead of:

virtual segment → physical segment

we use:

virtual page → physical frame

A page table stores this mapping. A page-table entry (PTE) contains information such as the physical frame number, validity, and permissions.

A virtual address is divided into:

| VPN | Offset |

For a 4 KiB page:

4 KiB = 2^12 bytes

so the offset is 12 bits.

For a 32-bit VA:

VPN = 32 - 12 = 20 bits

The physical address is:

PA = PFN × PageSize + Offset

Paging removes the need for contiguous physical allocation and therefore greatly reduces external fragmentation. However, a page table itself consumes memory, and looking up a PTE adds memory accesses.

A TLB (Translation Lookaside Buffer) is a small cache of recent address translations:

VPN → PFN

On a TLB hit, the translation is obtained quickly.

On a TLB miss, the hardware must perform a page-table walk. If the page table has N levels, the walk requires N additional memory accesses before accessing the actual data. Thus, the total can be roughly:

N page-table accesses + 1 actual memory access

Multi-level page tables reduce page-table memory usage for sparse address spaces. Instead of allocating the entire huge page table, lower-level tables are created only where mappings are needed.

For an N-level page table, if each level fits in one page, the smallest valid page-table structure still needs one root page. If an actual mapping exists, the relevant path through all N levels requires N page-table pages.

RISC-V’s Sv39 uses a 39-bit virtual address:

| L2 9 bits | L1 9 bits | L0 9 bits | Offset 12 bits |

The 9-bit fields are indices, not memory segments.

Why 9 bits?

2^9 = 512

Each page table therefore has 512 entries. Since each PTE is 8 bytes:

512 × 8 = 4096 bytes = 4 KiB

So one page table exactly fits in one page.

The translation works conceptually as:

VA
 ↓
L2 index
 ↓
L1 page table
 ↓
L1 index
 ↓
L0 page table
 ↓
L0 index
 ↓
PTE → Physical Frame
 ↓
+ Offset
 ↓
PA

The three 9-bit indices together identify the VPN. The 12-bit offset identifies the byte inside the 4 KiB page.

Important RISC-V registers include:

satp  → identifies the current root page table
stval → faulting virtual address
scause → reason for the trap/fault

satp is one CPU register, not one register per process. Each process has its own page table, and when the OS switches processes, it changes satp to point to the new process’s root page table.

Conceptually:

Process A → Page Table A
                 ↑
               satp

Context switch

Process B → Page Table B
                 ↑
               satp

Thus, the same virtual address can map to different physical addresses in different processes.

Important Sv39 PTE flags include:

V → valid
R → readable
W → writable
X → executable
U → accessible from user mode
G → global mapping
A → accessed
D → dirty

A page fault occurs when a translation is invalid or the requested access is not permitted. Relevant scause values in xv6 include:

0xC → instruction page fault
0xD → load page fault
0xF → store page fault

In xv6, physical addresses are determined by the hardware platform, while the OS constructs the virtual address space and page tables.

The xv6 kernel page table contains mappings for kernel code/data, devices, and other kernel structures. Each process also has its own user page table. xv6’s user stack is a single page and does not automatically grow.

The trampoline and trapframe are especially important:

trampoline → code
trapframe  → saved CPU state/data

The trampoline code is mapped at the same special virtual address in both user and kernel page tables. This allows the CPU to execute the transition code while switching between page tables during a trap.

The simplified trap path is:

User
 ↓
stvec
 ↓
uservec        ← trampoline code
 ↓
usertrap       ← kernel trap handling
 ↓
usertrapret
 ↓
userret        ← trampoline code
 ↓
User

The trapframe stores the register state that must survive the transition.

The big picture is:

Memory allocation
      ↓
How do we manage free space?
      ↓
malloc / free / free list / metadata
      ↓
Fragmentation
      ↓
How do we give each process its own memory?
      ↓
Base & Bounds
      ↓
Segmentation
      ↓
Paging
      ↓
Page Tables
      ↓
TLB
      ↓
Multi-Level Page Tables
      ↓
RISC-V Sv39
      ↓
xv6 implementation

The most important conceptual distinction to remember is:

Segmentation:
VA = Segment + Offset

Paging:
VA = VPN + Offset

Sv39:
VA = L2 + L1 + L0 + Offset

satp:
"Which page table is active right now?"