简介多任务的实现

原文:http://hosted.cjmovie.net/TutMultitask.htm
翻译:fleurer

恩,打算给你的操作系统实现多任务?可以说,多任务是现代操作系统里面最重要的元素之一──没多任务你没脸见人。只跑Bash的linux也有多任务一说──比如debain下边你可以使用Alt+F1,F2,F3,F4切换虚拟终端。不过话说回来,只有一颗cpu的电脑为什么能同时执行10件任务?

答案就是——不为什么,只不过看着像而已。它们切换的速度非常之快,以至于人可以觉得它们是同时执行的。当然也有双核和多核,不过那就不是本文讨论的范畴了。即使有双核多核,像一台普通的的Windows NT(包括XP)内核机器,没有用户登录、没有程序执行,也有约100条线程同时执行。

我们先列些名词好了:

  • 线程 – 进程的一个分子,可以同时执行。比如你玩的一个游戏是个进程,而这个游戏里面的背景音乐、键盘事件、3D绘图则是独立的线程。
  • 进程 - 在电脑上运行的一个完整程序,有自己的地址空间(通常使用分页实现)。
  • 调度算法 – 选出下一个要执行任务的方法。可以简单如Round Robina,也可以考虑上优先级,使一进程可以优先得到充足的时间片。调度算法与任务切换的实现无关。
  • 基于栈的任务切换 – 切换任务的方法之一。按照这个方法,在发生切换时我们把一些信息都”PUSH”到进程的栈里,于是只需要切换一个栈把用到的东西(eax, ebx, ds, es)都POP出来即可。这个方法比基于硬件的切换(这里不作讨论)更快,已经几乎是切换的首选。
  • Round Robin – 调度算法的一种,可以选出下一个执行的任务。它的实现很简单:把所有的进程(或线程)列出来放到一个表里,反复轮询之,公平分配时间片。

接下来动手吧。添加多任务,你的OS准备好了吗?我这里选择了最简单的方法(Round Robin,上面有介绍),需要:一个内存管理器(memory manager, 只要物理内存就够了);正确设置的IDT;PIT(可编程中断定时器,译者注) IRQ的hook;在保护模式之下。

我们首先得有一个结构体来表示每个进程的信息。简单起见,先这样:

typedef struct{        //Simple structure for a thread
 unsigned int esp0;   //Stack for kernel
 unsigned int esp3;   //Stack for process
} Thread;
 
Thread Threads[2];     //Space for our simple threads. Just 2!
int CurrentTask = -1;  //The thread currenlty running (-1 == none)

还得有个地方来存放线程信息。不过最好事先搞清楚——这个教程已是尽可能的简化了,我们没有让进程在Ring 3下执行,因为那样一来就得考虑TSS——我不想掉这个大坑。Beyond_Infinity同学在一篇类似的教程里用考虑了这个,如果感兴趣不妨一读。

在考虑创建新任务的方法之前,我先说下如何切换任务。其实很简单。

在收到来自PIC的IRQ时,你的IRQ Handler很可能会通过一个’pusha’或者’pushad’来储存一些寄存器。很好,这就清楚了,你可能使用’popa’或’popad’以相反的顺序重新得到这些寄存器。大约可以像这样:

_irq0:
cli    ;Disable interrupts
 push 0 ;Push IRQ number
 push 0 ;Push dummy error code
 jmp IRQ_CommonStub
 
.. ;Other IRQS are here, similiar to above
 
IRQ_CommonStub:
 pusha          ;Push all standard registers
 push ds        ;Push segment d
 push es        ;Push segmetn e
 push fs        ; ''
 push gs        ; ''
 
 mov eax, 0x10  ;Get kernel data segment
 mov ds, eax    ;Put it in the data segment registers
 mov es, eax
 mov fs, eax
 mov gs, eax
 
 push esp       ;Push pointer to all the stuff we just pushed
 call _IRQ_Handler ;Call C code
 
 pop gs         ;Put the data segments back
 pop fs
 pop es
 pop ds
 
 popa           ;Put the standard registers back
 
 add esp, 8     ;Take the error code and IRQ number off the stack
 
 iret           ;Interrupt-Return

考你个问题:这些pop可以将当前栈中的数据装回CPU,如果在这个C函数调用时将栈换掉又会怎样?哈哈~到点子上了。如果这样做,整个CPU的状态就切换了。把上面的代码稍微改下:

_irq0:
 ;Notice there is no IRQ number or error code - we don't need them
 
 pusha          ;Push all standard registers
 push ds        ;Push segment d
 push es        ;Push segmetn e
 push fs        ; ''
 push gs        ; ''
 
 mov eax, 0x10  ;Get kernel data segment
 mov ds, eax    ;Put it in the data segment registers
 mov es, eax
 mov fs, eax
 mov gs, eax
 
 push esp       ;Push pointer to all the stuff we just pushed
 call _TaskSwitch ;Call C code
 
 mov esp, eax   ;Replace the stack with what the C code gave us
 
 mov al, 0x20   ;Port number AND command number to Acknowledge IRQ
 out al, al     ;Acknowledge IRQ, so we keep getting interrupts
 
 pop gs         ;Put the data segments back
 pop fs
 pop es
 pop ds
 
 popa           ;Put the standard registers back
 
 ;We didn't push an error code or IRQ number, so we don't have to edit esp now
 
 iret           ;Interrupt-Return

有一点需要注意 – 只要你的C代码返回一个unsigned int,编译器就会把它放到eax寄存器里 – 简单漂亮(GCC才可以!)。好,接下来做什么?一半了,是的!

接下来考虑创建新任务。这就意味着,我们需要申请内存,并令它的堆栈看起来像是push了所有的寄存器的状态(这一来在切换栈之后,才能有东西pop)。恩,x86体系结构下栈是向下增长的。这就意味着你的push相当于设置esp指向的dword(双字),随后esp减去4。我们在C里模拟出来就行了。幸运的是,这很简单——只需要搞个unsigned int的指针,指向栈顶。每次push后都使用 — 运算符下移就好。好,就这么创建一个任务:

//This will create a task
//It will make a stack that looks like it has all
//of the stuff of an IRQ handler 'pushed' on it
void CreateTask(int id, void (*thread)()){
  unsigned int *stack;
  Threads[id].esp0 = AllocPage() + 4096; //This allocates 4kb of memory, then puts the pointer at the end of it
 
  stack = (unsigned int*)Threads[id].esp0; //This makes a pointer to the stack for us
 
  //First, this stuff is pushed by the processor
  *--stack = 0x0202; //This is EFLAGS
  *--stack = 0x08;   //This is CS, our code segment
  *--stack = (UINT)thread; //This is EIP
 
  //Next, the stuff pushed by 'pusha'
  *--stack = 0; //EDI
  *--stack = 0; //ESI
  *--stack = 0; //EBP
  *--stack = 0; //Just an offset, no value
  *--stack = 0; //EBX
  *--stack = 0; //EDX
  *--stack = 0; //ECX
  *--stack = 0; //EAX
 
  //Now these are the data segments pushed by the IRQ handler
  *--stack = 0x10; //DS
  *--stack = 0x10; //ES
  *--stack = 0x10; //FS
  *--stack = 0x10; //GS
  Threads[id].esp0 = (UINT)stack; //Update the stack pointer
}

好,已经设好了任务,接着切换它们。不过怎样?恩,还记得Round Robin吧,你已经知道了!我们只有两个任务,所以在PIT IRQ被触发时只需要知道在执行的是哪个人物,把栈切换成另一个的。再保存当前ESP到旧任务的结构体里。如下:

//Switch between our two tasks
//Notice how we get the old esp from the ASM code
//It's not a pointer, but we actually get the ESP value
//That way we can save it in our task structure
unsigned int TaskSwitch(unsigned int OldEsp){
if(CurrentTask != -1){ //Were we even running a task?
 Threads[CurrenTask].esp0 = OldEsp; //Save the new esp for the thread
 
 //Now switch what task we're on
 if(CurrentTask == 0)CurrentTask = 1;
 else CurrentTask = 0;
} else{
 CurrentTask = 0; //We just started multi-tasking, start with task 0
}
 return Threads[CurrentTask].esp0; //Return new stack pointer to ASM
}

随后我们需要由PIT来触发切换任务的asm stub,我假定你已经按照常规将IRQ映射到32-47。如果没,就设置一个IRQ0对应的handler。

extern void irq0(); //Our ASM stub
//This is a very simple function
//All it does is put us in the IDT
void StartMultitasking(){
IdtSetGate(0, (UINT)irq0); //Install us in IDT. We multitask NOW!
}

万事俱备,只剩调用这些函数!方便看执行效果起见,在kernel的主文件(可能是main.c)里面添上这两个函数。

//These are just two simple functions that act as
//'threads' to test our multi-tasker on
//I won't try to explain how they work
//Only that they change colors on two letters of the screen
 
//Also - they must NEVER return - just make an infinite loop
 
void ThreadTest1(){
unsigned char* VidMemChar = (unsigned char*)0xB8001;
for(;;)*VidMemChar++;
}
 
void ThreadTest2(){
unsigned char* VidMemChar = (unsigned char*)0xB8003;
for(;;)*VidMemChar++;
}

如你所见,执行结果是很容易想象的。不错。加上执行多任务的代码!把几句放到你的主函数(其它函数也行,能执行就好)里面。

CreateTask(0, ThreadTest1); //Install the first task
CreateTask(1, ThreadTest2); //Install the second task
StartMultitasking(); //Start your multitasking OS!
//We're now multitasking. Celebrate!

该差不多了,你已经可以把你的OS带出单任务的DOS时代了…多任务多线程的新时代系统!

你可以接着搞搞…这只是入门而已。简单的Round-Robin算法在很多情况下的效果并不好,不妨看下其他的调度算法,比如Mega Tokyo’s OS FAQ中列出来的那些。

还有件事情你可能感兴趣,那就是如何将分页整合进来。大多数操作系统都给每个应用程序一个0开始的虚拟地址空间,并一个用户栈。这一来,你就需要给每个任务添加一个页表目录,随后添加一些push和pop以适应CR3中值的改变。

有问题?有建议?Email me at service@cjmovie.net!

失语

最近几天感触最大的就是,几乎不会说话了。

总想敲些字出来说点事,结果怎么都是驴唇不对马嘴,最后看到桌面上满是word生成的tmp文件才幡然醒悟,马上关掉统统删除。年轻人写东西就容易不由自主地隐瞒对自己不利的东西,想要别人同情自己的处境,然而想说什么压根就不清楚。得,拉倒。

停止了校内和推特上面活跃的帐号。比起官方骗小孩子的套话,人们显然更愿意相信自己的臆想…几天不见各种自以为是的高谈阔论,世界终于清静了。

三天后是大三,三个月后是我20周岁的生日。跟同学们聊天考研工作已经是主流话题的时候还没正经想过以后怎样,多年攒下畏首畏尾的脾性也作祟的厉害…至今还没有头有尾地做完整过一件事情,可悲吧。

在豆瓣上看到一段话

    
1. 年轻人觉得一生的时间无穷无尽,浪费几个小时或者一天,没有什么大不了。然后慢慢就过了几十年。
2. Home again表现一种讽刺,年轻时总想离家,老了却只想回家,留在家里。
3. 虚度光阴,使理想化为泡影

自警。

简说写作

作者:Paul Graham
翻译:fleurer
原文:http://www.paulgraham.com/writing44.html

(这是在回复一封email时,随笔写下的即兴之作。通常,我写一篇文章都要花几个星期,不过这篇只花了67分钟——23分钟写作,44分钟重写。)

写作的重要性很容易被人们所忽视。写作,不只是交换想法的手段,更是产生想法的原动力。如果你并不熟悉写作、不喜欢写作,很可能会错失由此而生的很多想法。

这里就简谈一下,如何搞好写作:

尽可能快地打出一个草稿;反复重写;删掉所有不必要的部分;以对话的口吻写作;阅读时对不好的文章保持警惕,写作时对自己的文章也如此。

模仿你喜欢的作者;如果感到无从下笔,就找个人把你想表达的先说出来,再把你说的写下来;确保文章中80%的观点是动笔之后推敲的结果,而动笔前50%的观点都是经不住推敲的。

放心大胆的删改;找个信得过的朋友阅读你的文章,告诉你哪里不好理解或者不对劲;不要(总是)列出过于详细的大纲;动笔之前先酝酿几天;随身带个小笔记本;想到开头就别犹豫,马上动笔;要是时间紧,就先写重要的句子;为你喜欢的东西写作;

不要言辞激烈;中途想改变话题就改,不用犹豫;把主题无关的内容放到脚注里;使用排比;大声读出你的文章,找出蹩脚或者无趣的地方;告诉读者新鲜有用的东西;

在时间充裕时写作;决定重写时,从头阅读一遍已经写下的内容;写完了就放松下;没人认真听流行乐,也没人像你这样认真阅读你的文章;

要是说错了什么,马上改正;祸从口出,请朋友找出会让你后悔的句子;回头把激进的语气放缓;发布到网上,读者的存在会激励你继续写作;如果可以,打印出来;使用平实的语言;明辨跑题的迹象;遇到合适的地方就结尾。

update: 翻完之后杯具的看到原文底下有Chinese Translation。 TvT

抽象代数与计算-Monoid

作者:Mark C. Chu-Carroll
翻译:Fleurer
原文:http://scienceblogs.com/goodmath/2008/02/abstract_algebra_and_computati.php

在前两篇post,我们以范畴的角度观察了群论。范畴论给了我们一个全新的视角来理解对偶。与传统代数不同,范畴论的对偶是从groupoid中出现的,而群则被视为是带对偶的更简单的结构。

看其它的代数结构也是同样。比如环(rings),换个视角,也可以见到一个大不相同的环。

在看范畴论下的环之前,我们不妨先看个简单点的结构。在范畴中,环是通过monoid表示的。不过Monoid绝不仅仅只是环前面的开胃菜,它本身就是好东西。

它们的魅力在什么地方?首先,它们是范畴和代数之间的一座桥梁。我们知道,范畴中的groupoid(广群)使得群论无缝地归入了范畴论。Monoid也可以同样:它们也有范畴中的等价物。而且,Monoid还有地地道道的实际应用——你可以用Monoid表示计算。而且也许不广为人知,计算机科学中很多得力的基础工具其实都是Monoid。

我们先用代数的视角看下,呆会再换到范畴视角。在抽象代数中,Monoid正好跟复合函数的思想一致。开窍了吧,范畴论的基本思路就是复合函数的抽象化!

Monoid跟群类似,是一组支持二元运算的值的集合。Monoid更简单——它只要组合,不要逆元。我们令Monoid里面值的集合为M,二元运算为º,就有三条性质:

1. 封闭性(Closure): ∀a,m∈M: aºb ∈ M
2. 单位元(Identity): ∃ i∈M : ∀f∈M : iºf = fºi = f.
3. 结合律(Associativity): ∀ a,b,c∈M: (aºb)ºc = aº(bºc).

这就是了。有这几条性质,想想函数和复合函数,套进去就满靠谱了。这对大多数函数都适用,于是所有的函数都成了对象,比如定义域和值域都是自然数的函数。封闭性要求两个简单完全函数复合的结果依然是简单完全函数;单位元可以是一个函数f(x)=x;交换律是交换表达式中元素的顺序,不影响最终结果。这都是复合函数天生的性质。

如果拿monoid像群一样,给它加一个操作又会怎样?答案对我们学计科的同学再熟悉不过了:有限自动机!

取一个monoid,(M,º)。我们可以在集合S上定义这monoid的一个操作,也就是:*:M×S→S,取M的一个值和S的一个值,得S的一个值。这个monoid操作显示了两条性质——都是来自monoid。

1. Identity: ∀s∈S, i*s=s.
2. Associativity: ∀a,b∈M, ∀s∈S: a*(b*s) = (aºb)*s.

这意味着什么?意味着我们给这个monoid加上了函数应用。这个monoid操作就是M中函数的应用。

这样,有了一个组可组合的函数,一个可以应用到函数的特定集合。可以得到什么?

一台自动机——也就是一种数学上的计算模型。

这个自动机是怎么出来的?

在这个monoid操作里,monoid的每个成员都是函数,也就是值到值的映射;组合符将这些函数链到一起。对自动机来说,monoid中的每个成员都是计算中的一个步骤,组合符将这些步骤连续起来。这还不是完整的计算——但已经靠一个简单的形式,前进了一大步。

多想想。还记得lambda演算?它就是一个表示计算的逻辑工具,里面除了函数什么都没有。想到了吧,我们刚刚只是重新发明了lambda演算的一部分,以抽象代数的思路。

在以后的post里面我会多讲些——不过我得先给你过上一遍,在范畴论里面这些东西都是什么样子——下一步往哪走,在范畴的大陆上清晰无比。

数据结构课设,表达式计算

随便写了下,没仔细调试。

大约这么定义
double parse_expr(char *input, char **output);

input就是表达式的字符串,output是解析剩下的部分。如果output==input,就是解析失败。如果正确,返回运算结果。

用起来大约这样

    char *out, *exp="2+(1+3)*4";
    double r = parse_expr(exp, &out);
    if (out==exp){
        printf("parse fail\n");
        return 0;
    }
    printf("%s => %f \n", exp, r);

回头想下,思路跟以前写的parser几乎是葫芦画瓢,也该算是递归下降吧。

代码如下

exp.h

double parse_expr(char *input, char **output);
double parse_term(char *input, char **output);
double parse_fact(char *input, char **output);
double parse_numb(char *input, char **output);

exp.c

#include "exp.h"
 
// expr ::= term {[+-] term}
double parse_expr(char *input, char **output){
    double r=0;
    char *tmp, op;
    tmp = input;
    // factor
    r = parse_term(tmp, output);
    if (output==tmp){
        return 0;
    }
    // {[+-] term}
    tmp = *output;
    while ((op=*tmp)=='+' || op=='-'){
        double r2 = parse_term(++tmp, output);
        if (tmp==*output){
            *output = input;
            return 0;
        }
        r = (op=='+')? r+r2: r-r2;
        tmp = *output;
    }
    return r;
}
 
// term ::= factor {[*/] factor}
double parse_term(char *input, char **output){
    double r=0;
    char *tmp, op;
    tmp = input;
    // factor
    r = parse_fact(tmp, output);
    if (output==tmp){
        return 0;
    }
    // {[*/] factor}
    tmp = *output;
    while ((op=*tmp)=='*' || op=='/'){
        double r2 = parse_fact(++tmp, output);
        if (tmp==*output){
            *output = input;
            return 0;
        }
        r = (op=='*')? r*r2: r/r2;
        tmp = *output;
    }
    return r;
}
 
// fact ::= (expr) | numb
double parse_fact(char *input, char **output){
    double r=0;
    char *tmp;
    // (expr)
    if (*input=='(') {
        tmp = input+1;
        r = parse_expr(tmp, output);
        if(**output==')'){
            (*output)++;
            return r;
        }
        // if fail, output == input
        else {
            *output = input;
            return 0;
        }
    }
    // numb
    r = parse_numb(input, output);
    return r;
}
 
double parse_numb(char *input, char **output){
    double  r = 0;
    char ch, *tmp=input;
    while((ch = *tmp++)>='0' && ch<='9'){
        r = r*10+ch-'0';
    }
    *output = tmp-1;
    return r;
}

main.c

int main(){
    double r;
 
    char *out, exp[1024];
    scanf("%256s", exp);
    r = parse_expr(exp, &out);
    if (out==exp){
        printf("parse fail\n");
        return 0;
    }
    printf("%s => %f \n", exp, r);
 
    return 0;
}