Ivan 发表于 2006-3-8 10:35:58
浙江大学计算机专业课辅导班笔记
计算机组成复习提纲
1．计算机系统的层次结构,核心层为硬件->系统->外层应用软件
2．软件系统的分类:系统软件和应用软件.
系统软件:编译、os、汇编、应用软件：edit,cad…
3．计算机硬件组成：alu（数据通路datapath）、存储器、控制器、输入、输出
数据通道和控制器称为cpu或processor
4．机器指令格式及其分类
分类：算术运算指令、访问存储器指令（传送）、转移指令、移位指令、输入、输出指令
格式：无址
三地址
mips指令：三地址与二地址
5．用汇编指令进行程序设计
g=h+A #寄存器分配
add $t1,$s4,$s4 #i->$s4,i*2->$t1
add $t1,$t1,$t1 #i*4->$t1
add $t1,$t1,$s3 #$s3为A数组首址,$t1为A的地址
lw $t0,0($t1) #$t0=A的值
add $s1,$s2,$t0 #g=$s1=h+A
详见英文书p114
循环程序练习：转移指令应用 p126
loop:g=g+A;
i=i+j;
if(i!=h) goto loop;
(bne $s3,$s2,loop用法)
while(SAVE==k) P127
i=i+j;
(j loop用法)
case/switch statement P129
switch(k){//其中k取0,1,2,3
case 0:f=i+j;break;
case 1:f=g+h;break;
case 2:f=g-h;break;
case 3:f=i-j;break;
}
用beq，jr，j等指令给编写，开关语句要用汇编指令设计、编写，需要一张跳转表
k*4+首址（跳转表）
从表中取出跳转表地址
6．寻址方式
lw $t1,0($t2) #基地址寻址
add $t1,$t2,$t3 #寄存器寻址
addi $t1,$t2,100b #立即
beq $t1,$t2,l1 #pc相对寻址
j mm #j型寻址，相当于直接存储寻址
jr $t #寄存器寻址
重点掌握寻址方式、常用指令用于循环、当循环和开关语句汇编程序编程方法
7．数组与指令+编程设计（了解编程方法） P174
基于MIPS架构CPU及指令设计不要求
8．机器数的表示，补码，原码和标准的浮点数表示及运算
重点掌握串行加法、并行进行加法的设计，及进位时间的计算，并行进位链及串行进位的电路的设计方法，补码，浮点数表示（IE754标准）
原码乘法器（除法器）补码的设计原理及原理及逻辑框图设计
补码乘法，一位Booth’s P259,P257,加减交替法
IEEE 754标准：
e=E-127 e:真值 E:机器表示（移码）
1 8 23
E用移码表示，其中1位符号位
(-1)Sx(1+Significant)x2E
|M|=0.1XX......
9．掌握多时钟周期计算机数据通路的结构，掌握指令执行过程（能画出指令执行的状态转换图）
了解位程序的设计方法和基本工作原理
10．存储系统的体系结构，多级存储系统Cache----直接地址映射或组相联地址映射，全相联地址映射，地址映射的原理设计
虚拟地址、实地址、页表、页表寄存器，含义必须搞清楚，能计算页表容量=页表单元数x（标志位+实页号位长）
虚页号数=虚拟地址-页内地址 P545-549,P569-570
缺页中断、命中、失效，写通，回写术语概念
重点掌握抵制变换结构的工作原理，变换逻辑设计及给定虚地址，主存容量，页面大小，能计算，页表单元数，实页号长度，实地址位数及寻找到的实页号
段表不要求
11．I/O系统
磁盘系统，平均旋转时间，平均寻道时间
记录格式，地址表示：头号（页号），道号，扇区号
串行接口，并行接口（按位宽传输分）
中断分类，中断处理过程，中断请求，中断响应，中断处理，中断返回，中断屏蔽，开/关中断概念，多重中断
英文版P647-649
按控制方式分：
程序控制查询接口
程序控制中断方式，软件排队找中断源，矢量中断找中断源
DMA 直接存储器接口访问控制
通道 接口编址方式：单独编址方式（存储器统一编址）
重点掌握：向量中断，中断响应，执行中断隐指令，中断处理，中断返回等详细过程
英文版：第8章
王爱英：P332,P338 338-343
中断隐指令
题型：名词解释，计算题，若需要也可画图，编程（总分不少于30分）
友情提示：
Computer Organization&Design The Hardware/Software Interface(2th Edition)机械工业出版社 ，即为文中所指英文版，为本校教学用书。
复习时应该以英文版为主，再辅以其它中文参考书即可，另请参考往年试题。
操作系统原理复习（40分，选择题与主观题）
linux系统可作为实例分析
进程管理、存储管理、文件管理
第一部分：1 操作系统的概念
resource management (cpu,memory,i/o derice)资源管理
control of programme execution (schedule,dispatch,etc.)程序控制
user interface (system call,shell,gui)用户接口
选择题可考
2 os发展
simple batch system
系统逐个运行作业（job）,但操作员可以成批提交
multi-pregramme batch system
系统中存在多个作业，需要进行作业调度
time-sharing system (windows,unix,linux etc.)
各用户能分享计算机资源
强调公平性（faimess）
系统设计的主要目标：①缩短响应时间（response time）;
②提高吞吐量 （throughout）;
可考选择题
real-time system
满足应用的实时性要求 （有的系统取消虚存来提高速度）
distributed system,embeded system
(两头发展，一头大，一头小)
3 os的典型体系结构
monolithic(整体结构，单块结构) ：dos
layerd(层次结构)
micro-kernel(微内核结构) ㈠优点：1：扩充性好
2：内核子
3：不容易崩溃
㈡缺点：1：有可能速度偏慢
2：设计有困难
module 结构来克服linux 单块结构的弊端
4 现代操作系统
micro-kernel
multi-threading
multi-processor support
distributed os support
object-oriented desigh
virtual machine(如在windows上做linnx 的虚拟机)
real-time characteristics (solaris做的较好)
这些特点愈加明显,
5 操作系统的硬件支持
inside cpu:register,MMU,cache
interrupt
DMA
cache
第二部分 进程管理
进程
process-a programme in execution(并不意味着一个占用cpu在执行)
如：text section,data section,stack,current actirity.
进程是动态的。有生命的。主动的
进程是os 中资源拥有的基本单位（unit of responce ownership）
虚地址空间，内有及其他资源(i/o设备。文件等)
进程控制块（pcb）的管理：各种队列
如linnx用链式队列
进程的状态
如:running,ready,wait, stopped, swapped, zombie
（ 暂停）（一部分或全部调出）（僵死，进程执行完了，但
pcb还存在，进程还没消亡）状态迁移图
线程（thread）
线程式是调度的基本单位（unit of dispatching）
进程中的线程共享进程资源，但拥有私有堆栈及线程控制块（tcb,存储寄存器值，优先级及其他线程状态信息）
①用户级线程（ult:user-level thread）
用户自己管理，但操作系统提供一个库（library） 帮助，这个进程跟操作没关，os 不知道 不一定操作系统给，可自己写
操作系统调度的单位是进程，但如一个线程阻塞则整个阻塞 ，无法用多处理器
eg :posix thread (pthread)
②核心级线程
应用程序通过api调用核心线程管理例程(kernel thread facility) 来管理
需要进行模式切换
需os 调度的基本单位（不同线程式可以在多处理上运行，一个阻塞不会导致整个进程阻塞）
eg:windows thread
并发控制：互斥与同步
临界资源（critical resource）
一次只能有一个进程访问的资源
临界区（critical section）
访问临界资源的代码段（cs）
在一个时刻只有一个进程在临界区，为了保证只有一个进程在访问临界资源
互斥（mutual exclusicn）
在一个时刻最多一个进程在临界
同步
协调需要访问临界资源的进程，否则会导致race condition(竞争条件)
例：p0,p1习题课后
最大值？最小值？ ２－１００
two processes=p0,p1
shared variable int talty:=0
p0p1
临界区
①两个前提：
a．对处理器及各进程的相对速度（不会是的速度）不应有任何假设；
b．进程在临界区停留时间有限
②三个必须：
互斥（mutual exclusion）
有空让进：若没有进程在临界区，则应该让申请进入临界区的进程中的一个立即进入
有限等待（bounded waiting）：申请进入临界区的进程不会无止境的等待（即不会有饥饿现象）
１．软件方法
①例：课后习题
shared variables
boolean flag[2];//初始flase
int turn;//初始化0
Process Pi
do{
flag=true;
while(turn≠i)
{while(flag[j]);
turn=i;
}
<critical section>
flag=false;
<remainder section>
}while(1)
此算法正确吗？
不能保证互斥
②Dekker算法：算法不直观，只能解决二个进程问题
Peterson算法：直观，只能解决二个进程问题
Backery算法（面包房算法）
2．利用硬件支持
中断屏蔽：代价大，无法做到程序的交*执行；多处理机无法实现
特殊机器指令
Test and Set instruction
Exchange instruction
优点：适合多处理器环境、简单
缺点：必须忙等待，可能导致饿死
３．信号量
①数据结构
Count integer:>=0,表示可用资源数
<=0,绝对值表示挂起的起程数，初始化非负
②操作（是原语primitive）
wait(s) (即P):等待资源
siginal(s) (即V):释放资源
③二元信号量
不能判断有没有挂起进程
④producer consumer problem
缓冲区无限
缓冲区有限 wait操作肯定不能换
生产者消费者变换：写满时才能读，如何实现？
四、并发控制：死锁问题
死锁(deadlock)
系统存在一个进程集合，该集合中的每个进程都在等待被集合中的其它进程占用的资源
死锁发生的４个必要条件
①互斥(mutual exclusion)
②保持等待(hold and wait):保持等待，申请资源时拥有其他资源
③No preemption(非剥夺)
④Circular wait(循环等待)：若各类资源数均为１，一定死锁
dead lock prevention 死锁预防
间接预防：阻止Mutual exclusion,Hold and wait及No preemption都满足
直接预防：阻止Circular waut的发生
一种可行的方法：有序申请法（对所有资源类别编号，进程申请按序进行）
例：哲学家就餐问题，筷子编号，先拿编号小的，再满足大的
dead lock avoidance死锁避免
进程申请资源时，决定是否应该满足
必须预先知道每个进程需要的各类资源数
银行家算法：若新的状态是安全的，则满足它
Safe State:从此状态出发，存在某种执行序列（安全序列），可以使所有进程执行完毕，不安全状态不一定导致死锁。
Dead lock Detection 死锁检测
已知目前各进程占用资源数和申请资源数，判断当前是否发生死锁，方法是给每个进程做标记(mark)
五、进程调度(CPU Scheduling)
1．调度准则
用户角度：
①响应时间
②周转时间
系统角度：
①ＣＰＵ利用率
②公平性
③吞吐量
２．调度模式
①Non-preemptive 非剥夺
进程一旦被调度，则执行至结束或不能继续执行（如因发起I/O操作而等待）
②preemptive 可剥夺
３．调度算法(了解一下剥夺非剥夺的)
①FCFS：先来先服务，直到结束（非剥夺）
②RR：Round Robin(除了它，其它的都基于优先级)
③SPN：最短作业优先，shortest process next
如没有给出时间，则要预测执行时间，如指数平均法
④SRN：最短时间优先 shortest remaining next
⑤HRRT：最高响应比优先
⑥FeedBack:：反馈调度
⑦Fair-share scheduling 公平调度（Unix系统中）
a.多用户系统中，用户分组，每个组公平地享有CPU preemptive
b.进程数多的组，各进程享有CPU的时间相对较少
第三部分 存储管理
1．基础知识
①各种基本概念
②MMU
CPU Package
CPU MMU
逻辑地址变换为物理地址
2．连续存储分配：分区（Partition）
按内存分为若干分区，每个分区一个进程，以支持多道程序
......
3．分页（paging）
硬件支持：TLB，MMU...
每个进程一张页表
OS维护一张free-frame list
地址变换图
页表管理：
①分级法
②哈希页表法
③倒置页表（一个系统只有一个，可以节省空间，但速度慢）
POWERPC等就用到
4．分段
类似于连续存储分配中的动态分区，但有区别，段与段可以不连续
地址变换图
5．段页式
如80386地址变换图
第四部分 虚拟存储
进程的虚地址空间
1．页装入策略（page fetch policy）
a). Demand Paging(按需调页)：普通用
b). Prepare(预取)：Demand Paging的优化，发生缺页时，将该页及临近页一起装入
（因为局部性）
2．页替换策略
①Optimal：最优化方法
②FIFO：最先装入的被换出，得*队列实现
③LRU：最久未用的页被换出（基于locality，很有效）
④Clock policy：时钟算法，LRU不易实现，用它来近似模拟
Belady’s Anomaly(Belady异态)：内存分配大反而缺页率高，FIFO可能出现
⑤修改的Clock算法
3．抖动
进程缺页率过高，可用如下方法加以解决：
①优化算法
②提供更高速的交换设备
③增加内存
④减少进程数
Windows NT有一个工作集的方法
4．交换
实现虚拟存储的重要手段
扩大内存，可使系统运行比内存大的程序
交换空间
交换设备的管理
Swap cache
第五部分 文件系统与I/O管理
1．文件系统
文件分类
文件磁盘空间分配
文件控制块FCB
目录文件：存储目录下文件的信息（名字，FCB索引信息）
树型结构的文件系统
文件访问权限：
UNIX中的文件的三类用户：User,group,other
进程的uid和gid
2．文件系统空闲磁盘空间管理
位向量法
链接法
成组链接法：UNIX中用
索引法
UNIX文件系统，Linux文件系统 linux:
UNIX：i-node(索引节点)
3．I/O管理
I/O设备分类
Buffer
I/O buffering(缓冲)：
①解决CPU与I/O速度匹配
②解决数据传输大小匹配
③提高I/O的存取
④直接由OS管理
Buffer与Cache的区别
磁盘调度
......
友情提示：新的招生简章上的列出的操作系统参考书即为通常所说的恐龙书，然后还有一本William Stallings的也可以参考,时间不够可以参考这本书的中文版（第四版，电子工业出版社出版），恐龙书好像目前市面上是没有中文版的，其实看起来很容易懂得，耐心点好了！
^_^
数据结构复习
第一部分 数据结构复习大纲
复习目标
1) 掌握基本数据结构的概念及其应用，2) 如：堆栈、队列、链表、树、堆、图等
3) 掌握基本的sorting,Hashing和Searching算法
基本考试类型
证明题（如树的特性）出题概率不高
填空题 可能会有英文书的例子
问答题（含数据结构设计、算法结构等）
如图的表示方法、最小生成树、最短路径等
编程题（含算法设计）
注意思路清晰
数据结构的基本要素
链表
单向链表，双向链表、循环单双向链表、广义表
队列、堆栈：循环条件判断、数组表示
树
i. 树的二*树表示
ii. 二*树的特性（层次、结点等）
iii. 二*树的表达
iv. 二*树的周游（如已知先、中序，v. 求后序）
vi. 线索二*树（如已知中序线索，vii. 求遍历）、哈夫曼树
viii. 堆（Heap）---用数组表达，ix. 基本操作（插入、删除）
x. 二*搜索树（查找树）
xi. 森林（森林的二*树表达）
出题层次类型：
▲三种基本类型（线性表、树、图）的对象定义与操作实现---属于概念层次
▲应用问题（如最短路径）---属于方法层次
▲查找与排序---属于算法层次
查找：①静态查找（顺序、二分）
②动态查找（查找树、哈希）
查找树：平衡树，B+树，B-树）
排序：①选择排序......堆排序
②交换排序......快速排序
③插入排序......SHELL排序
图
1) 图的定义和表达(4种基本表达方法)
2) 图的操作：深度遍历、广度遍历、连通分量、生成树等
3) 最小生成树（两种算法）
4) 最短路径
迪杰斯特算法、动态规划法
5) AOV、AOE网
典型例子：拓扑排序、求关键路径
排序
i. 插入
ii. 快速
iii. 归并
iv. 堆
v. 拓扑
vi. 基数
查找
Hashing(构造、冲突解决)
最优二*查找树（概念即可）
AVL树（四种情况，如何维护即可）--->B+树
算法设计基本方法
回溯法
分治法（典型例子：归并排序）
贪心法（如：选择排序）
动态规划法
第二部分 复习内容
一、链表
1．单向链表就地逆转
q0 q1
q0 q1 q2
while(q1!=Null){
q2=q1->next;
q1->next=q0;
q0=q1;
q1=q2;}
初始：q0=Null
q1=L->next
广义链表
二、堆栈和队列
循环队列（判断满和空条件）
三、树
树的二*树表达
二*树的特性
a) 第i层二*树最多节点数 性质1
b) 深度为k的二*树最多节点数 性质2
c) 性质3（向上边的角度与向下边的角度结合
d) 2i,2i+1......
数组表示二*树
二*树的遍历
遍历算法
由前/中（后/中）推导后（或前）来构造树
线索二*树（加了一个结点，为了方便遍历实现）
中序线索（用此来实现遍历）
给出一棵树线索化
堆
插入元素、删除元素的算法
四、图
1．图的表示方法
数组表示：矩阵表示法（有向/无向）
邻接表（逆邻接表）表示法（有向/无向）
十字链表（有向）
多重链表（无向）
2．图的操作
深度搜索、广度搜索
最小生成树
a) Kruskal算法
b) Prim算法
最短路径
AOV和AOE
拓扑排序、关键路径
五、排序
插入排序，基本插入排序方法，希尔排序
交换排序：基本交换排序（冒泡、快速排序）
归并排序：循环、递归
选择排序：堆排序
快速排序（算法思想）
两种思路：①单向扫描；②双向扫描
堆排序
Adjust（从n/2开始调，保证左边是堆，右边是堆，往上调）
六、查找
1．Hashing
基本思想
构造方法
冲突解决（开放地址、线性探测、链表）
链表（关于其操作来实现冲突解决）
exp. Insert_LinkHashing(...)
2．AVL树
首先判别各种平衡旋转方法（找平衡因子被破坏的及谁破坏它的）
实现旋转来维护（简单的就是旋转后满足排序二*树）
友情提示：一般参考严版的书和习题就可以了，另外最好把上课用的英文课件下来看看，可能有算法填空题会从中间出的。^_^