initramfs 和 initrd 的区别

Linux 2.6内核引入了一个新的feature叫做initramfs。与initrd相比,initramfs有几个好处。
initrd模拟一个磁盘(这就是它的名字的由来,initramdisk或initrd)。模拟磁盘也就同时引入了Linux的块IO子系统的开销,比如缓存(caching),而initramfs从根本上把cache也装载(mounted)成filesystem(因此叫做initramfs).

Initramfs建立在page cahce之上,和page cache一样,会动态地自动增长和缩减尺寸来减入内存的使用量,而initrd做不到这点。
另外,不像initrd需要文件系统驱动(filesystem driver)的支持,比如EXT2 driver,如果你的initrd使用ext2。而initramfs则不需要文件系统的支持,initramfs的实现代码很简单,只是基于page cache的简单一层。

copyright blog.ykyi.net

Linux的开机启动顺序

对于x86机器的Linux的启动顺序,BIOS首先从启动设备载入MBR(Master Boot Record).存在MBR里的代码就去找分区表,从活动分区读入Linux的bootloader,最常用的像Grub,其它的有LILO,SYSLINUX。
Bootloader把压缩格式的内核映象载入并把控制权交给内核映像。
内核映像自解压,启动内核!

x86处理器有两种工作模式。实模式和保护模式。在实模式,你只能够寻址1M内存。保护模式下,就复杂得多,可以作到使用处理器的很多高级特性比如分页。CPU必须从实模式转到保护模式是一个单行通道(one-way street)。你不能从保护模式退入实模式。

内核第一阶段的内核初始化是在实模式中完成的。接下来从init/main.c 中定义的 start_kernel()函数进入你保护模式。start_kernel()先初始化CPU subsystem。接下来启动存储器和进程管理。然后启动外围总线和IO设备。启动序列的最后一个阶段便是init进程被启动。这个进程是所有的Linux进程的祖先。Init进程执行用户空间的脚本。这些脚本被用来启动必要的内核服务程序。Init最后spawn一个控制台给你。于是启动就完成了。

copyright blog.ykyi.net

ACM 马周游解题报告

 

 

 

简单的马周游问题

 

 

 

 
Description
 
在一个5 * 6的棋盘中的某个位置有一只马,如果它走29步正好经过除起点外的其他位置各一次,这样一种走法则称马的周游路线,试设计一个算法,从给定的起点出发,找出它的一条周游路线。
 
为了便于表示一个棋盘,我们按照从上到下,从左到右对棋盘的方格编号,如下所示:
 
1     2     3       4     5     6
 
7     8     9       10    11       12
 
13    14       15    16       17    18
 
19    20       21    22       23    24
 
25    26       27    28       29    30
 
马的走法是“日”字形路线,例如当马在位置15的时候,它可以到达2、4、7、11、19、23、26和28。但是规定马是不能跳出棋盘外的,例如从位置1只能到达9和14。
 
Input
 
输入有若干行。每行一个整数N(1<=N<=30),表示马的起点。最后一行用-1表示结束,不用处理。
 
Output
 
对输入的每一个起点,求一条周游线路。对应地输出一行,有30个整数,从起点开始按顺序给出马每次经过的棋盘方格的编号。相邻的数字用一个空格分开。
 
Sample Input
 
4
-1
Sample Output
 
注意:如果起点和输入给定的不同,重复多次经过同一方格或者有的方格没有被经过,都会被认为是错误的。
 
 
(1)原题中文大意
 
中国象棋的马按照象棋的规则在5 x 6 的棋盘上跑30步跑完所有的格子。
 
 
 
(2)算法思想及解题用到的主要数据结构
 
 
 
从每一个点往下走第二步,会有几点有效的行走位置。 把当前位置记在栈里面,以深度优先的方式进入下一个有效位置。如果下一个有效位置在之前已经走过,则从栈顶弹出上一位置,恢复到调出的位置后尝试未走过的有效位置。利用函数调用时会压栈的特别,用函数递归调用即可解决问题。
 
 
 
(3)详细解题思路
 
1. 先初始化一张表。这张表记下了棋盘上所有的30个位置的下一步可走的有效位置.
 
2. 写一个一般的递归调用自己的函数,表示马在走第几步时到了哪个位置,然后尝试走余下的所有可走位置。
 
3. 递归函数有两个退出条件。要么下一个要尝试的点已经走过了,要么走到了最后一步,即得解!
 
 
 
(4)逐步求精算法描述
 
用一个数组记下来经过的点。
 
 
 
(5)程序注释清单
 
#include <iostream>

#include <cstring>

#include <cstdlib>

#include <vector>

using namespace std;

const static char row_num = 5;   // 5行

const static char column_num = 6;  // 6列



// 这个全局数组在初始化后会记下每30个有效位置的下一步可走位置.

// elocution[x][0]记个数。最多8个有效可走位置。

char elocution[30][9];

struct coordinate  // 坐标.

{

char _x;  // start from zero.

char _y;

};

// 坐标转序号的函数。

char coordinate2serial_num(coordinate co)

{

char num = co._x * column_num + co._y + 1;

return num;

}

// 序号转坐标的函数。

coordinate serial_num2coordinate(char sn)

{

coordinate co;

co._x = (sn - 1) / column_num;

co._y = sn - co._x * column_num - 1;

return co;

}

// 增量数组.

char increments[8][2] =

{

1, -2, 2, -1, 2, 1, 1, 2,

-1, 2, -2, 1, -2, -1, -1, -2

};

// 得用增量数组来计算每一个位置的下一步有效位置。记到steps里面.

void next_step(char pos, char steps[])

{

char valid_count = 0;

coordinate co = serial_num2coordinate(pos);

coordinate tmp;

char serial_num;

for ( int i = 0; i < 8; i++ )

{

tmp._x = co._x + increments[i][0];

tmp._y = co._y + increments[i][1];

if ( tmp._x < 0 || tmp._x > 4 || tmp._y < 0 || tmp._y > 5 )

{

continue;

}

serial_num = coordinate2serial_num(tmp);

if ( serial_num >= 1 && serial_num <= 30 )

{

valid_count++;

steps[valid_count] = serial_num;

}

else

{

cerr << "Not expected to reach here.\n";

}

}

steps[0] = valid_count;

}

// 初始化记载所有点的下一步可走点的全局表。

void init_elocution()

{

for ( int i = 1; i <= 30; i++ )

{

next_step(i, elocution[i-1]);

}

}



char track[30];   // 记走过的路径.

bool quit_run_horse;

// 上文提高的递归函用函数.

void run_horse(char start_pos, char step_count)

{

if ( quit_run_horse ) // 用来快速退出深嵌套递归调用函数.

{

return;

}

for ( int i = 0; i < step_count; i++ )

{

// 已?经-经-过y这a点?了?.

if ( track[i] == start_pos )

{

return;

}

}

track[step_count] = start_pos; // 记下新走过的位置



if ( step_count == 29 )  // 最后一步则打印出结果。

{

for ( int i = 0; i < sizeof(track); i++ )

{

cout << (int)track[i];

if ( i + 1 != sizeof(track) )

{

cout << " ";

}

}

cout << endl;

quit_run_horse = true;

return;

}



for ( int i = 0; i < elocution[start_pos-1][0]; i++ )

{

run_horse(elocution[start_pos-1][i+1], step_count+1);

}

}

int main(int argc, char* argv[])

{

init_elocution();

int pos;

vector<int> vec;



while(true)

{

cin >> pos;

if (pos==-1)

{

break;

}

vec.push_back(pos);

}



for ( int i = 0; i < vec.size(); i++ )

{

quit_run_horse = false;

run_horse(vec[i], 0);

}

return 0;

}