| 进程 |
进程的状态([include/linux.h]):
TASK_RUNNING, it means that it is in the "Ready List"
TASK_INTERRUPTIBLE, task waiting for a signal or a resource (sleeping)
TASK_UNINTERRUPTIBLE, task waiting for a resource (sleeping), it is in same "Wait Queue"
TASK_ZOMBIE, task child without father
TASK_STOPPED, task being debugged
______________ CPU Available ______________
| | ----------------> | |
| TASK_RUNNING | | Real Running |
|______________| <---------------- |______________|
CPU Busy
| /|\
Waiting for | | Resource
Resource | | Available
\|/ |
______________________
| |
| TASK_INTERRUPTIBLE / |
| TASK-UNINTERRUPTIBLE |
|______________________|
Main Multitasking Flow
从系统内核的角度看来，一个进程仅仅是进程控制表（process table）中的一项。进程控制表中的每一项都是一个task_struct 结构，而task_struct 结构本身是在include/linux/sched.h中定义的。在task_struct结构中存储各种低级和高级的信息，包括从一些硬件设备的寄存器拷贝到进程的工作目录的链接点。
进程控制表既是一个数组，又是一个双向链表，同时又是一个树。其物理实现是一个包括多个指针的静态数组。此数组的长度保存在include/linux/tasks.h 定义的常量NR_TASKS中，其缺省值为128，数组中的结构则保存在系统预留的内存页中。链表是由next_task 和prev_task两个指针实现的，而树的实现则比较复杂。
系统启动后，内核通常作为某一个进程的代表。一个指向task_struct的全局指针变量current用来记录正在运行的进程。变量current只能由kernel/sched.c中的进程调度改变。当系统需要查看所有的进程时，则调用for_each_task，这将比系统搜索数组的速度要快得多。
二、用户进程和内核线程
某一个进程只能运行在用户方式（user mode）或内核方式（kernel mode）下。用户程序运行在用户方式下，而系统调用运行在内核方式下。在这两种方式下所用的堆栈不一样：用户方式下用的是一般的堆栈，而内核方式下用的是固定大小的堆栈（一般为一个内存页的大小）
尽管linux是一个宏内核系统，内核线程依然存在，以便并行地处理一些内核的“家务室”。这些任务不占用USER memory（用户空间），而仅仅使用KERNEL memory。和其他内核模块一样，它们也在高级权限（i386系统中的RING 0）下工作作。内核线程是被kernel_thread [arch/i386/kernel/process]创建的,它又通过调用著名的clone系统调用[arch/i386/kernel/process.c] (类似fork系统调用的所有功能都是由它最终实现):
int kernel_thread(int (*fn)(void *), void * arg, unsigned long flags)
{
long retval, d0;
__asm__ __volatile__(
"movl %%esp,%%esi\n\t"
"int $0x80\n\t" /* Linux/i386 system call */
"cmpl %%esp,%%esi\n\t" /* child or parent? */
"je 1f\n\t" /* parent - jump */
/* Load the argument into eax, and push it. That way, it does
* not matter whether the called function is compiled with
* -mregparm or not. */
"movl %4,%%eax\n\t"
"pushl %%eax\n\t"
"call *%5\n\t" /* call fn */
"movl %3,%0\n\t" /* exit */
"int $0x80\n"
"1:\t"
:"=&a" (retval), "=&S" (d0)
:"0" (__NR_clone), "i" (__NR_exit),
"r" (arg), "r" (fn),
"b" (flags | CLONE_VM)
: "memory");
return retval;
}
一旦调用，我们就有了一个新的任务（Task） (一般PID都很小, 例如2,3,等) 等待一个响应很慢的资源，例如swap或者usb事件，以便同步。下面是一些最常用的内核线程(你可以用ps x命令):
PID COMMAND
1 init
2 keventd
3 kswapd
4 kreclaimd
5 bdflush
6 kupdated
7 kacpid
67 khubd
init内核线程也是启动以后最初的进程。 它会调用其它用户模式的任务，(/etc/inittab)例如控制台守护进程（daemons）， tty守护进程以及网络守护进程(rc脚本)。
下面是一个典型的内核线程kswapd [mm/vmscan.c].
kswapd是被clone()建立的 [arch/i386/kernel/process.c]''
|do_initcalls
|kswapd_init
|kernel_thread
|syscall fork (in assembler)
·do_initcalls [init/main.c]
·kswapd_init [mm/vmscan.c]
·kernel_thread [arch/i386/kernel/process.c]
三 进程创建，运行和消失
Linux系统使用系统调用fork( )来创建一个进程，使用exit( )来结束进程。fork( )和exit( )的源程序保存在kernel/fork.c and kernel/exit.c中。fork( )的主要任务是初始化要创建进程的数据结构，其主要的步骤有：
1）申请一个空闲的页面来保存task_struct。
2）查找一个空的进程槽（find_empty_process( )）。
3）为kernel_stack_page申请另一个空闲的内存页作为堆栈。
4）将父进程的LDT表拷贝给子进程。
5）复制父进程的内存映射信息。
6）管理文件描述符和链接点。
|sys_fork
|do_fork
|alloc_task_struct
|__get_free_pages
|p->state = TASK_UNINTERRUPTIBLE
|copy_flags
|p->pid = get_pid
|copy_files
|copy_fs
|copy_sighand
|copy_mm // should manage CopyOnWrite (I part)
|allocate_mm
|mm_init
|pgd_alloc -> get_pgd_fast
|get_pgd_slow
|dup_mmap
|copy_page_range
|ptep_set_wrprotect
|clear_bit // set page to read-only
|copy_segments // For LDT
|copy_thread
|childregs->eax = 0
|p->thread.esp = childregs // child fork returns 0
|p->thread.eip = ret_from_fork // child starts from fork exit
|retval = p->pid // parent fork returns child pid
|SET_LINKS // insertion of task into the list pointers
|nr_threads++ // Global variable
|wake_up_process(p) // Now we can wake up just created child
|return retval
·sys_fork [arch/i386/kernel/process.c]
·do_fork [kernel/fork.c]
·alloc_task_struct [include/asm/processor.c]
·__get_free_pages [mm/page_alloc.c]
·get_pid [kernel/fork.c]
·copy_files
·copy_fs
·copy_sighand
·copy_mm
·allocate_mm
·mm_init
·pgd_alloc -> get_pgd_fast [include/asm/pgalloc.h]
·get_pgd_slow
·dup_mmap [kernel/fork.c]
·copy_page_range [mm/memory.c]
·ptep_set_wrprotect [include/asm/pgtable.h]
·clear_bit [include/asm/bitops.h]
·copy_segments [arch/i386/kernel/process.c]
·copy_thread
·SET_LINKS [include/linux/sched.h]
·wake_up_process [kernel/sched.c]
撤消一个进程可能稍微复杂些，因为撤消子进程必须通知父进程。另外，使用kill( )也可以结束一个进程。sys_kill( )、sys_wait( )和sys_exit( )都保存在文件exit.c中。
使用fork ( )创建一个进程后，程序的两个拷贝都在运行。通常一个拷贝使用exec ( )调用另一个拷贝。系统调用exec ( )负责定位可执行文件的二进制代码，并负责装入和运行。Linux系统中的exec ( )通过使用linux_binfmt结构支持多种二进制格式。每种二进制格式都代表可执行代码和链接库。linux _binfmt结构种包含两个指针，一个指向装入可执行代码的函数，另一个指向装入链接库的函数。
Unix系统提供给程序员6种调用exec( ) 的方法。其中的5种是作为库函数实现，而sys_execve( )是由系统内核实现的。它执行一个十分简单的任务：装入可执行文件的文件头，并试图执行它。如果文件的头两个字节是#! ,那么它就调用在文件第一行中所指定的解释器，否则，它将逐个尝试注册的二进制格式。
movl $sem,% ecx 通过寄存器ecx向__down函数传递sem指针
decl sem
js 2f 如果为负值,表示semaphore已被占用,执行__down_failed过程
1:
由于出现semaphore竞争的可能性比较小,将分支代码转移到.text.lock段,以缩短正常的指令路径.
.section .text.lock,"ax"
2: call __down_failed
jmp 1b
.previous
...
up(&sem) 编绎成:
movl $sem,% ecx
incl sem
jle 2f 如果小于或等于0,表示该semaphore有进程在等待,就去调用__up_wakeup
1:
.section .text.lock,"ax"
2: call __up_wakeup
jmp 1b
.previous
...
__down_failed:
pushl % eax
pushl % edx
pushl % ecx ; eax,edx,ecx是3个可用于函数参数的寄存器
call __down
popl % ecx
popl % edx
popl % eax
ret
__up_wakeup:
pushl % eax
pushl % edx
pushl % ecx
call __up
popl % ecx
popl % edx
popl % eax
ret
; semaphore.c
void __down(struct semaphore * sem)
{
struct task_struct *tsk = current;
DECLARE_WAITQUEUE(wait, tsk);
tsk->state = TASK_UNINTERRUPTIBLE;
add_wait_queue_exclusive(&sem->wait, &wait);
// 将当前进程加入到该semaphore的等待队列中
spin_lock_irq(&semaphore_lock);
sem->sleepers++;
for (;;) {
int sleepers = sem->sleepers;
/*
* Add "everybody else" into it. They aren't
* playing, because we own the spinlock.
*/
// atomic_add_negative(int i,atomic_t *v)将i + v->counter相加,
// 结果为负返回1,否则返回0
if (!atomic_add_negative(sleepers - 1, &sem->count)) {
// 如果(sleepers - 1 + sem->count.counter)非负,则说明
// semaphore已经被释放,可以返回
sem->sleepers = 0;
break;
}
sem->sleepers = 1; /* us - see -1 above */
spin_unlock_irq(&semaphore_lock);
// 当semaphore被up()唤醒时,schedule()返回
schedule();
// 虽然已线程被up恢复,但为防止碰巧又有一个线程获得了semaphore,
// 因此将它们放在循环体中
tsk->state = TASK_UNINTERRUPTIBLE;
spin_lock_irq(&semaphore_lock);
}
spin_unlock_irq(&semaphore_lock);
// 该进程获得了semaphore,将它从等待队列中删除
remove_wait_queue(&sem->wait, &wait);
tsk->state = TASK_RUNNING;
// 为什么这里要调用wake_up,是因为调用它没有副作用从而防止潜在的死锁吗?
wake_up(&sem->wait);
}
void __up(struct semaphore *sem)
{
扩展为
__wake_up_common(&sem->wait,TASK_UNINTERRUPTIBLE|TASK_INTERRUPTIBLE,1,0);
唤醒队列中第1个进程,即将第1个进程放入运行队列
wake_up(&sem->wait);
}
; sched.c
static inline void __wake_up_common (wait_queue_head_t *q, unsigned int
mode,
int nr_exclusive, const int sync)
{
struct list_head *tmp, *head;
struct task_struct *p;
unsigned long flags;
if (!q)
goto out;
wq_write_lock_irqsave(&q->lock, flags);
#if WAITQUEUE_DEBUG
CHECK_MAGIC_WQHEAD(q);
#endif
head = &q->task_list;
#if WAITQUEUE_DEBUG
if (!head->next || !head->prev)
WQ_BUG();
#endif
tmp = head->next;
while (tmp != head) {
unsigned int state;
wait_queue_t *curr = list_entry(tmp, wait_queue_t,
task_list);
tmp = tmp->next;
#if WAITQUEUE_DEBUG
CHECK_MAGIC(curr->__magic);
#endif
p = curr->task;
state = p->state;
if (state & mode) {
#if WAITQUEUE_DEBUG
curr->__waker = (long)__builtin_return_address(0);
#endif
if (sync)
wake_up_process_synchronous(p);
else
wake_up_process(p);
if ((curr->flags & WQ_FLAG_EXCLUSIVE) && !--nr_exclusive)
break;
}
}
wq_write_unlock_irqrestore(&q->lock, flags);
out:
return;
}
; sched.c
inline void wake_up_process(struct task_struct * p)
{
unsigned long flags;
/*
* We want the common case fall through straight, thus the goto.
*/
spin_lock_irqsave(&runqueue_lock, flags);
p->state = TASK_RUNNING;
if (task_on_runqueue(p))
goto out;
add_to_runqueue(p);
reschedule_idle(p);
out:
spin_unlock_irqrestore(&runqueue_lock, flags);
}
; sched.c
static inline void wake_up_process_synchronous(struct task_struct * p)
{
unsigned long flags;
/*
* We want the common case fall through straight, thus the goto.
*/
spin_lock_irqsave(&runqueue_lock, flags);
p->state = TASK_RUNNING;
if (task_on_runqueue(p))
goto out;
add_to_runqueue(p);
out:
spin_unlock_irqrestore(&runqueue_lock, flags);
}
; sched.h
static inline int task_on_runqueue(struct task_struct *p)
{
return (p->run_list.next != NULL);
}
; sched.c
static inline void add_to_runqueue(struct task_struct * p)
{
list_add(&p->run_list, &runqueue_head);
nr_running++;
}
static LIST_HEAD(runqueue_head);
; fork.c
void add_wait_queue_exclusive(wait_queue_head_t *q, wait_queue_t *
wait)
{
unsigned long flags;
wq_write_lock_irqsave(&q->lock, flags);
wait->flags = WQ_FLAG_EXCLUSIVE;
__add_wait_queue_tail(q, wait);
wq_write_unlock_irqrestore(&q->lock, flags);
}
; wait.h
static inline void __add_wait_queue_tail(wait_queue_head_t *head,
wait_queue_t *new)
{
#if WAITQUEUE_DEBUG
if (!head || !new)
WQ_BUG();
CHECK_MAGIC_WQHEAD(head);
CHECK_MAGIC(new->__magic);
if (!head->task_list.next || !head->task_list.prev)
WQ_BUG();
#endif
list_add_tail(&new->task_list, &head->task_list);
}
正执行调度的函数是schedule(void),它选择一个最合适的进程执行，并且真正进行上下文切换，
使得选中的进程得以执行。而reschedule_idle(struct task_struct *p)的作用是为进程选择
一个合适的CPU来执行，如果它选中了某个CPU，则将该CPU上当前运行进程的need_resched标志
置为1,然后向它发出一个重新调度的处理机间中断，使得选中的CPU能够在中断处理返回时执行
schedule函数，真正调度进程p在CPU上执行。在schedule()和reschedule_idle()中调用了goodness()
函数。goodness()函数用来衡量一个处于可运行状态的进程值得运行的程度。此外，在schedule()
函数中还调用了schedule_tail()函数;在reschedule_idle()函数中还调用了reschedule_idle_slow()。
/*
* 'sched.c' is the main kernel file. It contains scheduling primitives
* (sleep_on, wakeup, schedule etc) as well as a number of simple system
* call functions (type getpid(), which just extracts a field from
* current-task
*/
#include
#include
#include
#include
#include
#include
#include
#define LATCH (1193180/HZ)
extern void mem_use(void);
extern int timer_interrupt(void);
extern int system_call(void);
union task_union {
struct task_struct task;
char stack[PAGE_SIZE];
};
static union task_union init_task = {INIT_TASK,};
long volatile jiffies=0;
long startup_time=0;
struct task_struct *current = &(init_task.task), *last_task_used_math =
NULL;
struct task_struct * task[NR_TASKS] = {&(init_task.task), };
long user_stack [ PAGE_SIZE>>2 ] ;
struct {
long * a;
short b;
} stack_start = { & user_stack [PAGE_SIZE>>2] , 0x10 };
/*
* 'math_state_restore()' saves the current math information in the
* old math state array, and gets the new ones from the current task
*/
void math_state_restore() @@协处理器状态保存
{
if (last_task_used_math)
__asm__("fnsave %0"::"m" (last_task_used_math->tss.i387));
if (current->used_math)
__asm__("frstor %0"::"m" (current->tss.i387));
else {
__asm__("fninit"::);
current->used_math=1;
}
last_task_used_math=current;
}
/*
* 'schedule()' is the scheduler function. This is GOOD CODE! There
* probably won't be any reason to change this, as it should work well
* in all circumstances (ie gives IO-bound processes good response etc).
* The one thing you might take a look at is the signal-handler code
here.
*
* NOTE!! Task 0 is the 'idle' task, which gets called when no other
* tasks can run. It can not be killed, and it cannot sleep. The 'state'
* information in task[0] is never used.
*/
void schedule(void)
{
int i,next,c;
struct task_struct ** p;
/* check alarm, wake up any interruptible tasks that have got a signal
*/
for(p = &LAST_TASK ; p > &FIRST_TASK ; --p)
if (*p) {
if ((*p)->alarm && (*p)->alarm < jiffies) {
@@??
(*p)->signal |= (1<<(SIGALRM-1));@@14-1
(*p)->alarm = 0;
}
if ((*p)->signal && (*p)->state==TASK_INTERRUPTIBLE)
(*p)->state=TASK_RUNNING;
}
@@ task 1 如何变为TASK_RUNNING??signal 如何得到,alarm如何变非0且 /* this is the
scheduler proper: */
@@操作系统最重要的函数，调度算法
@@这个循环要找到一个可运行的任务才能退出,会死在这吗?即如没有一个可运行
while (1) {
c = -1;
next = 0;
i = NR_TASKS;
p = &task[NR_TASKS];
while (--i) {
if (!*--p)
continue;
if ((*p)->state == TASK_RUNNING && (*p)->counter > c)
c = (*p)->counter, next = i;
}
if (c) break; @@记数大于零
for(p = &LAST_TASK ; p > &FIRST_TASK ; --p)
if (*p)
(*p)->counter = ((*p)->counter >> 1) +
(*p)->priority;
}
switch_to(next);
}
int sys_pause(void)
{
current->state = TASK_INTERRUPTIBLE; @@任务可中断
schedule();
return 0;
}
void sleep_on(struct task_struct **p)
{
struct task_struct *tmp;
if (!p)
return;
if (current == &(init_task.task))
panic("task[0] trying to sleep");
tmp = *p;
*p = current;
current->state = TASK_UNINTERRUPTIBLE;
schedule();
if (tmp) @@激活p，什么时候回来？唤醒上次睡眠的进程
tmp->state=0;
}
void interruptible_sleep_on(struct task_struct **p)
{
struct task_struct *tmp;
if (!p)
return;
if (current == &(init_task.task))
panic("task[0] trying to sleep");
tmp=*p;
*p=current;
repeat: current->state = TASK_INTERRUPTIBLE;
schedule();
if (*p && *p != current) {
(**p).state=0;
goto repeat;
}
@@好象下不来
*p=NULL;
if (tmp)
tmp->state=0;
}
void wake_up(struct task_struct **p)
{
if (p && *p) {
(**p).state=0; @@唤醒该进程running
*p=NULL; @@睡眠栈为0
}
}
void do_timer(long cpl) @@定时调度
{
if (cpl)
current->utime++; @@用户态时间加一
else
current->stime++; @@系统态时间加一
if ((--current->counter)>0) return; @@当前记数减一
current->counter=0;
if (!cpl) return;
schedule();
}
int sys_alarm(long seconds)
{
current->alarm = (seconds>0)?(jiffies+HZ*seconds):0;
return seconds;
}
int sys_getpid(void)
{
return current->pid;
}
int sys_getppid(void)
{
return current->father;
}
int sys_getuid(void)
{
return current->uid;
}
int sys_geteuid(void)
{
return current->euid;
}
int sys_getgid(void)
{
return current->gid;
}
int sys_getegid(void)
{
return current->egid;
}
int sys_nice(long increment)
{
if (current->priority-increment>0)
current->priority -= increment;
return 0;
}
int sys_signal(long signal,long addr,long restorer)
{
long i;
switch (signal) {
case SIGHUP: case SIGINT: case SIGQUIT: case SIGILL:
case SIGTRAP: case SIGABRT: case SIGFPE: case SIGUSR1:
case SIGSEGV: case SIGUSR2: case SIGPIPE: case SIGALRM:
case SIGCHLD:
i=(long) current->sig_fn[signal-1];
current->sig_fn[signal-1] = (fn_ptr) addr;
current->sig_restorer = (fn_ptr) restorer;
return i;
default: return -1;
}
}
void sched_init(void)
{
int i;
struct desc_struct * p;
set_tss_desc(gdt+FIRST_TSS_ENTRY,&(init_task.task.tss));@@init task tss
set_ldt_desc(gdt+FIRST_LDT_ENTRY,&(init_task.task.ldt));@@init ldt
p = gdt+2+FIRST_TSS_ENTRY;
for(i=1;i task[i] = NULL;
p->a=p->b=0;
p++;
p->a=p->b=0;
p++;
}
ltr(0); @@调入task 0的tss
lldt(0); @@调入task 0的ldt
outb_p(0x36,0x43); /* binary, mode 3, LSB/MSB, ch 0 */
outb_p(LATCH & 0xff , 0x40); /* LSB */
outb(LATCH >> 8 , 0x40); /* MSB */
set_intr_gate(0x20,&timer_interrupt); @@irq 0 时钟中断
outb(inb_p(0x21)&~0x01,0x21);
set_system_gate(0x80,&system_call);
}
static int
send_signal(int sig, struct siginfo *info, struct sigpending *signals);
将信号sig和对应的消息结构info添加到信号队列signal中.
static int
collect_signal(int sig, struct sigpending *list, siginfo_t *info);
返回信号sig在队列list中的信息info.
struct task_struct {
...
struct sigpending pending;
...
};
struct sigpending {
struct sigqueue *head, **tail;
sigset_t signal;
};
struct sigqueue {
struct sigqueue *next;
siginfo_t info;
};
// kernel/signal.c
static int
send_signal(int sig, struct siginfo *info, struct sigpending *signals)
{
struct sigqueue * q = NULL;
/* Real-time signals must be queued if sent by sigqueue, or
some other real-time mechanism. It is implementation
defined whether kill() does so. We attempt to do so, on
the principle of least surprise, but since kill is not
allowed to fail with EAGAIN when low on memory we just
make sure at least one signal gets delivered and don't
pass on the info struct. */
if (atomic_read(&nr_queued_signals) < max_queued_signals) {
q = kmem_cache_alloc(sigqueue_cachep, GFP_ATOMIC);
}
// nr_queued_signals和max_queued_signals用来限制全局sigqueue成员的数目
if (q) {
atomic_inc(&nr_queued_signals);
q->next = NULL;
*signals->tail = q;
signals->tail = &q->next; tail总是指向最末的信号成员的next指针 switch ((unsign
ed long) info)
{
case 0:
// info参数如果为0,表示信号来源于当前用户进程 q->info.si_signo =
sig;
q->info.si_errno = 0;
q->info.si_code = SI_USER;
q->info.si_pid = current->pid;
q->info.si_uid = current->uid;
break;
case 1:
// info参数如果为1,表示信号来源于内核本身 q->info.si_signo = sig;
q->info.si_errno = 0;
q->info.si_code = SI_KERNEL;
q->info.si_pid = 0;
q->info.si_uid = 0;
break;
default:
// 否则从info指针中拷贝信号
copy_siginfo(&q->info, info);
break;
}
}
else if (sig >= SIGRTMIN && info && (unsigned long)info != 1 && info->
si_code != SI_USER)
{
; 如果该信号是内核发出的实时信号,就返回错误码
/*
* Queue overflow, abort. We may abort if the signal was rt
* and sent by user using something other than kill().
*/
return -EAGAIN;
}
sigaddset(&signals->signal, sig); 将sig号标记在队列的信号集上
return 0;
}
static int
collect_signal(int sig, struct sigpending *list, siginfo_t *info)
{
if (sigismember(&list->signal, sig)) {
/* Collect the siginfo appropriate to this signal. */ struct sigqueue *q, **
pp;
pp = &list->head; pp指向第一个信号成员的next指针
while ((q = *pp) != NULL) {
if (q->info.si_signo == sig) goto found_it;
pp = &q->next;
}
/* Ok, it wasn't in the queue. We must have
been out of queue space. So zero out the
info.
*/
sigdelset(&list->signal, sig);
info->si_signo = sig;
info->si_errno = 0;
info->si_code = 0;
info->si_pid = 0;
info->si_uid = 0;
return 1;
found_it:
// 将找到信号成员从信号队列中删除
if ((*pp = q->next) == NULL)
list->tail = pp;
/* Copy the sigqueue information and free the queue entry */
copy_siginfo(info, &q->info);
kmem_cache_free(sigqueue_cachep,q);
atomic_dec(&nr_queued_signals);
/* Non-RT signals can exist multiple times.. */
if (sig >= SIGRTMIN) {
while ((q = *pp) != NULL) {
if (q->info.si_signo == sig) goto found_another;
pp = &q->next;
}
}
sigdelset(&list->signal, sig);
found_another:
return 1;
}
return 0;
}
问题
当有多个CPU时，同样的代码可能同时在两个或多个CPU上执行。这在如下所示用于初始化某个图像设备的例程中可能会出问题。
void init_hardware(void)
{
outb(0x1, hardware_base + 0x30);
outb(0x2, hardware_base + 0x30);
outb(0x3, hardware_base + 0x30);
outb(0x4, hardware_base + 0x30);
}
假设该硬件依赖于寄存器0x30按顺序依次被设为0、1、2、3来初始化，那么要是有另一个CPU来参乎的话，事情就会搞糟。想象有两个CPU的情形，它们都在执行这个例程，不过2号CPU进入得稍慢点：
CPU 1 CPU 2
0x30 = 1
0x30 = 2 0x30 = 1
0x30 = 3 0x30 = 2
0x30 = 4 0x30 = 3
0x30 = 4
这会发生什么情况呢？从我们设想的硬件设备看来，它在寄存器0x30上收到的字节按顺序为：1、2、1、3、2、4、3、4。
啊！原本好好的事第二个CPU一来就搞得一团糟了也。所幸的是，我们有防止这类事情发生的办法。
自旋锁小历史
2.0.x版本的Linux内核通过给整个内核引入一个全局变量来防止多于一个CPU会造成的问题。这意味着任何时刻只有一个CPU能够执行来自内核空间的代码。这样尽管能工作，但是当系统开始以多于2个的CPU出现时，扩展性能就不怎么好。
2.1.x版本的内核系列加入了粒度更细的SMP支持。这意味着不再依赖于以前作为全局变量出现的“大锁”，而是每个没有SMP意识的例程现在都需要各自的自旋锁。文件asm/spinlock.h中定义了若干类型的自旋锁。
有了局部化的自旋锁后，不止一个CPU同时执行内核空间代码就变得可能了。
简单的自旋锁
理解自旋锁的最简单方法是把它作为一个变量看待，该变量把一个例程或者标记为“我当前在另一个CPU上运行，请稍等一会”，或者标记为“我当前不在运行”。如果1号CPU首先进入该例程，它就获取该自旋锁。当2号CPU试图进入同一个例程时，该自旋锁告诉它自己已为1号CPU所持有，需等到1号CPU释放自己后才能进入。
spinlock_t my_spinlock = SPIN_LOCK_UNLOCKED;
unsigned long flags;
spin_lock (&my_spinlock);
...
critical section
...
spin_unlock (&my_spinlock);
中断
设想我们的硬件的驱动程序还有一个中断处理程序。该处理程序需要修改某些由我们的驱动程序定义的全局变量。这会造成混乱。我们如何解决呢？
保护某个数据结构，使它免遭中断之修改的最初方法是全局地禁止中断。在已知只有自己的中断才会修改自己的驱动程序变量时，这么做效率很低。所幸的是，我们现在有更好的办法了。我们只是在使用共享变量期间禁止中断，此后重新使能。
实现这种办法的函数有三个：
disable_irq()
enable_irq()
disable_irq_nosync()
这三个函数都取一个中断号作为参数。注意，禁止一个中断的时间太长会导致难以追踪程序缺陷，丢失数据，甚至更坏。
disable_irq函数的非同步版本允许所指定的IRQ处理程序继续运行，前提是它已经在运行，普通的disable_irq则所指定的IRQ处理程序不在如何CPU上运行。
如果需要在中断处理程序中修改自旋锁，那就不能使用普通的spin_lock()和spin_unlock()，而应该保存中断状态。这可通过给这两个函数添加_irqsave后缀很容易地做到：
spinlock_t my_spinlock = SPIN_LOCK_UNLOCKED;
unsigned long flags;
spin_lock_irqsave(&my_spinlock, flags);
...
critical section
...
spin_unlock_irqrestore (&my_spinlock, flags);
>>> kernel_thread以标志CLONE_VM调用clone系统调用
/*
* Create a kernel thread
*/
int kernel_thread(int (*fn)(void *), void * arg, unsigned long flags)
{
long retval, d0;
__asm__ __volatile__(
"movl %%esp,%%esi\n\t"
"int $0x80\n\t" /* Linux/i386 system call */
"cmpl %%esp,%%esi\n\t" /* child or parent? */
/* Load the argument into eax, and push it. That way, it does
* not matter whether the called function is compiled with
* -mregparm or not. */
"movl %4,%%eax\n\t"
"pushl %%eax\n\t"
"call *%5\n\t" /* call fn */
"movl %3,%0\n\t" /* exit */
"int $0x80\n"
"1:\t"
:"=&a" (retval), "=&S" (d0)
:"0" (__NR_clone), "i" (__NR_exit),
"r" (arg), "r" (fn),
"b" (flags | CLONE_VM)
: "memory");
return retval;
}
>>> sys_clone->do_fork->copy_mm：
static int copy_mm(unsigned long clone_flags, struct task_struct * tsk)
{
struct mm_struct * mm, *oldmm;
int retval;
。。。。。。。。
tsk->mm = NULL;
tsk->active_mm = NULL;
/*
* Are we cloning a kernel thread?
*
* We need to steal a active VM for that..
*/
>>> 如果是内核线程的子线程（mm=NULL），则直接退出，此时内核线程mm和active_mm均为为NULL
oldmm = current->mm;
if (!oldmm)
return 0;
>>> 内核线程，只是增加当前进程的虚拟空间的引用计数
if (clone_flags & CLONE_VM) {
atomic_inc(&oldmm->mm_users);
mm = oldmm;
goto good_mm;
}
。。。。。。。。。。
good_mm:
>>> 内核线程的mm和active_mm指向当前进程的mm_struct结构
tsk->mm = mm;
tsk->active_mm = mm;
return 0;
。。。。。。。
}
然后内核线程一般调用daemonize来释放对用户空间的引用：
>>> daemonize->exit_mm->_exit_mm：
/*
* Turn us into a lazy TLB process if we
* aren't already..
*/
static inline void __exit_mm(struct task_struct * tsk)
{
struct mm_struct * mm = tsk->mm;
mm_release();
if (mm) {
atomic_inc(&mm->mm_count);
if (mm != tsk->active_mm) BUG();
/* more a memory barrier than a real lock */
task_lock(tsk);
>>> 释放用户虚拟空间的数据结构
tsk->mm = NULL;
task_unlock(tsk);
enter_lazy_tlb(mm, current, smp_processor_id());
>>> 递减mm的引用计数并是否为0，是则释放mm所代表的映射
mmput(mm);
}
}
asmlinkage void schedule(void)
{
。。。。。。。。。
if (!current->active_mm) BUG();
。。。。。。。。。
prepare_to_switch();
{
struct mm_struct *mm = next->mm;
struct mm_struct *oldmm = prev->active_mm;
>>> mm = NULL，选中的为内核线程
if (!mm) {
>>> 对内核线程,active_mm = NULL，否则一定是出错了
if (next->active_mm) BUG();
>>> 选中的内核线程active_mm借用老进程的active_mm
next->active_mm = oldmm;
atomic_inc(&oldmm->mm_count);
enter_lazy_tlb(oldmm, next, this_cpu);
} else {
>>> mm != NULL 选中的为用户进程，active_mm必须与mm相等，否则一定是出错了
if (next->active_mm != mm) BUG();
switch_mm(oldmm, mm, next, this_cpu);
}
>>> prev = NULL ，切换出去的是内核线程
if (!prev->mm) {
>>> 设置其 active_mm = NULL 。
prev->active_mm = NULL;
mmdrop(oldmm);
}
}
}
对内核线程的虚拟空间总结一下：
１、创建的时候：
父进程是用户进程，则mm和active_mm均共享父进程的，然后内核线程一般调用daemonize适头舖m
父进程是内核线程，则mm和active_mm均为NULL
总之，内核线程的mm = NULL；进程调度的时候以此为依据判断是用户进程还是内核线程。
２、进程调度的时候
如果切换进来的是内核线程，则置active_mm为切换出去的进程的active_mm；
如果切换出去的是内核线程，则置active_mm为NULL。
进程的切换包括三个层次:
·用户数据的保存: 包括正文段(TEXT), 数据段(DATA,BSS), 栈段(STACK), 共享内存段(SHARED MEMORY)的保存。
·寄存器数据的保存: 包括PC(program counter,指向下一条要执行的指令的地址), PSW(processor status word,处理机状态字), SP(stack pointer,栈指针), PCBP(pointer of process control block,进程控制块指针), FP(frame pointer,指向栈中一个函数的local 变量的首地址), AP(augument pointer,指向栈中函数调用的实参位置), ISP(interrupt stack pointer,中断栈指针), 以及其他的通用寄存器等。
·系统层次的保存: 包括proc,u,虚拟存储空间管理表格,中断处理栈。以便于该进程再一次得到CPU时间片时能正常运行下去。
多进程系统的一些突出的特点:
并行化
一件复杂的事件是可以分解成若干个简单事件来解决的, 这在程序员的大脑中早就形成了这种概念, 首先将问题分解成一个个小问题, 将小问题再细分, 最后在一个合适的规模上做成一个函数。 在软件工程中也是这么说的。如果我们以图的方式来思考, 一些小问题的计算是可以互不干扰的, 可以同时处理, 而在关键点则需要统一在一个地方来处理, 这样程序的运行就是并行的, 至少从人的时间观念上来说是这样的。 而每个小问题的计算又是较简单的。
简单有序
这样的程序对程序员来说不亚于管理一班人, 程序员为每个进程设计好相应的功能, 并通过一定的通讯机制将它们有机地结合在一起, 对每个进程的设计是简单的, 只在总控部分小心应付(其实也是蛮简单的), 就可完成整个程序的施工。
互不干扰
这个特点是操作系统的特点, 各个进程是独立的, 不会串位。
事务化
比如在一个数据电话查询系统中, 将程序设计成一个进程只处理一次查询即可, 即完成一个事务。当电话查询开始时, 产生这样一个进程对付这次查询; 另一个电话进来时, 主控程序又产生一个这样的进程对付, 每个进程完成查询任务后消失. 这样的编程多简单, 只要做一次查询的程序就可以了。
Linux是一个多进程的操作系统，进程是分离的任务，拥有各自的权利和责任。如果一个进程崩溃，它不应该让系统的另一个进程崩溃。每一个独立的进程运行在自己的虚拟地址空间，除了通过安全的核心管理的机制之外无法影响其他的进程。
在一个进程的生命周期中，进程会使用许多系统资源。比如利用系统的CPU执行它的指令，用系统的物理内存来存储它和它的数据。它会打开和使用文件系统中的文件，会直接或者间接使用系统的物理设备。如果一个进程独占了系统的大部分物理内存和CPU，对于其他进程就是不公平的。所以Linux必须跟踪进程本身和它使用的系统资源以便公平地管理系统中的进程。
系统最宝贵的资源就是CPU。通常系统只有一个CPU。Linux作为一个多进程的操作系统，它的目标就是让进程在系统的CPU上运行，充分利用CPU。如果进程数多于CPU（一般情况都是这样），其他的进程就必须等到CPU被释放才能运行。多进程的思想就是：一个进程一直运行，直到它必须等待，通常是等待一些系统资源，等拥有了资源，它才可以继续运行。在一个单进程的系统中，比如DOS，CPU被简单地设为空闲，这样等待资源的时间就会被浪费。而在一个多进程的系统中，同一时刻许多进程在内存中，当一个进程必须等待时，操作系统将CPU从这个进程切换到另一个更需要的进程。
我们组分析的是Linux进程的状态转换以及标志位的作用，它没有具体对应某个系统调用，而是分布在各个系统调用中。所以我们详细而广泛地分析了大量的原码，对进程状态转换的原因、方式和结果进行了分析，大致总结了整个Linux系统对进程状态管理的实现机制。
Linux中，每个进程用一个task_struct的数据结构来表示，用来管理系统中的进程。Task向量表是指向系统中每一个task_struct数据结构的指针的数组。这意味着系统中的最大进程数受到Task向量表的限制，缺省是512。这个表让Linux可以查到系统中的所有的进程。操作系统初始化后，建立了第一个task_struct数据结构INIT_TASK。当新的进程创建时，从系统内存中分配一个新的task_struct，并增加到Task向量表中。为了更容易查找，用current指针指向当前运行的进程。
task_struct结构中有关于进程调度的两个重要的数据项：
struct task_struct {
………….
volatile long state; /* -1 unrunnable , 0 runnable , >0 stopped */
unsigned long flags; /* per process flags, defined below */
………….
}；
每个在Task向量表中登记的进程都有相应的进程状态和进程标志，是进行进程调度的重要依据。进程在执行了相应的进程调度操作后，会由于某些原因改变自身的状态和标志，也就是改变state和flags这两个数据项。进程的状态不同、标志位不同对应了进程可以执行不同操作。在Linux2.2.8版本的sched.h中定义了六种状态，十三种标志。
//进程状态
#define TASK_RUNNING 0
#define TASK_INTERRUPTIBLE 1
#define TASK_UNINTERRUPTIBLE 2
#define TASK_ZOMBIE 4
#define TASK_STOPPED 8
#define TASK_SWAPPING 16
它们的含义分别是：
TASK_RUNNING：正在运行的进程（是系统的当前进程）或准备运行的进程（在Running队列中，等待被安排到系统的CPU）。处于该状态的进程实际参与了进程调度。
TASK_INTERRUPTIBLE：处于等待队列中的进程，待资源有效时唤醒，也可由其它进程被信号中断、唤醒后进入就绪状态。
TASK_UNINTERRUPTIBLE：处于等待队列中的进程，直接等待硬件条件，待资源有效时唤醒，不可由其它进程通过信号中断、唤醒。
TASK_ZOMBIE：终止的进程，是进程结束运行前的一个过度状态（僵死状态）。虽然此时已经释放了内存、文件等资源，但是在Task向量表中仍有一个task_struct数据结构项。它不进行任何调度或状态转换，等待父进程将它彻底释放。
TASK_STOPPED：进程被暂停，通过其它进程的信号才能唤醒。正在调试的进程可以在该停止状态。
TASK_SWAPPING：进程页面被兑换出内存的进程。这个状态基本上没有用到，只有在sched.c的count_active_tasks（）函数中判断处于该种状态的进程也属于active的进程，但没有对该状态的赋值。
//进程标志位：
#define PF_ALIGNWARN 0x00000001
#define PF_STARTING 0x00000002
#define PF_EXITING 0x00000004
#define PF_PTRACED 0x00000010
#define PF_TRACESYS 0x00000020
#define PF_FORKNOEXEC 0x00000040
#define PF_SUPERPRIV 0x00000100
#define PF_DUMPCORE 0x00000200
#define PF_SIGNALED 0x00000400
#define PF_MEMALLOC 0x00000800
#define PF_VFORK 0x00001000
#define PF_USEDFPU 0x00100000
#define PF_DTRACE 0x00200000
其中PF_STARTING没有用到。
PF_MEMEALLOC和PF_VFORK这两个标志位是新版本中才有的。
各个标志位的代表着不同含义，对应着不同调用：
PF_ALIGNWARN 标志打印“对齐”警告信息，只有在486机器上实现
PF_STARTING 进程正被创建
PF_EXITING 标志进程开始关闭。
在do_exit()时置位。
current->flags |= PF_EXITING
用于判断是否有效进程。
在nlmclnt_proc()(在fs\lockd\clntproc.c)，如果current_flag为PF_EXITING，则进程由于正在退出清除所有的锁，将执行异步RPC 调用。
PF_PTRACED 进程被跟踪标志，
在do_fork()时清位。
p->flags &= ~PF_PTRACED
当ptrace(0)被调用时置位，在进程释放前要清掉。
current->flags |= PF_PTRACED
在sys_trace()中判断
如果request为PTRACE_TRACEME，如是则将current_flag置为PF_PTRACED；
如果request为PTRACE_ATTACH，则将child_flag置为PF_PTRACED，给child发一个SIGSTOP信号;
如果request为PTRACE_DETACH ，则将child清除PF_PTRACED。
在syscall_trace()中判断current_flag如果为PF_TRACED和PF_TRACESYS,则current强行退出时的出错代码置为SIGTRAP并将状态置为STOPPED。
PF_TRACESYS 正在跟踪系统调用。
do_fork()时清位，在进程释放前要清掉。
在sys_trace()中判断request如果为PTRACE_SYSCALL，则将child->flags 置为 PF_TRACESYS；如为PTRACE_SYSCALL，则将child->flags 清除 PF_TRACESYS；然后唤醒child。如果request为PTRACE_SINGLESTEP（即单步跟踪），则将child_flag清除PF_TRACESYS,唤醒child。
PF_FORKNOEXEC 进程刚创建，但还没执行。
在do_fork()时置位。
p->flags |= PF_FORKNOEXEC
在调入格式文件时清位。
p->flags &= ~ PF_FORKNOEXEC
PF_SUPERPRIV 超级用户特权标志。
如果是超级用户进程则置位，用户特权设为超级用户，如是超级用户，在统计时置统计标志(accounting flag)为ASU。
PF_DUMPCORE 标志进程是否清空core文件。
Core文件由gdb进行管理，给用户提供有用信息，例如查看浮点寄存器的内容比较困难，事实上我们可以从内核文件里的用户结构中得到
Core文件格式如下图：
UPAGE
DATA
STACK
Core 文件结构
UPAGE是包含用户结构的一个页面，告诉gdb文件中现有内容所有寄存器也在 UPAGE中，通常只有一页。DATA存放数据区。STACK堆栈区
最小Core文件长度为三页（12288字节）
在task_struct中定义一个dumpable变量，当dumpable==1时表示进程可以清空core文件（即将core文件放入回收站），等于0时表示该进程不能清空core文件（即core文件以放在回收站中，不可再放到回收站中），此变量初值为1。
例如在调用do_aout_core_dump()时判断current->dumpable是否等于1（即判断该进程是否能将core文件放入回收站），如果等于1则将该变量置为0，在当前目录下建立一个core dump image ,在清空用户结构前，由gdb算出数据段和堆栈段的位置和使用的虚地址，用户数据区和堆栈区在清空前将相应内容写入core dump，将PF_DUMPCORE置位，清空数据区和堆栈区。
只有在aout_core_dump()内调用do_aout_core_dump(),而没有地方调用aout_core_dump()。对其它文件格式也是类似。
9、 PF_SIGNALED 标志进程被信号杀出。
在do_signal()中判断信号，如果current收到信号为SIGHUP, SIGINT, SIGIOT, SIGKILL, SIGPIPE, SIGTERM, SIGALRM, SIGSTKFLT, SIGURG, SIGXCPU, SIGXFSZ, SIGVTALRM, SIGPROF, SIGIO, SIGPOLL, SIGLOST, SIGPWR，则执行lock_kernel(),将信号加入current的信号队列，将current->flag置为PF_SIGNALED,然后执行do_exit()
PF_USEDFPU 标志该进程使用FPU，此标志只在SMP时使用。
在task_struct中有一变量used_math，进程是否使用FPU。
在CPU从prev切换到next时，如果prev使用FPU则prev的flag清除PF_USEDFPU。
prev->flags&=~PF_USEDFPU
在flush_thread()(arch\i386\kernel\process.c)、restore_i387_hard()、save_i387_hard()(arch\i386\kernel\signal.c)中，如果是SMP方式，且使用FPU则stts()，否则清除PF_USEDFPU。
current->flags &= ~PF_USEDFPU
在sys_trace()中如果request为PTRACE_SETFPREGS，则将child的used_math置为1，将child_flag清除PF_USEDFPU。
child->flags &= ~PF_USEDFPU
在SMP方式下进行跟踪时，判断是否使用FPU。
在跟踪时出现数学错误时清位。
current->flags &= ~PF_USEDFPU
PF_DTRACE 进程延期跟踪标志，只在m68k下使用。
跟踪一个trapping指令时置位。
current->flags |= PF_DTRACE
PF_ONSIGSTK 标志进程是否工作在信号栈，只在m68k方式下使用。
liunx 2.1.19版本中使用此标志位，而2.2.8版本中不使用。
在处理信号建立frame时如果sigaction标志为ONSTACK，则将current->flag置为PF_ONSIGSTK。
PF_MEMALLOC 进程分配内存标志。
linux 2.2.8版本中使用此标志位。
在kpiod()和kwpad()中置位。
tsk->flags |= PF_MEMALLOC
PF_VFORK linux 2.2.8版本中使用此标志位。
在copy_flags(unsigned long clone_flags, struct task_struct *p)，如果clone_flags为CLONE_VFORK，则将p的flags置为PF_VFORK。
在mm_release（）中将current ->flags清除PF_VFORK。
tsk->flags &= ~PF_VFORK
具体的分析由我组的另外同学进行。
Linux的各进程之间的状态转换的系统调用
我将参与Linux的各进程之间的状态转换的系统调用总结成一张流程图：
进程的创建：TASK_RUNNING
第一个进程在系统启动时创建，当系统启动的时候它运行在核心态，这时，只有一个进程：初始化进程。象所有其他进程一样，初始进程有一组用堆栈、寄存器等等表示的机器状态。当系统中的其他进程创建和运行的时候这些信息存在初始进程的task_struct数据结构中。在系统初始化结束的时候，初始进程启动一个核心进程（叫做init）然后执行空闲循环，什么也不做。当没有什么可以做的时候，调度程序会运行这个空闲的进程。这个空闲进程的task_struct是唯一一个不是动态分配而是在核心连接的时候静态定义的，为了不至于混淆，叫做init_task。
系统调用sys_fork 和sys_clone都调用函数do_fork（）（在kernel/fork.中定义）。
进程由do_fork()函数创建，先申请空间，申请核心堆栈；然后在Task向量表中找到空闲位置；在进行正式初始化以前，将新创建的进程的状态都置为TASK_UNINTERRUPTIBLE，以免初始化过程被打断；开始初始化工作，如初始化进程时钟、信号、时间等数据；继承父进程的资源，如文件、信号量、内存等；完成进程初始化后,由父进程调用wake_up_process()函数将其唤醒，状态变为TASK_RUNNING，挂到就绪队列run queue，返回子进程的pid。
// C:\SRCLNX\KERNEL\FORK.C
int do_fork(unsigned long clone_flags, unsigned long usp, struct pt_regs *regs)
{
为新进程申请PCB空间;
if (申请不到)
返回错误,退出;
为新进程申请核心堆栈;
if (核心堆栈申请不到)
返回错误,退出;
为新进程在Task向量表中找到空闲位置;
/*复制父进程current PCB中的信息，继承current的资源*/；
p = current;
在进行正式初始化以前，将新创建的进程的状态都置为TASK_UNINTERRUPTIBLE，以免初始化过程被打断,并置一些标志位.
/*为防止信号、定时中断误唤醒未创建完毕的进 程，将子进程的状态设成不可中断的*/
p->state = TASK_UNINTERRUPTIBLE;
/*跟踪状态和超级用户特权是没有继承性的，因为在root用户为普通用户创建进程时，出于安全考虑这个普通用户的进程不允许拥有超级用户特权。*/
p->flags &= ~(PF_PTRACED|PF_TRACESYS|PF_SUPERPRIV);
/*将进程标志设成初建，在进程第一次获得CPU时，内核将根据此标志进行一定操作*/
p->flags |= PF_FORKNOEXEC;
开始Task_struct的初始化工作，如初始化进程时钟、信号、时间等数据;
继承父进程所有资源:
拷贝父进程当前打开的文件;
拷贝父进程在VFS的位置;
拷贝父进程的信号量;
拷贝父进程运行的内存;
拷贝父进程的线程;
初始化工作结束，父进程将其将其唤醒,挂入running队列中，返回子进程的pid;
}
进程的调度（schedule()）：
处于TASK_RUNNING状态的进程移到run queue，会由schedule()按CPU调度算法在合适的时候选中，分配给CPU。
新创建的进程都是处于TASK_RUNNING状态，而且被挂到run queue的队首。进程调度采用变形的轮转法（round robin）。当时间片到时（10ms的整数倍），由时钟中断引起新一轮调度，把当前进程挂到run queue队尾。
所有的进程部分运行与用户态，部分运行于系统态。底层的硬件如何支持这些状态各不相同但是通常有一个安全机制从用户态转入系统态并转回来。用户态比系统态的权限低了很多。每一次进程执行一个系统调用，它都从用户态切换到系统态并继续执行。这时让核心执行这个进程。Linux中，进程不是互相争夺成为当前运行的进程，它们无法停止正在运行的其它进程然后执行自身。每一个进程在它必须等待一些系统事件的时候会放弃CPU。例如，一个进程可能不得不等待从一个文件中读取一个字符。这个等待发生在系统态的系统调用中。进程使用了库函数打开并读文件，库函数又执行系统调用从打开的文件中读入字节。这时，等候的进程会被挂起，另一个更加值得的进程将会被选择执行。进程经常调用系统调用，所以经常需要等待。即使进程执行到需要等待也有可能会用去不均衡的CPU事件，所以Linux使用抢先式的调度。用这种方案，每一个进程允许运行少量一段时间，200毫秒，当这个时间过去，选择另一个进程运行，原来的进程等待一段时间直到它又重新运行。这个时间段叫做时间片。
需要调度程序选择系统中所有可以运行的进程中最值得的进程。一个可以运行的进程是一个只等待CPU的进程。Linux使用合理而简单的基于优先级的调度算法在系统当前的进程中进行选择。当它选择了准备运行的新进程，它就保存当前进程的状态、和处理器相关的寄存器和其他需要保存的上下文信息到进程的task_struct数据结构中。然后恢复要运行的新的进程的状态（又和处理器相关），把系统的控制交给这个进程。为了公平地在系统中所有可以运行（runnable）的进程之间分配CPU时间，调度程序在每一个进程的task_struct结构中保存了信息。
policy 进程的调度策略：Linux有两种类型的进程：普通和实时。实时进程比所有其它进程的优先级高。如果有一个实时的进程准备运行，那么它总是先被运行。实时进程有两种策略：环或先进先出（round robin and first in first out）。在环的调度策略下，每一个实时进程依次运行，而在先进先出的策略下，每一个可以运行的进程按照它在调度队列中的顺序运行，这个顺序不会改变。
Priority 进程的调度优先级。也是它允许运行的时候可以使用的时间量（jiffies）。你可以通过系统调用或者renice命令来改变一个进程的优先级。
Rt_priority Linux支持实时进程。这些进程比系统中其他非实时的进程拥有更高的优先级。这个域允许调度程序赋予每一个实时进程一个相对的优先级。实时进程的优先级可以用系统调用来修改Coutner 这时进程可以运行的时间量（jiffies）。进程启动的时候等于优先级（priority），每一次时钟周期递减。
调度程序schedule()从核心的多个地方运行。它可以在把当前进程放到等待队列之后运行，也可以在系统调用之后进程从系统态返回进程态之前运行。需要运行调度程序的另一个原因是系统时钟刚好把当前进程的计数器(counter)置成了0。每一次调度程序运行它做以下工作：
（1）kernel work 调度程序运行bottom half handler并处理系统的调度任务队列。
（2）Current pocess 在选择另一个进程之前必须处理当前进程。
（3）如果当前进程的调度策略是环则它放到运行队列的最后。
（4）如果任务状态是TASK_INTERRUPTIBLE的而且它上次调度的时候收到过一个信号，它的状态变为TASK_RUNNING;
如果当前进程超时，它的状态成为RUNNING;
如果当前进程的状态为RUNNING则保持此状态;
不是RUNNING或者INTERRUPTIBLE的进程被从运行队列中删除。这意味着当调度程序查找最值得运行的进程时不会考虑这样的进程。
(5)Process Selection 调度程序查看运行队列中的进程，查找最值得运行的进程。如果有实时的进程（具有实时调度策略），就会比普通进程更重一些。普通进程的重量是它的counter，但是对于实时进程则是counter 加1000。这意味着如果系统中存在可运行的实时进程，就总是在任何普通可运行的进程之前运行。当前的进程，因为用掉了一些时间片（它的counter减少了），所以如果系统中由其他同等优先级的进程，就会处于不利的位置：这也是应该的。如果几个进程又同样的优先级，最接近运行队列前段的那个就被选中。当前进程被放到运行队列的后面。如果一个平衡的系统，拥有大量相同优先级的进程，那么回按照顺序执行这些进程。这叫做环型调度策略。不过，因为进程需要等待资源，它们的运行顺序可能会变化。
(6)Swap Processes 如果最值得运行的进程不是当前进程，当前进程必须被挂起，运行新的进程。当一个进程运行的时候它使用了CPU和系统的寄存器和物理内存。每一次它调用例程都通过寄存器或者堆栈传递参数、保存数值比如调用例程的返回地址等。因此，当调度程序运行的时候它在当前进程的上下文运行。它可能是特权模式：核心态，但是它仍旧是当前运行的进程。当这个进程要挂起时，它的所有机器状态，包括程序计数器(PC)和所有的处理器寄存器，必须存到进程的task_struct数据结构中。然后，必须加载新进程的所有机器状态。这种操作依赖于系统，不同的CPU不会完全相同地实现，不过经常都是通过一些硬件的帮助。
(7)交换出去进程的上下文发生在调度的最后。前一个进程存储的上下文，就是当这个进程在调度结束的时候系统的硬件上下文的快照。相同的，当加载新的进程的上下文时，仍旧是调度结束时的快照，包括进程的程序计数器和寄存器的内容。
(8)如果前一个进程或者新的当前进程使用虚拟内存，则系统的页表需要更新。同样，这个动作适合体系结构相关。Alpha AXP处理器，使用TLT（Translation Look-aside Table）或者缓存的页表条目，必须清除属于前一个进程的缓存的页表条目。
下面我就来总结一下进程创建以后到被杀死的整个进程生命周期中，状态可能在TASK_RUNNING、TASK_INTERRUPTIBLE、TASK_UNINTERRUPTIBLE 、TASK_STOPPED以及TASK_ZOMBLE之间转换的原因。
进程在TASK_RUNNING以及TASK_UNINTERRUPTIBLE、TASK_INTERRUPTIBLE之间转换：
获得CPU而正在运行的进程会由于某些原因，比如：申请不到某个资源，其状态会从TASK_RUNNING变为TASK_INTERRUPTIBLE或TASK_UNINTERRUPTIBLE的等待状态。同样在经历了某些情况，处于等待状态的进程会被重新唤醒，等待分配给CPU。状态为TASK_INTERRUPTIBLE的睡眠进程会被唤醒，回到TASK_RUNNING状态，重新等待schedule()分配给它CPU，继续运行，比如：当申请资源有效时，也可以由signal或定时中断唤醒。而状态为TASK_INTERRUPTIBLE的睡眠进程只有当申请资源有效时被唤醒，不能被signal、定时中断唤醒。
1.通过sleep_on()、interruptible_sleep_on()、sleep_on_timeout()、interruptible_sleep_on_timeout（）以及wake_up()、wake_up_process()、wake_up_interruptible()函数对进行的转换：
sleep_on():TASK_RUNNING->TASK_UNINTERRUPTIBLE
当拥有CPU的进程申请资源无效时，会通过sleep_on()，将进程从TASK_RUNNING切换到TASK_UNINTERRUPTIBLE状态。sleep_on()函数的作用就是将current进程的状态置成TASK_UNINTERRUPTIBLE,并加到等待队列中。
一般来说引起状态变成TASK_UNINTERRUPTIBLE的资源申请都是对一些硬件资源的申请，如果得不到这些资源，进程将不能执行下去，不能由signal信号或时钟中断唤醒，而回到TASK_RUNNING状态。
我们总结了这种类型的转换原因有：
（1）对某些资源的操作只能由一个进程进行，所以系统对该项资源采用上锁机制。在申请该项资源时，必须先申请资源的锁，如果已经被别的进程占用，则必须睡眠在对该锁的等待队列上。而且这种睡眠不能被中断，必须等到得到了资源才能继续进行下去。
如：
对网络连接表锁（Netlink table lock）的申请, sleep_on(&nl_table_wait)；
对交换页进行I/O操作的锁的申请, sleep_on(&lock_queue)；
对Hash表操作的锁的申请, sleep_on(&hash_wait)；
在UMSDOS文件系统创建文件或目录时，必须等待其他同样的创建工作结束,sleep_on (&dir->u.umsdos_i.u.dir_info.p);
（2）某些进程在大部分时间处于睡眠状态，仅在需要时被唤醒去执行相应的操作，当执行完后，该进程又强制去睡眠。
如：
wakeup_bdflush（)是对dirty buffer进行动态的响应，一旦该进程被激活，就将一定数量的dirty buffer写回磁盘，然后调用sleep_on(&bdflush_done),又去睡眠。
interruptible_sleep_on():TASK_RUNNING->TASK_INTERRUPTIBLE
与sleep_on()函数非常地相象，当拥有CPU的进程申请资源无效时，会通过interruptible_sleep_on()，将进程从TASK_RUNNING切换到TASK_INTERRUPTIBLE状态。interruptible_sleep_on()函数的作用就是将current进程的状态置成TASK_INTERRUPTIBLE,并加到等待队列中。
处于TASK_INTERRUPTIBLE状态的进程可以在资源有效时被wake_up()、wake_up_interruptible()或wake_up_process()唤醒，或收到signal信号以及时间中断后被唤醒。
进行这种转换的原因基本上与sleep_on()相同，申请资源无效时进程切换到等待状态。与之不同的是处于interruptible_sleep_on()等待状态的进程是可以接受信号或中断而重新变为running状态。所以可以认为对这些资源的申请没有象在sleep_on()中资源的要求那么严格，必须得到该资源进程才能继续其运行下去。
sleep_on_timeout():TASK_RUNNING->TASK_UNINTERRUPTIBLE
sleep_on_timeout(&block.b_wait, 30*HZ);
interruptible_sleep_on_timeout（）：TASK_RUNNING->TASK_INTERRUPTIBLE
虽然在申请资源或运行中出现了某种错误，但是系统仍然给进程一次重新运行的机会。调用该函数将进程从TASK_RUNNING切换到TASK_INTERRUTIBLE状态，并等待规定的时间片长度,再重新试一次。
如：在smb_request_ok 中产生了连接失败的错误，会在sem_retry()中给一次重新连接的机会。//interruptible_sleep_on_timeout(&server->wait, 5*HZ)；
wake_up():TASK_UNINTERRUPTIBLE-> TASK_RUNNING;
TASK_INTERRUPTIBLE-> TASK_RUNNING
处于TASK_UNINTERRUPTIBLE状态的进程不能由signal信号或时钟中断唤醒，只能由wake_up()或wake_up_process()唤醒。wake_up()函数的作用是将wait_queue中的所有状态为TASK_INTERRUPTIBLE或TASK_UNINTERRUPTIBLE的进程状态都置为TASK_RUNNING,并将它们都放到running队列中去，即唤醒了所有等待在该队列上的进程。
void wake_up(struct wait_queue **q)
{
struct wait_queue *next;
struct wait_queue *head;
if (!q || !(next = *q))
return;
head = WAIT_QUEUE_HEAD(q);
while (next != head) {
struct task_struct *p = next->task;
next = next->next;
if (p != NULL) {
if ((p->state == TASK_UNINTERRUPTIBLE) ||
(p->state == TASK_INTERRUPTIBLE))
wake_up_process(p);
}
if (!next)
goto bad;
}
return;
bad:
printk("wait_queue is bad (eip = %p)\n",
__builtin_return_address(0));
printk(" q = %p\n",q);
printk(" *q = %p\n",*q);
}
wake_up()在下列情况下被调用：
这个函数通常在资源有效时调用，资源锁已经被释放，等待该资源的所有进程都被置为TASK_RUNNING状态，移到run queue，重新参与调度，对这一资源再次竞争。这时又会有某个进程竞争到了该项资源，而其他的进程在申请失败后，又回到TASK_UNINTERRUPTIBLE或TASK_INTERRUPTIBLE状态。
如：
网络连接表锁（Netlink table lock）释放后,唤醒等待该锁的所有睡眠进程 wake_up(&nl_table_wait)；
对交换页进行I/O操作的锁释放后,唤醒等待该锁的所有睡眠进程, wake_up(&lock_queue)；
对Hash表操作的锁释放后,唤醒等待该锁的所有睡眠进程，wake_up(&hash_wait)；
在UMSDOS文件系统创建文件或目录工作结束后,唤醒其他由于等待它创建结束而睡眠的进程， wake_up (&dir->u.umsdos_i.u.dir_info.p)；
唤醒睡眠进程执行某些操作：
如：
bd_flush()函数要将一些dirty buffer写回磁盘，就调用wake_up(&bdflush_done)，唤醒正在睡眠的wakeup_bdflush（)进程去处理写回。
wake_up_process()：TASK_UNINTERRUPTIBLE-> TASK_RUNNING;
TASK_INTERRUPTIBLE-> TASK_RUNNING
wake_up_process()函数的作用是将参数所指的那个进程状态从TASK_INTERRUPTIBLE,TASK_UNINTERRUPTIBLE变为TASK_RUNNING,并将它放到running队列中去。
void wake_up_process(struct task_struct * p)
{
unsigned long flags;
/*
* We want the common case fall through straight, thus the goto.
*/
spin_lock_irqsave(&runqueue_lock, flags);
p->state = TASK_RUNNING;
if (p->next_run)
goto out;
add_to_runqueue(p);
spin_unlock_irqrestore(&runqueue_lock, flags);
reschedule_idle(p);
return;
out:
spin_unlock_irqrestore(&runqueue_lock, flags);
}
这个函数的实现机制与wake_up()的不同在于，它只能唤醒某一个特定的睡眠进程，而wake_up()是唤醒整个等待队列的睡眠进程。所以，它的唤醒的原因与wake_up()也有一定的区别，除了由于wake_up()对它的调用之外，它唤醒进程并不是由于资源有效造成的，唤醒的进程也不是因等待资源有效而睡眠的进程。有以下几种情况：
父进程对子进程的唤醒：
如：
在sys_ptrace()中当收到的跟踪请求为：PTRACE_CONT（在处理完信号后继续）；PTRACE_KILL（将子进程杀出）；PTRACE_SINGLESTEP（对子进程进行单步跟踪）；PTRACE_DETACH的时候，都会在处理结束时，唤醒子进程，给子进程一个运行的机会。
在do_fork()中，新建进程初始化完毕，会由父进程唤醒它，将该进程移到run queue中，置状态为TASK_RUNNING。
当需要的时候唤醒某个睡眠的系统调用，进行处理：
如：
kswapd_process页面交换进程，通常是处于睡眠状态的，当某个进程需要更多的内存，而调用try_to_free_pages（）时，就会唤醒kswapd_process页面交换进程，调入更多的内存页面。
收到信号所进行的相应处理：
如：
某一进程的时间片到了，process_timeout()会调用wake_up_process()唤醒该进程；
收到某些signal信号:处于STOPPED状态的进程收到SIGKILL或SIGCONT会被唤醒（注：处于STOPPED状态的进程不能被wake_up()唤醒）；以及收到某些非实时信号，不需加到signal队列中去，处于TASK_INTERRUPTIBLE的进程有机会被唤醒。
资源有效时，wake_up()对整个等待队列的唤醒是通过对每个等待队列上的进程调用wake_up_process()实现的。
wake_up_interruptible（）：TASK_INTERRUPTIBLE-> TASK_RUNNING
将wait_queue中的所有状态为 TASK_INTERRUPTIBLE的进程状态都置为TASK_RUNNING,并将它们都放到running queue中去。
这个函数通常在send_sig(发出信号)后调用,以使信号发出后能及时得到响应，或者当空闲下来时，希望检查一下是否有收到有效信号的能运行的进程时，也可以调用这个函数，如：
在进程退出前调用notify_parent(),给父进程send_sig（）后，将调用wake_up_interruptible （），使信号能够得到及时的响应。
usr\src\linux\KERNEL\EXIT.C 中定义了
void notify_parent(struct task_struct * tsk, int signal)
{
send_sig(signal, tsk->p_pptr, 1);
wake_up_interruptible(&tsk->p_pptr->wait_chldexit);
}
当某一进程要结束时，它可以通过调用notify_parent(current, current->exit_signal)通知父进程以唤醒睡眠在wait_chldexit上的父进程
2. Semaphores（信号灯）
信号量用于生成锁机制,避免发生数据不一致。
信号量最简单的形式就是内存中一个位置，它的取值可以由多个进程检验和设置。检验和设置的操作，至少对于关联的每一个进程来讲，是不可中断或者说有原子性：只要启动就不能中止。检验和设置操作的结果是信号灯当前值和设置值的和，可以是正或者负。根据测试和设置操作的结果，一个进程可能必须睡眠直到信号灯的值被另一个进程改变。信号灯可以用于实现临界区域（critical regions），就是重要的代码区，同一时刻只能有一个进程运行。
对信号灯的操作是通过以下两组基本函数实现的：
1．void __up(struct semaphore *sem) ：TASK_UNINTERRUPTIBLE-> TASK_RUNNING;
TASK_INTERRUPTIBLE-> TASK_RUNNING
int __do_down(struct semaphore * sem, int task_state)由以下两个函数调用，分别转换到不同的等待状态：
(1)int __down_interruptible (struct semaphore * sem)：
TASK_RUNNING ->TASK_INTERRUPTIBLE;
(2)void __down(struct semaphore * sem):
TASK_RUNNING ->TASK_UNINTERRUPTIBLE；
2. extern inline void up(struct semaphore * sem)
extern inline void down(struct semaphore * sem)；
extern inline int down_interruptible(struct semaphore * sem)；
Linux信号量是通过两路counter变量实现的：当进程由于申请不到临界区资源而睡眠时，会将semaphore结构中的”count”变量值原子地递减1，进程睡眠等待临界区资源的释放；而当up()函数唤醒睡眠等待进程时，如果”count”变量值小于0，会将semaphore结构中的” waking”变量值原子地递增1，唤醒睡眠进程。虽然所有等待进程都被唤醒。但只有首先得到” waking”的进程才能得到信号量，继续运行下去，其他进程仍然回到最初的等待状态。
Linux定义信号灯结构是：
struct semaphore {
atomic_t count;
int waking;
struct wait_queue * wait;
};
信号灯的值初始化为一个宏定义的结构MUTEX的值{count=1，waking=0，wait=NULL}。
void __up(struct semaphore *sem)：
占有临界区资源的进程，调用__up()释放资源。在__up()函数中，调用wake_one_more ()函数，原子地读sem->count, 如果sem->count <=0,则sem->waking ++,并唤醒所有等待在该sem-->wait上的进程。
void __up(struct semaphore *sem)
{
wake_one_more(sem);
wake_up(&sem->wait);
}
int __do_down(struct semaphore * sem, int task_state):
申请临界区资源的进程会通过调用__do_down()来竞争资源。在__do_down()函数中，调用waking_non_zero(struct semaphore *sem)或waking_non_zero_interruptible(struct semaphore *sem)抢占临界区资源，如果抢占到，则将当前进程置为TASK_RUNNING,否则将当前进程的状态置为task_state，并处于循环等待状态。
进程通过waking_non_zero（）来竞争临界区资源，在该函数中判断sem-->waking的值，如果sem-->waking 大于0,sem->waking -- 并返回1，否则返回0。
int __do_down(struct semaphore * sem, int task_state)
{
struct task_struct *tsk = current;
struct wait_queue wait = { tsk, NULL };
int ret = 0 ;
tsk->state = task_state;
add_wait_queue(&sem->wait, &wait); /*将进程加入到等待队列*/
for (;;)
{
if (waking_non_zero(sem)) /* 是否已经被唤醒 */
break ; /* 是的，跳出循环 */
if ( task_state == TASK_INTERRUPTIBLE
&& (tsk->signal & ~tsk->blocked)
/* 如果进程状态为TASK_INTERRUPTIBLE，且收到信号量，并未被屏蔽*/
)
{
ret = -EINTR ; /* 中断 */
atomic_inc(&sem->count) ; /* 放弃down操作，原子递增信号量的count值 */
break ;
}
schedule(); /* 重新调度 */
tsk->state = task_state; /*未能竞争到信号量的进程重新置成执行down操
作前的状态*/
}
tsk->state = TASK_RUNNING; /*竞争到信号量的进程置为TASK_RUNNING状态*/
remove_wait_queue(&sem->wait, &wait);/*将进程从等待队列中删除*/
return(ret) ;
} /* __do_down */
其中_do__down()又分别由__down()和__do_down()调用，进程转换到不同状态。
void __down(struct semaphore * sem): TASK_RUNNING ->TASK_UNINTERRUPTIBLE；
void __down(struct semaphore * sem)
{
__do_down(sem,TASK_UNINTERRUPTIBLE) ;
}
int __down_interruptible (struct semaphore * sem)： TASK_RUNNING ->TASK_INTERRUPTIBLE;
int __down_interruptible(struct semaphore * sem)
{
return(__do_down(sem,TASK_INTERRUPTIBLE)) ;
}
在Linux中定义了两种不同的信号灯：
（1）定义在某个数据结构上：
在linux系统中有很多数据结构中定义了这样的信号灯，来控制对这个数据结构的资源访问，比如不允许对某个内存单元进行多进程访问，就通过定义在该内存单元上的某个信号灯mmap_sem进行__up()、_down()、up()、down()操作。
如：
struct mm_struct中有mmap_sem信号灯；
struct inode中有i_sem、i_atomic_write信号灯；
struct nlm_file中有f_sema信号灯；
struct nlm_host中有h_sema信号灯；
struct superblock中有s_vfs_rename_sem信号灯；
struct vfsmount中有mnt_dquot.semaphore信号灯；
struct task_struct中有vfork_sem信号灯；//注：这个信号灯在2.0.36版本是没有的，新版本2.2.8中才有的，用于vfork()。
struct unix_opt中有readsem信号灯；
struct smb_sb_info中有sem信号灯；
申请这些数据结构中的临界区资源，就要进行相应的信号灯操作。
（2）定义在全局的单独信号灯数据：
还有一些单独的全局信号灯，它们并不属于某一个数据结构，而是系统定义的全局静态的信号灯，可能有多个进程对这种不属于某个特定数据结构的全局临界资源的申请，则系统通过这些全局信号灯来分配资源。
如：
nlm_file_sema；
nlmsvc_sema；
lockd_start；
read_sem；
nlm_host_sema；
read_semaphore；
uts_sem
mount_sem；
cache_chain_sem；
rpciod_sema；
rpciod_running；
mfw_sema；
firewall_sem；
我们来分析一个例子说明信号灯的操作。例如对文件的写操作，我们假设有许多协作的进程对一个单一的数据文件进行写操作。我们希望对文件的访问必须严格地协调。因此这里就利用了inode结构上定义的信号灯inode->i_sem。
在 /usr/src/linux/mm/filemap.c中：
static int filemap_write_page(struct vm_area_struct * vma,
unsigned long offset,
unsigned long page)
{
int result;
struct file file;
struct inode * inode;
struct buffer_head * bh;
……………
down(&inode->i_sem);
result = do_write_page(inode, &file, (const char *) page, offset);
up(&inode->i_sem);
return result;
}
在该文件写操作的代码中，加入两个信号灯操作，第一个down(&inode->i_sem)检查并把信号灯的值减小，第二个up(&inode->i_sem)检查并增加它。访问文件的第一个进程试图减小信号灯的数值，如果成功，信号灯的count取值成为0。这个进程现在可以继续运行并使用数据文件。但是，如果另一个进程需要使用这个文件，现在它试图减少信号灯的count数值，它会失败因为结果会是-1。这个进程会被挂起直到第一个进程处理完数据文件。当第一个进程处理完数据文件，它会增加信号灯的waking数值成为1。现在等待进程会被唤醒，这次它减小信号灯的尝试会成功。
每一个独立的信号灯操作可能都需要维护一个调整动作。Linux至少为每一个进程的每一个信号灯数组都维护一个sem_undo的数据结构。如果请求的进程没有，就在需要的时候为它创建一个。这个新的sem_undo数据结构同时在进程的task_struct数据结构和信号灯队列的semid_ds数据结构的队列中排队。对信号灯队列中的信号灯执行操作的时候，和这个操作值相抵消的值加到这个进程的sem_undo数据结构的调整队列这个信号灯的条目上。所以，如果操作值为2，那么这个就在这个信号灯的调整条目上增加-2。
当进程被删除，比如退出的时候，Linux遍历它的sem_undo数据结构组，并实施对于信号灯数组的调整。如果删除信号灯，它的sem_undo数据结构仍旧停留在进程的task_struct队列中，但是相应的信号灯数组标识符标记为无效。这种情况下，清除信号灯的代码只是简单地废弃这个sem_undo数据结构。
3.锁机制
lock_…（）；
unlock_…（）；
wait_on_…（）：TASK_RUNNING ->TASK_UNINTERRUPTIBLE；
进程在RUNNING,WAITING状态间转换时，锁机制也是Linux中解决进程之间共享资源的一个方法。锁就是在资源的结构定义中加入一个锁成员，或为一个标志位,它的取值可以由多个进程检验和设置。锁可以用于实现对资源的共享竞争。具体来说当一个进程占用一个资源时，先对其上锁，然后再进行相关的操作，如果这时别的进程也要用这个资源，则必须等待这个锁被解开后，才可以进行下去。
但是，锁仅在某些数据结构和资源申请中才会用到，进程在申请某种特定资源时，会调用相应的__wait_on_… 函数来判断是否该资源已经被上锁，如果未上锁或已被解锁，则分配资源给进程，否则进程加入到等待队列中去。这种类型的申请有：__wait_on_dquot、__wait_on_buffer、__wait_on_inode、__wait_on_page、__wait_on_super等。
值得注意的是，如果申请不到这种资源，进程的状态都是转变成TASK_UNINTERRUPTIBLE。
定义锁的方式有两种：
专门的某项数据结构：
如：Superblock的数据结构中专门定义了锁数据项：s_lock；
置数据结构中某一项的某个标志位为锁标志：
如：
struct inode中定义了i_state的数据项，通过判断i_state 是否置了 I_LOCK，来判断该inode节点是否上锁。（2.2.8版本中定义）//注意：在2.2.0.34版本中是采用了专门的数据项i_lock来进行锁操作的。
struct buffer_head 中定义了b_state的数据项，通过判断b_state是否置了 BH_Lock位,来判断该缓冲区头是否上锁。
struct dquot中定义了dq_flags的数据项，通过判断dq_flags是否置了DQ_LOCKED位,来判断该dquot是否上锁。
struct page中定义了flags的数据项，通过判断flags是否置了PG_locked 位,来判断该页是否上锁。//注：程序中一般采用PageLocked(page)函数来判断是否上锁。
我们以buffer_head的加锁和解锁操作为例来解释一下通过锁机制进行的状态转换，在这里要申请buffer_head 资源，先要申请到锁，buffer_head的加锁和解锁就是通过置位和复位bh->b_state来实现的：
//申请资源时将该缓冲区上锁，置锁位，如果申请不到，睡眠在等待队列上，等待该锁的释放。
extern inline void lock_buffer(struct buffer_head * bh)
{
while (set_bit(BH_Lock, &bh->b_state))
__wait_on_buffer(bh);
}
//资源释放时，清该缓冲区锁位，并唤醒等待队列上的进程，参与竞争资源。
void unlock_buffer(struct buffer_head * bh)
{
......
clear_bit(BH_Lock, &bh->b_state);
wake_up(&bh->b_wait);
......
}
//检验该锁位是否已经置位
static inline int buffer_locked(struct buffer_head * bh)
{
return test_bit(BH_Lock, &bh->b_state);
}
//在 \USR\SRC\LINUX\FS\BUFFER.C中定义了__wait_on_buffer(stuct buffer_head * bh);该函数判断该buffer_head是否已经被上了锁，如果是，则不能得到资源，将进程置成TASK_UNINTERRUPTIBLE，加入bh-->b_wait队列中，调用schedule()转去调用其他的进程，否则，分配给资源，进程进入TASK_running状态。
void __wait_on_buffer(struct buffer_head * bh)
{
struct wait_queue wait = { current, NULL };
bh->b_count++;
add_wait_queue(&bh->b_wait, &wait);/*进程加入到等待锁的队列*/
repeat:
run_task_queue(&tq_disk);
current->state = TASK_UNINTERRUPTIBLE;/*进程状态置为TASK_UNINTERRUPTIBLE*/
if (buffer_locked(bh)) {
schedule(); /*如果申请不到锁，重新调度CPU*/
goto repeat;
}
remove_wait_queue(&bh->b_wait, &wait);/*进程从等待队列中删除*/
bh->b_count--;
current->state = TASK_RUNNING; /*进程状态置为TASK_ RUNNING*/
}
4. 管道（流）
管道做为系统的特殊设备文件,可以是内存方式的,也可以是外存方式的。管道的传输一般是单向的,即一个管道一向,若两个进程要做双向传输则需要2个管道.管道生成时即有两端,一端为读,一端为写,两个进程要协调好,一个进程从读方读,另一个进程向写方写。管道的读写使用流设备的读写函数,即:read(),write.管道的传输方式为FIFO,流方式的.不象消息队列可以按类型读取.管道分为有名管道和无名管道：
1． 有名管道
一般为系统特殊文件方式,使用的进程之间不一定要有父子关系或兄弟关系.
2． 无名管道
一般为内存方式,使用的进程之间一定要有父子关系或兄弟关系.
Linux shell允许重定向。例如：
$ ls | pr | lpr
把列出目录文件的命令ls的输出通过管道接到pr命令的标准输入上进行分页。最后，pr命令的标准输出通过管道连接到lpr命令的标准输入上，在缺省打印机上打印出结果。管道是单向的字节流，把一个进程的标准输出和另一个进程的标准输入连接在一起。没有一个进程意识到这种重定向，和它平常一样工作。是shell建立了进程之间的临时管道。在Linux中，使用指向同一个临时VFS INODE节点（本身指向内存中的一个物理页）的两个file数据结构来实现管道。当写进程向管道中写的时候，字节拷贝到了共享的数据页，当从管道中读的时候，字节从共享页中拷贝出来。Linux必须同步对于管道的访问。必须保证管道的写和读步调一致，它使用锁、等待队列和信号。
运用管道方式进行通讯的进程，由于都是调用sleep_on_interruptible,因此都是睡眠在TASK_INTERRUPTIBLE状态的。
管道结构的定义在include\linux\pipe_fs_i.h中，
struct pipe_inode_info {
struct wait_queue * wait;
char * base;
unsigned int start;
unsigned int len;
unsigned int lock; //用到了锁
unsigned int rd_openers;
unsigned int wr_openers;
unsigned int readers;
unsigned int writers;
};
对管道的操作主要有读和写两种：
1．向一个管道写pipe_write()：
在\fs\pipe.c中定义了static int pipe_write(struct inode * inode, struct file * filp, const char * buf, int count)；
实现机制：当写进程向管道写的时候，它使用标准的write库函数。这些库函数传递的文件描述符是进程的file数据结构组中的索引，每一个都表示一个打开的文件，在这种情况下，是打开的管道。Linux系统调用使用描述这个管道的file数据结构指向的write例程。这个write例程使用表示管道的VFS INODE节点存放的信息，来管理写的请求。如果有足够的空间把所有的字节都写导管到中，只要管道没有被读进程锁定，Linux为写进程上锁，并把字节从进程的地址空间拷贝到共享的数据页。如果管道被读进程锁定或者空间不够，当前进程睡眠，并放在管道INODE节点的等待队列中，并调用调度程序，运行另外一个进程。它是可以中断的，所以它可以接收信号。当管道中有了足够的空间写数据或者锁定解除，写进程就会被读进程唤醒。当数据写完之后，管道的VFS INODE 节点锁定解除，管道INODE节点的等待队列中的所有读进程都会被唤醒。
2．从一个管道读Pipe_read()：
在\fs\pipe.c中定义了static int pipe_read(struct inode * inode, struct file * filp, char * buf, int count)；
实现机制：从管道中读取数据和写数据非常相似。进程允许进行非阻塞的读（依赖于它们打开文件或者管道的模式），这时，如果没有数据可读或者管道被锁定，会返回一个错误。这意味着进程会继续运行。另一种方式是在管道的INODE节点的等待队列中等待，直到写进程完成。如果管道的进程都完成了操作，管道的INODE节点和相应的共享数据页被废弃。
进程在TASK_RUNNING和TASK_STOPPED间的转换：
1．进程从TASK_RUNNING->TASK_STOPPED的转换：
TASK_STOPPED状态是一种暂停状态，和TASK_STOPPED状态配合工作的标志为PF_PTRACED和PF_TRACESYS，分别表示被跟踪和正在跟踪系统调用，一个是被动的，一个是主动的。
进程可通过两种途径进入TASK_STOPPED状态：
1)．受其它进程的syscall_trace（）系统调用的控制而暂时将CPU交给控制进程。
在调用syscall_trace（）之前必须先调用sys_ptrace()（简称ptrace（）），进行跟踪系统调用之前的准备工作。只有调用sys_ptrace()后，current的PF_PTRACED和PF_TRACESYS标志都已置位，跟踪和被跟踪的关系都已明确，再调用syscall_trace（）才能真正使进程转入STOPPED状态。
syscall_trace（）实现步骤：
（1）检验是否调用过ptrace（）做过准备，没有则返回；
（2）置状态STOPPED ，通知父进程，子进程状态已变；
（3）进行CPU重新调度，将current进程从runqueue删除。
（4）如果exit_code非空，将它的值作为接收到的信号放到signal中。若是SIGTRAP
则current进程将一直处于stopped，直到收到其它信号。
sys_ptrace()实现步骤：
（1）如果request == PTRACE_TRACEME，则有进程要求跟踪current进程:
若current进程已被其它进程跟踪返回；
否则置current进程已被进程跟踪的标记；
（2）如果current进程想跟踪其它进程:
a.不能跟踪init进程；
b.找pid对应的进程child，找不到返回出错；
c.如果request为PTRACE_ATTACH
如果current进程试图ATTACH自己，出错；
如果试图attach的进程child已被attach，出错；
否则 child->flags |= PF_PTRACED;做上标记，child已被attach；如果child
不是current的子进程，将它变成current的子进程；并且发SIGSTOP信号，暂
停它。
（3）进行其他合法性检查；
（4）判断request，执行相应操作：
case PTRACE_SYSCALL:继续执行，在下一个系统调用返回处停下。
case PTRACE_CONT:发信号后重新开始运行。
如果request == PTRACE_SYSCALL，置child标志位PF_TRACESYS;
否则 清child标志位PF_TRACESYS，以防止重新运行后因历史原因在下一个
系统调用返回处停下；
唤醒child进程。
case PTRACE_KILL: 想要结束child进程，唤醒child进程，并在退出信息
exit_code中存放SIGKILL信号。
case PTRACE_SINGLESTEP: 进行单步运行环境设置。
case PTRACE_DETACH: 恢复child进程的自由。清跟踪标志，并唤醒child进程 恢复child进程的原始亲属关系。
2)．收到要求它暂停的信号。
另一种进入STOPPED状态的方法是信号，SIGSTOP信号使自由的current进程，打上PF_PTRACED标记，并将它转入STOPPED状态。do_signal在检查进程收到的信号时，若发现current进程已打上PF_PTRACED标记，则除收到的SIGKILL信号的情况外，current进程都将马上进入STOPPED状态。
do_signal（）实现步骤：
（1）current进程已打上PF_PTRACED标记，则除收到的SIGKILL信号的情况外，进程都将进入TASK_STOPPED状态，通知父进程，并重新调度；
（2）如果收到信号SIGSTOP:如果当前进程标志位不是PF_PTRACED，则置当前进程状态为TASK_STOPPED; 通知父进程，并重新调度；
2.进程从TASK_STOPPED->TASK_RUNNING的转换:
从TASK_STOPPED状态转到TASK_RUNNING状态通过“信号唤醒”。当有SIGKILL或SIGCONT信号发给TASK_STOPPED状态下的进程时，进程将被wake_up_process()唤醒。
int send_sig(unsigned long sig,struct task_struct * p,int priv)
{
………;
save_flags(flags); cli(); /*保存标志，关中断*/
if ((sig == SIGKILL) || (sig == SIGCONT)) {
if (p->state == TASK_STOPPED)
wake_up_process(p); /*若进程p的状态是STOPPED，并且所发送的信号是SIGKILL和SIGCONT，将p状态赋成RUNNING，并挂到run-queue*/
p->exit_code = 0; /*退出信息没有*/
p->signal &= ~( (1<<(SIGSTOP-1)) | (1<<(SIGTSTP-1)) |
(1<<(SIGTTIN-1)) | (1<<(SIGTTOU-1)) ); /*处理过信号后，将p的可能曾接受到的SIGSTOP、SIGTSTP、SIGTTIN、SIGTTOU信号清掉*/
}
if (sig == SIGSTOP || sig == SIGTSTP || sig == SIGTTIN || sig == SIGTTOU)
p->signal &= ~(1<<(SIGCONT-1)); /*若信号为SIGSTOP、SIGTSTP、SIGTTIN、SIGTTOU中的任一种，将p可能曾接受到的SIGCONT信号清掉*/
restore_flags(flags); /*恢复CPU标志同时打开中断*/
generate(sig,p); /*登记不能立即被处理的信号。*/
return 0;
}
进程的终止:从TASK_RUNNING->TASK_ZOMBIE的转换
进程终止由可终止进程的系统调用通过调用do_exit（）实现，do_exit（）终止current进程，首先为current进程做上PF_EXITING的标记，释放current进程的存储管理信息、文件系统、文件信息、信号响应函数指针数组，将状态置成TASK_ZOMBIE，通知current的父进程，最后进行重新调度。do_exit()带一个参数code，用于传递终止进程的原因。
do_exit(long code)流程：
（1）如果进程在中断服务程序中调用do_exit（），则打印提示信息
（2）记录进程的记帐信息
（3）进程标志置为PF_EXITING
（4）释放定时器链表
（5）释放临界区数据
（6）将消息队列中和current进程有关项删除
（7）释放进程的存储管理信息
（8）释放进程已打开文件的信息
（9）释放进程的文件系统
（10）释放进程的信号响应函数指针数组等管理信息
（11）释放进程的LDT
（12）进程状态置为TASK_ZOMBIE
（13）置上退出信息，通知所有进程亲戚，它要退出了#
（14）exec_domain结构共享计数减1， binfmt结构共享计数减1
（15）重新调度，将current进程从run-queue中删除，交出CPU
exit_notify （）函数向所有和current进程有关的进程发相应的消息，以便它们开展工作，exit_notify （）还判断cueernt进程所在组是否会因current进程的退出而悬空，如果悬空并且组内有stopped状态的进程则发信号；同时进行一系列的指针调整，调整因current进程的死亡引起的进程关系转变。
exit_notify （）流程：
将所有原始进程为current的进程变成init进程的孙子。
如果父进程和current进程不在同一组，但在同一session内并且current进程组内所有进程的父进程和它在同一组，也就是说，current进程所在组会因current的退出而悬挂，同时current进程所在组内有stopped进程，就向整个组发SIGHUP和SIGCONT信号。
通知父进程进程死了。
调整所有current进程的子进程的父进程指针，将它们挂到它们的原始进程下，
将以往的跟踪被跟踪历史清除，调整它和新的兄弟的关系；检查每一个current
进程的子进程所在的组是否会悬挂，如果子进程和current进程不在同一组，并
且这个组已悬挂，组内有stopped的进程，就向组员发SIGHUP 和 SIGCONT信号。 （5）如果current进程是session的主管， 就和它所控制的tty脱离，向current
进程显示终端所在的组发SIGHUP 和 SIGCONT信号。
进程直接或间接地调用do_exit() 后，进程进入ZOMBIE状态，还有一块PCB未释放。PCB的释放必须由它的父进程执行，当父进程调用sys_wait4（）时释放进入ZOMBIE状态的子进程的PCB。
具体调用do_exit()的函数有以下情况：
具体对应的系统调用出错，不得不终止进程，如：
do_page_fault（）：这个系统调用处理页面错误，它找到页面地址，出错原因，并将它转入相应的处理函数。当发生越界（out of memory）等bad page的致命错误。
sys_sigreturn（）：一般情况下sys_sigreturn（）将sigcontext的内容保存到堆栈中，保存过程中当发现段寄存器越界了，这个致命错误就将导致进程结束。
setup_frame（）：setup_frame（）建立信号响应函数的运行的环境，保存当前寄存器，将相应寄存器赋上信号响应函数的信息。在具体设定之前首先进行存储条件检验，不满足就不得不结束进程。
save_v86_state（）：save_v86_state（）保存虚拟86模式下（virtual 86 mode）的信息，如果进程PCB中vm86的信息为空的，无法继续进行操作，只能结束进程。
（2）其他终止进程的情况，通过调用以下函数实现终止：
sys_exit（）：是一个系统调用，实现终止调用它的当前进程。
sys_reboot()：sys_reboot()只能被特权级用户调用，用于重新启动系统。
do_signal（）：do_signal（）是处理信号的一个函数。检查current进程每一个接收到的signal，如果是结束进程的信号，结束进程进行相应处理。
die_if_kernel（）。
1.2 Threads Implementation
Threads can be implemented in one of two ways:
1. User-level threads:
There is no kernel support for multi-threaded processes. Hence, the kernel only has a single-threaded process abstraction, but multi-threaded processes are implemented in a library of procedures linked with application programs. The kernel has no knowledge of lightweight processes (threads), and therefore cannot schedule them independently. A threads run-time library organizes the scheduling of threads. A thread would block the process and therefore all threads within it if it made a blocking system call, so the asynchronous I/O facilities of UNIX are used. The major disadvantage of this scheme is that threads within a process cannot take advantage of a multi-processor.
（上段译文）User-level没有核心支持的多线程的进程。因此，核心只有单线程进程概念，而多线程进程由与应用程序连接的过程库实现。核心不知道线程的存在，也就不能独立的调度这些线程了。一个线程运行库组织线程的调度。如果一个线程调用了一个阻塞的系统调用，进程可能被阻塞，当然其中的所有线程也同时被阻塞，所以UNIX使用了异步I/O工具。这种机制的的最大缺点是不能发挥多处理器的优势。
The advantages include:
（系统消耗小）Certain thread operations are significantly less costly. For example, switching between threads belonging to the same process do not necessarily involve a system call, and hence save this over-head.
（可以修改以适应特殊的应用）User-level thread implementations can be customized or changed to suit the particular application requirements. This is particularly useful for real-time multimedia processing etc. Also, it is possible to support many more user-level threads than can by default by a kernel.
2. Kernel-level threads:
This implementation allows threads within different processes to be scheduled according to a single scheme of relative prioritizing. This is suited for exploiting the concurrence of multiprocessors.
核心级线程如许不同进程里的线程按照同一相对优先方法调度，这适合于发挥多处理器的并发优点。
Most of the current thread library implementations available today implement user-level threads. There have been several research projects that have implemented some form of Kernel-level threads. Notable among these are the Mach distributed OS, which combines the advantages of user-level and kernel-level threads by allowing user-level code to provide scheduling hints to the kernel thread scheduler. By providing such a two-level scheduling scheme, the kernel retains control over the allocation of processor time, but also allows a process to take advantage of multiple processors.
1.3 Thread Libraries
The two most widely used thread libraries are POSIX and Solaris thread libraries. Both implementations are inter-operable, their functionality is similar, and can be used within the same application. However, only POSIX threads are guaranteed to be fully portable to other POSIX-compliant environments.
Similarities:
Most of the functions in both libraries, libpthread and libthread, have a counterpart in the other library. POSIX functions and Solaris functions, whose names have similar endings, usually have similar functionality, number of arguments, and use of arguments. All POSIX threads function names begin with the prefix pthread? where as the Solaris threads function names begin with the prefix thr?
Differences:
POSIX
is more portable
establishes characteristics for each thread according to configurable attribute objects
implements thread cancellation
enforces scheduling algorithms
allows for clean-up handlers for fork(2) calls
Solaris
threads can be suspended and continued
implements an optimized mutex, readers/writer locking
may increase the concurrency
implements daemon threads, for whose demise the process does not wait
1.4 Threads Standards
There are three different definitions for thread libraries competing for attention today: Win32, OS/2, and POSIX. The first two are proprietary and limited to their individual platforms (Win32 threads run only under NT and Win95, OS/2 threads on OS/2). The POSIX specification (IEEE 1003.1c, aka Pthreads) is intended for all computing platforms, and implementations are available or in the works for almost all major UNIX systems (including Linux), along with VMS.
POSIX Threads
The POSIX standard defines the API and behavior that all the Pthreads libraries must meet. It is part of the extended portion of POSIX, so it is not a requirement for meeting XPG4, but it is required for X/Open UNIX 98, and all major UNIX vendors have committed to meeting this standard. As of this writing, (7/97) almost all UNIX vendors have released a library.
Win32 and OS/2 Threads
Both the NT and OS/2 implementations contain some fairly radical differences
from the POSIX standard--to the degree that even porting from one or the other
to POSIX will prove moderately challenging. Microsoft has not announced any
plans to adopt POSIX. There are freeware POSIX libraries for Win32 (see
Commercial Products on page 249), and OS/2 also has an optional POSIX library.
DCE Threads
Before POSIX completed work on the standard, it produced a number of drafts which it published for comment. Draft 4 was used as the basis for the threads library in DCE. It is similar to the final spec, but it does contain a number of significant differences. Presumably, no one is writing any new DCE code.
Solaris Threads
Also known as UI threads, this is the library, which SunSoft used in developing Solaris 2 before the POSIX, committee completed their work. It will be available on Solaris 2 for the foreseeable future, although we expect most applications writers will opt for Pthreads. The vast majority of the two libraries are virtually identical.
1.5 Linux线程的思想及特点
1.5.1 LinuxThreads
http://pauillac.inria.fr/~xleroy/linuxthreads
Xavier Leroy at INRIA (Paris, France), with input from Pavel Krauz, Richard Henderson and others, has developed a Pthreads library that implements the One-to-One model, allowing it to take advantage of multiple processors. It is based on the new Linux system call, clone()2 . It runs on Linux 2.0 and up, on Intel, Alpha, SPARC, m68k, and MIPS machines. One limitation is its non-standard implementation of signal handling.
1.5.2 Implementation model for LinuxThreads
LinuxThreads follows the so-called "one-to-one" model: each thread is actually a separate process in the kernel. The kernel scheduler takes care of scheduling the threads, just like it schedules regular processes. The threads are created with the Linux clone() system call, which is a generalization of fork() allowing the new process to share the memory space, file descriptors, and signal handlers of the parent.
LinuxThreads采用称为1-1模型：每个线程实际上在核心是一个个单独的进程，核心的调度程序负责线程的调度，就象调度普通进程。线程是用系统调用clone()创建的，clone()系统调用是fork()的普遍形式，它允许新进程共享父进程的存储空间、文件描述符和软中断处理程序。
Advantages of the "one-to-one" model include:
Minimal overhead on CPU-intensive multiprocessing (with about one thread per processor); 最小限度消耗的CPU级多处理技术（每个CPU一个线程）；
Minimal overhead on I/O operations; 最小限度消耗的I/O操作；
A simple and robust implementation (the kernel scheduler does most of the hard work for us)；一种简单和强壮的实现（核心调度程序为我们做了大部分艰难的工作）。
The main disadvantage is more expensive context switches on mutex and condition operations, which must go through the kernel. This is mitigated by the fact that context switches in the Linux kernel are pretty efficient.
1.5.3 Consider other implementation models
There are basically two other models. The "many-to-one" model relies on a user-level scheduler that context-switches between the threads entirely in user code; viewed from the kernel, there is only one process running. This model is completely out of the question for me, since it does not take advantage of multiprocessors, and require unholy magic to handle blocking I/O operations properly. There are several user-level thread libraries available for Linux, but I found all of them deficient in functionality, performance, and/or robustness.
还有另外两种基本模型。多对一模型依赖于用户级的调度程序，线程切换完全由用户程序完成；从核心角度看，只有一个进程正在运行。这种模型不是我们所关心的，因为它无法利用多处理器的优点，而且要用不合理的方法处理I/O操作阻塞。
The "many-to-many" model combines both kernel-level and user-level scheduling: several kernel-level threads run concurrently, each executing a user-level scheduler that selects between user threads. Most commercial Unix systems (Solaris, Digital Unix and IRIX) implement POSIX threads this way. This model combines the advantages of both the "many-to-one" and the "one-to-one" model, and is attractive because it avoids the worst-case behaviors of both models -- especially on kernels where context switches are expensive, such as Digital Unix. Unfortunately, it is pretty complex to implement, and requires kernel supporting which Linux does not provide. Linus Torvalds and other Linux kernel developers have always been pushing the "one-to-one" model in the name of overall simplicity, and are doing a pretty good job of making kernel-level context switches between threads efficient. LinuxThreads is just following the general direction they set.
2 Linux核心对线程的支持
Linux核心对线程的支持主要是通过其系统调用，下文将进行系统的介绍。
2.1 系统调用clone()
以下是系统调用clone的代码：
asmlinkage int sys_clone(struct pt_regs regs)
{
unsigned long clone_flags;
unsigned long newsp;
clone_flags = regs.ebx;
newsp = regs.ecx;
if (!newsp)
newsp = regs.esp;
return do_fork(clone_flags, newsp, ®s);
}
与系统调用clone功能相似的系统调用有fork,但fork事实上只是clone的功能的一部分，clone与fork的主要区别在于传递了几个参数，而当中最重要的参数就是conle_flags,下表是系统定义的几个clone_flags标志：
标志 Value 含义
CLONE_VM 0x00000100 置起此标志在进程间共享VM
CLONE_FS 0x00000200 置起此标志在进程间共享文件系统信息
CLONE_FILES 0x00000400 置起此标志在进程间共享打开的文件
CLONE_SIGHAND 0x00000800 置起此标志在进程间共享信号处理程序
如果�