习题讲解678(计算机概论).ppt

计算机概论第二次习题课,6、7、8KeyPointsExplanation,六章,OSI模型和TCP/IP协议OSI模型七层结构及其功能TCP/IP协议中协议类型及其应用互联网上文档分类网络分类:LAN、MAN、WAN连接设备：中继器、网桥、路由器和网关,OSI模型和TCP/IP协议(1),模型：由标准化组织制定的用于网络设计的指南OSI(OpenSystemsInterconnection)模型：由国际标准化组织ISO设计，理论上允许任意两个不同系统之间可以相互通信而无需考虑它们的底层体系结构。协议：用于控制网络或者交互式网络中不同设备间交互的一系列规则。TCP/IP(Transmissioncontrol/Internetprotocol)协议：TCP/IP协议是互联网上正式使用的协议组。所以TCP/IP协议中的层并不完全与OSI模型中的层相同。,OSI模型和TCP/IP协议(2),OSI模型,OSI模型例子,49.下面动作包含在OSI模型中的哪个层？a发送数据帧给下一个站点b从源至目的地发送数据包c从源至目的地发送长消息d登录远程计算机e加密和解密数据f将数据的机器码转换成统一字符编码标准(Unicode),DataLink,Network,Transport,Application,Presentation,Presentation,TCP/IP(1)分类,TCP/IP(2),IP地址：IPv4地址由4个字节（32位）组成；通常用点分十进制来表示客户端-服务器模型：客户向服务器请求服务客户：本地计算机上运行的应用程序；需要时运行服务器：在远程计算机上运行的应用程序；一直运行邮件地址：唯一的标示Internet上的一个邮箱本地部分：定义了特殊文件的名称，即用户邮箱域名：定义了作为SMTP服务器的计算机名,URL,URL(统一资源定位器)：HTTP所用的特殊地址，它是互联网上用于指定任何一种信息的标准。方法：用来传输文档的客户-服务程序，HTTP既是方法主机：存储信息的计算机，通常为计算机赋予www.开头的别名端口：定义了服务器的端口数量，可选路径：存储信息的文件的路径名例如：使用http协议，路径为：/user/general，计算机别名为：www.hadb,则其URL地址为：http：/www.hadb/user/general,文档类型,静态文档(staticdocuments)：在服务器端生成，只能被复制；如用户用浏览器下载文档动态文档(dynamicdocuments)：驻留在服务器端的程序，当浏览器发送请求，服务器就运行该程序并将结果返回给浏览器；如浏览器向服务器发出运行日期的请求活动文档(activedocuments)：程序，不能在服务器端运行，浏览器需要请求程序的传输，传输后这个程序会在浏览器中运行；如用户用浏览器下载游戏,网络分类,LAN局域网：MAN城域网WAN广域网,例子,如果有一个每个角落有一台计算机的正方形房间，哪种拓扑结构需要较少的电缆？a总线局域网b环形局域网c在房间中央有一个集线器的星形LAN解答：假设正方形边长为Lcm，则总线局域网需要3Lcm的电缆；环形局域网需要4Lcm的电缆；星形局域网需要2*sqrt(2)*Lcmor2.828Lcm的电缆。故需要较少电缆的为C,连接设备,连接设备比较,七章：操作系统,OS定义与组成部分内存管理系统单道程序多道程序虚拟内存进程管理器程序、作业和进程状态图进程同步：死锁(deadlock)和饿死(starvation)主流操作系统：windows、Unix和Linux,OS(operationsystem)定义,操作系统是计算机硬件和用户(程序和人)的接口，它使得其他程序更加方便有效地执行，并能方便地对计算机硬件和软件资源进行管理。操作系统组成部分,内存管理系统单道程序和多道程序,单道程序中，大多数内存专用于单一的程序，仅仅一小部分用来装载操作系统。多道程序中，同一时刻可以装入多个程序并能够同时执行这些程序，CPU轮流为它们服务。,例子,计算机装有一个单道程序的操作系统，如果内存容量为64MB，操作系统需要4MB，那么该计算机可以执行程序的最大内存是多少？若操作系统自动分配10MB内存给数据，则可以执行程序的最大内存又是多少？解答：64MB-4MB=60MB64MB-4MB-10MB=50MB,多道程序分区调度,内存被分成不定长度的几个分区，每个分区保存一个程序。此技术中，每个程序需完全载入内存，并占用连续的地址。执行模式：CPU在各程序之间交替服务。1.由一个程序开始，执行一些指令直到有输入/输出或者分配给当前程序的时间片结束2.CPU保存现场并转入下一个程序；重复1步骤3.所有程序执行完之后，CPU转回第一个程序,例子,多道程序的操作系统将60MB内存分为10MB、12MB、18MB、20MB；第一个程序运行需要17MB使用第三分区，第二个需要8MB使用了第一分区，第三个需要10.5MB，使用了第二分区；第四个需要20MB使用第四分区。问总共使用多少内存？总共浪费了多少内存？内存浪费率是多少？解答：总共使用的内存：17+8+10.5+20=55.5（MB）浪费的内存：60MB-55.5MB=4.5MB内存浪费率：4.5/60=7.5%,多道程序分页调度,内存被分成大小相同的帧；程序则分成大小相等的页；页和帧的大小一样；此技术下，程序在运行前全部载入内存，但在内存中不必是连续的；,例子,多道程序的操作系统使用分页调度，将可用内存60MB内存分为15页，每一页大小为4MB；第一个程序运行需要17MB，第二个需要8MB，第三个需要10.5MB，；第四个需要20MB。问总共使用多少内存？总共浪费了多少内存？内存浪费率是多少？解答：第一个程序需要5页4MB*5=20MB17MB第二个程序需要2页4MB*2=8MB第三个程序需要3页4MB*3=12MB10.5MB第四个程序需要5页4MB*5=20MB总共使用了60MB；浪费内存为：3+1.5=4.5MB；内存浪费率为7.5%,虚拟内存,微软的官方定义是:计算机使用的临时存储器，用来运行所需内存大于计算机具有的物理内存的程序；虚拟内存用部分硬盘空间做内存来弥补计算机RAM空间的不足。例1：内存空间为10MB，而我们需要运行10个程序，每个程序3MB；若同时运行10个这样的程序，则至少需要30MB的内存空间，这时候，虚拟内存大小就是至少20MB。,例子：,例2：一OS执行时需要所有的程序驻留在物理内存中。物理内存大小为100MB，虚拟内存为1GB；有多少10MB大小的程序可以同时运行？它们之中有多少可以随时驻留在内存中？多少则必须要存在磁盘里？解答：100MB/10MB=101GB/10MB=102.4可以同时运行112个10MB大小的程序有10个可以随时驻留在内存中有102个必须存在磁盘中,进程管理器程序、作业和进程,状态图,例子,进程在下面的情况下处于什么状态？a进程在使用CPUb进程结束打印，等待CPU又一次调用c进程因为时间片用尽而被终止d进程从键盘读取数据e进程打印数据,运行,就绪,就绪,等待,等待,死锁(Deadlock),死锁：是指两个或两个以上的进程在执行过程中,因争夺资源而造成的一种互相等待的现象,若无外力作用,它们都将无法推进下去.此时称系统处于死锁状态或系统产生了死锁,这些永远在互相等待的进程称为死锁进程.死锁发生需要四个必要条件：互斥：一个资源只能被一个进程调用占有资源占有：虽然不使用资源，但进程仍然占用直到有其他可用的资源先到先得：操作系统不能临时对资源重新分配循环等待：所有的进程和资源包含在一个环里,例子：,例1：三个进程(A、B、C)同时运行，进程A占用File1但需要File2，进程B占用File3需要File1，进程C占用File2需要File3.画出资源与进程之间的关系框图，并判断是否是死锁？例1：三个进程(A、B、C)同时运行，进程A占用File1，进程B占用File2需要File1，进程C占用File3需要File2.画出资源与进程之间的关系框图，并判断是否是死锁,第八章：算法,算法定义算法的三种结构：顺序、判断、循环算法的表示：流程图、伪代码基本算法排序：选择排序、冒泡排序、插入排序查找：顺序查找、折半查找递归,算法定义、结构,算法是一组明确步骤的有序集合，它产生结果并在有限的时间内终止。三种结构,算法的表示(1),流程图：只显示算法从开始到结束的整个流程，而无细节规则：椭圆或者圆角表示“开始”或者“终止”菱形表示“判断”长方形表示“处理”平行四边形表示“输入输出”,算法的表示(2),伪代码：类似英语的表示法，现在还无相应标准,基本算法排序(1),选择排序算法：该算法将列表分为两个子列表：已排序的和未排序的。使用两重循环，外层循环每次扫描时迭代一次，内层循环在未排序列表中寻找最小的元素并把它和未排序数据中第一个元素进行交换。,SelectsortInput：unsortedlist1.Setwallatthebeginning；2.Whiletherearemoreelmentsintheunsortedlist2.1Findsmallestelmentinunsortedlist2.2Swap(Smallest,First)2.3AdvancewallEndloop3.ReturnlistEnd,基本算法排序(2),冒泡排序：两重循环，外层循环每次扫描过程中迭代一次，每次内层循环则将一个元素冒泡至顶部(左部)。,基本算法排序(3),插入排序：双层循环，外层循环每次扫描迭代一次，内层循环则寻找插入的位置。,例子,例1：分别使用选择排序、冒泡排序和插入排序算法，手工排序下列数据并给出每次扫描所做的工作；147233140567892,基本算法查找,顺序查找：从表头开始查找，若当前元素不是目标元素，右移指针，直到找到目标值或者确信查找目标不在列表中。一般用于查找无序列表，针对较小的列表或者是不常用的列表，效率低。折半查找：从测试列表的中间元素开始查找，判别目标值是在前半部分还是后半部分；若在前半部分，则无需查找后半部分；重复此过程直至找到目标值。用于有序列表查找，效率比较高。递归算法包含了算法本身，则为递归；换句话说，递归是算法自我调用的过程,例子,一个列表包含以下元素。使用折半查找法，跟踪查找88的步骤，要求给出每一步中first、mid和last的值。813172644568897,例子,使用如下定义编写一个寻找两个整数最大公约数(gcd)的递归算法。GCDInput:2integers(XandY)1.IfXY1.1ReturnGCD(Y,X)2.ElseifYequals02.2ReturnX3.Else3.3ReturnGCD(Y,X%Y)EndifEnd,