C++博客-Blogging Fan's Planethttp://www.cppblog.com/fanfuns/Live Simply, Stay Happy, Give More, Expect Lesszh-cnSun, 12 Apr 2026 09:27:54 GMTSun, 12 Apr 2026 09:27:54 GMT60[导入]learning kernel: 预备知识http://www.cppblog.com/fanfuns/archive/2009/11/26/101984.htmlFan HongweiFan HongweiThu, 26 Nov 2009 09:15:00 GMThttp://www.cppblog.com/fanfuns/archive/2009/11/26/101984.htmlhttp://www.cppblog.com/fanfuns/comments/101984.htmlhttp://www.cppblog.com/fanfuns/archive/2009/11/26/101984.html#Feedback0http://www.cppblog.com/fanfuns/comments/commentRss/101984.htmlhttp://www.cppblog.com/fanfuns/services/trackbacks/101984.html预备知识
=======

Intel X86 CPU系列的寻址方式
========================

实地址模式
----------------

Intel在8086 CPU中设置了四个“段寄存器”：CS, DS, SS和ES， 分别用于可执行代码，数据，堆栈和其他。每个段寄存器都是16位，对应于地址总线的高16位。这样和某个段寄存器中的内容相加就得到20位实际地址的转化。对于这种类型的断式内存管理，一个进程可以随心所欲的访问从基地址开始的连续的64K字节空间，没有任何的保护机制，所以称这种模式为“实地址模式”。由于缺乏保护机制，所以一个现代的操作系统是无法在此建造起来的。

保护地址模式
-------------------

为了增加保护机制，80386 CPU增设了两个寄存器：GDTR(global descriptor table register)和LDTR(local descritor table register)， 分别可以用来指向内存中的一个段描述结构数组，或者称为段表述表。段描述表的数据结构可以用如下伪代码表述：

typedef struct {
unsigned int base24_31 : 8; /* 基地址最高8位 */
unsigned int g : 1; /* 表段的长度单位，0表示字节， 1表示 */
unsigned int d_b :1; /* 存取方式： 0＝16位， 1＝32位 */
unsigned int unused :1; /* 未使用，设置成0 */
unsigned int avl :1; /* */
unsigned int seg_limit 16_19 :4; /* 段长度的最高4位 */
unsigned int p :1; /* segment present, 为0时表示该段的内容不在内存中 */
unsigned int dpl :2； /* Descriptor privilege level, 访问本段所需权限 */
unsigned int s :1; /* 描述项类型 1表示系统 0表示代码或数据 */
unsigned int type : 4; /* 段的类型 */
unsigned int base_0_23 :24; /* 基地址的低24位 */
unsigned int seg_limmit_0_15: 16; /* 段长度的低16位 */
} 段描述项;

可以看出每个段描述项的大小是8个字节，含有段的基地址和段的大小，再加上一些其他的信息。

16位段寄存器中的高13位用作下标访问段描述表，低3位含有其他信息：

typedef struct {
unsigned short seg_idx : 13; /* 13位的段描述项下标 */
unsigned short ti :1; /* 段描述表指示位， 0表示GDT， 1表示LDT */
unsigned short rpl :2; /* Requested Privilege level, 要求的优先级别 */
} 段寄存器;

页式内存管理机制
--------------------------

在段式内存管理中逻辑地址映射成物理地址，但在页式管理中不再是物理地址，intel称之为线性地址，再通过页式管理转变成实际的物理地址。32位的线性地址的伪代码可以表示如下：

typedef struct {
unsigned short dir :10; /* 用作页面表目录中的下标， 该目录项指向一个页表项 */
unsigned short page :10; /* 用作具体页面表中的下标，该表项指向一个物理页面 */
unsigned short offset :12; /* 在4K字节物理页面内的偏移量 */
} 线性地址;

由于页面表和页面的起始地址总是在4K字节的边界上，这些指针的低12位都永远是0。可以利用这12位控制。目录项的结构的伪代码为：

typedef struct {
unsigned int ptba : 20; /* 页面基地址的高20位 */
unsigned int avail :3; /* 供系统程序员使用 */
unsigned int g :1; /* global,全局性页面 */
unsigned int ps :1; /* 页面大小， 0表示4K字节 */
unsigned int reserved :1; /* 保留， 默认为0*/
unsigned int a :1; /* accessed, 表示已访问过 */
unsigned int pcd; /*关闭缓存存储器 */
unsigned int pwt; /* Write-Through，用于缓冲存储区 */
unsigned int u_s; /* 为0时表示系统权限， 为1时表示用户权限 */
unsigned int r_w : 1; /* 只读或可写 */
unsigned int p :1; /* 为0时表示相应的页面不在内存中 */
} 目录项;

页表项的结构基本和目录项相同。

linux内核源代码的汇编语言代码
-----------------------------------------------
参见：http://asm.sourceforge.net/articles/linasm.html

文章来源:http://fanfuns.blogspot.com/2009/03/learning-kernel.html

Fan Hongwei 2009-11-26 17:15 发表评论
]]>[导入]learning kernel -- 进程管理http://www.cppblog.com/fanfuns/archive/2009/11/26/101983.htmlFan HongweiFan HongweiThu, 26 Nov 2009 09:15:00 GMThttp://www.cppblog.com/fanfuns/archive/2009/11/26/101983.htmlhttp://www.cppblog.com/fanfuns/comments/101983.htmlhttp://www.cppblog.com/fanfuns/archive/2009/11/26/101983.html#Feedback0http://www.cppblog.com/fanfuns/comments/commentRss/101983.htmlhttp://www.cppblog.com/fanfuns/services/trackbacks/101983.htmllearning kernel -- 进程管理
====================================

linux系统的kernel stack和process descriptor
=========================================
系统为每个进程在linux内核中分配一个kernel stack，每个kernel stack的底端（对于向下增长的栈）存放struct thread_info:

struct thread_info {
struct task_struct *task;
struct exec_domain *exec_domain;
unsigned long flags;
unsigned long status;
__u32 cpu;
__s32 preempt_count;
mm_segment_t addr_limit;
struct restart_block restart_block;
unsigned long previous_esp;
__u8 supervisor_stack[0];
};
其中thread_info里的struct task_struct里面保存了运行进程的几乎所有信息。内核提供current宏得到当前运行进程的task_struct的地址。
一个进程的可以具有5种状态：

* TASK_RUNNING: 该进程正在运行或者在runqueue里通过进程调度等待运行
* TASK_INTERRUPTIBLE: 该进程处于睡眠状态，放在waitqueue里面，等待特定的条件来唤醒。当收到信号，它也会被唤醒。唤醒后变成TASK_RUNNING状态。
* TASK_UNINTERRUPTIBLE: 和TASK_INTERRUPTIBLE类似，但不能使用信号唤醒。
* TASK_ZOMBIE: 子进程退出后但父进程还没有使用wait4来获取子进程退出状态，此时子进程处于TASK_ZOMBIE。此时子进程基本上已经释放了内存和打开的文件等，但它对应的kernel stack和task_struct内容还是保存的。这些在父进程调用完wait4后来回收。
* TASK_STOPED

Process and The Linux Implementation of Threads
================================================
Why Copy-on-Write
-----------------
Linux系统运行基本上都是基于进程fork一个子进程方式的，为此如何尽量减少fork的成本是个很重要的问题。本来fork一个子进程要拷贝父进程的kernel stack, task_struct, 父进程的user space的栈空间等，这样的开销是比较大的，尤其对于很多进程，常常fork子进程后马上来一个exec清除这些内容，拷贝的过程完全是浪费的。Copy-on-Write的想法是fork一个子进程后不马上copy那些内容（但kernel stack和task_struct还是省不了的，不过这两个结构不大），而是共享这些资源。只有在需要write修改这些数据时才会标记哪些数据然后copy这些标记的数据。这样就保证了quick process execution。

Process Creation--fork过程
-------------------------
fork调用clone函数， clone再调用do_fork，do_fork做以下事：dup_task_struct, copy_process, get_pid,然后根据copy_process的参数选择到底是copy还是share打开的文件，文件系统信息，信号处理器，进程地址空间等。这些都完了后split父进程的时间片给一部分给子进程。

The Linux Implementation of Threads
-----------------------------------
linux实现线程的方式有些unique，几乎把线程当作进程来处理。配合Copy-on-Write技术，达到了数据的共享，对于每个线程只是copy一份task_struct的结构和kernel stack。

Process Termitation
-------------------
每个进程结束后都会调用exit（编译器会在main函数后默认添加它），它会release该进程占用的空间，files，fs等，set它的exit_code,然后通知父进程自己退出并把自己设置为TASK_ZOMDIE状态。此时kernel stack和task_struct内容还保留，只有父进程调用wait返回后这些资源才开始回收。

文章来源:http://fanfuns.blogspot.com/2009/04/learning-kernel.html

Fan Hongwei 2009-11-26 17:15 发表评论
]]>[导入]learning kernel -- 进程调度http://www.cppblog.com/fanfuns/archive/2009/11/26/101982.htmlFan HongweiFan HongweiThu, 26 Nov 2009 09:15:00 GMThttp://www.cppblog.com/fanfuns/archive/2009/11/26/101982.htmlhttp://www.cppblog.com/fanfuns/comments/101982.htmlhttp://www.cppblog.com/fanfuns/archive/2009/11/26/101982.html#Feedback0http://www.cppblog.com/fanfuns/comments/commentRss/101982.htmlhttp://www.cppblog.com/fanfuns/services/trackbacks/101982.htmllearning kernel -- 进程调度
====================================

linux调度算法
==============

Linux调度特点
--------------------
* Implement fully O(1) scheduling. Every algorithm in the new scheduler completes in constant-time, regardless of the number of running processes.

* Implement perfect SMP scalability. Each processor has its own locking and individual runqueue.

* Implement improved SMP affinity. Attempt to group tasks to a specific CPU and continue to run them there. Only migrate tasks from one CPU to another to resolve imbalances in runqueue sizes.

* Provide good interactive performance. Even during considerable system load, the system should react and schedule interactive tasks immediately.

* Provide fairness. No process should find itself starved of timeslice for any reasonable amount of time. Likewise, no process should receive an unfairly high amount of timeslice.

* Optimize for the common case of only one or two runnable processes, yet scale well to multiple processors, each with many processes.

runqueue结构和O(1) scheduling
--------------------------------------
runqueue的数据结构：
struct runqueue {
spinlock_t lock; /* spin lock that protects this runqueue */
unsigned long nr_running; /* number of runnable tasks */
unsigned long nr_switches; /* context switch count */
unsigned long expired_timestamp; /* time of last array swap */
unsigned long nr_uninterruptible; /* uninterruptible tasks */
unsigned long long timestamp_last_tick; /* last scheduler tick */
struct task_struct *curr; /* currently running task */
struct task_struct *idle; /* this processor's idle task */
struct mm_struct *prev_mm; /* mm_struct of last ran task */
struct prio_array *active; /* active priority array */
struct prio_array *expired; /* the expired priority array */
struct prio_array arrays[2]; /* the actual priority arrays */
struct task_struct *migration_thread; /* migration thread */
struct list_head migration_queue; /* migration queue*/
atomic_t nr_iowait; /* number of tasks waiting on I/O */
};

其中里面active有间接的相关的进程信息,它的数据结构：
struct prio_array {
int nr_active; /* number of tasks in the queues */
unsigned long bitmap[BITMAP_SIZE]; /* priority bitmap */
struct list_head queue[MAX_PRIO]; /* priority queues */
};

Linux就是靠这个实现O(1)算法的，BITMAP_SIZE为5（对于32位机和MAX_PRIO为140的情况），这样就5×32=160位，每一位对应一个priority的任务列，要找出最高priority的任务列，只需要找到第一个为1的位。所以不管进程量有多少，通过这个位就保证了O(1)的算法。
还有一个比较有意思的地方就是存在active和expired两个数据结构。active结构里维护着系统中状态为TASK_RUNNING的进程，然后保证所有这些进程的时间片都用完之后再交给系统重新给每个进程分配时间片。但是一下子给这么多进程重新分配时间片，效率是O(n),还有就是多了你就要考虑锁来锁去，效率更低。linux想了个方法，每当active中一个进程的时间片用完，linux就给他重新分配时间片，然后添加到相应priority的expired结构中。这样当active全部进程的时间片都使用完的时候，只要把active和expired的指针换一下，active结构里又是系统重新分配过时间片的进程。
schedule()是负责从一个进程调度到另一个进程的kernel api

Sleeping and Waking Up
-----------------------
Linux为了使那些IO比较多的进程具有比较好的交互性，选择了给这些进程比较高的priority和比较久的时间片，但是这些进程其实是使用CPU比较少的。当这些进程等待IO的过程中，这些进程暂时就变成TASK_INTERRUPTIBLE(或TASK_UNINTERRUPTIBLE)的状态，处于sleeping中，从runqueue中暂时扔出去加入到waitqueue中，这样下次就不用对这些进程进行调度了。但他们等待到IO结束，它们又从waitqueue中移除加入到runqueue中，由于这些进程的priority比较高，所以马上可以抢占其他进程使自己得到执行，这样就既保证了CPU不浪费，又保证了这些进程的好的交互性。

The Load Balancer
------------------
按照前面所讲，每个CPU都有自己的runqueue，自己调度自己的进程。但是对于多cpu的情况，如果每个cpu上的任务分配不均匀，就会导致cpu利用率低的问题。为此linux还有个loadbalance的策略去平衡每个cpu上的任务数。方法不外乎是把某些具有比较多任务的runqueue元素扔到任务比较少的runqueue里。

文章来源:http://fanfuns.blogspot.com/2009/04/learning-kernel_05.html

Fan Hongwei 2009-11-26 17:15 发表评论
]]>