/*
* 2010-1-21
* 該文件時內核中有關任務調度的函數程序，其中包含基本函數sleep_on，
* wakeup，schedule等，以及一些簡單的系統調用。同時將軟盤的幾個操作
* 函數也放置在這里。
*
* schedule函數首先對所有的任務檢查，喚醒任何一個已經得到信號的任務，
* 具體的方法是針對任務數組中的每個任務，檢查其警報定時值alarm。如果任務
* 的alarm已經超期（alarm < jiffies），則在它的信號位圖中設置SIGALARM，然后
* 情書alarm值。jiffies是系統自從開機之后算起的滴答數。在scheed.h中定義，
* 如果進程信號的位圖中除去被阻塞的信號之外還有其他信號，并且任務處于可
* 中斷睡眠狀態，則置任務為就緒狀態。
* 隨后是調度函數的核心處理，這部分代碼根據進程時間片和優先權的調度機制，
* 來選擇將要執行的程序。他首先是循環檢查任務數組中的所有任務。根據每個就緒
* 任務剩余執行時間值counter中選取一個最大的，利用switch_to函數完成任務
* 轉換。如果所有的就緒任務的該值都是0，則表示此刻所有任務的時間片都已運行完。
* 于是就根據任務的優先權值priority，重置每個任務的運行時間counter。在重新
* 循環檢查所有的任務重的執行的時間片值。
* 另一個值得一說的是sleep_on函數，該函數雖短，卻要比schedule函數難理解，
* 簡單的講，sleep_on函數主要的功能是當一個進程所請求的資源正在忙，或者是
* 不在內存中被切換出去，放在等待隊列中等待一段時間。切換回來后在繼續執行。
* 放入等待隊列的方式是，利用了函數中的tmp指針為各個正在等待任務的聯系。
* 還有一個函數interrupt_sleep_on，該函數的主要功能是在進程調度之前，把當前
* 任務設置為可中斷等待狀態，并在本任務被喚醒之后還需要查看隊列上是否還有
* 后來的等待任務，如果有，先調度他們。
*
*/
/*
* linux/kernel/sched.c
*
* (C) 1991 Linus Torvalds
*/
/*
* '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 <linux/sched.h>
#include <linux/kernel.h>
#include <linux/sys.h>
#include <linux/fdreg.h> // 軟驅頭文件
#include <asm/system.h>
#include <asm/io.h>
#include <asm/segment.h> // 端操作頭文件，定義端操作的匯編函數
#include <signal.h>
#define _S(nr) (1<<((nr)-1)) // 取nr（1-32）對應的位的二進制數值，取出的
// 并不是一位
// 定義除了SIGKILL和SIGSTOP之外，其他信號位全是阻塞的
#define _BLOCKABLE (~(_S(SIGKILL) | _S(SIGSTOP)))
//----------------------------------------------------------------------
// show_task
// 顯示任務號nr，pid，進程狀態和內核堆棧空閑字節
void show_task(int nr,struct task_struct * p)
{
int i,j = 4096-sizeof(struct task_struct);
printk("%d: pid=%d, state=%d, ",nr,p->pid,p->state);
i=0;
while (i<j && !((char *)(p+1))[i])
i++;
printk("%d (of %d) chars free in kernel stack\n\r",i,j);
}
//---------------------------------------------------------------------
// show_stat
// 顯示所有任務的信息
void show_stat(void)
{
int i;
for (i=0;i<NR_TASKS;i++)
if (task[i]) // task是一個指針數組，如果存在”任務“
show_task(i,task[i]);
}
#define LATCH (1193180/HZ) // 每個時間片滴答數
extern void mem_use(void);
extern int timer_interrupt(void); // 時鐘中斷處理程序
extern int system_call(void); // 系統調用處理程序
union task_union
{
// 定義任務聯合(任務結構成員和stack 字符數組程序成員),聯合體是共享內存的
struct task_struct task; // 因為一個任務數據結構與其堆棧放在同一內存頁中，所以
char stack[PAGE_SIZE]; // 從堆棧段寄存器ss 可以獲得其數據段選擇符
};
static union task_union init_task = {INIT_TASK,}; // 定義初始任務數據
long volatile jiffies=0; // 定義開機以來時鐘滴答數
long startup_time=0; // 開機時間
struct task_struct *current = &(init_task.task); // 當前任務指針
struct task_struct *last_task_used_math = NULL; // 使用過協處理器的任務指針
struct task_struct * task[NR_TASKS] = {&(init_task.task), }; // 定義任務數組
long user_stack [ PAGE_SIZE>>2 ] ; // 定義系統堆棧指針
struct { // 該結果用于設置堆棧ss：esp
long * a;
short b;
} stack_start = { & user_stack [PAGE_SIZE>>2] , 0x10 };
//---------------------------------------------------------------------
// math_state_restore
/*
* '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 == current) // 如果任務沒有改變返回
return;
__asm__("fwait"); // 在發送協處理器指令之前首先發出wait指令
if (last_task_used_math) // 如果上個使用協處理器的進程存在
{
// 保存狀態
__asm__("fnsave %0"::"m" (last_task_used_math->tss.i387));
}
last_task_used_math=current; // 現在last_task_used_math指向當前任務
if (current->used_math) // 如果當前的任務使用過協處理器
{
__asm__("frstor %0"::"m" (current->tss.i387));// 恢復狀態
} else // 沒有使用過協處理器
{
__asm__("fninit"::); // 初始化協處理器
current->used_math=1; // 設置使用協處理器標志
}
}
//--------------------------------------------------------------------
// schedule
/*
* '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 */
/* 檢查alarm，喚醒任何已得到信號的可中斷任務 */
// 從任務數組最后開始檢查alarm
for(p = &LAST_TASK ; p > &FIRST_TASK ; --p)
if (*p) // 任務存在？
{
if ((*p)->alarm && (*p)->alarm < jiffies)
/*
* 下面是對(*p)->alarm < jiffies理解：
* 如果不調用alarm()函數，alarm的值就是0，但是調用了alarm函數
* 之后，比如說alarm(5),就是5秒后報警
*/
{
// 在位圖信號中置位AIGALARM
(*p)->signal |= (1<<(SIGALRM-1));
// 將alarm值置位0
(*p)->alarm = 0;
}
// 如果信號位圖中除被阻塞的信號外還有其他信號，即是該
// 進程申請的自愿被別的進程釋放，或者是其他條件導致該
// 進程能夠被執行，并且該任務處于的是可中斷編程。linux
// 內核進程轉換見文檔<進程運行狀態圖.txt>。此時將該進程
// 進程狀態置位就緒。
if (((*p)->signal & ~(_BLOCKABLE & (*p)->blocked)) &&
(*p)->state==TASK_INTERRUPTIBLE)
(*p)->state=TASK_RUNNING;
}
/* this is the scheduler proper: */
/* 這是調度的主要部分 */
while (1) // 循環，直到存在counter的值大于0
{
c = -1;
next = 0;
i = NR_TASKS;
p = &task[NR_TASKS];
////////////////////////////////////////////////
// 下面的代碼是尋找最大counter值的進程。counter
// 值的含義見文檔 <linux0.11task_struct中counter解釋.txt>
while (--i) {
if (!*--p)
continue;
if ((*p)->state == TASK_RUNNING && (*p)->counter > c)
c = (*p)->counter, next = i;
}
////////////////////////////////////////////////
if (c) break; // 如果進程存在。退出，去執行switch_to
// 否則更新counter值
for(p = &LAST_TASK ; p > &FIRST_TASK ; --p)
if (*p)
(*p)->counter = ((*p)->counter >> 1) +
(*p)->priority;
}
switch_to(next);
}
//--------------------------------------------------------------------
// sys_pause
// 將當前任務設置為可中斷，執行調度函數
int sys_pause(void)
{
current->state = TASK_INTERRUPTIBLE;
schedule();
return 0;
}
//-------------------------------------------------------------------
// sleep_on
// struct task_struct **p是等待隊列頭指針
// 該函數就是首先將當前任務設置為TASK_UNINTERRUPTIBLE，并讓睡眠隊列
// 頭指針指向當前任務，執行調度函數，直到有明確的喚醒時，該任務才重新
// 開始執行。
void sleep_on(struct task_struct **p)
{
struct task_struct *tmp;
if (!p) // 無效指針
return;
if (current == &(init_task.task)) // 當前任務是0，死機
panic("task[0] trying to sleep");
tmp = *p;
*p = current;
current->state = TASK_UNINTERRUPTIBLE; // 設置狀態
schedule(); // 執行調度，直到明確的喚醒
// 肯能存在多個任務此時被喚醒，那么如果還存在等待任務
// if (tmp),則將狀態設置為”就緒“
if (tmp)
tmp->state=0;
}
//--------------------------------------------------------------------------
// interruptible_sleep_on
// struct task_struct **p是等待隊列對頭
void interruptible_sleep_on(struct task_struct **p)
{
/*
* 首先需要明確的是TASK_INTERRUPTIBLE。它是指當進
* 程處于可中斷等待狀態時，系統不會調度該進行執行。
*/
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 != current表示當前任務不是原來保存的任務，即是
* 有新的任務插入到等待隊列中了。由于本任務是不可中斷的
*，所以首先執行其他的任務
*/
(**p).state=0;
goto repeat;
}
/*
* 下面的代碼錯誤，應該是*p = tmp，讓隊列頭指針指向隊列中其他任務
*/
*p=NULL;
// 原因同上。sleep_on
if (tmp)
tmp->state=0;
}
//----------------------------------------------------------------
// wake_up
// 喚醒任務p
void wake_up(struct task_struct **p)
{
if (p && *p)
{
(**p).state=0; // 置狀態為可運行
*p=NULL;
}
}
/*
* OK, here are some floppy things that shouldn't be in the kernel
* proper. They are here because the floppy needs a timer, and this
* was the easiest way of doing it.
*/
/*
* 由于軟盤需要時鐘，所以就將軟盤的程序放到這里了
*/
// 利用下面的數組來存儲的是馬達運轉或者是停止的滴答數，下列的
// 數組在函數do_floppy_timer中更新
static struct task_struct * wait_motor[4] = {NULL,NULL,NULL,NULL};
static int mon_timer[4]={0,0,0,0}; // 軟驅到正常運轉還需要的時間
static int moff_timer[4]={0,0,0,0}; // 馬達到停止運轉還剩下的時刻
unsigned char current_DOR = 0x0C; // 數字輸出寄存器（初值：允許dma和中斷請求，啟動fdc）
// oxoc -- 0000,1100
//----------------------------------------------------------------
// ticks_to_floppy_on
// 指定軟盤到正常運轉所需的滴答數
// nr -- 軟盤驅動號，該函數返回的是滴答數
int ticks_to_floppy_on(unsigned int nr)
{
extern unsigned char selected; // 當前選中軟盤號
// ox10 -- 0001, 0000
unsigned char mask = 0x10 << nr; // 所選軟盤對應的數字輸出
// 寄存器啟動馬達比特位
/*
* 數字輸出端口（數字控制端口）是一個8位寄存器，它控制驅動器馬達開啟
* ，驅動器選擇，啟動和復位FDC，以及允許和禁止DMA及中斷請求。
* FDC的主狀態寄存器也是一個8位寄存器，用戶反映軟盤控制器FDC和軟盤
* 驅動器FDD的基本狀態。通常，在CPU想FDC發送命令之前或者是從FDC獲得
* 操作結果之前，都要讀取主狀態寄存器的狀態位，以判定當前的數據是否
* 準備就緒，以及確定數據的傳輸方向
*
*/
if (nr>3) // 最多3個軟盤驅動號
panic("floppy_on: nr>3");
moff_timer[nr]=10000; /* 100 s = very big :-) */
cli(); /* use floppy_off to turn it off 關中斷 */
mask |= current_DOR; // mask =
// 如果不是當前軟驅，則首先復位其它軟驅的選擇位，然后置對應軟驅選擇位
if (!selected)
{
mask &= 0xFC; // 0xfc -- 1111,1100
mask |= nr;
}
if (mask != current_DOR) // 如果數字輸出寄存器的當前值和要求不同
// 即是需要的狀態還沒有到達
{
outb(mask,FD_DOR); // 于是向FDC數字輸出端口輸出新值
if ((mask ^ current_DOR) & 0xf0) // 如果需要啟動的馬達還沒有
// 啟動，則置相應的軟驅馬達定
// 時器值（50個滴答數）
mon_timer[nr] = HZ/2;
else if (mon_timer[nr] < 2)
mon_timer[nr] = 2;
current_DOR = mask; // 更新數字輸出寄存器的值current_DOR，即是反映
// 當前的狀態
}
sti(); // 開中斷
return mon_timer[nr];
}
//--------------------------------------------------------------
// floppy_on
// 等待指定軟驅馬達啟動所需時間，啟動時間
void floppy_on(unsigned int nr)
{
cli(); // 關中斷
while (ticks_to_floppy_on(nr))// 還沒有到時間？
sleep_on(nr+wait_motor); // 為不可中斷睡眠狀態并放在
// 等待馬達運行隊列中
sti(); // 開中斷
}
//---------------------------------------------------------------
// floppy_off
// 初始化數組moff_timer，即是表示置相應軟驅馬達停轉定時器（3秒）
void floppy_off(unsigned int nr)
{
moff_timer[nr]=3*HZ;
}
//----------------------------------------------------------------
// do_floppy_timer
// 軟盤定時處理子程序。更新馬達啟動定時值和馬達關閉停轉計時值。該子程序
// 是在時鐘定時中斷被調用，因此每一個滴答（10ms）被嗲用一次，更新馬達開啟
// 或者是停止轉動定時器值。如果在某一個馬達停轉時刻到達，那么則將數字輸出
// 寄存器馬達啟動復位標志
void do_floppy_timer(void)
{
int i;
unsigned char mask = 0x10;
for (i=0 ; i<4 ; i++,mask <<= 1) {
if (!(mask & current_DOR)) // 如果不是指定馬達
continue;
if (mon_timer[i])
{
if (!--mon_timer[i])// 如果馬達啟動定時器到達
wake_up(i+wait_motor);//則喚醒進程
} else if (!moff_timer[i]) { // 如果馬達停止運轉時刻到達
current_DOR &= ~mask; // 復位相應馬達啟動位
outb(current_DOR,FD_DOR); // 更新數字輸出寄存器
} else
moff_timer[i]--; // 馬達停轉計時器遞減
}
}
#define TIME_REQUESTS 64
static struct timer_list {
long jiffies; // 定時滴答數
void (*fn)(); // 定時處理函數
struct timer_list * next;
} timer_list[TIME_REQUESTS], * next_timer = NULL;
//----------------------------------------------------------------------
// add_timer
// 增加定時器。輸入參數為指定的定時器的滴答數和相應的處理函數指針。
// jiffies -- 以10ms計時的滴答數
// *fn() -- 定時時間到達時執行函數
void add_timer(long jiffies, void (*fn)(void))
{
struct timer_list * p;
if (!fn) // 如果處理函數為空
return; // 退出
cli(); // 關中斷
if (jiffies <= 0) // 定時器到達
(fn)(); // 執行函數fn
else { // 否則，從定時器數組中，找到一個空閑項，使用fn來標識
for (p = timer_list ; p < timer_list + TIME_REQUESTS ; p++)
if (!p->fn)
break;
// 當上面的循環結束時，可能存在p == timer_list + TIME_REQUESTS
if (p >= timer_list + TIME_REQUESTS) // 這樣的話，表明用完了數組
panic("No more time requests free");
// 將定時器數據結構填入相應信息
p->fn = fn;
p->jiffies = jiffies;
p->next = next_timer;
next_timer = p;
// 鏈表項按定時器值的大小排序。下面就是鏈表排序的實現。這樣的好處是
// 在查看是否有定時器到期時，只需要查看鏈表的頭結點即可
while (p->next && p->next->jiffies < p->jiffies) {
p->jiffies -= p->next->jiffies;
fn = p->fn;
p->fn = p->next->fn;
p->next->fn = fn;
jiffies = p->jiffies;
p->jiffies = p->next->jiffies;
p->next->jiffies = jiffies;
p = p->next;
}
}
sti(); // 開中斷
}
//------------------------------------------------------------------------
// do_timer
// 時鐘中斷處理函數，在/kernel/system_call.s中_timer_interrupt_中被調用
// 參數cpl是當前的特權級0或3，0標識在內核代碼段運行
// 對于一個進程由于時間片用完，則進行內核任務切換。并進行及時更新工作
void do_timer(long cpl)
{
extern int beepcount; // 揚聲器發聲時間滴答數
extern void sysbeepstop(void); // 關閉揚聲器
if (beepcount)
if (!--beepcount) // 如果揚聲器計數次數到
sysbeepstop(); // 關閉發生器
if (cpl) // 如果實在內核程序，即是超級用戶
current->utime++; // 超級用戶時間增加
else
current->stime++; // 普通用戶運行時間增加
// 如果有用戶定時器存在的話，則將第一個定時器的值減去1，如果已經等于0
// 那么調用函數fn，并將函數指針置為空值，然后去掉該定時器。注意的是上述
// 鏈表已經排序，同時在尋找空閑結點時，是通過fn是否為空來判斷的，所以
// 將fn置位null
if (next_timer)
{
next_timer->jiffies--;
while (next_timer && next_timer->jiffies <= 0) {
void (*fn)(void); //
// 刪除定時器
fn = next_timer->fn;
next_timer->fn = NULL;
next_timer = next_timer->next;
(fn)();
}
}
// 如果當前軟盤控制器FDC的數字輸出寄存器馬達啟動位有置位，則執行相應的
// 軟盤定時程序
if (current_DOR & 0xf0)
do_floppy_timer();
if ((--current->counter)>0) return; // 如果進程運行時間還沒有完，退出
current->counter=0;
if (!cpl) return; // 超級用戶程序，不依賴counter值來調度
schedule();
}
//----------------------------------------------------------------------
// sys_alarm
// 如果已經設置了alarm的值，那么返回的是舊值，如果沒有設置返回0
int sys_alarm(long seconds)
{
int old = current->alarm;
if (old)
old = (old - jiffies) / HZ;
current->alarm = (seconds>0)?(jiffies+HZ*seconds):0;
return (old);
}
//-----------------------------------------------------------------------
// sys_getpid
// 取得當前的進程號
int sys_getpid(void)
{
return current->pid;
}
//----------------------------------------------------------------------
// sys_getppid
// 取得父進程進程號
int sys_getppid(void)
{
return current->father;
}
//-----------------------------------------------------------------------
// sys_getuid
// 取得用戶號uid
int sys_getuid(void)
{
return current->uid;
}
//------------------------------------------------------------------------
// sys_geteuid
// 取得用戶號euid
int sys_geteuid(void)
{
return current->euid;
}
//----------------------------------------------------------------------
// sys_getgid
// 取得組號gid
int sys_getgid(void)
{
return current->gid;
}
//----------------------------------------------------------------------
// sys_getegid
// 取得進程的egid，有關egid的解釋，參見文檔<Linux 關于SUID和SGID的解釋.txt>
int sys_getegid(void)
{
return current->egid;
}
//--------------------------------------------------------------------
// sys_nice
// 改變進程優先級
int sys_nice(long increment)
{
if (current->priority-increment>0)
current->priority -= increment;
return 0;
}
//----------------------------------------------------------------------
// sched_init
// 調度程序初始化，即是初始化進程0，init
void sched_init(void)
{
int i;
struct desc_struct * p;
if (sizeof(struct sigaction) != 16) // sigaction中存放的是信號狀態結構
panic("Struct sigaction MUST be 16 bytes");
// 設置初始任務（任務0）的任務狀態描述符表和局部數據描述符表
set_tss_desc(gdt+FIRST_TSS_ENTRY,&(init_task.task.tss));
set_ldt_desc(gdt+FIRST_LDT_ENTRY,&(init_task.task.ldt));
// 清楚任務數組和描述符表項
p = gdt+2+FIRST_TSS_ENTRY;
for(i=1;i<NR_TASKS;i++) {
task[i] = NULL;
p->a=p->b=0;
p++;
p->a=p->b=0;
p++;
}
/* Clear NT, so that we won't have troubles with that later on */
/* nt標志置位的話，那么當前的中斷任務執行iret命令時引起任務的切換 */
__asm__("pushfl ; andl $0xffffbfff,(%esp) ; popfl");
ltr(0); // 將任務0的tss加載到寄存器
lldt(0); // 將局部描述符表加載到局部描述符表寄存器
// 是將gdt和相應的ldt描述符的選擇符加載到ldtr。只是明確的加載這一次
// 以后任務的ldt加載，是cpu根據tss中的ldt自動加載的
// 初始化8253定時器
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);
// 修改中斷控制器屏蔽碼，允許時鐘中斷
outb(inb_p(0x21)&~0x01,0x21);
// 設置系統調用中斷門
set_system_gate(0x80,&system_call);
}
/*
* 下面解釋linux的init進程的整體認識
* 1.在系統的啟動階段時，bootsect.s文件只是見將系統加載到內存中，內核都
* 沒有加載完成，談不上對于進程管理的影響。setup.s中加載了全局的gdtr，
* 但是此時的gdt只是為了讓程序運行在保護模式下，沒有什么作用。在setup.s
* 文件中設置的gdt的格式如下 ：
* -----------
* | 0 0 0 0 |
* -----------
* | code seg|
* ------------
* | data seg|
* -----------
* | ...... |
* 在head.s文件中還需要改寫該gdt。經過該文件的修改后新生成的gdt如下：
* -----------
* | 0 0 0 0 |
* -----------
* | code |
* -----------
* | data |
* -----------
* | system | -- do not use in linux
* -----------
* | | -|
* ----------- |--剩下的各項是預留給其他任務，用于放置ldt和tss
* | | -|
*
* 在main.c文件中調用函數sched_init，此函數加載進程init。
* 加載init進程的ldt和tdd段
* |
* 由程序來執行加載ldt和tss段寄存器的任務
* |
* 即實現init進程的加載，即是手工創建的第一次進程。
* 此時的gdt大概上講是：
* ----------
* | 0 0 0 0 |
* -----------
* | code |
* -----------
* | data |
* -----------
* | system |
* -----------
* | ldt0 |
* -----------
* | tss0 |
* -----------
* | ... |
* 此后，進程使用fork系統調用來產生新的進程，同時進程調度開始起作用。
*
*/
|
