learning kernel -- 进程调度

====================================
learning 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里。

learning kernel -- 进程管理

====================================
learning 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返回后这些资源才开始回收。

Happy Time Show

Happy time slide show


酒越饮越暖，人越玩越开怀。Actually I admire myself at that moment.