KZnight

What I cannot create, I do not understand.

Linux 核心的红黑树

Linux 核心原始程式碼中,許多地方出現紅黑樹的蹤影,例如:hr_timer 使用紅黑樹來記錄計時器 (timer) 端發出的要求、ext3 檔案系統使用紅黑樹來追蹤目錄內容變更,以及 CFS (Completely Fair Scheduler) 這個 Linux 預設 CPU 排程器,由於需要頻繁地插入跟移除節點 (任務),因此開發者選擇用紅黑樹 (搭配一些效能調整)。VMA(Virtual Memory Area)也用紅黑樹來紀錄追蹤頁面 (page) 變更,因為後者不免存在頻繁的讀取 VMA 結構,如 page fault 和 mmap 等操作,且當大量的已映射 (mapped) 區域時存在時,若要尋找某個特定的虛擬記憶體地址,鏈結串列 (linked list) 的走訪成本過高,因此需要一種資料結構以提供更有效率的尋找,於是紅黑樹就可勝任。

并行程序设计: POSIX Threads

POSIX (Portable Operating System Interfaces) is a family of standards for maintaining compatibility between operating systems. POSIX is a Unix-like operating system environment and is currently available on Unix/Linux, Windows, OS/2 and DOS.

Pthreads (POSIX Threads) is a POSIX standard for threads. The standard, POSIX.1c thread extension, defines thread creation and manipulation. This standard defines thread management, mutexes, conditions, read/write locks, barriers, etc. Except for the monitors, all features are available in Pthreads.

南京大学 计算机系统基础 重点提示

理解一个系统的最佳实践就是去实现它。因此在本课程的PA 部分,你将会在框架代码的基础上实现一个 RISC-V 全系统模拟器 NEMU,它不仅能运行各类测试程序,甚至还可以运行操作系统和 “仙剑奇侠传”。模拟过硬件的执行,自然就能深 (痛) 入 (苦) 理解计算机系统了。

0%