UNIX简单shell的设计和实现实验报告
- 格式：doc
- 大小：172.50 KB
- 文档页数：5
UNIX第一次实验报告
实验题目
实验1 简单shell的设计和实现（20分）
目的：
练习使用编程环境，包括shell的命令，vi和gcc编译器。
体会进程概念，了解fork，execve，wait等系统调用。
要求：
1、除了系统调用execve，不允许使用其他的exec函数。
输入应当允许带多个参数(一行内可以表示)，不考虑通配符(即“*”、“?”、“-”等等)的处理。
2、输入错误命令能提示出错并进入下一轮接收命令状态。
3、可以用Ctrl-C和Ctrl-\结束简单shell的运行。
4、程序运行正确，提示简洁明确。
编程环境
UNIX 虚拟环境
题目分析
实验一利用课本第9页程序1-5的框架，实现允许输入命令带参数的简单shell。
原来的实现是不能够带参数的。
输入命令所能带的参数个数，只受到系统键盘输入缓冲区长度（以及shell输入缓冲区长度）的限制，该缓冲区的缺省长度是4096个字节。
实现时要解决的主要问题有：
1.正确理解并使用系统调用fork()，execve()和waitpid()；
2.根据简单shell的输入，构造execve函数的参数。
根据程序1-5，数组buf保存用户的输入，包括命令和参数。
由于shell命令的命令名和各参数之间是用空格分开，因此可以用空格作为分界符。
通过一个循环可以把buf数组中的命令和各个参数依次分离开来，并赋给数组argv 的各元素适当的指针值。
argv数组的最后一个指针必须是NULL。
接着就可以调用execve(argv[0],argv, environ)来执行用户输入的命令。
3.
4.算法设计
a)基本动态规划方法
i.基本思想：⑴、计算所给定的两个序列整个的相似分值，并得到一个相似度矩
阵（similarity matrix），也称做动态规划矩阵或得分矩阵；⑵根据相似度矩阵，
按照动态规划的方法回溯寻找最优的联配。
ii.递归关系
iii.算法描述
b)节省空间的全局比对算法
在利用动态规划表法计算时，每个数值只与前一行和本行的值有关，所以可以算完一行删掉一行，这样就在线性空间里解决的全局比对。
i.算法描述
ii.回溯
Hirschberg提出了一种更加实际的回溯算法，利用分治的思想，把空间复杂度从O(nm)减少到O(m)，其中m < n。
我们定义V r( i, j )为序列S的后i个字符所组成的子序列和序列T的后j个字符所组成的子序列的最优联配的分值。
定理：
在这个定理的基础上，Hirschberg给出了计算全局最优联配的算法：
1.计算V(n/2, m)，并将所得的分值存储于前趋矩阵F中
2.计算V r(n/2, m)，并将所得的分值存储于后续矩阵B中
3.寻找某一列k，使得在交叉点（n/2, k）处满足：
F( n/2, k) + B( n/2, m-k) = F( n, m)
4.将回溯任务划分为两个子问题：
a)在（0, 0）到（n/2, k）之间，找出一条最佳的路径
b)在（n, m）到（n/2, m-k）之间，找出一条最佳的路径
5.遇到的问题与解决方案
a)基本动态规划方法动态规划表无法建立
i.问题：最开始我想用基本DP方法解决，可是发现给定的DNA序列长度长达
一万六千多个字符，16000*16000这样的数组在java虚拟机中开辟不出来，导
致后面程序无法继续。
ii.解决方案：参考老师上课的幻灯片以及网上的资料，我采用线性空间的算法解决了问题，虽然多花了一些时间，可是总比算不出来好。
b)Hirschberg算法回溯出口问题
i.问题：在利用Hirschberg算法回溯时，当分治后的序列足够短时如何让程序正
确的跳出
ii.解决方案：两个字符串s, t，当其中有一个字符串的长度小于等于1时，则不再进行分治，而进入判断输出阶段。
在判断环节，如果s和t中有一个长度为
0，则说明另一个字符串对应的都是空格；如果其中一个字符串长度为1，即
只有一个字符，则将这个字符与另一个字符串中的每个字符比较，如果相同就
算对上，若不同则对空格，要是比到最后一个都没对上，则强制错对最后一个
字符。
c)找分治点时用时过长问题
i.问题：在回溯时，S的每个确定的分点S[i]要与T字符串的每个字符依次进行
判断，而且每次判断需要算两次全局比对，很费时间。
ii.解决方案：直接从T字符串的中点开始寻找，并向两边依次寻找。
实验代码及结果
另附压缩包。
实验心得
1.合作
这次实验虽然老师要求每个人独立完成，但是我在代码调试阶段得到了任智宇同学的大力帮助。
尤其是Hirschberg算法出口的问题上我们一起研究了很长时间。
而且工程中的Output类主要由任智宇编写。
所以希望老师能够认可我们的合作。
2.多渠道获取信息与耐心调试
这次实验所涉及的课件基本上都是英文的，理解起来有一定困难，所以我通过互联网找了很多相关。
其实这次工程的框架早已构建好了，就是一直在头疼那个分治思想的回溯方法，之后又在调试那个出口问题。
在彻底明白分治思想之前，曾经试过很多幼稚的方
法，比如直接截成四段，还有妄想把动态规划表输出到文件（结果输出了1G还停不下来）等。
经过耐心的调试于不断的改进，终于能有输出结果了。
还有很多地方不尽如人意，比如运行时间过长等。
希望能得到老师的进一步指导。
2010年6月9日星期三。
