1.Linux操作系统的简单介绍
Linux系统一般有4个主要部分：内核、shell、文件系统和应用程序。内核、shell和文件系统一起形成了基本的操作系统结构，它们使得用户可以运行程序、管理文件并使用系统。
1.1 内核
内核是系统的核心，是运行程序和管理诸如磁盘和打印机等硬件设备的核心程序。操作系统是一个用来和硬件打交道并为用户程序提供有限服务集的低级支撑软件。一个计算机系统是一个硬件和软件的共生体，它们相互依赖、不可分割。外围设备、处理器、内存、硬盘和其他的电子塞河北组成了计算机的发动机，但是如果没有软件来操作和控制它，硬件自身是不能工作的。完成这个控制工作的软件就称为操作系统。在Linux的术语中“内核”也称为“核心”。
Linux内核的主要模块分以下几个部分：存储管理、CPU和进程管理、文件系统、设备管理和驱动、网络通信，以及系统的初始化（引导）、系统调用等。内核最重要的部分就是内存管理和进程管理。
1.2 Shell
Shell是系统的用户界面，提供了用户与内核进行交互操作的一种接口。它接收用户输入的命令并把它送入内核。不仅如此，Shell有自己的编程语言用于对命令的编辑，它允许用户编写由Shell命令组成的程序。Shell编程语言具有普通编程语言的很多特点，比如它也有循环结构和分支控制结构等，用这种编程语言编写的Shell程序与其他应用程序具有同样的效果。
Shell中命令分为内部命令和外部命令，前者包含在Shell之中，如cd,exit等，查看内部命令可用help命令.后者存于文件系统某个目录下的具体可操作程序，如cp等。查看外部命令的路径可用which
1.3 文件系统
Linux文件系统是文件存放在磁盘等存储设备上的组织方法。Linux能支持多种目前流行的文件系统。如EXT2、EXT3、FAT、VFAT、ISO9660、NFS、SMB等。
文件系统是Linux操作系统的重要组成部分，Linux文件具有强大的功能。文件系统中的文件是数据的集合，文件系统不仅包含着重要组成部分，所有Linux用户和程序看到的文件、目录、软连接及文件保护信息等都存储在其中。一个文件系统的好坏主要体现在对文件和目录的组织上。目录提供了管理文件的一个方便而有效的途径。使用Linux，用户可以设置目录和文件的权限，以便允许或拒绝其他人对其进行访问。Linux目录采用多级树形结构，用户可以浏览整个系统，可以进入任何一个已授权进入的目录，访问那里的文件。文件结构的相互关联性使共享数据变得容易，几个用户可以访问同一个文件。Linux是一个多用户系统，操作系统本身的驻留程序存放在从根目录开始的专用目录中，有时被指定为系统目录。
1.4 应用系统
标准的Linux系统都有一整套称为应用程序的程序集，包括文本编辑器、编程语言、X-Window、办公套件、Internet工具、数据库等。
2.Linux操作系统的进程组织
2.1 什么是进程
进程（Process）是计算机中的程序关于某数据集合上的一次运行活动，是系统进行资源分配和调度的基本单位，是操作系统结构的基础。在早期面向进程设计的计算机结构中，进程是程序的基本执行实体；在当代面向线程设计的计算机结构中，进程是线程的容器。程序是指令、数据及其组织形式的描述，进程是程序的实体；进程是处于执行期的程序以及它所包含的所有资源的总称，包括虚拟处理器，虚拟空间，寄存器，堆栈，全局数据段等。
在Linux中，每个进程在创建时都会被分配一个数据结构，称为进程控制（Process Control Block，简称PCB）。PCB中包含了很多重要的信息，供系统调度和进程本身执行使用。所有进程的PCB都存放在内核空间中。PCB中最重要的信息就是进程PID，内核通过这个PID来唯一标识一个进程。PID可以循环使用，最大值是32768。init进程的pid为1，其他进程都是init进程的后代。
除了进程控制块（PCB）以外，每个进程都有独立的内核堆栈（8k），一个进程描述符结构，这些数据都作为进程的控制信息储存在内核空间中；而进程的用户空间主要存储代码和数据。
2.2 进程的组织
2.2.1 从task_struct开始学习linux内核
一. 数据结构
进程控制块PCB（Process Control Block）是进程存在和运行的唯一标志，在Linux中用task_struct这个结构体来表示。这个结构体中有很多数据项，查看源代码时没必要理解全部的数据项，只需要在以后使用时再理解。
1 struct task_struct 2 { 3 .... 4 };
下面重点介绍几个基本的数据项：
1. 进程状态
task_struct中用一个长整形state表示进程的状态。
1 volatile long state；
2. 进程标识符
linux用一个32位无符号整形pid来简单的标识一个进程，用uid和gid分别来标识进程所属的用户和组。
1 pid_t pid; 2 uid_t uid; 3 gid_t gid;
pid的上限是由pid_max决定的。编译内核时会让选择0x1000和0x8000两种数值，即pid_max=4096和pid_max=32768两种。
3. 亲属关系
1 struct list_head children; //子进程链表 2 struct list_head sibling; //兄弟进程链表 3 struct task_struct *real_parent; //真正创建当前进程的进程 4 struct task_struct *parent; //养父进程
二. 进程控制块的存放
1.内核栈
当进程从用户态进入内核态时要使用位于内核数据段上的内核栈。
2.数据结构
1 union thread_union 2 { 3 struct thread_info thread_info; 4 unsigned long stack[THERAD_SIZE/sizeof(long)];//内核栈，一般为8KB 5 };
内核中将task_struct的指针放在thread_info结构体中，而这个结构体又与内核栈一块被放在8KB的内核空间thread_union中。
1 struct thread_info{ 2 struct task_struct *task; 3 struct exec_domain *exec_domain; 4 ..... 5 };
2.2.2 linux的进程组织方式
一. 进程链表
每个task_struct中都有一个tasks的域来连接到进程链表上去。
1 struct task_struct{ 2 ... 3 struct list_head tasks; 4 ... 5 char comm[TASK_COMM_LEN];//可执行程序名 6 ... 7 };
而这个链表的头是init_task.它是0号进程的PCB，0号进程永远不会被撤销，它被静态的分配到内核数据段上。也就是Init_task的PCB是由编译器预先分配的，在程序运行的过程中一直存在，直到程序结束。
1 struct task_struct init_task = INIT_TASK(init_task);
可以编写以下内核模块，得到所有进程的pid和进程名，并统计出进程总数。
1 #include<linux/kernel.h> 2 #include<linux/init.h> 3 #include<linux/module.h> 4 #include<linux/sched.h> 5 6 MODULE_LICENSE("GPL"); 7 8 static int __init print_pid_init(void) 9 { 10 struct task_struct *task,*p; 11 struct list_head *pos; 12 int count = 0; 13 printk("Begin to print process :\n"); 14 task = &init_task; 15 list_for_each(pos,&task->tasks) 16 { 17 p = list_entry(pos,struct task_struct,tasks); 18 count++; 19 printk("%d ======> %s\n",p->pid,p->comm); 20 } 21 printk("the number of process is %d\n",count); 22 return 0; 23 } 24 static void __exit print_pid_exit(void) 25 { 26 printk("End to print process.\n"); 27 } 28 module_init(print_pid_init); 29 module_exit(print_pid_exit);
二. 哈希表
由于进程链表是将所有的进程连接到一个链表上去，所以查找一个进程的时间复杂度是O（N），是相当的低效。为此，使用哈希表来提高查找的效率。
1. 哈希表的定义
1 static struct hlist_head *pid_hash;
2.哈希函数
学过数据结构的应该知道，哈希函数对整个查找是至关重要的，它决定了发生冲突的概率。好的哈希函数能够得到减少冲突。
1 #define pid_hashfn(nr, ns) \ 2 hash_long((unsigned long)nr + (unsigned long)ns, pidhash_shift)
1 #define hash_long(val, bits) hash_32(val, bits)
1 static inline u32 hash_32(u32 val, unsigned int bits) 2 { 3 /* On some cpus multiply is faster, on others gcc will do shifts */ 4 u32 hash = val * GOLDEN_RATIO_PRIME_32; 5 6 /* High bits are more random, so use them. */ 7 return hash >> (32 - bits); 8 }
1 /* 2^31 + 2^29 - 2^25 + 2^22 - 2^19 - 2^16 + 1 */ 2 #define GOLDEN_RATIO_PRIME_32 0x9e370001UL
3. 通过pid查找task_struct
内核并不能直接通过pid找到对应的task_struct，而是先通过pid找到对应的struct pid,在通过struct pid 找到对应的task_struct。
下面是详细介绍这两个的链接：
ii.struct pid 到task_struct的内核函数详解
三. 就绪队列
与进程链表类似，task_struct也定义了一个连接到就绪队列的域run_list。
1 struct sched_rt_entity { 2 struct list_head run_list; 3 .... 4 }; 5 struct task_struct 6 { 7 .... 8 struct sched_rt_entity rt; 9 ...... 10 };
就绪队列头：
同样，内核中有一个就绪队列头runqueue_head。
四. 等待队列
1. 等待队列的数据结构
1 typedef struct __wait_queue wait_queue_t; 2 struct __wait_queue { 3 unsigned int flags; 4 #define WQ_FLAG_EXCLUSIVE 0x01 5 void *private; 6 wait_queue_func_t func; 7 struct list_head task_list; 8 };
task_list链接到等待队列上去。
func是一个函数指针，指向唤醒等待队列中进程的函数。prviate是传递给func的参数，用于指定所要唤醒的进程。
1 typedef int (*wait_queue_func_t)(wait_queue_t *wait, unsigned mode, int flags, void *key);
flags标志进程是否互斥：flags为WQ_FLAG_EXCLUSIVE 时互斥，否则，非互斥。
2. 等待队列头
1 struct __wait_queue_head { 2 spinlock_t lock; 3 struct list_head task_list; 4 }; 5 typedef struct __wait_queue_head wait_queue_head_t;
因为等待队列是由中断处理程序和主要的内核函数修改的，因此要避免被同时访问。lock自旋锁对其进行同步，避免了双向链表被同时访问。task_list是双向链表的节点。
3. 等待队列的操作
i. 初始化
首先，使用了下面的宏声明并初始化了一个等待队列头。
1 #define __WAIT_QUEUE_HEAD_INITIALIZER(name) { \ 2 .lock = __SPIN_LOCK_UNLOCKED(name.lock), \ 3 .task_list = { &(name).task_list, &(name).task_list } } 4 5 #define DECLARE_WAIT_QUEUE_HEAD(name) \ 6 wait_queue_head_t name = __WAIT_QUEUE_HEAD_INITIALIZER(name)
如果要对列中一个元素初始化，要使用这个函数：
1 static inline void init_waitqueue_entry(wait_queue_t *q, struct task_struct *p) 2 { 3 q->flags = 0; 4 q->private = p; 5 q->func = default_wake_function;//default_wake_function能够唤醒睡眠的进程p，并将其从等待队列中删除。 6 }
ii.插入/删除
add_wait_queue()将一个非互斥进程插入到等待队列的第一个位置。
1 void add_wait_queue(wait_queue_head_t *q, wait_queue_t *wait) 2 { 3 unsigned long flags; 4 5 wait->flags &= ~WQ_FLAG_EXCLUSIVE; 6 spin_lock_irqsave(&q->lock, flags); 7 __add_wait_queue(q, wait); 8 spin_unlock_irqrestore(&q->lock, flags); 9 }
add_wait_queue_exclusive()将一个互斥进程插入到等待队列的最后一个位置 。
1 void add_wait_queue_exclusive(wait_queue_head_t *q, wait_queue_t *wait) 2 { 3 unsigned long flags; 4 5 wait->flags |= WQ_FLAG_EXCLUSIVE; 6 spin_lock_irqsave(&q->lock, flags); 7 __add_wait_queue_tail(q, wait); 8 spin_unlock_irqrestore(&q->lock, flags); 9 }
之所以将非互斥进程放在队首，而将互斥进程放在队尾，大概是因为非互斥进程不需要临界资源，将它唤醒不会影响其它进程的执行，而互斥进程得到临界资源会导致别的进程无法执行。
remove_wait_queue()将一个进程从等待队列中删除。
1 void remove_wait_queue(wait_queue_head_t *q, wait_queue_t *wait) 2 { 3 unsigned long flags; 4 5 spin_lock_irqsave(&q->lock, flags); 6 __remove_wait_queue(q, wait); 7 spin_unlock_irqrestore(&q->lock, flags); 8 }
iii.检查是否为空队列,直接调用了list.h中的list_empty()
1 static inline int waitqueue_active(wait_queue_head_t *q) 2 { 3 return !list_empty(&q->task_list); 4 }
iv.睡眠
1 sleep_on_common(wait_queue_head_t *q, int state, long timeout) 2 { 3 unsigned long flags; 4 wait_queue_t wait; 5 6 init_waitqueue_entry(&wait, current); 7 8 __set_current_state(state); 9 10 spin_lock_irqsave(&q->lock, flags); 11 __add_wait_queue(q, &wait); 12 spin_unlock(&q->lock); 13 timeout = schedule_timeout(timeout); 14 spin_lock_irq(&q->lock); 15 __remove_wait_queue(q, &wait); 16 spin_unlock_irqrestore(&q->lock, flags); 17 18 return timeout; 19 }
v.唤醒
1 static void __wake_up_common(wait_queue_head_t *q, unsigned int mode, 2 int nr_exclusive, int wake_flags, void *key) 3 { 4 wait_queue_t *curr, *next; 5 6 list_for_each_entry_safe(curr, next, &q->task_list, task_list) { 7 unsigned flags = curr->flags; 8 9 if (curr->func(curr, mode, wake_flags, key) && 10 (flags & WQ_FLAG_EXCLUSIVE) && !--nr_exclusive) 11 break; 12 } 13 }
3.Linux操作系统的进程控制
3.1进程的各个状态
为了更好地理解进程控制，我们需要知道进程状态这个概念。和其他普通事物一样，进程始终处于一系列的状态中，比如我们至少可以想象出“运行”，“休眠”之类的。
TASK_RUNNING：
可执行状态。这是 “进程正在被CPU执行” 和 “进程正在可执行队列中等待被CPU执行” 统称。也可以将它们拆开成“RUNNING”和“READY”两种状态。
TASK_INTERRUPTIBLE 和 TASK_UNINTERRUPTIBLE：
可中断的睡眠状态 和 不可中断的睡眠状态。处于睡眠状态的进程不会被调度到CPU进行执行，而是否可中断的意思是指进程是否会响应异步信号，如果是可中断的，当进程收到某个信号时其会重新回到TASK_RUNNING状态。值得注意的是，如果处于不可中断的睡眠状态时，进程将不响应异步信号，比如你无法“kill -9”。
TASK_STOPPED：
暂停状态。这里的STOPPED是指停止运行（暂停），而不是进程终止。向进程发送SIGSTOP信号可以让进程暂停下来，相反，发送SIGCONT可以将其从TASK_STOPPED状态唤醒而重新进入TASK_RUNNING状态。
TASK_TRACED：
被跟踪状态。一个进程被另一个进程“TRACE（跟踪）"最经典的例子是DEBUG，比如使用gdb或任何一款ide的debug功能。TASK_TRACED和TASK_STOPPED非常相近，都是让进程暂停下来，区别是不能通过向TASK_TRACED的进程发送SIGCONT信号让其恢复，只能由跟踪该进程的那个进程发送PTRACE_CONT,PTRACE_DETACH等，也就是说得让跟踪进程来决定是否挂起或继续被跟踪进程，当然，跟踪进程如果退出的话，被跟踪进程也会重新回到TASK_RUNNING状态。
TASK_DEAD：
僵尸状态。很搞笑的名字，之所以是“僵尸”而不是“死亡”是因为进程已不响应任何信号以及大部分相关数据已被清除，但其TASK_STRUCT结构仍存在，这个结构相当于进程的“躯壳”，还保留着一些信息，父进程可以利用这些信息得到进程终止前的一些状态。如果你看到某些文档上描写的ZOMBIE也是指的这个状态。
下图描述了进程各个状态之间的相互转化：
3.2 退出/终止进程
void _exit(int status) 与 void exit(int status)
这两个函数都是让进程退出， 参数status表示进程将以何种状态退出，在<stdlib.h>中预定义了一些状态，比如EXIT_SUCCESS(值为0)表示以成功状态退出，EXIT_FAILURE(值为1)表示以失败状态退出。
调用_exit函数时，其会关闭进程所有的文件描述符，清理内存以及其他一些内核清理函数，但不会刷新流(stdin, stdout, stderr ...). exit函数时在_exit函数之上的一个封装，其会调用_exit，并在调用之前先刷新流。
参考下面这段代码：
1 #include <stdio.h> //for printf(const char *) 2 #include <unistd.h> //for fork() 3 #include <sys/wait.h> //for wait(int *) 4 #include <stdlib.h> //for EXIT_SUCCESS 5 6 7 int main () 8 { 9 printf("app start...\n"); 10 11 if(fork() == 0) 12 { 13 printf("do something in child process ...\n"); 14 15 exit(EXIT_SUCCESS); 16 17 printf("this will not been executed\n"); 18 } 19 20 int status; 21 wait(&status); 22 23 printf("app end\n"); 24 25 return 0; 26 }
上面的代码无论时用exit还是_exit输出结果都如下：
1 app start... 2 do something in child process ... 3 app end
这是因为stdout缓冲区是按行缓冲的，当遇到换行符时会刷新当前缓冲区，所以当进程退出前即便_exit不刷新，"do somethign in child process "这句话仍然被输出到了屏幕上。
现在我们将使用不带换行符的printf, 并且也不调用fflush之类的函数，在使用_exit试试：
1 #include <stdio.h> //for printf(const char *) 2 #include <unistd.h> //for fork() 3 #include <sys/wait.h> //for wait(int *) 4 #include <stdlib.h> //for EXIT_SUCCESS 5 6 7 int main () 8 { 9 printf("app start...\n"); 10 11 if(fork() == 0) 12 { 13 printf("do something in child process ..."); 14 15 _exit(EXIT_SUCCESS); 16 17 printf("this will not been executed\n"); 18 } 19 20 int status; 21 wait(&status); 22 23 printf("app end\n"); 24 25 return 0; 26 }
输出结果为：
1 app start... 2 app end
如果换成exit则输出结果为：
1 app start... 2 do something in child process ...app end
void abort ()
非正常地退出进程。其会产生一个SIGABORT信号(关于信号，会在下一篇“进程间通信”介绍)，然后使进程戛然而止，也就意外着其不会进行清理工作, 但它会刷新缓冲区。
1 #include <stdio.h> //for printf() 2 #include <unistd.h> //for fork() 3 #include <sys/wait.h> //for wait() 4 #include <stdlib.h> //for EXIT_SUCCESS 5 6 int main () 7 { 8 printf("app start...\n"); 9 10 if(fork() == 0) 11 { 12 printf("do something in child process ..."); 13 14 abort(); 15 16 printf("this will not been executed\n"); 17 } 18 19 int status; 20 wait(&status); 21 22 printf("app end\n"); 23 24 return 0; 25 }
输出为：
1 app start... 2 do something in child process ...app end
void atexit( void (*f) () )
如果想在进程正常结束之前干一点自定义的事情，就可以调用这个函数. 其简单地利用你传入的函数指针执行一个函数回调。
值得注意的是：其仅仅在调用exit函数结束进程或进程执行完所有代码后自然结束这两种状态下，回调函数才会被执行，也就是说如果进程是被_exit或abort结束的，则atexit函数无效。
1 #include <stdio.h> //for printf() 2 #include <unistd.h> //for fork() 3 #include <sys/wait.h> //for wait() 4 #include <stdlib.h> //for EXIT_SUCCESS 5 6 void before_exit() 7 { 8 printf("1,2,3 exit!\n"); 9 } 10 11 int main () 12 { 13 printf("app start...\n"); 14 15 if(fork() == 0) 16 { 17 printf("do something in child process ...\n"); 18 19 void (*f)() = before_exit; 20 atexit(f); 21 22 exit(EXIT_SUCCESS); 23 24 printf("this will not been executed\n"); 25 } 26 27 int status; 28 wait(&status); 29 30 printf("app end\n"); 31 32 return 0; 33 }
输出为：
1 app start... 2 do something in child process ... 3 1,2,3 exit! 4 app end
3.3暂停进程
int pause()
暂停进程，可以使用pause函数，其会挂起当前进程直到有信号来唤醒或者进程被结束。
随便提一下，如果你仅仅需要简单地暂停一下（press any key to continue...）, 可以使用 system("pause")这个系统调用，甚至是getch()之类的。
关于pause这个函数的Demo和更详细的理解，由于其会涉及到比较多与“信号”相关的知识，所以我打算放到下一篇“进程间通信”来讲
unsigned sleep(unsigned seconds)
int usleep(useconds_t useconds)
int nanosleep(const struct timespec *rqtp, struct timespec *rmtp)
sleep系列函数都是让进程挂起一段时间，sleep只能精确到秒，usleep能精确到微妙，而nanosleep传说精度更高。
3.4 进程跟踪
long ptrace(/*some args*/)
要像debug程序一样去跟踪进程，是一个比较复杂的问题。
3.5 waitpid 与 wait（等待子进程结束）
大家经常看到的关于waitpid的经典例子是：你下载了某个软件的安装程序A，其在安装即将结束时启动了另外一个流氓软件的安装程序B，当B也安装结束后，其告诉你所有安装成功了。A和B分别在不同的进程中，A如何启动B并知道B安装完成了呢？可以很简单地在A中用fork启动B，然后用waitpid(或wait)来等待B的结束。
pid_t waitpid(pid_t pid, int *stat_loc, int options);
参数pid：
如果大于0，表示父进程所需要等待的子进程的进程号
如果等于0，则表示任意任意group id和父进程相同的子进程
如果等于-1, 则表示等待任意子进程（有多个子进程时，任意进程结束，函数都会返回），此时waitpid和wait相同。
如果小于－1，则取其绝对值作为需要等待的子进程的进程号
参数stat_loc:
表示进程退出时进程状态的存储位置，有一些专门的宏类根据该位置计算状态值，可以参考这里。
参数options:
这个参数控制函数是否立即返回，它有三个值：0，WNOHANG（值为1），WUNTRACED（值为2），这三个值多少让有有些迷惑，有个帖子中是如此说的：options的各个常量不是互斥关系，而是通过按位或运算组合起来的关系。进程的状态数是有限的，所有的进程状态改变可能性，是一个元素个数有限的集合，waitpid中指定的子进程的状态改变，必然是这个集合的子集，记为A。options决定如何取A中的元素，默认时(0)，只有A不是空集的时候，才会返回，否则阻塞。WNOHANG 告诉waitpid，即使A是空集，也不会挂起，而是立即返回。WUNTRACED 告诉waitpid，如果A中含有进程STOPED状态，也立即返回。如果是被trace的子进程，那么即使不提供WUNTRACED参数，也会理解返回。
另外，关于waitpid和wait的关系： wait(&status) 等于 waitpid(-1, &status, 0)
1 #include <stdio.h> //for printf() 2 #include <unistd.h> //for fork() 3 #include <sys/wait.h> //for wait() 4 #include <stdlib.h> //for EXIT_SUCCESS 5 6 7 int main () 8 { 9 printf("app start...\n"); 10 11 printf("do something in main process\n"); 12 13 sleep(5); 14 15 if(fork() == 0) 16 { 17 printf("do something in child process ...\n"); 18 19 sleep(5); 20 21 exit(EXIT_SUCCESS); 22 23 printf("this will not been executed\n"); 24 } 25 26 int status; 27 wait(&status); 28 29 printf("app end\n"); 30 31 return 0; 32 }
wait的另外一个用途是替子进程“收尸”，这有点难听，但是一个恰当的比喻。我们知道，当进程结束后，进程的大部分资源会被回收，比如释放内存，关闭描述符等，但表示进程的那个结构体STRUCT_TASK却还存在，此时的进程相当于“灵魂已亡，尸体犹在”，所以称之为ZOMBIE状态，这个结构体存在是有它的意义的，因为进程在退出前会讲一些信息保存在其中，父进程可以在wait或waitpid中得到这个结构体并取得相关信息，最后在讲结构体销毁，子进程彻底地消失了。 关于僵尸进程，更多地可以看这里。
4.Linux操作系统的进程调度
4.1 调度基础
很多书中将进程分为CPU密集型和I/O密集型，另外还有一种分法：
- 交互式进程
这些进程与用户进行交互，因此会花很多时间等待鼠标键盘的输入，当接受输入之后，必须很快得到相应，否则系统会显得很迟钝。 - 批处理进程
不必与用户交互，常运行于后台。 - 实时进程
典型的是视频音频应用程序、机器人控制程序等，这些进程有很强的调度需要，不应该被低优先级的进程阻塞，应该有很短的响应时间。
Linux中调度算法可以明确所有实时程序的身份，但没法区分交互式程序和批处理程序。Linux实现了基于进程过去行为的启发式算法以确定进程应被当作交互式进程还是批处理进程，相比批处理进程，调度程序偏爱调度交互式进程。
Linux2.6实现了一个O(1)的调度程序，本博文主要就是要介绍这个算法，Linux将进程分为下面三种：
- SCHED_FIFO
先进先出的实时进程，如果没有其他更高优先级的实时进程，进程可以继续使用CPU，想用多久用多久。 - SCHED_RR
时间片轮转的实时进程。 - SCHED_NORMAL
普通的分时进程。
不同的进程对应的调度算法有很大的区别。
4.2 普通进程的调度
每个普通进程都有自己的静态优先级，内核用从100（最高优先级）到139（最低优先级）的数来表示普通进程的静态优先级。新进程总是继承父进程的静态优先级，用户可以改变自己拥有进程的静态优先级，通过nice()和setpriority()。
静态优先级的本质上决定了进程的基本时间片，静态优先级和基本时间片的关系用下面的公式确定：
基本时间片(ms) = (140 – 静态优先级) X 20 若静态优先级<120
基本时间片(ms) = (140 – 静态优先级) X 5 若静态优先级>=120
普通进程除了静态优先级还有动态优先级，其值范围是100~139，动态优先级是调度程序在选择新进程来运行时使用的数，它与静态优先级的关系如下：
动态优先级=max(100, min(静态优先级 – bonus + 5, 139))
bonus是范围从0~10的值，值小于5表示降低优先级以示惩罚，值大于5表示增加优先级以示奖赏。bonus的值依赖于进程的平均睡眠时间。
Linux使用平均睡眠时间来确定进程时交互式进程还是批处理进程，如果满足下面的公式则被看做是交互式进程，否则为批处理进程。
动态优先级<= 3 X 静态优先级 / 4 + 28
即 bonus – 5 >= 静态优先级/4 – 28
另外，表达式 静态优先级/4 – 28 被称为交互式的δ。基本上可以理解成将睡眠时间较长的进程可以看做交互式进程（因为一直在等待I/O）。
为了使低优先级的进程也能够被CPU调度，以免总被高优先级的进程饿死，当一个进程用完它的时间片后，应该被还没用完时间片的低优先级进程取代，为了实现这这种机制，调度程序维护两个不想交的可运行进程的集合。
- 活动进程
这些进程的时间片还没用完，因此允许运行。 - 过期进程
这些可运行进程的时间片已经用完，因此被禁止运行，直到所有活动进程都过期。
不过因为调度程序试图提升交互式进程（并不一定是优先级高，而是睡眠时间相对较多的进程）的性能，用完其时间片的活动批处理进程进入过期进程，而交互式进程仍然是活动进程，调度程序会重新装填它的时间片。但是如果最老的过期进程已经等待了很长的时间，或者过期进程中比交互式进程的静态优先级高，调度程序就把用完时间片的交互式进程移到过期进程集合中。最终活动进程变为空，过期进程将有机会运行。
4.3 实时进程的调度
每个实时进程都与一个实时优先级相关，实时优先级是一个范围从1（最高优先级）到99（最低优先级）的值。调度程序总是让优先级高的进程运行，与普通进程不同，实时进程总是被当做活动进程（不考虑低优先级的进程饥饿问题）。只有发生下面是事件之一时实时进程才会被另一个进程取代：
- 进程被另一个具有更高实时优先级的实时进程取代。
- 进程执行了阻塞操作并进入了睡眠。
- 进程停止或被杀死。
- 进城通过系统调用sched_yield()自愿放弃CPU。
- 进程时基于时间片轮转的实时进程（SCHED_RR），且用完了时间片。
基于时间片轮转的实时进程的时间片长度与实时进程的优先级无关，只与进程的静态优先级有关，关系见4.2的公式。
4.4 调度程序分析
既然是从源码深入了解调度程序，那一定要从数据结构开始分析，然后再看Linux如何实现/优化调度。
4.4.1 调度程序相关数据结构
运行队列runqueue
runqueue是2.6调度最重要的数据结构，系统中每个CPU拥有自己的运行队列，定义如下：
1 struct runqueue { 2 spinlock_t lock; 3 4 /* 5 * nr_running and cpu_load should be in the same cacheline because 6 * remote CPUs use both these fields when doing load calculation. 7 */ 8 unsigned long nr_running; 9 unsigned long cpu_load; 10 unsigned long long nr_switches; 11 12 /* 13 * This is part of a global counter where only the total sum 14 * over all CPUs matters. A task can increase this counter on 15 * one CPU and if it got migrated afterwards it may decrease 16 * it on another CPU. Always updated under the runqueue lock: 17 */ 18 unsigned long nr_uninterruptible; 19 20 unsigned long expired_timestamp; 21 unsigned long long timestamp_last_tick; 22 task_t *curr, *idle; 23 struct mm_struct *prev_mm; 24 prio_array_t *active, *expired, arrays[2]; 25 int best_expired_prio; 26 atomic_t nr_iowait; 27 28 struct sched_domain *sd; 29 30 /* For active balancing */ 31 int active_balance; 32 int push_cpu; 33 34 task_t *migration_thread; 35 struct list_head migration_queue; 36 };
系统中每个可运行进程属于且只属于一个运行队列，所以每个进程只能运行在拥有该运行队列的CPU上，但是linux可以将进程从一个运行队列迁移到另一个运行队列。
简单解释一下每个字段：
- lock就是运行队列锁，因为其他CPU也会将进程插入到本CPU的运行队列中，所以虽然是CPU私有队列也需要锁保护。
- nr_running是运行队列中可运行的进程数。
- cpu_load是基于运行队列中进程的平均数量的CPU负载因子。
- nr_switches是CPU进程切换的次数。
- nr_uninterruptible表示先前在运行队列链表中而现在睡眠在TASK_UNINTERRUPTIBLE状态的进程数。
- expired_timestamp过期队列中最老的进程被插入队列的时间。
- timestamp_last_tick最近一次定时器中断的时间戳的值。
- curr当前正在运行的进程描述符。
- idle当前CPU上swapper进程描述符指针。
- prev_mm在进程切换期间用来保存被替换进程内存描述符的地址。
- active指向活动进程链表的指针
- expired指向过期进程链表的指针
- arrays活动进程和过期进程的两个集合
- best_expired_prio过期进程中静态优先级最高的进程
- nr_iowait先前在运行队列中而现在在等待I/O操作结束的进程数量。
- sd指向当前CPU的基本调度域。
- active_balance如果要把一些进程从本地运行队列迁移到另外的运行队列，就设置这个标志。
- 未使用push_cpu字段。
- migration_thread迁移内核线程的进程描述符指针。
- migration_queue从运行队列中被删除的进程的列表。
稍微解释一下活动进程和过期进程的设计，arrays声明了一个prio_array_t结构数组，active指向其中一个作为运行进程队列链表，expired就指向另一个作为过期进程队列链表，如此反复切换只有修改指针值的开销，拥有很高的效率。
运行队列链表prio_array_t
1 struct prio_array { 2 unsigned int nr_active; 3 unsigned long bitmap[BITMAP_SIZE]; 4 struct list_head queue[MAX_PRIO]; 5 }; 6 typedef struct prio_array prio_array_t; 7 8 /* 进程描述符中的prio_array_t */ 9 struct task_t{ 10 .... 11 prio_array_t *array; 12 .... 13 };
- nr_active表示队列中的进程数。
- 因为Linux有0~139（140个）种优先级，因此queue拥有140个链表，每个链表对应一个优先级。
- bitmap用位来表示各个优先级的链表是否有元素。
进程描述符task_t
这个结构包含了进城相关的所有数据结构，去掉一些调试用的仍然有一百多项，因此只说明和调度程序有关的一些字段。
1 struct task_struct { 2 volatile long state; /* -1 unrunnable, 0 runnable, >0 stopped */ 3 struct thread_info *thread_info; 4 int prio, static_prio; 5 struct list_head run_list; 6 prio_array_t *array; 7 unsigned long sleep_avg; 8 unsigned long long timestamp, last_ran; 9 int activated; 10 unsigned long policy; 11 cpumask_t cpus_allowed; 12 unsigned int time_slice, first_time_slice; 13 unsigned long rt_priority; 14 ...... 15 }; 16 typedef struct task_struct task_t;
挑一些和调度相关的字段注释一下：
- state包含进程的当前状态。
- thread_info是存放在内核态栈的底端的数据结构对应的指针，thread_info->flags存放TIF_NEED_RESCHED标志，表示必须调用调度程序。thread_info->cpu表示可运行进程所在队列的CPU逻辑号。
- prio是进程的动态优先级。
- static_prio是进程的静态优先级。
- run_list指向进程所属的运行队列（对应的优先级）中的下一个和上一个元素。
- array指向包含进程的运行队列集合。
- sleep_avg是进程的平均睡眠时间。
- timestamp是进程最近插入运行队列的时间，或涉及本进程最后一次进程切换的时间。
- last_ran最近一次替换本进程的进程切换时间。
- activated进程被唤醒时所使用的条件代码：
0表示处于TASK_RUNNING状态；
1表示TASK_INTERRUPTBLE或TASK_STOP状态，并正在被系统调用或内核线程唤醒；
2表示TASK_INTERRUPTBLE或TASK_STOP状态，并且正在被中断处理程序或可延迟函数唤醒；
-1表示TASK_UNINTERRUPTIBLE状态并且正在被唤醒； - policy进程的调度类型（SCHED_NORMAL, SCHED_RR或SCHED_FIFO）
- cpus_allowed能执行进程的CPU位掩码。
- first_time_slice第一个时间片标志，在创建新进程时总会置1。
- rt_priority进程的实时优先级。
4.4.2 调度程序使用的方法
- scheduler_tick()
维持当前最新的time_slice计数器 - try_to_wake_up()
唤醒睡眠进程 - recalc_task_prio()
更新进程的动态优先级 - schedule()
选择要被执行的新进程 - load_balance()
维持多处理器系统中运行队列的平衡（下一节）
scheduler_tick()函数
在每次硬件时钟节拍到来时，中断处理函数中会调用本函数，本函数更新当前进程的时间片，如果需要重新调度会设置标志位，函数如下（注释直接放在代码中）
1 void scheduler_tick(void) 2 { 3 /* 获得CPU编号 */ 4 int cpu = smp_processor_id(); 5 /* 获得当前CPU的运行队列 */ 6 runqueue_t *rq = this_rq(); 7 /* 获得当前正在运行的进程 */ 8 task_t *p = current; 9 10 /* sched_clock()返回被转化为纳秒的64寄存器TSC 11 * 更新timestampt_last_tick，此字段即为最后一次定时器中断的时间戳 12 */ 13 rq->timestamp_last_tick = sched_clock(); 14 15 /* 如果当前进程是当前CPU的swapper进程 */ 16 if (p == rq->idle) { 17 /* 18 * 如果有其他进程，则设置TIF_NEED_RESCHED字段 19 * 如果没有待运行进程，标志为空闲状态退出 20 */ 21 if (wake_priority_sleeper(rq)) 22 goto out; 23 /* 这个函数在后面介绍，维持多处理器中运行队列的平衡 */ 24 rebalance_tick(cpu, rq, SCHED_IDLE); 25 return; 26 } 27 28 /* 29 * 如果当前进程所在运行队列链表(prio_array_t类型)不等于运行队列的运行队列， 30 * 则说明当前进程应该停止运行，强制重新调度。 31 */ 32 if (p->array != rq->active) { 33 set_tsk_need_resched(p); 34 goto out; 35 } 36 spin_lock(&rq->lock); 37 38 /* 是否为实时进程 */ 39 if (rt_task(p)) { 40 /* 如果时间片轮转实时进程时间片用完 */ 41 if ((p->policy == SCHED_RR) && !--p->time_slice) { 42 /* 使用前面的公式计算时间片长度 */ 43 p->time_slice = task_timeslice(p); 44 /* 时间片用完，将标志位去除 */ 45 p->first_time_slice = 0; 46 /* 设置TIF_NEED_RESCHED标志 */ 47 set_tsk_need_resched(p); 48 49 /* 将进程加入活动进程队列队尾，使其他同优先级的实时进程得以运行 */ 50 requeue_task(p, rq->active); 51 } 52 goto out_unlock; 53 } 54 /* 普通进程执行 */ 55 if (!--p->time_slice) { 56 /* 如果时间片用完，则将进程从活动进程队列中移除 */ 57 dequeue_task(p, rq->active); 58 /* 设置需要重新调度 */ 59 set_tsk_need_resched(p); 60 /* 重新计算动态优先级 */ 61 p->prio = effective_prio(p); 62 /* 重新分配时间片 */ 63 p->time_slice = task_timeslice(p); 64 /* 将第一次时间片标志位置0 */ 65 p->first_time_slice = 0; 66 67 /* 如果过期进程队列为空，则将最老被插入的进程的插入时间更新 */ 68 if (!rq->expired_timestamp) 69 rq->expired_timestamp = jiffies; 70 /* 71 * 将当前进程插入活动进程或者过期进程， 72 * TASK_INTERACTIVE判断是否是交互式进程， 73 * EXPIRED_STARVING判断过期进程是否等待太久或者有优先级更高的进程 74 * 75 * 那么这个判断就是如果当前进程是批处理进程或者过期进程已经等待太长时间 76 * 或者等待进程中有优先级更高的进程时， 77 * 将当前进程加入过期进程； 78 * 否则将当前进程重新加入活动进程 */ 79 if (!TASK_INTERACTIVE(p) || EXPIRED_STARVING(rq)) { 80 /* 插入过期进程 */ 81 enqueue_task(p, rq->expired); 82 /* 更新过期进程的最高优先级 */ 83 if (p->static_prio < rq->best_expired_prio) 84 rq->best_expired_prio = p->static_prio; 85 } else 86 /* 插入活动进程 */ 87 enqueue_task(p, rq->active); 88 } else { 89 /* 时间片未用完，检查剩余时间片是否过长，如果是则将当前进程置到队列队尾， 90 * 然后设置重新调度标志位。 */ 91 if (TASK_INTERACTIVE(p) && !((task_timeslice(p) - 92 p->time_slice) % TIMESLICE_GRANULARITY(p)) && 93 (p->time_slice >= TIMESLICE_GRANULARITY(p)) && 94 (p->array == rq->active)) { 95 96 requeue_task(p, rq->active); 97 set_tsk_need_resched(p); 98 } 99 } 100 out_unlock: 101 spin_unlock(&rq->lock); 102 out: 103 rebalance_tick(cpu, rq, NOT_IDLE); 104 }
try_to_wake_up()函数
将进程设置为TASK_RUNNING，并把进程插入某个CPU的运行队列来唤醒睡眠或停止的进程，代码和注释如下。
1 /*** 2 * try_to_wake_up - 唤醒一个进程 3 * @p: 带唤醒进程 4 * @state: 可以被唤醒的进程状态 5 * @sync: 同步唤醒标志 6 * 7 * 如果进程已经是激活状态则返回0 8 */ 9 static int try_to_wake_up(task_t * p, unsigned int state, int sync) 10 { 11 int cpu, this_cpu, success = 0; 12 unsigned long flags; 13 long old_state; 14 runqueue_t *rq; 15 unsigned long load, this_load; 16 struct sched_domain *sd; 17 int new_cpu; 18 19 /* task_rq_lock函数会禁用本地中断， 20 * 并根据进程最后在哪个CPU上运行，获取该CPU运行队列 */ 21 rq = task_rq_lock(p, &flags); 22 /* 保存进程旧状态 */ 23 old_state = p->state; 24 /* 如果旧状态不属于允许唤醒进程的状态掩码，则无法唤醒 */ 25 if (!(old_state & state)) 26 goto out; 27 28 /* 如果进程已经属于某个运行队列，则设置state为TASK_RUNNING后结束 */ 29 if (p->array) 30 goto out_running; 31 32 /* 获取之前运行p的CPU和当前CPU编号 */ 33 cpu = task_cpu(p); 34 this_cpu = smp_processor_id(); 35 36 /* 如果p进程正在运行, rq->curr == p */ 37 if (unlikely(task_running(rq, p))) 38 goto out_activate; 39 40 new_cpu = cpu; 41 42 /* 如果当前CPU和进程之前运行所在的CPU相同或者进程p不允许运行在当前CPU上 43 * 那么直接将p放在p原来运行的CPU上。*/ 44 if (cpu == this_cpu || unlikely(!cpu_isset(this_cpu, p->cpus_allowed))) 45 goto out_set_cpu; 46 47 /* 进入这里则表示当前CPU和之前运行p的CPU不是同一个CPU，且p可以在当前CPU上运行 */ 48 49 /* 获取运行p进程原CPU的负载猜测，两种算法取较小值 */ 50 load = source_load(cpu); 51 /* 获取当前CPU的负载猜测，两种算法取较大值 */ 52 this_load = target_load(this_cpu); 53 54 /* 如果设置同步标志则当前cpu负载降低 */ 55 if (sync) 56 this_load -= SCHED_LOAD_SCALE; 57 58 /* 如果先前执行进程的CPU工作量远小于当前CPU，则运行在原CPU上 */ 59 if (load < SCHED_LOAD_SCALE/2 && this_load > SCHED_LOAD_SCALE/2) 60 goto out_set_cpu; 61 62 new_cpu = this_cpu; 63 64 for_each_domain(this_cpu, sd) { 65 unsigned int imbalance; 66 /* 当到达imbalance_pct限制时，开始被动平衡 */ 67 imbalance = sd->imbalance_pct + (sd->imbalance_pct - 100) / 2; 68 69 if ((sd->flags & SD_WAKE_AFFINE) && 70 !task_hot(p, rq->timestamp_last_tick, sd)) { 71 /* 72 * 这个域有SD_WAKE_AFFINE标志，并且p进程的缓存可能可以用 */ 73 if (cpu_isset(cpu, sd->span)) { 74 goto out_set_cpu; 75 } 76 } else if ((sd->flags & SD_WAKE_BALANCE) && 77 imbalance*this_load <= 100*load) { 78 /* 这个域有SD_WAKE_BALANCE标志并且有不平衡发生 */ 79 if (cpu_isset(cpu, sd->span)) { 80 goto out_set_cpu; 81 } 82 } 83 } 84 85 new_cpu = cpu; /* 没找到合适的CPU，那么使用原CPU */ 86 87 /* 将进程放进new_cpu对应的运行队列 */ 88 out_set_cpu: 89 /* 检查是否有空闲CPU，如果有空闲CPU直接让p运行在空闲CPU上 */ 90 new_cpu = wake_idle(new_cpu, p); 91 if (new_cpu != cpu) { 92 set_task_cpu(p, new_cpu); 93 task_rq_unlock(rq, &flags); 94 /* might preempt at this point */ 95 rq = task_rq_lock(p, &flags); 96 old_state = p->state; 97 if (!(old_state & state)) 98 goto out; 99 if (p->array) 100 goto out_running; 101 102 this_cpu = smp_processor_id(); 103 cpu = task_cpu(p); 104 } 105 106 /* 处理进程激活的标志位 */ 107 out_activate: 108 if (old_state == TASK_UNINTERRUPTIBLE) { 109 /* 进程已经不处于TASK_UNINTERRUPTIBLE状态，更新原运行队列的状态 */ 110 rq->nr_uninterruptible--; 111 p->activated = -1; 112 } 113 114 /* 115 * activate_task函数的作用： 116 * 1、获取以纳秒为单位的当前时间戳，如果CPU不是本地CPU会补偿偏差 117 * 2、调用recalc_task_prio重新计算出动态描述符，见下一个函数 118 * 3、设置p->activated字段的值 119 * 4、把当前进程描述符插入活动进程集合 120 * */ 121 activate_task(p, rq, cpu == this_cpu); 122 /* 123 * 如果没有设置sync标志或者目标CPU不是本地CPU，检查新进程的动态优先级是否高于 124 * rq运行队列当前正在运行的进程，则强制调度。 */ 125 if (!sync || cpu != this_cpu) { 126 if (TASK_PREEMPTS_CURR(p, rq)) 127 resched_task(rq->curr); 128 } 129 success = 1; 130 131 out_running: 132 p->state = TASK_RUNNING; 133 out: 134 task_rq_unlock(rq, &flags); 135 136 return success; 137 }
recalc_task_prio()函数
更新进程的平均睡眠时间和动态优先级，它接受进程描述符p和由函数sched_clock()计算出来的当前时间戳now作为参数。
1 static void recalc_task_prio(task_t *p, unsigned long long now) 2 { 3 unsigned long long __sleep_time = now - p->timestamp; 4 unsigned long sleep_time; 5 6 /* 计算上次睡眠时间 */ 7 if (__sleep_time > NS_MAX_SLEEP_AVG) 8 sleep_time = NS_MAX_SLEEP_AVG; 9 else 10 sleep_time = (unsigned long)__sleep_time; 11 12 if (likely(sleep_time > 0)) { 13 if (p->mm && p->activated != -1 && 14 sleep_time > INTERACTIVE_SLEEP(p)) { 15 /* 进程不是从uninterruptible状态被唤醒，并且睡眠时间大于交互式进程的睡眠时间 16 * 更新睡眠时间为最大睡眠时间减去一个标准进程的基本睡眠时间片长度，这是一个经验值 */ 17 p->sleep_avg = JIFFIES_TO_NS(MAX_SLEEP_AVG - 18 DEF_TIMESLICE); 19 } else { 20 /* 如果平均睡眠时间越短，sleep_time则越大 */ 21 sleep_time *= (MAX_BONUS - CURRENT_BONUS(p)) ? : 1; 22 23 if (p->activated == -1 && p->mm) { 24 if (p->sleep_avg >= INTERACTIVE_SLEEP(p)) 25 /* 如果进程原来处于TASK_UNINTERRUPTIBLE状态，且是交互式进程，则睡眠时间置为0 */ 26 sleep_time = 0; 27 else if (p->sleep_avg + sleep_time >= 28 INTERACTIVE_SLEEP(p)) { 29 /* 如果进程原来处于TASK_UNINTERRUPTIBLE状态，且是批处理进程，将平均睡眠时间设为极限值 */ 30 p->sleep_avg = INTERACTIVE_SLEEP(p); 31 sleep_time = 0; 32 } 33 } 34 35 /* 加上睡眠时间 */ 36 p->sleep_avg += sleep_time; 37 38 if (p->sleep_avg > NS_MAX_SLEEP_AVG) 39 p->sleep_avg = NS_MAX_SLEEP_AVG; 40 } 41 } 42 43 /* 使用前文介绍的公式计算动态优先级 */ 44 p->prio = effective_prio(p); 45 }
schedule()函数
实现调度程序，它的任务是从运行队列的链表中找到一个进程，并将CPU分配给这个进程。schedule()可以由几个内核控制路径调用。
直接调用
如果current进程因不能获得必要的资源而要立刻被阻塞，就直接调用调度程序。在这种情况下，要阻塞进程的内核路径按以下步骤执行：
- 把current进程插入到合适的等待队列；
- 把current的进程状态改为TASK_INTERRUPTBLE或者TASK_UNINTERUPTBLE。
- 调用schedule()
- 检查资源是否可用，否则返回第2步。
- 一旦资源可用，就从等待队列中删除current进程。
延迟调用
把当前进程的TIF_NEED_RESCHED标志置为1，而以延迟方式调用调度程序。由于用户总是在恢复用户态进程的执行之前检查这个标志的值，所以schedule()将在不久之后某个时间被明确地调用。以下是典型的例子：
- 当current进程用完了时间片之后，由scheduler_tick()函数完成schedule()的延迟调用。
- 当一个被唤醒进程的优先级比当前进程的优先级高的时候，由try_to_wake_up()函数完成schedule()的延迟调用。
- 当发出系统调用sched_setscheduler()时。
1 asmlinkage void __sched schedule(void) 2 { 3 long *switch_count; 4 task_t *prev, *next; 5 runqueue_t *rq; 6 prio_array_t *array; 7 struct list_head *queue; 8 unsigned long long now; 9 unsigned long run_time; 10 int cpu, idx; 11 12 /* 13 * Test if we are atomic. Since do_exit() needs to call into 14 * schedule() atomically, we ignore that path for now. 15 * Otherwise, whine if we are scheduling when we should not be. 16 */ 17 if (likely(!current->exit_state)) { 18 if (unlikely(in_atomic())) { 19 printk(KERN_ERR "scheduling while atomic: " 20 "%s/0x%08x/%d\n", 21 current->comm, preempt_count(), current->pid); 22 dump_stack(); 23 } 24 } 25 profile_hit(SCHED_PROFILING, __builtin_return_address(0)); 26 27 need_resched: 28 /* 关闭本地中断，当前current赋值给prev，释放内核锁 */ 29 preempt_disable(); 30 prev = current; 31 release_kernel_lock(prev); 32 need_resched_nonpreemptible: 33 rq = this_rq(); 34 35 now = sched_clock(); 36 if (likely(now - prev->timestamp < NS_MAX_SLEEP_AVG)) 37 run_time = now - prev->timestamp; 38 else 39 run_time = NS_MAX_SLEEP_AVG; 40 run_time /= (CURRENT_BONUS(prev) ? : 1); 41 42 spin_lock_irq(&rq->lock); 43 44 if (unlikely(prev->flags & PF_DEAD)) 45 prev->state = EXIT_DEAD; 46 47 switch_count = &prev->nivcsw; 48 if (prev->state && !(preempt_count() & PREEMPT_ACTIVE)) { 49 switch_count = &prev->nvcsw; 50 if (unlikely((prev->state & TASK_INTERRUPTIBLE) && 51 unlikely(signal_pending(prev)))) 52 /* 如果是可打断的状态且有信号到达，则进入重新修改为可运行状态 */ 53 prev->state = TASK_RUNNING; 54 else { 55 if (prev->state == TASK_UNINTERRUPTIBLE) 56 rq->nr_uninterruptible++; 57 /* 如果prev是不可打断地状态则将其从运行队列中删除 58 * 函数让rq进程数减一，删除prev，使prev->array=NULL */ 59 deactivate_task(prev, rq); 60 } 61 } 62 63 cpu = smp_processor_id(); 64 if (unlikely(!rq->nr_running)) { 65 go_idle: 66 /* 无可运行进程，从其他运行队列迁移一些可运行进程到本地 */ 67 idle_balance(cpu, rq); 68 if (!rq->nr_running) { 69 /* 如果依然没有进程，则运行swapper进程 */ 70 next = rq->idle; 71 rq->expired_timestamp = 0; 72 wake_sleeping_dependent(cpu, rq); 73 74 /* swapper进程结束后也许有新的进程 */ 75 if (!rq->nr_running) 76 goto switch_tasks; 77 } 78 } else { 79 if (dependent_sleeper(cpu, rq)) { 80 /* 检查本CPU最高优先级的进程是否比其他CPU上正在运行的进程优先级低 81 * 如果是则运行swapper进程。 82 */ 83 next = rq->idle; 84 goto switch_tasks; 85 } 86 if (unlikely(!rq->nr_running)) 87 goto go_idle; 88 } 89 90 /* 已经有可运行进程 */ 91 array = rq->active; 92 if (unlikely(!array->nr_active)) { 93 /* 如果活动进程中没有进程，则将过期进程和活动进程交换 */ 94 rq->active = rq->expired; 95 rq->expired = array; 96 array = rq->active; 97 rq->expired_timestamp = 0; 98 rq->best_expired_prio = MAX_PRIO; 99 } 100 101 /* 寻找最高优先级（数字最小）不为空的链表下标 */ 102 idx = sched_find_first_bit(array->bitmap); 103 /* 对应最高优先级的活动进程链表头 */ 104 queue = array->queue + idx; 105 next = list_entry(queue->next, task_t, run_list); 106 107 if (!rt_task(next) && next->activated > 0) { 108 unsigned long long delta = now - next->timestamp; 109 110 /* 进程原来处于TASK_INTERRUPTIBLE，被系统调用或内核线程唤醒的 111 * 增加睡眠时间，间接增加动态优先级 */ 112 if (next->activated == 1) 113 delta = delta * (ON_RUNQUEUE_WEIGHT * 128 / 100) / 128; 114 115 array = next->array; 116 dequeue_task(next, array); 117 recalc_task_prio(next, next->timestamp + delta); 118 enqueue_task(next, array); 119 } 120 next->activated = 0; 121 switch_tasks: 122 /* 准备切换进程 */ 123 124 /* 将next进程描述符装入硬件高速缓存 */ 125 prefetch(next); 126 /* 清除prev的TIF_NEED_RESCHEHD标志 */ 127 clear_tsk_need_resched(prev); 128 /* 记录CPU正在经历静态状态 */ 129 rcu_qsctr_inc(task_cpu(prev)); 130 131 /* 更新prev的平均睡眠时间 */ 132 prev->sleep_avg -= run_time; 133 if ((long)prev->sleep_avg <= 0) 134 prev->sleep_avg = 0; 135 prev->timestamp = prev->last_ran = now; 136 137 if (likely(prev != next)) { 138 /* 两进程不相等 */ 139 next->timestamp = now; 140 rq->nr_switches++; 141 rq->curr = next; 142 ++*switch_count; 143 144 /* 建立next的地址空间，并调用switch_to函数进行进程切换 */ 145 prev = context_switch(rq, prev, next); 146 barrier(); 147 148 /* 恢复地址空间，如果prev进程结束，则还要释放页表相关的描述符 */ 149 finish_task_switch(prev); 150 } else 151 /* 两进程相等，不需要切换进程 */ 152 spin_unlock_irq(&rq->lock); 153 154 prev = current; 155 if (unlikely(reacquire_kernel_lock(prev) < 0)) 156 /* 如果获取了大内核锁，则继续调度，直到本进程主动释放大内核锁？ */ 157 goto need_resched_nonpreemptible; 158 /* 打开内核抢占 */ 159 preempt_enable_no_resched(); 160 if (unlikely(test_thread_flag(TIF_NEED_RESCHED))) 161 /* 如果设置了TTIF_NEED_RESCHED标志，则重新调度 */ 162 goto need_resched; 163 }
5. 总结
- linux作为开源系统拥有许多优点：
①开源，可以让大家对系统进行随意开发，设计出自己所需要的系统。
②安全，提供大量网络管理软件，网络安全软件
③广泛的硬件支持，可以在现如今的主流处理器上完美运行
然而他没有windous那样拥有友好的图形化界面，对于初学者来说需要多多学习操作命令，所以需要有比较长的学习时间才能够熟悉使用。
- 进程是一种数据结构，进程的引入为了使程序在多道程序环境下能并发执行。尽管进程只是计算机操作系统中很小的一方面，但它却为了整个系统运行提供了极大地帮助。我们完全可以将进程比拟成我们现今纷繁复杂的世界，我们人类便是一个个程序，如何更好的调整社会朝着安稳和谐快速发展，这是我们要努力的。在如今计算机越来越复杂的情况下，我们急需对进程进行更深入的研究。
6. 参考资料
https://blog.csdn.net/qq_29115063/article/details/53242835
https://blog.csdn.net/fdssdfdsf/article/details/7891748
https://blog.csdn.net/fdssdfdsf/article/details/7894211
http://www.cnblogs.com/zhouyinhui/archive/2010/09/09/1822594.html