实验内容
进程从创建(Linux下调用fork())到结束的整个过程就是进程的生命期,进程在其生命期中的运行轨迹实际上就表现为进程状态的多次切换,如进程创建以后会成为就绪态;当该进程被调度以后会切换到运行态;在运行的过程中如果启动了一个文件读写操作,操作系统会将该进程切换到阻塞态(等待态)从而让出CPU;当文件读写完毕以后,操作系统会在将其切换成就绪态,等待进程调度算法来调度该进程执行……
本次实验包括如下内容:
基于模板“process.c”编写多进程的样本程序,实现如下功能:
所有子进程都并行运行,每个子进程的实际运行时间一般不超过30秒;
父进程向标准输出打印所有子进程的id,并在所有子进程都退出后才退出;
在Linux 0.11上实现进程运行轨迹的跟踪。基本任务是在内核中维护一个日志文件/var/process.log,把从操作系统启动到系统关机过程中所有进程的运行轨迹都记录在这一log文件中。
在修改过的0.11上运行样本程序,通过分析log文件,统计该程序建立的所有进程的等待时间、完成时间(周转时间)和运行时间,然后计算平均等待时间,平均完成时间和吞吐量。可以自己编写统计程序,也可以使用python脚本程序—— stat_log.py ——进行统计。
修改0.11进程调度的时间片,然后再运行同样的样本程序,统计同样的时间数据,和原有的情况对比,体会不同时间片带来的差异。
1
问题背景
KNN 算法,即 K 最近邻算法,是模式识别中一种最基本的用于分类与回归的非参方法。
KNN 算法的核心思想是如果一个样本在特征空间中的 K 个最相邻的样本中的大多数属于某一个类别,则该样本也属于这个类别,并具有这个类别上样本的特性。该方法在确定分类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。 KNN 方法在类别决策时,只与极少量的相邻样本有关。由于 KNN 方法主要靠周围有限的邻近的样本,而不是靠判别类域的方法来确定所属类别的,因此对于类域的交叉或重叠较多的待分样本集
来说,KNN 方法较其他方法更为适合。
KNN 问题最主要的难点在于,在输入数据规模较大(N 较大)的情况下,朴素的线性查找算法变得难以接受。为此,学界主要提出两种不同的改进思路:空间划分和哈希。
这里我们重点了解下局部敏感哈希。
局部敏感哈希
Indyk(1998) 最早提出了局部敏感哈希算法,为了解决所谓的“高维诅咒”给空间划分方法带来的优化难题。
1.基本原理
我们知道,通过建立 hash table 的方式我们能够得到 O(1)的查找时间性能,其中关键在于选取一个 hash function,将原始数据映射到相对应的桶内(bucket, hash bin),例如对数据求模:h = x mod w,w 通常为一个素数。在对数据集进行 hash 的过程中,会发生不同的数据被映射到了同一个桶中(即发生了冲突 collision),这一般通过再次哈希将数据映射到其他空桶内来解决。这是普通 hash 方法或者叫传统 hash 方法,其与 LSH 有些不同之处。
##实验内容##
此次实验的基本内容是:在Linux 0.11上添加两个系统调用,并编写两个简单的应用程序测试它们。
####iam()####
第一个系统调用是iam(),其原型为:
int iam(const char * name);
完成的功能是将字符串参数name的内容拷贝到内核中保存下来。要求name的长度不能超过23个字符。返回值是拷贝的字符数。如果name的字符个数超过了23,则返回“-1”,并置errno为EINVAL。
在kernal/who.c中实现此系统调用。
####whoami()####
第二个系统调用是whoami(),其原型为:
int whoami(char* name, unsigned int size);
它将内核中由iam()保存的名字拷贝到name指向的用户地址空间中,同时确保不会对name越界访存(name的大小由size说明)。返回值是拷贝的字符数。如果size小于需要的空间,则返回“-1”,并置errno为EINVAL。
##实验内容##
改写bootsect.s主要完成如下功能:
- bootsect.s能在屏幕上打印一段提示信息“XXX is booting…”,其中XXX是你给自己的操作系统起的名字,例如LZJos、Sunix等(可以上论坛上秀秀谁的OS名字最帅,也可以显示一个特色logo,以表示自己操作系统的与众不同。)
改写setup.s主要完成如下功能:
- bootsect.s能完成setup.s的载入,并跳转到setup.s开始地址执行。而setup.s向屏幕输出一行”Now we are in SETUP”。
- setup.s能获取至少一个基本的硬件参数(如内存参数、显卡参数、硬盘参数等),将其存放在内存的特定地址,并输出到屏幕上。
- setup.s不再加载Linux内核,保持上述信息显示在屏幕上即可。
####第一个非常简单,而且在实验指导书里写的很清楚了####
! 首先读入光标位置
mov ah,#0x03
xor bh,bh
int 0x10