- 博客(0)
- 资源 (46)
- 收藏
- 关注
RSS订阅进程调度算法包括先来先服务调度算法、最短作业时间优先（抢占式和非抢占式）、最高响应比调度算法4种
1. 实验目的
调度的实质是操作系统按照某种预定的策略来分配资源。进程调度的目的是分配CPU资源。由于进程调度程序执行的频率很高，因此调度算法的好坏直接影响到操作系统的性能。本实验的目的是编程模拟实现几种常用的进程调度算法，通过对几组进程分别使用不同的调度算法，计算进程的平均周转时间和平均带权周转时间，比较各种算法的性能优劣。
2. 实验原理
[1]. 进程调度算法描述
进程调度算法包括先来先服务调度算法、最短作业时间优先（抢占式和非抢占式）、最高响应比调度算法4种。(每个人必须做FCFS，然后在后面的三种中任选一种，即每个人必须做2种调度算法的模拟。)
[2]. 衡量算法性能的参数
计算进程的平均周转时间和平均带权周转时间。
3. 实验内容
（1）编程实现本实验的程序，要求：
[1]. 建立进程的进程控制块，进程控制块至少包括：
a) 进程名称；
b) 进程需要执行时间；
c) 进入就绪队列时间；
d) 进程执行开始时间
e) 进程执行结束时间
[2]. 编程实现调度算法。
[3]. 进程及相关信息的输入。这些信息可以直接从键盘上输入，也可以从文件读取。
[4]. 时间片与时间流逝的模拟。本实验需要对算法的执行计时，程序应该提供计算时间的方法。一种最简单的方法是使用键盘，比如每敲一次空格代表一个时间片的流逝。另一种方法是使用系统时钟。
[5]. 一组进程序列执行完毕，打印出结果信息。程序需要计算出每个进程的开始执行时间、结束时间、周转时间和带权周转时间，并为整个进程序列计算平均周转时间和平均带权周转时间。程序将计算结果按一定的格式显示在计算机屏幕上或输出到文件中。打印出进程调度顺序图。
[6]. 实现数据在磁盘文件上的存取功能。
（2）对下列就绪进程序列分别使用上面的几种算法进行调度，计算每种算法下的平均周转时间和平均带权周转时间。
进程号 到达时间 要求执行时间
0 0 1
1 1 35
2 2 10
3 3 5
4 6 9
5 7 21
6 9 35
7 11 23
8 12 42
9 13 1
10 14 7
11 20 5
12 23 3
13 24 22
14 25 31
2013-04-11
编写一个词法分析器，它针对输入文件，实现以下功能：
1、编写一个词法分析器，它针对输入文件，实现以下功能：
1）每遇到你的学号，就输出你的名字，对于其他的串原样输出。
2）统计输入文件中字母的数目。
例如：（以肖永跃的上机题为例）：
输入文件如下所示：
200213001 hello world
wo ai tian an men
hello world i love
200213001
输出应该如下所示：
肖永钦 hello world
wo ai tian an men
hello world i love
肖永钦
# of ids = 11, # of chars = 66
2013-04-02
设有二元函数f(x,y) = f(x) + f(y) 其中： f(x) = f(x-1) * x (x >1)
设有二元函数f(x,y) = f(x) + f(y)
其中： f(x) = f(x-1) * x (x >1)
f(x)=1 (x=1)
f(y) = f(y-1) + f(y-2) (y> 2)
f(y)=1 (y=1,2)
请编程建立3 个并发协作进程，它们分别完成f(x,y)、f(x)、f(y)
管道
2013-03-28
编写一个程序，用于统计文件中单词的总数，不同单词的数目。（假设输入文件中只包含字母和空格）
练习题（要求使用伪代码给出算法）：
编写一个程序，用于统计文件中单词的总数，不同单词的数目。（假设输入文件中只包含字母和空格）
eg: I love Beijing and I love Shanghai
单词总数：7
不同单词数目：5
2013-03-20
大连理工大学软件学院编译技术课程——词法分析上机实验
大连理工大学软件学院编译技术课程——词法分析上机实验
实验目的：对循环语句和条件判断语句编写词法分析编译程序，只能通过一遍扫描完成。(用c++实现)
实验要求：
(1) 关键字：
for if then else while do
所有关键字都是小写。
(2）运算符和分隔符：
： = + - * / <= >= ; ( ) #
(3)其他标识符（ID）和整型常数（NUM），通过以下正规式定义：
ID=letter(letter | digit)*
NUM=digit digit*
(4)空格由空白、制表符和换行符组成。空格一般用来分隔ID、NUM、运算符、分隔符和关键字，词法分析阶段通常被忽略。
各种词法单元对应的词法记号如下：
词法单元 词法记号 词法单元 词法记号
for 1 : 17
if 2 := 18
then 3 < 20
else 4 21
while 5 23
letter(letter+digit)* 10 >= 24
digit digit* 11 = 25
+ 13 ; 26
- 14 ( 27
* 15 ) 28
/ 16 # 0
词法分析程序的功能
输入：源程序
输出：二元组（词法记号,属性值/其在符号表中的位置）构成的序列。
例如：对源程序
x:=5; if (x>0) then x:=2*x+1/3; else x:=2/x; #
经词法分析后输出如下序列：
（10,’x’）(18, :=) (11,5) (26, ;) (2, if ) (27,( )……
1.几点说明：
（1）关键字表的初值。
关键字作为特殊标识符处理，把它们预先安排在一张表格中（称为关键字表），当扫描程序识别出标识符，查关键字表。如能查到匹配的单词，则该单词的关键字，否则为一般标识符。关键表为一个字符串数组，其描述如下：
char *keyword[6]={”for”, ”if”, ”then” ,”else”，”while”, ”do” };
(2) 程序中需要用到的主要变量为 token , id和num.
1）id用来存放构成词法单元的字符串；
2）num用来存放整数（可以扩展到浮点数和科学计数法表示）；
3）token用来存放词法单元的词法记号。
可以参考下面的代码：
do{
lexical(); //将词法单元对应的记号保存到token中，属性值保存到num或者id中
switch(token) {
case 11: printf ("(token, %d\n) ", num); break;
case -1: printf("error!\n");break;
default: printf("(%d,%s)\n", token, id);
}
}while (token!=0);
2013-03-18
七种排序算法（包括直接插入排序，折半插入排序，希尔排序，冒泡排序，快速排序，简单选择排序，归并排序）
七种排序算法（包括直接插入排序，折半插入排序，希尔排序，冒泡排序，快速排序，简单选择排序，归并排序）
还有两道题
1./*设计并实现一个有效的对n个整数重排的算法，使得所有负数位于非负数之前，给出算法的性能分析*/
2./*试给出一个同时找到n个元素中最大元素与最小元素的有效算法，并说明理由*/
2012-12-25
可用“破圈法”求解带权连通无向图的一棵最小代价生成树。所谓“破圈法”就是“任取一圈，去掉圈上权最大的边”，反复执行这一步骤，直到没有圈为止。
可用“破圈法”求解带权连通无向图的一棵最小代价生成树。所谓“破圈法”就是“任取一圈，去掉圈上权最大的边”，反复执行这一步骤，直到没有圈为止。请给出用“破圈法”求解给定的带权连通无向图的一棵最小代价生成树的详细算法，并用程序实现你所给出的算法。注：圈就是回路。
VS运行会出错，用visual studio 2010运行就可以
2012-12-21
假设以邻接矩阵作为图的存储结构，编写算法判别在给定的有向图中是否存在一个简单有向回路，若存在，则以顶点序列的方式输出该回路
假设以邻接矩阵作为图的存储结构，编写算法判别在给定的有向图中是否存在一个简单有向回路，若存在，则以顶点序列的方式输出该回路（找到一条即可）。（注：图中不存在顶点到自己的弧）
2012-12-21
已知有一个循环双链表，p指向第一个元素为x的节点，设计一个算法，从该循环双链表中删除*p结点
内存中一片连续空间(不妨假设地址从1到m)，提供给两个栈S1和S2使用，怎样分配这部分存储空间，使得对任一个栈，仅当这部分空间全满时才发生上溢。
2012-11-29
设双链表表示的线性表L=（a1,a2,……an）,试写一时间复杂吨为O(n)的算法，将L改造为L=（a1,a3……an……,a4,a2）
设双链表表示的线性表L=（a1,a2,……an）,试写一时间复杂度为O(n)的算法，将L改造为L=（a1,a3……an……,a4,a2）
2012-11-29
设ha和hb分别是两个带头结点的非递减有序单链表的表头指针
设ha和hb分别是两个带头结点的非递减有序单链表的表头指针，试设计一个算法，将这两个有序链表合并成一个非递减有序的单链表。要求结果链表仍使用原来两个链表的存储空间，不另外占用其他的存储空间。表中允许有重复的数据。
2012-11-29
设A和B是两个单链表，其表中元素递增有序
设A和B是两个单链表，其表中元素递增有序。试写一算法将A和B归并成一个按元素值递减有序的单链表C，并要求辅助空间为O(1),试分析算法的时间复杂度。
2012-11-29
已知head为单链表的表头指针，链表中存储的都是整形数据，实现下列运算的递归算法
已知head为单链表的表头指针，链表中存储的都是整形数据，实现下列运算的递归算法：
（1）求链表中的最大值。
（2）求链表中的结点个数。
（3）求所有整数的平均值。
2012-11-29
设计一个环形队列，用front和rear分别作为队头和队尾指针
设计一个环形队列，用front和rear分别作为队头和队尾指针，另外用一个tag表示队列是空（0）还是不空（1），这样就可以用front==rear作为队满的条件。要求设计队列的相关基本运算算法。
2012-11-29
由用户输入n个10以内的数，每输入i（0~9）
由用户输入n个10以内的数，每输入i（0~9），就把它插入到第i号队列中，最后把10个队列中非空队列，按队列号从小到大的顺序串接成一条链，并输出该链的所有元素。
2012-11-29
第六次上机作业
编译技术第6次上机内容
目的：充分理解并掌握中间代码生成的相关方法，用C++程序实现。
要求：
1．以S属性的语法制导定义为基础，将下列产生式附上一定的语义规则。即在原来语法分析的基础上插入相应的语义动作：将输入串翻译成三地址代码序列。
E ® E1 + T
E ® T
T ® T1 * F
T ® F
F® (E)
F ® digit
F ® id
2．以词法分析和语法分析部分的上机结果为基础，添加语义分析部分。即以LR文法为基础。当进行产生式归约时执行对应的语义动作。
3．输入：（-b+c*d）+c*d
输出：
t1= -b
t2= c*d
t3=t1+t2
t4= c*d
t5=t3+t4
4． 若输入有误，如：a++b**c(d+e)
则应提示：+后面缺少运算对象，
*后面缺少运算对象，
c后面缺少运算符，
请重新输入！
扩展：
将三地址代码优化为DAG代码
例如：
输入： （-b+c*d）+c*d
输出：
t1= -b
t2= c*d
t3=t1+t2
t5=t3+t2
2013-06-08
编译技术第5次上机内容
编译技术第5次上机内容
目的：充分理解语义分析的方法及相关语义计算的执行时机，用C++程序实现。
要求：
1．以S属性的语法制导定义为基础，将下表的语义规则嵌套在语法分析的过程中，即实现语法制导的翻译过程。
产 生 式 语 义 规 则
L ® E n print (E.val)
E ® E1 + T E.val := E1 .val + T.val
E ® T E.val := T.val
T ® T1 * F T.val := T1.val * F.val
T ® F T.val := F.val
F® (E) F.val := E.val
F ® digit F.val := digit.lexval
2．以语法分析部分的两次上机结果为基础，添加语义分析部分。即以LL(1)文法或者LR文法为基础。当产生式完全推导出来或者归约时执行对应的语义动作。
3．输入：
5+3+8*2
输出：24
4． 若输入有误，如：3**2(4+5)
则应提示：*后面缺少运算对象，
2后面缺少运算符，
请重新输入！
5． 由于输入串是具体的数值，因此应调用相应的词法分析的功能。
扩展：
1． 对浮点数也能完成上述的操作。
2． 增加减法和除法对应的产生式，并能计算其语义结果。
3． 在FTP中第五次上机的文件夹中有两个压缩包，用递归下降法实现的程序在压缩包“recursion_calculator.rar”中，用非递归的预测分析方法实现的程序在压缩包“predict_calculator.rar”中。可以任选其一作为基础进行改进。将其改造成有减法和除法的程序，并写出对应的产生式。
2013-05-28
实验五、进程互斥实验
5.4 独立实验
理发店问题：假设理发店的理发室中有3 个理发椅子和3 个理发师，有一个可容
纳4 个顾客坐等理发的沙发。此外还有一间等候室，可容纳13 位顾客等候进入理发
室。顾客如果发现理发店中顾客已满（超过20 人），就不进入理发店。
在理发店内，理发师一旦有空就为坐在沙发上等待时间最长的顾客理发，同时
空出的沙发让在等候室中等待时间最长的的顾客就坐。顾客理完发后，可向任何一
位理发师付款。但理发店只有一本现金登记册，在任一时刻只能记录一个顾客的付
款。理发师在没有顾客的时候就坐在理发椅子上睡眠。理发师的时间就用在理发、
收款、睡眠上。
请利用linux 系统提供的IPC 进程通信机制实验并实现理发店问题的一个解法。
里面包含示例以及需要完成的独立实验的代码。
2013-05-28
LR分析器，带纠错功能
第4次上机—语法分析2
目的：熟练掌握自下而上的语法分析方法，并能用C++程序实现。
要求：
1. 使用如下文法：
E ® E+T | T
T ® T*F | F
F ® (E) | id
2. 对于任意给定的输入串（词法记号流）进行语法分析，要求采用LR分析器来完成。手工构造LR分析表，利用移进-归约分析算法（P69 图3.12）输出（P70 表3.8）对应的动作部分。如：
输入：id*+id/(id+id)#
输出：移进
按 F->id归约
按 T->F归约
移进
error
……
3. 要有一定的错误处理功能。即对错误能提示，并且能在一定程度上忽略尽量少的记号来进行接下来的分析。
例如：
从状态0开始的记号流为：bm
将b移进之后，栈里的情况应该为： 0 b 2
此时查表发现 action[2,m]=error
输出打印：error
把A和状态1相继压入栈，用户指针后移到FOLLOW(A)对应的元素继续分析。
4. 利用P92页的表3.13的方式将错误进行分类提示，即给出具体的出错信息。
扩展：
在已有文法的基础上再加上减法“-”和除法“/”对应的产生式构成最终的文法。从而使得记号流可以处理带括号的加、减、乘、除四则运算。
2013-05-14
对于任意给定的输入串（词法记号流）进行语法分析，递归下降方法和非递归预测分析方法可以任选其一来实现。
第三次上机—语法分析1
目的：熟练掌握自上而下的语法分析方法，并能用C++程序实现。
要求：
1. 使用的文法如下：
E ® TE ¢
E ¢ ® + TE ¢ | e
T ® FT ¢
T ¢ ® * FT ¢ | e
F ® (E) | id
2. 对于任意给定的输入串（词法记号流）进行语法分析，递归下降方法和非递归预测分析方法可以任选其一来实现。
3. 要有一定的错误处理功能。即对错误能提示，并且能在一定程度上忽略尽量少的记号来进行接下来的分析。可以参考书上介绍的同步记号集合来处理。
可能的出错情况：idid*id, id**id, （id+id， +id*+id ……
4. 输入串以#结尾，输出推导过程中使用到的产生式。例如：
输入：id+id*id#
输出：E ® TE ¢
T ® FT ¢
F ® id
E ¢ ® + TE ¢
T ® FT ¢
……
如果输入串有错误，则在输出中要体现是跳过输入串的某些记号了，还是弹栈，弹出某个非终结符或者是终结符了，同时给出相应的出错提示信息。比如：
idid*id对应的出错信息是：“输入串跳过记号id，用户多输入了一个id”；
id**id对应的出错信息是：“弹栈，弹出非终结符F，用户少输入了一个id”
(id+id对应的出错信息是：“弹栈，弹出终结符 ) ，用户少输入了一个右括号（或者说，括号不匹配）”
有余力的同学可进一步考虑如下扩展：
1. 将递归下降方法和非递归预测分析方法都实现
2. 在语法分析的过程中调用第二次上机的结果，即利用词法分析器来返回一个记号给语法分析器。
3. 编写First和Follow函数，实现其求解过程。
测试文法：
A->BCDE
B->aBA|ε
C->F|ε
D->b|c|ε
E->e|ε
F->d|ε
2013-04-27
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人