[转帖]浙江大学计算机专业课辅导班笔记

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习题课后
最大值?最小值?  2-100
two processes=p0,p1
shared variable int talty:=0
p0p1
临界区
①两个前提:
  a.对处理器及各进程的相对速度(不会是的速度)不应有任何假设;
  b.进程在临界区停留时间有限
②三个必须:
互斥(mutual exclusion)
有空让进:若没有进程在临界区,则应该让申请进入临界区的进程中的一个立即进入
有限等待(bounded waiting):申请进入临界区的进程不会无止境的等待(即不会有饥饿现象)
1.软件方法
 ①例:课后习题
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
优点:适合多处理器环境、简单
缺点:必须忙等待,可能导致饿死
3.信号量
①数据结构
Count integer:>=0,表示可用资源数
      <=0,绝对值表示挂起的起程数,初始化非负
②操作(是原语primitive)
wait(s) (即P):等待资源
siginal(s) (即V):释放资源
③二元信号量
不能判断有没有挂起进程
④producer consumer problem
缓冲区无限
缓冲区有限 wait操作肯定不能换
 生产者消费者变换:写满时才能读,如何实现?
四、并发控制:死锁问题
死锁(deadlock)
系统存在一个进程集合,该集合中的每个进程都在等待被集合中的其它进程占用的资源
死锁发生的4个必要条件
①互斥(mutual exclusion)
②保持等待(hold and wait):保持等待,申请资源时拥有其他资源
③No preemption(非剥夺)
④Circular wait(循环等待):若各类资源数均为1,一定死锁
dead lock prevention 死锁预防
间接预防:阻止Mutual exclusion,Hold and wait及No preemption都满足
直接预防:阻止Circular waut的发生
一种可行的方法:有序申请法(对所有资源类别编号,进程申请按序进行)
例:哲学家就餐问题,筷子编号,先拿编号小的,再满足大的 
dead lock avoidance死锁避免
进程申请资源时,决定是否应该满足
必须预先知道每个进程需要的各类资源数
银行家算法:若新的状态是安全的,则满足它
Safe State:从此状态出发,存在某种执行序列(安全序列),可以使所有进程执行完毕,不安全状态不一定导致死锁。
Dead lock Detection 死锁检测
已知目前各进程占用资源数和申请资源数,判断当前是否发生死锁,方法是给每个进程做标记(mark)
五、进程调度(CPU Scheduling)
1.调度准则
用户角度:
①响应时间
②周转时间
系统角度:
①CPU利用率
②公平性
③吞吐量
2.调度模式
①Non-preemptive 非剥夺
  进程一旦被调度,则执行至结束或不能继续执行(如因发起I/O操作而等待)
②preemptive 可剥夺
3.调度算法(了解一下剥夺非剥夺的)
①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树
首先判别各种平衡旋转方法(找平衡因子被破坏的及谁破坏它的)
实现旋转来维护(简单的就是旋转后满足排序二*树)

友情提示:一般参考严版的书和习题就可以了,另外最好把上课用的英文课件下来看看,可能有算法填空题会从中间出的。^_^