Monday, May 4, 2009

五一徽杭古道归来

强大的丐帮在绩溪村的23点留下了“大不自多”的求是回音,在古道中轻松而写意的享受山水,在山中做烟雾腾飞的神仙,更有丐三同学路见蚂蝗为蚂蝗献血的光荣作风,还有丐帮弟子们大吃叫花鸡的传统。
深夜,某帮外人物带着羡慕的眼神问道:“丐帮帮主真牛B,他到底是哪位?”
“在下献丑了。” 本人不无谦虚的回答他。

Sunday, April 5, 2009

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

Friday, April 3, 2009

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

Thursday, April 2, 2009

Happy Time Show


Happy time slide show


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

Sunday, March 15, 2009

劝君更尽一杯酒 ---- 我的兄弟龙的婚宴印象

2009年3月14日,我的兄弟龙结婚了! 在此祝福他和他的妻子在新的人生旅途中开心幸福!

在KTV唱最后一首歌的时候我突然莫名其妙的眼泪哗哗的流了,回想起《非诚勿扰》中在秦奋的北海道的老友在他们离开后失声的哭起来,当时我怎么也看不懂,现在我大概懂了。

兄弟,永远祝福你。

Monday, March 2, 2009

learning kernel: 预备知识

=======
预备知识
=======

Intel X86 CPU系列的寻址方式
========================

实地址模式
----------------

Intel在8086 CPU中设置了四个“段寄存器”:CS, DS, SS和ES, 分别用于可执行代码,数据,堆栈和其他。每个段寄存器都是16位,对应于地址总线的高16位。这样和某个段寄存器中的内容相加就得到20位实际地址的转化。对于这种类型的断式内存管理,一个进程可以随心所欲的访问从基地址开始的连续的64K字节空间,没有任何的保护机制,所以称这种模式为“实地址模式”。由于缺乏保护机制,所以一个现代的操作系统是无法在此建造起来的。

保护地址模式
-------------------

为了增加保护机制,80386 CPU增设了两个寄存器:GDTR(global descriptor table register)和LDTR(local descritor table register), 分别可以用来指向内存中的一个段描述结构数组,或者称为段表述表。段描述表的数据结构可以用如下伪代码表述:

typedef struct {
unsigned int base24_31 : 8; /* 基地址最高8位 */
unsigned int g : 1; /* 表段的长度单位,0表示字节, 1表示 */
unsigned int d_b :1; /* 存取方式: 0=16位, 1=32位 */
unsigned int unused :1; /* 未使用,设置成0 */
unsigned int avl :1; /* */
unsigned int seg_limit 16_19 :4; /* 段长度的最高4位 */
unsigned int p :1; /* segment present, 为0时表示该段的内容不在内存中 */
unsigned int dpl :2; /* Descriptor privilege level, 访问本段所需权限 */
unsigned int s :1; /* 描述项类型 1表示系统 0表示代码或数据 */
unsigned int type : 4; /* 段的类型 */
unsigned int base_0_23 :24; /* 基地址的低24位 */
unsigned int seg_limmit_0_15: 16; /* 段长度的低16位 */
} 段描述项;

可以看出每个段描述项的大小是8个字节,含有段的基地址和段的大小,再加上一些其他的信息。

16位段寄存器中的高13位用作下标访问段描述表,低3位含有其他信息:

typedef struct {
unsigned short seg_idx : 13; /* 13位的段描述项下标 */
unsigned short ti :1; /* 段描述表指示位, 0表示GDT, 1表示LDT */
unsigned short rpl :2; /* Requested Privilege level, 要求的优先级别 */
} 段寄存器;

页式内存管理机制
--------------------------

在段式内存管理中逻辑地址映射成物理地址,但在页式管理中不再是物理地址,intel称之为线性地址,再通过页式管理转变成实际的物理地址。32位的线性地址的伪代码可以表示如下:

typedef struct {
unsigned short dir :10; /* 用作页面表目录中的下标, 该目录项指向一个页表项 */
unsigned short page :10; /* 用作具体页面表中的下标,该表项指向一个物理页面 */
unsigned short offset :12; /* 在4K字节物理页面内的偏移量 */
} 线性地址;

由于页面表和页面的起始地址总是在4K字节的边界上,这些指针的低12位都永远是0。可以利用这12位控制。目录项的结构的伪代码为:

typedef struct {
unsigned int ptba : 20; /* 页面基地址的高20位 */
unsigned int avail :3; /* 供系统程序员使用 */
unsigned int g :1; /* global,全局性页面 */
unsigned int ps :1; /* 页面大小, 0表示4K字节 */
unsigned int reserved :1; /* 保留, 默认为0*/
unsigned int a :1; /* accessed, 表示已访问过 */
unsigned int pcd; /*关闭缓存存储器 */
unsigned int pwt; /* Write-Through,用于缓冲存储区 */
unsigned int u_s; /* 为0时表示系统权限, 为1时表示用户权限 */
unsigned int r_w : 1; /* 只读或可写 */
unsigned int p :1; /* 为0时表示相应的页面不在内存中 */
} 目录项;

页表项的结构基本和目录项相同。

linux内核源代码的汇编语言代码
-----------------------------------------------
参见:http://asm.sourceforge.net/articles/linasm.html

Saturday, February 28, 2009

本杰明·巴顿奇事 感动的台词

——每个人在某种程度上都对自己有不同的认识,但是我们最后都会往同一个地方,只是走的路不同罢了。你也有属于你的路,Benjamin。
  Queenie: Everyone feels different about themselves one way or another, but we all goin' the same way.

——你永远也不清楚,接下来会发生什么。(You never know what's coming for you)

——大部分都是一个人,你是个与众不同的人,你的生活也注定如此。但我告诉你一个秘密,胖子们,瘦子们,高个的,或是白人......他们其实都一样孤独,但是他们格外害怕。

——弹琴不是看你弹得有多好,而是你对于你弹的东西有什么感受。这其实就是在为你自己演奏音乐。

——这儿也没有什么新奇的事情,事实便是如此,一个人在那里还好好的,说不定某天就会被别人替代了。

——如果我告诉你我并不是在变老,而是变得比别人越来越年轻呢?
  Benjamin Button: What if I told you that instead of gettin' older, I was gettin' younger than everybody else?
  ——那样的话,我为你感到难受,你要经历所有爱你的人都比你先死去,这还真是一个不小的责任呢。
  ——OS:我还从来没有以这种方式考虑过生与死的问题。
  ——Benjamin,我们注定要失去我们所爱的人,要不然我们怎么会知道他们对我们多么的重要。
  Mrs. Maple: Benjamin, we're meant to lose the people we love. How else would we know how important they are to us?

——我想如果我年轻很多的话,我将改变很多事情,并且弥补以前的那些遗憾。
——什么遗憾?
——我不断的在等待,思考我是不是能够做些什么来改变我的现状,做一些什么......这就是浪费生命......你永远也不能够再挽回了......那些逝去的时间......

——你可以像疯狗那样对周围的一切愤愤不平,你可以诅咒命运...但是等到了最后一刻...你还是得平静的放手而去。
  Captain Mike: You can be as mad as a mad dog at the way things went. You could swear, curse the fates, but when it comes to the end, you have to let go.

——我有一只眼睛瞎了,耳朵也基本听不清了,身体到处抽搐,我还经常忘记事情,但是你知道么?上帝不断地提醒我,我能活到今天就是很幸运了。
  Mr. Daws: Blinded in one eye; can't hardly hear. I get twitches and shakes out of nowhere; always losing my line of thought. But you know what? God keeps reminding me I'm lucky to be alive.

——当我的皮肤变得又老又松弛时,你还会爱我吗?
  Daisy: Would you still love me if I were old and saggy?
——但我满脸粉刺,你还会爱我吗?当我尿床的时候?害怕楼上有什么的时候?
  Benjamin Button: Would you still love ME if I were young and had acne? When I'm afraid of what's under the bed? Or if I end up wetting the bed?

——你在想什么?
——我在想没有什么东西能持续到永远的,我们也不例外。
  Benjamin Button: I was thinking how nothing lasts, and what a shame that is.
——有些东西时可以持续到永远的......
  Daisy: Some things last.

——一件事无论太晚,或者对我来说太早,都不会阻拦你成为你想成为的那个人。这个过程没有时间的期限,只要你想,随时都可以开始。要改变或者保留原状都 无所谓,做事本不应该有所束缚。我们可以办好这件事却也可以把它搞砸,但我希望最终你能成为你想成为的那个人。我希望你有时候能驻足于这个令你感到惊叹的 世界,体会你从未有过的感觉,我希望你能见到其他与你观点不同的人们,我希望你能有一个值得自豪的一生。如果和你想象的生活不一样,我希望你能有勇气,重 新启程。
  Benjamin Button: [Voice over; letter to his daughter] For what it's worth: it's never too late or, in my case, too early to be whoever you want to be. There's no time limit, stop whenever you want. You can change or stay the same, there are no rules to this thing. We can make the best or the worst of it. I hope you make the best of it. And I hope you see things that startle you. I hope you feel things you never felt before. I hope you meet people with a different point of view. I hope you live a life you're proud of. If you find that you're not, I hope you have the strength to start all over again.

  有些人 就在河边出生;
  有些人 被闪电击中过;
  有些人 对音乐有着非凡的天赋;
  有些人 是艺术家;
  有些人 游泳;
  有些人 懂得纽扣;
  有些人 知道莎士比亚 而有些人 是母亲;
  也有些人 能够跳舞
  Some people, were born to sit by a river.
  Some get struck by lightning.
  Some have an ear for music.
  Some are artists.
  Some swim.
  Some know buttons.
  Some know Shakespeare.
  Some are mothers.
  And some people, dance.

  Daisy: Will you sleep with me?
  Benjamin Button: Absolutely.
  
  
  Daisy:Goodnight Benjamin.
  Benjamin Button: Goodnight Daisy.

语言和刮胡子 && 自我修养问题

早上起来终于准备打理自己的胡子,我还是钟情于手动的剃须刀,刀片划过皮肤的感觉很好,Ronaldo同学听到我刮胡子的声音说:你还用手动剃须刀啊 后来我们引出了一段刮胡子和语言的对话:
word, excel等是电动剃须刀,很好用,很强大,直接推就行了;
perl等脚本语言是手动剃须刀,你可以比较好的控制,有自己的参与感(对比刀划过皮肤的感觉);
c/c++是牛刀,做这些文本编辑的功能牛刀确实不怎么好使;
汇编那是直接一根根的拔胡子,嗯,直接的赤裸裸的体会来了。。。

好了,扯皮到此, 语言就是个语言,是个表达工具而已,程序员的自我修养才是王道。下午打电话给萝卜恭喜了一番他的《程序员的自我修养》终于快要出书了。准备入手一本来ym一把。

Saturday, January 10, 2009

Weekly Report(WW01)

Weekly Report (WW01)

Accomplishments
  • Complete reading the chapter "Machine-Level Representation of Programs" of CSAPP
  • Complete to install Ubuntu on VirtualBox, configure the network and install and configure the powerful and lovely emacs23 on Ubuntu
  • Watch the movie "Once" and Listen to Album "Once"; Listen to the Album "菊次郞的夏天"

Plans for next week

  • Begin to work
  • Continue to read TICPP 2vol

Engineering

  • Install Ubuntu on VirtualBox and Configure the network --0.5d
  • Install and configure the powerful and lovely emacs23 on Ubuntu --0.5d

Overhead

  • Reading books --1d
Issues
  • Spend too much time to read news and surf on the internet
  • The time used to read books is too limitting.

Thursday, January 8, 2009

610室的四“博士”聚会

人物:阿杜(歌声起:我不是阿杜,我不会唱天黑。。。旋律参照“我不是黄蓉”),JiqiHuman, 小强,还有我(江湖人称老丐)

聚会地点:青芝屋某店某方桌

精彩瞬间:倒满茶,为四个博士的聚会干杯:祝阿杜脱离苦海成功,祝老丐临近绞刑,祝JiqiHuman和小强继续凌迟。

旁注:610室诞生了阿杜退学开始了SW工程师的生涯,今日修成正果;小强继续用凝聚态和美剧为自己煮着delicious and colorful life,K歌是他为doctor奋斗过程中的甜点;Jiqihuman“一心一意”的爱着预印本库里的quantum Robot,还"一心一意"的为CS所着迷,两心两意继续他的doctor;我take a big turn, transfer to Master,transfer to IT。

补充:期待Racking和Linny的back后举行610室的六"博士"聚会