开始用Word 2007发布日志
发现书上很多加了星号的题目我都得看Instructor's Manual才会做 =_=
Problem: Show how to solve the fractional knapsack problem in O(n) time. Assume that you have a solution to Problem 9-2.
Problem 9-2就是在最差情况下也能在O(n)时间内求出第k大元素的算法。
解答：
使用线性算法找出Vi / Wi的中位数
将物体分成三个集合，G = { i : Vi / Wi > m } E = { i : Vi / Wi = m} L : { i : Vi / Wi < m}，同样能在线性时间内完成
计算WG = Sigma(Wi), i ∈ G; WE = Sigma(Wi), i ∈ E
-
如果WG > W，则不在G中取出任何物体，而是继续递归分解G
-
如果WG <= W，取出G中所有物体，并尽可能多得取出E中物体
-
如果WG + WE >= W，也就是说步骤2以后背包已经放满，则问题解决
-
否则如果尚未放满，则继续在L上递归调用查找W – WG - WE的方案
以上所有调用都在线性时间内完成，每次递归调用都能减少一半的数据规模
因此运行时间的递归式为
T(n) <= T(n/2) + Omega(n)
有Master Theorem可得
T(n) = O(n)
问题：
已知一些活动的起止时间{Si}, {Fi}，把它们安排在若干个大厅中进行，要求任一大厅任意时间段内不能有两项活动同时进行，求出所需的最少的大厅数。
分析：(from CLRS Instructor's Manual)
这是一个区间图的着色问题(Interval-graph Coloring Problem)，用点表示活动，把时间冲突的活动连起来，然后进行点的着色，要求同一线段的两端不能有相同颜色的点。
首先最容易想到的就是用书上的Greedy-Activity-Selector找出可安排在大厅1的最长序列，然后删去这些活动，再次调用该方法，找出安排在大厅2的活动，以此类推。
复杂度O(n*n)
还有一个O(n*logn)的算法，甚至在起止时间都是比较小的数字时复杂度只有O(n)。
主要思想是依次遍历每个活动，把它们安排到不同的大厅中。
维护两张表，一张记录当前时间t已经安排了活动的大厅，另一张记录当前时间空闲的大厅
然后从头扫描排序后的时间点序列（如果事件a的结束时间等于时间b的开始时间，那么前者应该排在后者后面）
碰到开始时间t，把该活动放到空闲列表的第一个大厅中（如果空闲列表为空则新加一个大厅），然后把该大厅放入已安排的大厅列表中；
碰到结束时间t，从已安排的大厅列表中移出相应大厅到空闲列表。
复杂度分析：
排序：O(n logn)，如果时间范围有限制还可以做到O(n)
处理：O(n)
发信人: CJC (蓝色雪狐), 信区: 05SS
标 题: OS_Lab3 指南 List
发信站: 复旦燕曦BBS (2007年10月11日03:55:12 星期四), 转信
先写点List的东西吧，这个其实在以前并不作为重点讲，不过好像大家对它还是有些偏
见，所以这次稍微讲下吧。作用是为到时候建立进程关系列表做准备。
讲的内容都在/usr/src/linux.../include/linux/list.h中，大家只要把一些不必要的
ifdef和一些prefetch的东西删掉就好了。
首先讲讲历史。在没有范型的Java里面我们用的链表往往会这样（如果转成C的话）：
typedef struct list_head {
struct list_node *prev;
void *data;
struct list_node *next;
} list_t;
通过这个结构，我们就能完成链表的功能了。但是我觉得这个数据结构不好，原因有二
：
第一：这个结构比较容易引起内存碎片。
┌──┬─┬──┐
│prev│ │next│<----多余内存消耗
└──┴┼┴──┘
│ ┌───┐
└─>│ data │
└───┘
这种设计每一个节点都会引起一块多余的内存消耗。
第二：类型不明确，因为现在没办法用范型。如果写明了类型，那么还要为每种类型的
list自己再做一整套函数，得不偿失。
当然，还会考虑类似于我们希望用别人写得比较好的代码之类的原因。
那让我们来看看我们版本里的list_t是怎么定义的
typedef struct list_head {
struct list_head *next, *prev;
} list_t;
乍一看，这个list_head里面什么都没包含，只有一对前后指针，没有指向数据的指针
。那怎么用呢？这里的做法我叫做：反包含。我们来看一个具体的使用例子：
typedef struct test_struct {
int val1;
int val2;
char vals[4];
list_t all_tests; //千万注意，这里是list_t，不是list_t *
} test_t;
那么我们声明了这个数据结构在内存中是什么样的呢？
(test_list) ┌─────┐┬ <--my_test_struct_p(test_t *)
┌──┬──┐ │ val1 ││
│prev│next├┐ ├─────┤│
└──┴──┘│ │ val2 ││h
│ ├─────┤│
│ │ vals ││
表示指向首地址└──>├──┬──┤┴ <--my_list_p(list_t *)
│prev│next│ //这里如果是list_t *就不是这样画了！
└──┴──┘
上图就是一个test_t的结构图。小地址在上，大地址在下，val1上面的那条分界线作为
val1的起始地址（请注意我my_test_struct_p及其它指针的画法，是指向上面那根线，表示
为那个东西的起始地址，为清楚起见推荐大家以后这样画）
然后为了把所有的test_t数据结构串起来，我们需要一个全局变量：test_list，类行
为list_t（如果这里声明list_t *的话一定要为它分配空间！如果是死的全局变量、全局数
组和一些临时数组，推荐直接声明成类型而不是指针，因为编译器会放在dat/bss和stack段
里。但是如果这个数据结构是返回类型的分配空间，一定要malloc!否则回去就会错。这里
也提醒一下）
我们可以看到test_list.next是指向my_test_struct_p->all_tests，而不是my_test_s
truct。但是对我有用的应该是my_test_struct。所以一般处理方法有二，
第一种比较死板，就是在数据结构的一开始就放一个list_t（命名为list），那么&lis
t=&stru，可以直接(xxx *)list_p。但是问题是如果一个数据结构可以同属两个链表，如pc
b，又要是run_list的成员，又要是all_tasks的成员，还要是父进程children的成员……这
种方法显然是不够的。
第二种方法就相对好些。大家可以看，
((unsigned int)my_list_p)-h=(unsigned int)my_test_struct_p
而怎么得到h呢？是不是需要每个数据结构都定义一个h呢？不需要，可以这样看
h=(unsigned int)(&(((test_t *)0)->all_tests))
就是把0地址当作是test_t数据结构的开始地址，那么这个数据结构的all_tests所在的
地址就是h了。
通过把这两个算式结合，我们可以得到一个宏：
#define list_entry(ptr, type, member) \
((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))
在这里的用法就是：
my_test_struct_p = list_entry(test_list.next, test_t, all_tests);
（如果使用类似于Simics的编辑器的话，all_tests的显示会是类似于没有定义变量，
不用管它，的确是这样的。最后编译成功就对了）。
看过了最精妙的list_entry之后我们就可以来看一些简单的操作了
#define INIT_LIST_HEAD(ptr) do { \
(ptr)->next = (ptr); (ptr)->prev = (ptr); \
} while (0)
为什么要加while(0)可以参见lab2指南里面的一些define帮助。其大致概念如下：
┌─────────┐
│ │
└->┌──┬──┐ │
┌─┤prev│next├─┘ //这里为了画清逻辑，不把指针放在首地址
│ └──┴──┘<-┐
│ │
└─────────┘
这是一个环状链表。一般这个作为头指针，链表为空的判断依据就是：
static inline int list_empty(struct list_head *head)
{
return head->next == head;
}
然后是添加，先有一个辅助函数：
static inline void __list_add(struct list_head *new,
struct list_head *prev,
struct list_head *next)
{
next->prev = new;
new->next = next;
new->prev = prev;
prev->next = new;
}
这个是添加在第一个：
static inline void list_add(struct list_head *new, struct list_head *head)
{
__list_add(new, head, head->next);
}
┌───────────────────┐
│ ┌─────┐ │
└->┌──┬──┐┌─>├──┬──┤ │
┌─┤prev│next├┘ ┌┤prev│next├-─┘ //这里的数据结构就省略画了
│ └──┴──┘<─┘├──┴──┤ <-┐
│ └─────┘ │
└───────────────────┘
ori_first
┌────────────────────────────┐
│ ┌─────┐ ┌─────┐ │
└->┌──┬──┐┌─>├──┬──┤┌─>├──┬──┤ │
┌─┤prev│next├┘ ┌┤prev│next├┘ ┌┤prev│next├─┘
│ └──┴──┘<─┘├──┴──┤<─┘├──┴──┤<-┐
│ └─────┘ └─────┘ │
└────────────────────────────┘
new ori_first
这个是添加在head->prev，由于是环状的，那么就是添在了最后一个
static inline void list_add_tail(struct list_head *new, struct list_head *head)
{
__list_add(new, head->prev, head);
}
┌────────────────────────────┐
│ ┌─────┐ ┌─────┐ │
└->┌──┬──┐┌─>├──┬──┤┌─>├──┬──┤ │
┌─┤prev│next├┘ ┌┤prev│next├┘ ┌┤prev│next├─┘
│ └──┴──┘<─┘├──┴──┤<─┘├──┴──┤<-┐
│ └─────┘ └─────┘ │
└────────────────────────────┘
ori_first new
接下来是删除：
这是辅助方法
static inline void __list_del(struct list_head *prev, struct list_head *next)
{
next->prev = prev;
prev->next = next;
}
这个是用了辅助方法__list_del并且把entry的前后都设为NULL，是为了安全起见
static inline void list_del(struct list_head *entry)
{
__list_del(entry->prev, entry->next);
entry->next = (void *) 0;
entry->prev = (void *) 0;
}
个人觉得list_del_init, list_move, list_move_tail, list_splice没啥太大作用…
…不过后面两个非常重要：
#define list_for_each(pos, head) \
for (pos = (head)->next; pos != (head); pos = pos->next)
#define list_for_each_prev(pos, head) \
for (pos = (head)->prev, prefetch(pos->prev); pos != (head); \
pos = pos->prev, prefetch(pos->prev))
使用方法：
list_t *pos;
list_for_each(pos, &test_list) {
test_t *tmp = list_entry(pos, test_t, all_tests);
//do something on tmp
}
=======================================================================
list_t *pos, *n;
list_for_each_safe(pos, n, &test_list) {
test_t *tmp = list_entry(pos, test_t, all_tests);
//do something on tmp
}
======================================================================
那么这两个有什么差别呢？我们可以来看这个例子：
list_for_each(pos, &test_list) {
list_del(pos);
}
首先，我们得到pos=test_list.next，然后删除，此时pos->next=0，如果按照list_fo
r_each的话下一个循环的pos就是NULL，再访问下去就出错了！同样的，修改位置也是。所
以在需要修改队列结构的时候，一定要使用list_for_each_safe。如果只修改对应的数据结
构其他字段，可以用list_for_each，因为这个效率比较高。
有了这些方法基本上就可以使用了。我们可以来看一个物理内存管理的例子：
#define USER_MEM_SIZE (256*1024*1024)
#define USER_MEM_START (16*1024*1024)
#define PAGE_SHIFT 12
#define PAGE_SIZE (1<<(PAGE_SHIFT))
#define PAGE_COUNT (((USER_MEM_SIZE)-(USER_MEM_START))>>(PAGE_SHIFT))
#define PAGE_START(ptr) (((ptr)-(all_pages))<<(PAGE_SHIFT)+(USER_MEM_START))
//获取这个page数据结构对应的起始地址
#define PAGE_STRU(addr) (&all_pages[((addr)-(USER_MEM_START))<<(PAGE_SHIFT)])
typedef struct page_struct {
unsigned long use_count;
list_t mem_list;
} page_t;
list_t free_list, lru_list; //lru是用作换出的，最近使用在队首，换出队尾页
//如果编译器不肯让我们这样定义的话用lmm_alloc或者out_alloc也可以。
page_t all_pages[PAGE_COUNT];
void init()
{
int i;
INIT_LIST_HEAD(&free_list);
INIT_LIST_HEAD(&lru_list); //初始化两个链表
for (i = 0; i < PAGE_COUNT; i++) {
all_pages[i] = 0;
list_add_tail(&all_pages[i].mem_list, &free_list); //加入free_list
}
}
//此处返回值作为错误信息，addr作为所需返回的物理内存起始地址
int get_page(unsigned int *addr)
{
if (list_empty(&free_list)) //没有空页
return -1;
list_t *lst = free_list.next;
list_del(lst);
list_add(lst, &lru_list); //最近使用，放到队首
*addr = PAGE_START(list_entry(lst, page_t, mem_list);
return 0;
}
void use_page(unsigned int addr)
{
page_t *pg = PAGE_STRU(addr);
list_del(&pg->mem_list);
list_add(&pg->mem_list, &lru_list); //将页面放到lru队列首
}
void return_page(unsigned int addr)
{
page_t *pg = PAGE_STRU(addr);
list_del(&pg->mem_list);
list_add(&pg->mem_list, &free_list); //将页面放到free队列首，下次取时用
}
物理页面管理基本上就类似于此。我们接下来来看一个稍微复杂些的例子，就是进程父
子关系的例子，去年又同学跟我反映这是一个交错链接或者说是嵌套链接，其实不然。我们
拆分开来看：
┌─────────-┐
│┌-────────┼───┐
│ ↘ A->children │ │
┌───-┼─>┌──┬──┐ │ │
│ └-─┤prev│next├┐│ │
│ └──┴──┘││ │
│┌────────────┘│ │
││ ┌-───┘ │
││ ┌─────┐ ↘┌─────┐│
│└>├──┬──┤┌─>├──┬──┤│
└-─┤prev│next├┘ ┌┤prev│next├┘
├──┴──┤<─┘├──┴──┤
└─────┘ └─────┘
B C
由图可知，A有BC两个子进程，分别连接到A进程的children上。此时，处理A的childre
n又有两种方法，第一种是增加指针，第二种是作为A进程的一部分。利用上面的思考方法，
我们可以知道，如果按照第一种做法，那么势必会引起更多的内存碎片，不方便。于是我们
把children作为pcb的一个field。那么B和C里面的prev/next该叫什么呢？因为B和C也是pc
b的数据结构，已经不可能再叫children了（而且他们也应该有children节点，因为他们也
可能有子进程）。那么我们就叫它为sibling吧。因为在这个链表里，除了A是父进程，其余
的都是兄弟进程。
所以pcb的父子关系可以这样写：
#define TASK_STATE_RUNNING 0
#define TASK_STATE_ZOMBIE 1
//调用了wait指令，等待子进程结束
#define TASK_STATE_WAIT_CHILD 2
typedef struct pcb_struct{
struct pcb_struct *parent; 父进程
unsigned long state;
list_t children;
list_t sibling;
list_t all_tasks;
} pcb_t;
//init是一个非常特殊的进程，一般我们的kernel一起来，就只负责两个进程：init和idle
//init的作用是先fork，子进程运行shell，它自身while(1) {wait(...);}就是负责回收
//孤儿进程。
//并且在此，我们可以把所有的进程都连接在init的all_tasks上面，这样又可以节省一个
//相当于前例test_list的全局变量。找所有进程只须遍历init->all_tasks即可。
//所以在生成init的时候应该是INIT_LIST_HEAD(&task->all_tasks)
void init_pcb(pcb_t *task, pcb_t *init)
{
INIT_LIST_HEAD(&task->children);
INIT_LIST_HEAD(&task->sibling);
task->parent = NULL;
task->state = TASK_STATE_RUNNING;
list_add_tail(&task->all_tasks, &init->all_tasks);
}
void add_child(pcb_t *parent, pcb_t *child)
{
child->parent = parent;
list_add_tail(&child->sibling, &parent->children); //想想为什么
}
void do_exit(pcb_t *task, pcb_t *init)
{
//exit_mem_first_part
list_t *pos, *n;
list_for_each_safe(pos, n, &task->children) //将所有子进程交给init
{ //~~~~
task_t *child = list_entry(pos, task_t, sibling); //这里是sibling
child->parent = init;
list_del(&child->sibling);
list_add_tail(&child->sibling, &init_children);
if (child->state == TASK_STATE_ZOMBIE && init->state != TASK_STATE_WAIT_
CHILD)
{
//这里激活init，并把init放到进程列表的尾端
}
}
//然后切换到父进程运行
}
如果看懂了以上的所有例子，那么链表结构应该就差不多了。由于篇幅关系，PCB的构
建就单列开来吧。这里专门讲LIST好了。:)
如果有代码觉得看的郁闷的，拿张纸画画对应的内存结构应该就会好些了
--
※ 修改:·CJC 于 Oct 11 03:57:46 修改本文·[FROM: 穿梭而来]
※ 来源:·复旦燕曦BBS yanxibbs.cn·[FROM: 穿梭而来]
http://10.132.140.73/lxr/http/blurb.html
在机房搭了一个，原本以为有笔记的功能，装好以后才发现只能阅读用，不过搜索功能还是很强大的。
转载，部分修改（标为红色）
我们在阅读linux源代码时都有这样的体会:核心的组织相对松散，在看一个文件时往往要牵涉到其他的头文件、源代码文件。如此来回跳转寻找变量、常量、函数的定义十分不方便，这样折腾几次，便使读代码的心情降到了低点。
lxr(linux cross reference)就是一个解决这个问题的工具：他对你指定的源代码文件建立索引数据库，利用perl脚本CGI动态生成包含源码的web页面，你可以用任何一种浏览器查阅。在此web页中，所有的变量、常量、函数都以超连接的形式给出，十分方便查阅。比如你在阅读/usr/src/linux/net/socket.c的源代码，发现函数 get_empty_inode不知道是如何以及在哪里定义的，这时候你只要点击get_empty_inode,lxr将返回此函数的定义、实现以及各次引用是在什么文件的哪一行，注意，这些信息也是超连接，点击将直接跳转到相应的文件相应的行。另外lxr还提供标识符搜索、文件搜索，结合程序 glimpse还可以提供对所有的源码文件进行全文检索，甚至包括注释！
下面将结合实例介绍一下lxr和glimpse的基本安装和使用，由于glimpse比较简单，就从它开始：
首先访问站点： http://glimpse.cs.arizona.edu/ 得到glimpse的源码
,比如我得到的是glimpse-4.12.5.tar.gz . 用root登录，在任一目录下用tar zxvf glimpse-4.12.5.tar.gz解开压缩包，在当前目录下出现新目录glimpse-4.12.5 .
进入该目录，执行
./configure
make
make install
如果单独使用glimpse，那么只要简单的执行glimpseindex foo即可，其中foo是你想要索引的目录，比如说是/usr/src/linux .glimpseindex的执行结果是在你的起始目录下产生若干.glimpse*的索引文件。
然后你只要执行glimpse yourstring即可查找/usr/src/linux下所有包含字符串yourstring的文件。
对于lxr，你可以访问lxr.linux.no得到它的源代码解包后，遵循如下步骤：
/*下面的文字来源于lxr的帮助文档以及本人的安装体会*/
1)修改Makefile中的变量PERLBIN和INSTALLPREFIX,使它们分别为 perl程序的位置和你想lxr安装的位置.在我的机器上，PERLBIN的值为/usr/bin/perl .至于INSTALLPREFIX，有如下原则，lxr的安装路径必须是web服务器能有权限访问。因此它的值简单一点可取 /home/httpd/html/lxr (对于Apache web server)。
2)执行 make install
3)修改$INSTALLPREFIX/http/lxr.conf :
baseurl : http://yourIP/lxr/http/
htmlhead: /home/httpd/html/lxr/http/template-head
htmltail: /home/httpd/html/lxr/http/template-tail
htmldir: /home/httpd/html/lxr/http/template-dir
sourceroot : /usr/src/linux # 假如对linux核心代码索引
dbdir : /home/httpd/html/lxr/dbdir/ #dbdirk可任意起名，且位置任意 glimpsebin: /usr/bin/glimpse #可执行程序glimpse的位置
4)在$INSTALLPREFIX/http/下增加一个文件.htaccess内容：
<Files ~ (source|search|ident|diff|find)$> ***
SetHandler cgi-script
</Files>
上面这个文件保证Apache server将几个perl文件作为cgi-script.
5)按照lxr.conf中的设置建立dbdir ,按照上例,建立目录
/home/httpd/html/lxr/dbdir
进入这个目录执行$INSTALLPREFIX/bin/genxref yourdir
其中yourdir是源码目录，比如/usr/src/linux
如果要结合glimpse，则执行glimpseindex -H . yourdir
6)修改 /etc/httpd/conf/
httpd.conf ,加入
<Directory /home/httpd/html/lxr/http>
Options All
AllowOverride All
order allow,deny
allow from all
</Directory>
7)进入/etc/rc.d/init.d/ 执行
killall httpd
./httpd start
进入X ，用浏览器
http://yourIP/lxr/http/blurb.html
大功告成 ，这下你可以舒心的读源码了。
Problem: You are given n real numbers - they are NOT sorted. Develop a linear time（O(n)）algorithm to find the largest gap between consecutive numbers when the n numbers are sorted. For example, given:
10 23 7 1 35 27 50 41
the algorithm should produce 13 as its result, since the sorted list is:
1 7 10 23 27 35 41 50
and the largest gap is 13 (between 10 and 23).
Please note that your algorithm cannot actually sort the n numbers.
Macsy (真心) 于 (Fri Oct 5 11:59:16 2007) 提到:
有一个方法需要额外的O(n)的空间。
首先找到最大最小数max,min
max gap 肯定不小于 (max-min)/n 。
然后以(max-min)/n为步长，建立n个桶
每个桶里面记录落在这个桶中的最大最小值。
最后顺序扫描这n个桶中的值就可以了。
大概代码是
input: a[n];
min=min_of(a[1..n]);
max=max_of(a[1..n]);
step=(max-min)/n;
b[0..n].min=maxfloat; b[0..n].max=-maxfloat;
for i=1 to n
ind = (a[i]-min)/step;
b[ind].min=min(b[ind].min, a[i]);
b[ind].max=max(b[ind].max, a[i]);
maxgap=step;
last=b[0].max;
for i=1 to n
if (b[i].min != maxfloat)
maxgap=max(maxgap, b[i].min-last);
last=b[i].max;
output maxgap
proftpd.conf中增加两行设置：
UseReverseDNS off
IdentLookups off
Come From Alacner Blog：http://blog.alacner.com/post/168.htm
同目录下包含这三个文件即可
mingwm10.dll
QtCore4.dll
QtGui4.dll
以下转载自《Linux kernel》
核心源码的顶层是/usr/src/linux目录，在此目录下你可以看到大量子目录：
arch
这个子目录包含了所有体系结构相关的核心代码。它还包含每种支持的体系结构的子目录，如i386。
include
这个目录包括了用来重构核心的大多数include文件。对于每种支持的体系结构分别有一个子目录。 此目录中的asm子目录中是对应某种处理器的符号连接，如include/asm-i386。要修改处理器结构 则只需编辑核心的makefile并重新运行Linux核心配置程序。
init
此目录包含核心启动代码。
mm
此目录包含了所有的内存管理代码。与具体体系结构相关的内存管理代码位于arch/*/mm目录下， 如arch/i386/mm/fault.c 。
drivers
系统中所有的设备驱动都位于此目录中。它又进一步划分成几类设备驱动，如block。
ipc
此目录包含了核心的进程间通讯代码。
modules
此目录仅仅包含已建好的模块。
fs
所有的文件系统代码。它也被划分成对应不同文件系统的子目录，如vfat和ext2。
kernel
主要核心代码。同时与处理器结构相关代码都放在arch/*/kernel目录下。
net
核心的网络部分代码。
lib
此目录包含了核心的库代码。与处理器结构相关库代码被放在arch/*/lib/目录下。
scripts
此目录包含用于配置核心的脚本文件（如awk和tk脚本）。
主要是做DS Project 1时碰到的问题
1. 泛型方法push(elemType &x)无法接受常数等const类型，必须将形参声明为const elemType &x
2. 在给泛型类SimpleList增加operator<<方法时，把实现代码放在类的声明外部会报错，直接放在里面就可以，不知道是不是必须是内联inline的才可以。
水木问了下，答案是
除非在友元声明中显式指定了模板参数，否则与函数模板同名的友元函数的声明不会引用该函数模板.如果未指定模板参数，则友元声明将声明一个非模板函数。
3. C++中可以throw很多东西，比如String, int等。catch (...)表示把所有的异常都捕捉到。
from 水木
1. 两两比较，找出最大的，n-1次
2. 从找最大的这条路线回溯，次大的必然在这条路线上，找到它需要logn - 1次（败者树的最大高度为logn）
其实就是一个锦标赛排序