深入理解 Linux 内核(二)(上):https://developer.aliyun.com/article/1597421
七、进程调度
1、调度策略
2、调度程序所使用的函数
八、内存管理
1、页框管理
(1)页描述符
内核必须记录每个页框当前的状态。例如,内核必须能区分哪些页框包含的是属于进程的页,而哪些页框包含的是内核代码或内核数据。类似地,内核还必须能够确定动态内存中的页框是否空闲。如果动态内存中的页框不包含有用的数据,那么这个页框就是空闲的。在以下情况下页框是不空闲的:包含用户态进程的数据、某个软件高速缓存的数据、动态分配的内核数据结构、设备驱动程序缓冲的数据、内核模块的代码等等。
页框的状态信息保存在一个类型为 page 的页描述符中,其中的字段如表 8-1 所示。所有的页描述符存放在 mem_map 数组中。因为每个描述往长度为 32 字节。所以 mem_map 所需要的空间略小于整个 RAM 的 1%。virt_to_page(addr) 宏产生线性地址 addr 对应的页描述符地址。pfn_to_page(pfn) 宏产生与页框号 Pfn 对应的页描述符地址。
// include/linux/mm_types.h /* * Each physical page in the system has a struct page associated with * it to keep track of whatever it is we are using the page for at the * moment. Note that we have no way to track which tasks are using * a page, though if it is a pagecache page, rmap structures can tell us * who is mapping it. */ struct page { /* 一组标志(参见表 8-2)。也对页框所在的管理区进行编号 */ unsigned long flags; /* Atomic flags, some possibly * updated asynchronously */ /* 页框的引用计数器 */ atomic_t _count; /* Usage count, see below. */ union { /* 页框中的页表项数目(如果没有则为 -1) */ atomic_t _mapcount; /* Count of ptes mapped in mms, * to show when page is mapped * & limit reverse map searches. */ struct { /* SLUB */ u16 inuse; u16 objects; }; }; union { struct { /* 可用于正在使用页的内核成分(例如,在缓冲页的情况下它是一个缓冲器 * 头指针;参见第15章的 “块缓冲区和缓冲区首部” 一节)。如果页是 * 空闲的,则该字段由伙伴系统使用 */ unsigned long private; /* Mapping-private opaque data: * usually used for buffer_heads * if PagePrivate set; used for * swp_entry_t if PageSwapCache; * indicates order in the buddy * system if PG_buddy is set. */ /* 当页被插入页高速缓存中时使用(参见第15章 “页高速缓存” 一节), * 或者当页属于匿名区时使用(参见第17章的 “匿名页的反向映射” * 一节) */ struct address_space *mapping; /* If low bit clear, points to * inode address_space, or NULL. * If page mapped as anonymous * memory, low bit is set, and * it points to anon_vma object: * see PAGE_MAPPING_ANON below. */ }; #if USE_SPLIT_PTLOCKS spinlock_t ptl; #endif struct kmem_cache *slab; /* SLUB: Pointer to slab */ struct page *first_page; /* Compound tail pages */ }; union { /* 作为不同的含义被几种内核成分使用。例如,它在页磁盘映像 * 或匿名区中标识存放在页框中的数据的位置(参见第15章), * 或者它存放一个换出页标识符(第17章) */ pgoff_t index; /* Our offset within mapping. */ void *freelist; /* SLUB: freelist req. slab lock */ }; /* 包含页的最近最少使用(LRU)双向链表的指针 */ struct list_head lru; /* Pageout list, eg. active_list * protected by zone->lru_lock ! */ /* * On machines where all RAM is mapped into kernel address space, * we can simply calculate the virtual address. On machines with * highmem some memory is mapped into kernel virtual memory * dynamically, so we need a place to store that address. * Note that this field could be 16 bits on x86 ... ;) * * Architectures with slow multiplication can define * WANT_PAGE_VIRTUAL in asm/page.h */ #if defined(WANT_PAGE_VIRTUAL) void *virtual; /* Kernel virtual address (NULL if not kmapped, ie. highmem) */ #endif /* WANT_PAGE_VIRTUAL */ #ifdef CONFIG_WANT_PAGE_DEBUG_FLAGS unsigned long debug_flags; /* Use atomic bitops on this */ #endif #ifdef CONFIG_KMEMCHECK /* * kmemcheck wants to track the status of each byte in a page; this * is a pointer to such a status block. NULL if not tracked. */ void *shadow; #endif };
这里详细地描述以下两个字段:
_count
页的引用计数器。如果该字段为 -1,则相应页框空闲,并可被分配给任一进程或内核本身;如果该字段的值大于或等于0,则说明页框被分配给了一个或多个进程,或用于存放一些内核数据结构。page_count() 函数返回 _court 加 1 后的值,也就是该页的使用者的数目。
flags
- 包含多达 32 个用来描述页框状态的标志(参见表 8-2)。对于每个 PG_xyz 标志,内核都定义了操纵其值的一些宏。通常,PageXyz 宏返回标志的值,而 SetPageXyz 和 ClearPageXyz 宏分别设置和清除相应的位。
(2)非一致内存访问(NUMA)
我们习惯上认为计算机内存是一种均匀、共享的资源。在忽略硬件高速缓存作用的情况下,我们期望不管内存单元处于何处,也不管 CPU 处于何处,CPU 对内存单元的访问都需要相同的时间。可惜,这种假设在某些体系结构上并不总是成立。例如,对于某些多处理器 Alpha 或 MIPS 计算机,这就不成立。
Linux 2.6 支持非一致内在访问(Non-Uniform Memory Access ,NUMA)模型,在这种模型中,给定 CPU 对不同内存单元的访问时间可能不一样。系统的物理内存被划分为几个节点(node)。在一个单独的节点内,任一给定 CPU 访问页面所需的时间都是相同的。然而,对不同的 CPU,这个时间可能就不同。对每个 CPU 而言,内核都试图把耗时节点的访问次数减到最少,这就要小心地选择 CPU 最常引用的内核数据结构的存放位置(注 1)。
每个节点中的物理内存又可以分为几个管理区(Eone),这我们将在下一节介绍。每个节点都有一个类型为 pg_data_t 的描述符,它的字段如表 8-3 所示。所有节点的描述符存放在一个单向链表中,它的第一个元素由 pgdat_list 变量指向。
// include/linux/mmzone.h typedef struct pglist_data { /* 节点中管理区描述符的数组 */ struct zone node_zones[MAX_NR_ZONES]; /* 页分配器使用的 zonelist 数据结构的数组 * (参见后面 “内存管理区” 一节) */ struct zonelist node_zonelists[MAX_ZONELISTS]; /* 节点中管理区的个数 */ int nr_zones; #ifdef CONFIG_FLAT_NODE_MEM_MAP /* means !SPARSEMEM */ /* 节点中页描述符的数组 */ struct page *node_mem_map; #ifdef CONFIG_CGROUP_MEM_RES_CTLR struct page_cgroup *node_page_cgroup; #endif #endif #ifndef CONFIG_NO_BOOTMEM /* 用在内核初始化阶段 */ struct bootmem_data *bdata; #endif #ifdef CONFIG_MEMORY_HOTPLUG /* * Must be held any time you expect node_start_pfn, node_present_pages * or node_spanned_pages stay constant. Holding this will also * guarantee that any pfn_valid() stays that way. * * Nests above zone->lock and zone->size_seqlock. */ spinlock_t node_size_lock; #endif /* 节点中第一个页框的下标 */ unsigned long node_start_pfn; /* 内存节点的大小,不包括洞(以页框为单位) */ unsigned long node_present_pages; /* total number of physical pages */ /* 节点的大小,包括洞(以页框为单位) */ unsigned long node_spanned_pages; /* total size of physical page range, including holes */ /* 节点标识符 */ int node_id; /* kswapd 页换出守护进程使用的等待队列 * (参加第17章的 “周期回收” 一节) */ wait_queue_head_t kswapd_wait; /* 指针指向 kswapd 内核线程的进程描述符 */ struct task_struct *kswapd; /* kswapd 将要创建的空闲块大小取对数的值 */ int kswapd_max_order; } pg_data_t;
我们同样只关注 80x86 体系结构。IBM 兼容 PC 使用一致访问内存(UMA)模型,因此,并不真正需要 NUMA 的支持。然而,即使 NUMA 的支持没有编译进内核,Linux 还是使用节点,不过,这是一个单独的节点,它包含了系统中所有的物理内存。因此,pgdat_list 变量指向一个链表,此链表是由一个元素组成的,这个元素就是节点 0 描述符,它被存放在 contig_page_data 变量中。
在 80x86 结构中,把物理内存分组在一个单独的节点中可能显得没有用处,但是,这种方式有助于内存代码的处理更具有可移植性,因为内核假定在所有的体系结构中物理内存都被划分为一个或多个节点。
(3)内存区管理
在一个理想的计算机体系结构中,一个页框就是一个内存存储单元,可用于任何事情:存放内核数据和用户数据、缓冲磁盘数据等等。任何种类的数据页都可以存放在任何页框中,没有什么限制。
但是,实际的计算机体系结构有硬件的制约,这限制了页框可以使用的方式。尤其是,Linux 内核必须处理 80x86 体系结构的两种硬件约束:
- ISA 总线的直接内存存取(DMA)处理器有一个严格的限制:它们只能对 RAM 的前 16MB 寻址。
- 在具有大容量 RAM 的现代 32 位计算机中,CPU 不能直接访问所有的物理内存,因为线性地址空间太小。
为了应对这两种限制,Linux 2.6 把每个内在节点的物理内在划分为 3 个管理区(zone)。在 80x86 UMA 体系结拉中的管理区为:
- ZONE_DMA
包含低于 16 MB 的内存页框 - ZONE_NORMAL
包含高于 16 MB 且低于 896 MB 的内存页框 - ZONE_HIGHMEM
包含从 896MB 开始高于 896 MB 的内存页框
ZONE_DMA 和 ZONE_NORMAL 区包含内存的 “常规” 页框,通过把它们线性地映射到线性地址空间的第 4 个 GB,内核就可以直接进行访问(参见第二章的 “内核页表” 一节)。相反,ZONE_HIGHMEM 区包含的内存页不能由内核直接访问。尽管它们也线性地映射到了线性地址空间的第 4 个 GB(参见本章后面 “高端内存页框的内核映射” 一节)。在 64 位体系结构上 ZONE_HIGHMEM 区总是空的。
每个内存管理区都有自己的描述符。它的字段如表 8-4 所示。
管理区结构中的许多字段用于回收页框,相关内容将在第十七章中描述。
每个页描述符都有到内存节点和到节点内管理区(包含相应页框)的链接。为节省空间,这些链接的存放方式与典型的指针不同,而是被编码成索引存放在 flags 字段的高位。
实际上,刻画页框的标志的数目是有限的,因此保留 flags 字段的最高位来编码特定内存节点和管理区号总是可能的(注 3)。page_zone() 函数接收一个页描述符的地址作为它的参数;它读取页描述符中 flags 字段的最高位,然后通过查看 zone_table 数组来确定相应管理区描述符的地址。在启动时用所有内存节点的所有管理区描述符的地址初始化这个数组。
当内核调用一个内存分配函数时,必须指明请求页框所在的管理区。内核通常指明它愿意使用哪个管理区。例如,如果一个页框必须直接映射在线性地址的第 4 个 GB,但它又不用于 ISA DMA 的传输,那么,内核不是在 ZONE_NORMAL 区就是在 ZONE_DMA 区请求一个页框。当然,如果 ZONE_NORMAL 没有空闲页框,那么,应该从 ZONE_DMA 获取页框。为了在内存分配请求中指定首选管理区,内核使用 zonelist 数据结构,这就是管理区描述符指针数组。
注 3:为索引保留的位的数目取决于内核是否支持 NUMA 模型以及 flags 字段的大小。如果不支持 NUMA,那么 flags 字段中管理区索引占两位、节点索引占一位(通常设为 0)。在 NUMA 32 位体系结构上,flags 中管理区索引占两位,节点数目占六位。最后,在 NUMA 64 位体系结构上,64 位的 flags 字段中管理区索引占两位,节点数目占十位。
(4)保留的页框池
可以用两种不同的方法来满足内存分配请求。如果有足够的空闲内存可用,请求就会被立刻满足。否则,必须回收一些内存,并且将发出请求的内核控制路径阻塞,直到有内存被释放。
不过,当请求内存时,一些内核控制路径不能被阻塞 —— 例如,这种情况发生在处理中断或在执行临界区内的代码时。在这些情况下,一条内核控制路径应当产生原子内存分配请求(使用 GFP_ATOMIC 标志; 参见稍后的 “分区页框分配器” 一节)。原子请求、从不被阻塞:如果没有足够的空闲页,则仅仅是分配失败而已。
尽管无法保证一个原子内存分配请求决不失败,但是内核会设法尽量减少这种不幸事件发生的可能性。为做到这一点,内核为原子内存分配请求保留了一个页框池,只有在内存不足时才使用。
保留内存的数量(以 KB 为单位)存放在 min_free_kbytes 变量中。它的初始值在内核初始化时设置,并取决于直接映射到内核线性地址空间第 4 个 GB 的物理内存的数量 —— 也就是说,取决于包含在 ZONE_DMA 和 ZONE_NORMAL 内存管理区内的页框数目:
但是,min_free_kbytes 的初始值不能小于 128 也不能大于 65536(注 4)。ZONE_DMA 和 ZONE_NORMAL 内存管理区将一定数量的页框贡献给保留内存,这个数目与两个管理区的相对大小成比例。例如,如果 ZONE_NORMAL 管理区比 ZONE_DMA 大 8 倍,那么页框的 7/8 从 ZONE_NORMAL 获得,而 1/8 从 ZONE_DMA 获得。
管理区描述符的 pages_min 字段存储了管理区内保留页框的数目。正如我们将在第十七章看到的,这个字段和 pages_low、pages_high 字段一起还在页框回收算法中起作用。 pages_low 字段总是被设为 pages_min 的值的 5/4,而 pages_high 总是被设为 pages_min 的值的 3/2。
注 4: 稍后系统管理员可以通过写入 /proc/sys/vm/min_free_kbytes 文件或通过发出一个适当的 sysctl() 系统调用来更改保留内存的数量。
(5)分区页框分配器
被称作分区页框分配器(zoned page frame allocator)的内核子系统,处理对连续页框组的内存分配请求。它的主要组成如图 8-2 所示。
其中,名为 “管理区分配器” 部分接受动态内存分配与释放的请求。在请求分配的情况下,该部分搜索一个能满足所请求的一组连续页框内存的管理区(参见后面的 “管理区分配器” 一节)。在每个管理区内,页框被名为伙伴系统(参见后面的 “伙伴系统算法” 一节)的部分来处理。为达到更好的系统性能,一小部分页框保留在高速缓存中用于快速地满足对单个页框的分配请求 (参见后面的 “每 CPU 页框高速缓存” 一节)。