操作系统原理与设计实现 课件 第8-13章 换入换出 -图形子系统

操作系统OperatingSystem第8章换入换出Chapter10:SwapIn/Out内存管理视图cs:ip逻辑地址0x00345008线性地址内存操作系统段04G用户代码段用户数据段用户栈段地址空间物理地址0x7008对用户是透明的用户眼里的内存!cs:ip逻辑地址操作系统段04G用户代码段用户数据段用户栈段地址空间1个4GB(很大)的地址空间用户可随意使用该地址空间，就象单独拥有4G内存该地址空间就被称为“虚拟内存”这个地址空间怎么映射到物理内存，用户全然不知必须映射，否则不能用!虚拟内存的优点内存04G地址空间优点1:地址空间>物理内存用户可以编写比内存大的程序4G空间可以使用，简化编程优点2:部分程序放入物理内存内存中可以放更多进程，并发度好，效率高将需要的部分放入内存，有些用不到的部分从来不放入内存，内存利用率高如一些处理异常的代码!程序开始执行、响应时间等更快虚拟内存思想既有利于系统，又有利于用户如何实现虚拟内存!从段页式内存管理开始页框号保护5R1R/W3R/W7R基址长度保护段号0x40000x0800R00x48000x1400R/W10xF0000x1000R/W20x00000x3000R3段号+偏移(cs:ip)逻辑地址页号偏移偏移物理地址物理页号线性地址部分逻辑地址对应段表项，发现缺段后调入部分线性地址对应页表项，发现缺页后调入分页易于硬件实现、对用户透明，适合请求调入请求调页!磁盘页表物理内存虚拟内存中的页面映射关系部分线性地址(逻辑页)对应物理页，那其它页呢?磁盘页表物理内存请求调页过程当访问没有映射的线性地址时…load[addr]i页错误处理程序(1)(2)(3)(4)(5)(6)但完成这个过程很费时间(有时候一条指令会引起几次调页)!显然是一个很好理解的过程请求调页的性能分析分析的背景:又一个计算机基本特征!决定了请求调页是否可用RegistersDatapath处理器MainMemory(DRAM)1ns10msSpeed(ns):100ns100sGsSize(bytes):MsSecondaryStorage(Disk)存储器层次请求调页时的有效访问时间有效访问时间=(1-p)ma+p调页时间100(1-p)+10000000p=100+9999900p110p<0.000001缺页率(页错误率)应该很小:1/105为什么请求调页仍是可行的?分配给一个进程的物理页框数应该足够多!页面应该足够大!这又违背了分页和请求调页的原则，又需要折衷!如何设计这些参数?再从计算机的基本特征开始!

实践性很强的学科怎么学?内存地址访问频率物理内存90/10原则!90%的程序访问10%的地址!页面4K，调入一页后许多指令不出现页错误这些参数从实践中获得!

请求调页的具体实现细节(1):load[addr]，而addr没有映射到物理内存物理内存磁盘页表load[addr]i页错误处理程序(1)(2)(3)(4)(5)(6)根据addr查页表(MMU)，页表项的P位为0，引起缺页中断(pagefault)(2):

设置“缺页中断”即可(3):“缺页中断处理程序”需要读磁盘(4):

选一个空闲页框学过磁盘处理后自然就明白了!(5):

修改页表(6):

重新开始指令如何重新开始指令?在指令执行过程中出现页错误addr1,r2,r3mov+(sp),(r2)页错误分配页面从磁盘读入设置映射OS指令重执行显然这一切应该对用户透明!需要一点硬件支持Fault:epc=0xffdd0页错误处理程序jmp0xffdd00xffdcc:addr1,r2,r30xffdd0:ldr1,0(sp)如何选一个空闲页框?没有空闲页框怎么办?分配的页框数是有限的页面淘汰(置换)需要选择一页淘汰有多种淘汰选择。如果某页刚淘汰出去马上又要用…FIFO，最容易想到，怎么评价?有没有最优的淘汰方法，MIN最优淘汰方法能不能实现，能否借鉴思想，LRU再来学习几种经典方法，它可以用在许多需要淘汰(置换)的场合…FIFO页面置换淘汰算法:FIFO一实例:分配了3个页框(frame)，页面引用序列为ABCABDADBCBCBADCBABCBDADBACBA321Ref:Page:评价准则:缺页次数；本实例，FIFO导致7次缺页D换A不太合适!选A、B、C中最远将使用的MIN页面置换MIN算法:选最远将使用的页淘汰。是一种最优的方案，可以证明缺页数最小!继续上面的实例:(3frame)ABCABDADBCBCDCBABCBDADBACBA321Ref:Page:本实例，MIN导致5次缺页可惜，MIN需要知道将来发生的事…怎么办?LRU页面置换用过去的历史预测将来。LRU算法:选最近最长一段时间没有使用的页淘汰(最近最少使用)。继续上面的实例:(3frame)ABCABDADBCBCDCBABCBDADBACBA321Ref:Page:本实例，LRU也导致5次缺页LRU是公认的很好的页置换算法，怎么实现?和MIN完全一样!LRU的准确实现每页维护一个时间戳(timestamp)继续上面的实例:(3frame)ABCABDADBCBBCBDADBACBAtimestampA1BC0D001200123042304530选具有最小时间戳的页!453675367538793879108选A淘汰!711108每次地址访问都需要修改时间戳，需维护一个全局时钟(该时钟溢出怎么办?)，需要找到最小值

…这样的实现代价较大

几乎没人用LRU准确实现之页码栈维护一个页码栈继续上面的实例:(3frame)ABCABDADBCBBCBDADBACBA页码栈每次地址访问都需要修改栈(修改10次左右栈指针)…实现代价仍然较大

LRU准确实现用的少AABCABABCBCA选栈底页淘汰!DABABDDBABADCDBBDCLRU近似实现将时间计数变为是和否每个页加一个引用位(referencebit)每次访问一页时，硬件自动设置该位选择淘汰页：扫描该位，是1时清0，并继续扫描；是0时淘汰该页再给一次机会(SecondChanceReplacement)组织成循环队列较合适！R=1R=1R=0R=1R=1R=1R=0R=0R=1R=0R=0R=1R=1R=1R=0R=1R=1R=1R=0R=0R=1R=0R=0R=0SCR这一实现方法称为ClockAlgorithmClock算法实例继续上面的实例:(3frame)ABCABDADBCB**C********D*******C***B**A*BCBDADBACBA321Ref:Page:本实例，Clock算法也导致5次缺页Clock算法是公认的很好的近似LRU的算法引用位！扫描指针！Clock算法分析的改造如果缺页很少，会?R=1R=1R=0R=1R=1R=1R=0R=0R=1R=0R=0R=1所有的R=1handscan一圈后淘汰当前页，将调入页插入hand位置，hand前移一位退化为FIFO!原因:记录了太长的历史信息…怎么办?定时清除R位…再来一个扫描指针!R=1R=1R=0R=1R=1R=1R=0R=0R=1R=0R=0R=1用来清除R位，移动速度要快!用来选择淘汰页，移动速度慢!更像Clock吧!清除R位的hand如何定速度，若太快?又成了FIFO!来看一个实际例子Solaris下键入命令:vmstat-sR=1R=1R=0R=1R=1R=1R=0R=0R=1R=0R=0R=1free?>>14157550pagesexaminedbyclockdaemon>>13065972pagesfreedbyclockdaemon>>110revolutionsofclockhand#sinceboot!原理:

第2条指针不是在缺页时工作，而是定期执行，检查引用位，将为0的页释放到空闲链表中。使用freelist回收最近一段时间没引用指针扫描速度如何定?一个定时调度的内核任务继续这个实际例子设定值吗?在slowscan和fastscan之间调整系统负载并不固定…slowsacnfastsacn空闲内存比率lotsfreeminfree空闲内存比率高于lotsfree时，扫描速度设为slowscan,并往大调稳定在这个区间上!清除指针和扫描指针的距离:handspread参数R=1R=1R=0R=1R=1R=1R=0R=0R=1R=0R=0R=1一个夹角scanrate=100,handspread=1000

两针间隔=10s两种置换策略Solaris换页daemon中的freelist使用freelist回收DBBCADAB全局置换局部置换想一想前面的例子!只能淘汰进程自己的页面可以淘汰别的进程的页面全局置换:实现简单但全局置换不能实现公平、保护:一个经过巧妙优化的程序里会出现大量goto，则…局部置换需要考虑的关键问题给进程分配多少页框(帧frame)分配的多，请求调页的意义就没了!一定要少?至少是多少?

可执行任意一条指令，如mov[a],[b]是不是就选该下界值?最坏情况需要6帧!来看一个实例:操作系统监视CPU使用率，发现CPU使用率太低时，向系统载入新进程。会发生什么?多道程序程度CPU利用率急剧下降CPU利用率急剧下降的原因系统内进程增多

每个进程的缺页率增大

缺页率增大到一定程度，进程总等待调页完成

CPU利用率降低进程进一步增多，缺页率更大…多道程序程度CPU利用率急剧下降此时:进程调入一页，需将一页淘汰出去，刚淘汰出去的页马上要需要调入，就这样……称这一现象为颠簸(thrashing)显然，防止的根本手段给进程分配足够多的帧问题时怎么确定进程需要多少帧才能不颠簸?工作集模型任何计算都需要一个模型!要确定进程所需的帧数该依靠什么信息呢?从请求调页的可行性开始!访问频率局部性现象!只要分配的帧空间能覆盖整个局部就不会出现太多的缺页!工作集模型就用来计算一个局部的宽度(帧数)工作集定义进程Pi工作集合WSi=在最近的时间内访问的页面集合，其中为工作集窗口一个例子:

定义为10个页引用数!10个页引用WSi的用法:(1)计算D=|WSi|;(2)如果D>m，则选择一个进程换出;(3)如果D<m，可以选一个进程换入。选择哪个进程换入、换出，中程调度工作集的计算根据定义，每次引用都重新计算WS，会很低效

该定为多少?太小盖不住一个局部，太大会包含多个局部。试试看?但系统有时并不敏感提出了基于页错误率的帧分配方案工作集大小定期扫描+定期计算(在定时中断中)是近似计算一种方案:每个页增加一个属性idletime()。扫描:如果访问位R为1，=0，R=0;否则+=CPU执行时间。计算WS：在WS中。UNIX,扫描周期:几秒.计算周期:几分钟.基于页错误率的帧分配页错误率(PFF)=页错误/指令执行条数

如果PFF>上限，增加分配帧数往往是PFF和WS互相配合如果没有空闲帧，则换出进程此种方法简单直接，在处理颠簸时常用。那WS呢?分配帧数PPF上限下限有趣的是，帧数越多，PPF并不一定下降但现代OS并不十分重视颠簸现象，因为CPU更快了，进程很快exit；内存更大了，局部的变化不大Belady异常来看一个例子!

引用序列1，2，3，4，1，2，5，1，2，3，4，5FIFO页置换13frame121234234134125125325349faults4frame112123123452345134512451234123452310faults什么样的页置换没有Belady异常看个模型!

引用序列1，2，3，4，1，2，5，1，2，3，4，5结论：栈式算法无Belady异常，LRU属于栈式算法!121321432114322143521431524321543321544321514325LRU栈实现m=3m=4m是分配的帧数特征:M(m,r)M(m+1,r)，如{5,2,1}{5,2,1,4}(m=3)满足这一特征的算法称为栈式算法!看看FIFO12323413412412312534m=312312341234123423451m=4不在一些技术预调页:

页可以不同自己的页错误而调入

进程创建(换入)时一次调入多个页(可由WS确定)页面尺寸:

该定为多少?受许多因素影响!减少碎片，页应该小程序结构:for(j..128){for(i..128){A[i][j]=0;}}//页大小128操作系统难吗?不难吗?难吗?不难吗?启动快，但可能有页用不着!页错误数降低页错误，页应大页大小碎片按行存储128*128faultsfor(i..128){for(j..128){A[i][j]=0;}}128faults整理一下前面的学习温故而知新虚拟内存的基本思想

将进程的一部分(不是全部)放进内存其他部分放在磁盘需要的时候调入:请求调页内存利用率高，程序编制容易，响应时间快…why?请求调页的基本思想

what?当MMU发现页不在内存时，中断CPUCPU处理此中断，找到一个空闲页框CPU将磁盘上的页读入到该页框如果没有空闲页框需要置换某页(LRU)how?一个实际系统的请求调页!Linux的请求调页从哪里开始这个故事?从缺页中断开始中断号名称说明10InvalidTSSCPU任务切换时发觉TSS无效12SegmentnotPresent描述符所指的段不存在14Pagefault页不在内存voidtrap_init(void){set_trap_gate(14,&page_fault);}#defineset_trap_gate(n,addr)\_set_gate(&idt[n],15,0,addr);dplLinux处理中断pagefault//在linux/mm/page.s中

.globl_page_faultxchgl%eax,(%esp)pushl%ecxpushl%edxpush%dspush%espush%fsmovl$0x10,%edxmov%dx,%dsmov%dx,%esmov%dx,%fsmovl%cr2,%edxpushl%edxpushl%eaxtestl$1,%eaxjne1fcall_do_no_pagejmp2f1:call_do_wp_page//保护2:add$8,%esppop%fspop%espop%dspop%edxpop%ecxpop%eaxiret测试标志P压入参数页错误线性地址取出错误码到eax置内核数据段选择符do_no_page//在linux/mm/memory.c中

voiddo_no_page(unsignedlongerror_code,unsignedlongaddress){intnr[4];unsignedlongtmp,page;intblock,i;address&=0xfffff000;//页面地址

tmp=address–cuurent->start_code;//页面对应逻辑地址

if(!current->executable||tmp>=current->end_data){

get_empty_page(address);return;}page=get_free_page();block=1+tmp/BLOCK_SIZE;for(i=0;i<4;block++,i++)nr[i]=bmap(current->executable,block);bread_page(page,current->executable->i_dev,nr);

不是代码和数据!指向可执行文件!需要等文件系统学完!do_no_page(续)voiddo_no_page(unsignedlongerror_code,unsignedlongaddress)...i=tmp+4096-current->end_data;tmp=page+4096;while(i-->0){tmp--;*(char*)tmp=0;}

put_page(page,address);//完成线性地址和物理地址的映射}

把超过end_data的数据清0//在linux/mm/memory.c中

voidget_empty_page(unsignedlongaddress){unsignedlongtmp=get_free_page();put_page(tmp,address;}put_page//在linux/mm/memory.c中unsignedlongput_page(unsignedlongpage,//物理地址

unsignedlongaddress){unsignedlongtmp，*page_table;page_table=(unsignedlong*)((address>>20)&ffc);if((*page_table)&1)page_table=(unsignedlong*)(0xfffff000&*page_table);else{tmp=get_free_page();*page_table=tmp|7;page_table=(unsignedlong*)tmp;}

page_table[(address>>12)&0x3ff]=page|7;returnpage;}页目录项_pg_dir=0do_wp_page//写时复制，进程创建//在linux/mm/memory.c中

voiddo_wp_page(xxerror_code,unsignedlongaddress){un_wp_page((unsignedlong*)(((address>>10)&0xffc)+(0xfffff000&*((unsignedlong*)((address>>20)&0xffc)))));}页表项的指针(物理地址)页表的开始地址对齐4K//在linux/mm/memory.c中

voidun_wp_page(unsignedlong*table_entry){unsignedlongold_page,new_page;old_page=0xfffff000&*table_entry;if(old_page>=LOW_MEM&&mem_map[MAP_NR(old_page)]==1){*table_entry|=2;invalidate();return;}Un-WriteProtect#defineMAP_NR(addr)(((addr)-LOW_MEM)>>12)//在linux/mm/memory.c中

voidun_wp_page(unsignedlong*table_entry)...new_page=get_free_page();if(old_page>=LOW_MEM)mem_map[MAP_NR(old_page)]--;*table_entry=new_page|7;invalidate();copy_page(old_page,new_page);}un_wp_page(续)//在linux/mm/memory.c中

#definecopy_page(from,to)\__asm__(“cld;rep;movsl”::”S”(from),”D”(to),”c”(1024):“cx”,”di”,”si”)虚拟内存总结内存的根本目的把程序放在内存并让其执行只要将部分程序放进内存即可执行内存利用率高可编写比内存大的程序使用一个大地址空间(虚拟内存)部分程序在内存其他部分在磁盘需要的时候调入内存页表项存在P位缺页产生中断中断处理完成页面调入调入页面需要一个空闲页框如果没有空闲页框置换需要给进程分配页框全局、局部颠簸

工作集置换方法FIFOMINLRUClockLinux如何处理缺页中断!操作系统OperatingSystem第9章设备驱动Chapter11:DeviceDriver回顾一下图灵机控制器纸带0111010对应CPU管理(进程)!对应内存管理!显示器键盘磁盘网卡等是操作系统的核心内容，让轮子转起来!I/O管理是操作系统的重要内容，它让轮子转的更好!认识计算机外设与计算机!PCI总线图形控制器IDE控制器总线控制器CPU-内存总线图灵机!扩展总线接口扩展总线并行口越来越多的任务超越了这个部分(如Web)!想一想外设怎么工作?PCI总线总线控制器CPU-内存总线IDE控制器发出一个读命令读完后向CPU发出中断将数据送往内存读磁盘CPU向控制器中的寄存器读写数据控制器完成真正的工作，并向CPU发中断信号想让外设工作并不复杂!I/O系统想给用户提供一个什么样的视图?从用户开始讲操作系统的故事总是合适的!看一段操纵外设的程序

intfd=open(“/dev/something”);

for(inti=0;i<10;i++){

fprintf(fd,”Count%d\n”,i);

}

close(fd);(1)不论什么设备都是open,read,write,close操作系统为用户提供统一的接口!(2)不同的设备对应不同的文件(设备文件)设备文件中存放了设备的属性!显然操作系统将完成…键盘命令系统调用接口open()，read()，write()，close()磁盘命令设备驱动设备属性数据进行解释键盘控制器磁盘控制器中断处理中断处理键盘磁盘称为I/O系统I/O系统如何向设备发命令?系统接口设备命令设备控制器系统接口中断处理设备中断I/O系统向设备控制器发命令设备控制器的结构readwritecontrolstatus显存寄存器组硬件控制器总线接口I/O系统向哪里发送设备发命令?读写设备控制器的寄存器!怎么读写?readwritecontrolstatus显存寄存器组硬件控制器总线接口mov[100],ax关键是地址设备寄存器的编址独立编址:

需要独立的指令(in,out)，如out0x21,AL内存映像编址:

是内存物理地址空间的一部分，使用mov命令，如mov[0x8000f000],AL查查硬件手册就知道了!I/O系统发完命令后做什么?方案1:原地踏步等待!发送Read命令ReadI/O状态

检查I/O状态没有就绪从I/O读取数据就绪将数据写内存原地踏步出错处理inAL,0x??while(AL!=reday){inAL,0x??}读数据...轮询!轮询浪费CPU资源(CPU比外设快太多了)!I/O系统发完命令后做什么?方案2:设备就绪了告诉CPU一声!set_trap_gate(??,do?())do?(){inAL,0x??if(AL!=reday){error();}

读数据...}中断发送Read命令ReadI/O状态

检查I/O状态从I/O读取数据就绪将数据写内存CPU做其它工作I/O中断CPU和I/O并行出错处理中断是大部分I/O的处理方式!?中断在某些场合还不够!如果用中断来读磁盘…磁盘缓存磁盘控制器总线内存CPU中断将数据读入内存每个字节从缓存移动内存都由CPU负责完成可以设计有一定处理能力的外围设备，将一些简单任务交给它!I/O系统发完命令后做什么?方案3:简单任务自己做，完成了告诉CPU一声!引入DMA(直接内存存取)总线磁盘缓存磁盘控制器内存CPUDMA地址计数中断发送命令计数地址命令将数据读入内存幸运的是:

该方式的细节由DMA设计者考虑，对于操作系统而言，考虑的仍然只是中断处理总结一些I/O系统要完成的工作!read(buf,10);OS需要提供系统调用接口DMA.addr=buf;DMA.count=10;……sleep_on(Disk);do_read_end()//中断处理

{wakeup(Disk);}查一下手册就可以找到该写什么命令?该向哪里写?让出CPU?需要写中断处理程序!总的感觉:

很简单处理流程是很简单，复杂的是一些细节问题，如滚屏PC终端和Linux终端管理!为什么选择终端设备?前面的内容已经可以让(多个)程序运行起来?现在我们很想看到屏幕显示，很想输入参数…完成这些任务的I/O设备通常称为终端设备(控制台)voidmain(void){if(!fork()){init();}从哪里开始这个故事呢?Shell要打出提示符，等待输入命令Shell启动前必定会初始化终端设备。就从这里开始……voidinit(void){open(“dev/tty0”,O_RDWR,0);dup(0);dup(0);}open展开成系统调用!在linux/lib/open.c中intopen(constchar*filename,intflag,…){__asm__(“int0x80”:”=a”(_res):””(__NR_open),”b”(filename),”c”(flag));return_res;}0x80的中断处理程序会找到__NR_open(编号，在ax中)对应的函数sys_open!在linux/fs/open.c中intsys_open(constchar*filename,intflag){i=open_namei(filename,flag,&inode);if(S_ISCHR(inode->i_mode))//字符设备

{if(MAJOR(inode->i_zone[0])==4)current->tty=MINOR(inode->i_zone[0]);}}解析目录，读入设备信息!和块设备(磁盘)对应。终端设备是典型的字符设备!我们来向屏幕输出点东西!voidinit(void){open(“/dev/tty0”...);

printf(“Thisisinitprocess”);}write中的printbuf显然是要输出的字符串，那么1呢?在linux/fs/read_write.c中intsys_write(unsignedintfd,char*buf,intcount){structfile*file;

file=current->filp[fd];inode=file->f_inode;...}staticintprintf(constchar*fmt,...){...

write(1,printbuf,sizeof(??));}write也要展开成系统调用!fd成为了找到file的索引!文件描述符表和打开文件表回头再看一下sys_open在linux/fs/open.c中intsys_open(constchar*filename,intflag){structfile*f;f=0+file_table;

cuurent->filp[fd]=f;//第一个空闲的fdf->f_mode=inode->i_mode;f->f_inode=inode;f->f_count=1;returnfd;}全局打开文件表在linux/fs/file_table.c中structfilefile_table[NR_FILE];PCBfilpfile_tableinodeinode开始真正向屏幕输出!继续sys_write!在linux/fs/read_write.c中intsys_write(unsignedintfd,char*buf,intcnt){inode=file->f_inode;if(S_ISCHR(inode->i_mode))returnrw_char(WRITE,inode->i_zone[0],buf,cnt);...转到rw_char!在linux/fs/char_dev.c中intrw_char(intrw,intdev,char*buf,intcnt){crw_ptrcall_addr=crw_table[MAJOR(dev)];call_addr(rw,dev,buf,cnt);...}一个函数数组，处理各种字符设备!看看crw_table!staticcrw_ptrcrw_table[]={...,rw_ttyx,};typedef(*crw_ptr)(intrw,unsignedminor,char*buf,intcount)第4个!再转到tty_write!//实现输出的核心函数staticintrw_ttyx(intrw,unsignedminor,char*buf,intcount){return((rw==READ)?tty_read(minor,buf):

tty_write(minor,buf));}在linux/kernel/tty_io.c中inttty_write(unsignedchannel,char*buf,intnr){structtty_struct*tty;tty=channel+tty_table;

sleep_if_full(&tty->write_q);...}可以猜测:输出就是放入队列!继续tty_write这一核心函数在linux/kernel/tty_io.c中inttty_write(unsignedchannel,char*buf,intnr){...charc,*b=buf;while(nr>0&&!FULL(tty->write_q)){c=get_fs_byte(b);if(c==‘\r’){PUTCH(13,tty->write_q);continue;}if(O_LCUC(tty))c=toupper(c);b++;nr--;PUTCH(c,tty->write_q);}//输出完事或写队列满!

tty->write(tty);if(nr>0)schedule();}fs:数据段选择符!tty->write应该是真的开始输出屏幕了!看看tty->write在include/linux/tty.h中structtty_struct{void(*write)(structtty_struct*tty);structtty_queueread_q,write_q;}先应该看看tty_struct这个结构!看看tty_struct结构的初始化!tty=channel+tty_table在linux/kernel/chr_drv/tty_io.c中structtty_structtty_table[]={{con_write,{0,0,0,0,””},{0,0,0,0,””}},{},…};structtty_queue{unsignedlongdata;unsignedlonghead;unsignedlongtail;structtask_struct*proc_list;charbuf[TTY_BUF_SIZE];};走了很久的路，终于到了con_write在linux/kernel/chr_drv/console.c中voidcon_write(structtty_struct*tty){intnr=CHARS(tty->write_q);charc;while(nr--){GETCH(tty->write_q,c);switch(state){//不同状态按不同方式处理(字符或命令)case0:if(c>31&&c<127){__asm__(“movb_attr,%%ah\n\t”“movw%%ax,%1\n\t”::”a”(c),”m”(*(short*)pos):”ax”);pos+=2;x++;}...con_write用来真正的向显示器写东西!32-126是可视字符!其它是控制字符。32是空格，126是~。将c写到pos处，pos指向显存。看看pospos指向显存，先来了解一下显存…PC/AT机内存区域图0x000000xA0000显存0xC0000……ROMBIOSVGAROMBIOS0x1000000xffffffff回忆:分页时内存640K-1M不和逻辑页映射!pos指向显存:pos=0xA0000别忘了，段选择符改为内核段，基址为0所以完成显示中最核心的秘密就是控制pos跟踪pos...pos的修改:pos+=2跟踪pos:pos初值+pos修改为什么加2?屏幕上的一个字符在显存中除了字符本身还应该有字符的属性(如颜色等)这就需要说一说适配器标准了…1个byte字符，1个byte属性!CGA彩色图形适配器0xb8000~0xbc000适配器标准内存地址字符属性字节BLD7RD6GD5BD4ID3RD2GD1BD0闪烁高亮度背景色前景色字符的显示属性EGA/VGA的显存起始地址:0xa0000现代计算机大都是EGA/VGAEGA/VGA兼容CGA和MDAStaticunsignedcharattr=0x07;__asm__(“movb_attr,%%ah\n\t”“movw%%ax,%1\n\t”::”a”(c),”m”(*(short*)pos):”ax”);黑底白字!跟踪pos之pos初值!pos初值的设定一定在终端控制台的初始化con_initmain(){tty_init();}tty_init(){con_init();rs_init()}con_init()在linux/kernel/chr_drv/console.c中voidcon_init(void){if(ORIG_VIDEO_MODE==7)//是MDAelse{//彩色显示卡CGA/EGA/VGAvideo_mem_start=0xb80000;//显存起始地址

video_mem_end=0xbc000;//显存末端地址

}origin=video_mem_start;

gotoxy(ORIG_X,ORIG_Y);staticunsignedlongvideo_mem_start;staticunsignedlongvideo_mem_end;staticunsignedlongorigin;Staticunsignedlongpos;一些控制显示的全局变量!#defineORIG_VIDEO_MODE((*(unsignedshort*)0x90006)&0xff)//显示模式一些物理参数取出来放在0x90000处!gotoxy(ORIG_X,ORIG_Y)在linux/kernel/chr_drv/console.c中staticinlinevoidgotoxy(unsignedintnew_x,unsignedintnew_y){if(new_x>video_num_columns||new_y>=video_num_lines)return;//不合法的x、yx=new_x;y=new_y;

pos=origin+y*video_size_row+(x<<1);}

#defineORIG_X(*(unsignedchar*)0x90000)//初始光标列号#defineORIG_Y(*(unsignedchar*)0x90001)//初始光标行号在con_init()中video_num_columns=ORIG_VIDEO_COLS;video_size_row=video_num_columns*2;video_num_lines=ORIG_VIDEO_LINES;设为250x90006的高字节屏幕有限而显示内容无限

翻页case0:if(c>31&&c<127){if(x>=video_num_columns){x-=video_num_columns;

pos-=video_size_row;

lf();//换行}__asm__(“movb...在movw(ax,pos)之前，还有一小段程序…x的作用!staticvoidlf(void){if(y+1<bottom){y++;pos+=video_size_row;return;}

scrup();//翻页

}staticunsignedlongx,y;staticunsignedlongtop,bottom;staticunsignedlongscr_end;x,y定位光标行列坐标!显然，翻页时的pos另外处理?用来控制翻页的…翻页scrup()根据显存想一想如何翻页?staticvoidscrup(void)if(video_type==VIDEO_TYPE_EGAC||video_type==VIDEO_TYPE_EGAM){if(!top&&bottom==video_num_lines){orgin+=video_size_row;pos+=video_size_row;scr_end+=video_size_row;if(scr_end>video_mem_end){(移动整屏数据)}else{(新行上填入空格字符)}set_origin();//”移动”显示器

}else{(非整屏向上翻)}}

显存?A?B?C?D?E?F?G?H......?W?X?Y?Z显示器向下翻页整屏向上翻!超过显存末端!在显存中移动数据、填充空格新行填充空格字符

__asm__(“cld\n\t”“rep\n\t”“movsl\n\t”movl_video_num_columns,%1\n\t”“rep\n\t”“stosw”::”a”(video_erase_char),“c”((video_num_lines-1)*video_num_columns>>1),”D”(video_mem_start),”S”(origin):”cx”,”di”,”si”);scr_end-=origin-video_mem_start;pos-=origin-video_mem_start;origin=video_mem_start;

移动整屏数据(向下翻动一行)初始化为0x0720

__asm__(“cld\n\t”“rep\n\t”“stosw”::”a”(video_erase_char),“c”(video_num_columns),”D”(scr_end-video_size_row):”cx”,”di”);留1行!set_origin()//真正的翻屏各参数初始化(con_init)staticinlinevoidset_origin(void){

cli();//下面的动作是原子的

outb_p(12,video_port_reg);//选择“索引”寄存器端口

outb_p(0xff&((origin-video_mem_start)>>9),video_port_val);outb_p(13,video_port_reg);

outb_p(0xff&((origin-video_mem_start)>>1),video_port_val);sti();}移动整屏数据(向下翻动一行)top=0;bottom=video_num_lines;src_end=video_mem_start+video_num_lines*video_size_row;video_port_reg=0x3d4;video_port_val=0x3d5;r12:卷屏起始地址高字节梳理printf的整个过程!

库函数(printf)read_write.cchar_dev.ctty设备写(tty_write)字符设备接口(crw_table[])系统调用(write)write_q队列显示器写(con_write)tty_io.c显存写pos位置终端控制台设备=显示器+键盘关于键盘的故事从哪里开始?对于使用者(人):敲键盘、看结果voidcon_init(void)//应为键盘也是console的一部分{set_trap_gate(0x21,&keyboard_interrupt);outb_p(inb_p(0x21)&0xfd,0x21);//操作中断控制器

a=inb_p(0x61);//操作键盘控制器

outb_p(a|0x80,0x61);outb_p(a,0x61);}对于操作系统:“等着”你敲键盘，敲了就中断故事应该从键盘中断开始，从中断初始化开始…了解一点键盘硬件…0x21是什么?两个0x21一样吗?set_trap_gate(0x21,&keyboard_interrupt);outb_p(inb_p(0x21)&0xfd,0x21);CPUINTR8259A主片IR0时钟IR1键盘INT8259A从片IR0IR1INTIR2端口0x20~端口0xA0~inb_p(0x21)//取中断屏蔽字&0xfd//11111101IR1置0outb_p(?,0x21)//允许键盘中断set_trap_gate(0x21)//中断号在setup.s中初始化moval,#0x20out#0x21,almoval,#0x28out#0xA1,al8259初始化后才使用主片中断号从0x20开始，从片从0x28开始了解一点键盘硬件…0x61是什么?a=inb_p(0x61);outb_p(a|0x80,0x61);outb_p(a,0x61);键盘控制器804X端口0x61端口可读可写:其中位7=1表示禁止键盘；位7=0表示允许键盘outb_p(a|0x80,0x61);//禁止键盘outb_p(a,0x61);//又允许键盘禁止了一下，又允许了一下。挺好玩!con_init:设置键盘中断处理；允许中断；复位键盘控制器，让键盘开始正常工作…键盘中断处理keyboard_interrupt在kernel/chr_drv/keyboard.S中.globl_keyboard_interrupt_keyboard_interrupt:pushl%eaxpushl%ebxpushl%ecxpushl%edxpush%dspush%esmov$0x10,%eaxmov%ax,%dsmov%ax,%es//内核段

xorl%al,%alinb$0x60,%al//从端口0x60读扫描吗

callkey_table(,%eax,4)//调用key_table+eax*4inb$0x61,%aljmp1f1:jmp1f//延迟一会儿

1:orb$0x80,%aljmp1f1:jmp1f1:outb%al,0x61jmp1f1:jmp1f1:andb$0x7f,%aloutb%al,$0x61movb$0x20,%aloutb%al,$0x20//向8259发送EOIpush$0//传递参数0call_do_tty_interruptaddl$4,%esppop%esiret处理扫描码!处理扫描码key_table+eax*4在kernel/chr_drv/keyboard.S中key_table:.longnone,do_self,do_self,do_self//扫描码00-03.longdo_self,...,func,scroll,cursor等等key_table是一个函数数组扫描码02对应按键1；01对应ESC；12对应E等等显示字符通常都用此函数处理!mode:.byte0do_self:leaalt_map,%ebxtestb$0x20,mode//alt键是否同时按下jne1fleashift_map,%ebxtestb$0x03,modejne1fleakey_map,%ebx1:

找到映射表，如a的key_map映射为a，而shift_map映射为A从key_map中取出ASCII码各种map(alt_map,shift_map,key_map)放在哪里?#ifdefined(KBD_US)key_map:.byte0,27.ascii“1234567890-=“...shift_map:.byte0,27.ascii“!@#$%^&*()_+”...#elifdefined(KBD_GR)...继续do_self，从1f开始，ebx放的是map起始地址1:movb(%ebx,%eax),%al//扫描码索引，ASCII码

alorb%al,%aljenone//没有对应的ASCII码

testb$0x4c,mode//看caps是否亮

je2fcmpb$’a,%aljb2fcmpb$’},%alja2fsubb$32,%al//变大写2:testb$??,mode//处理其他模式，如ctrl同时按下3:andl$0xff,%eaxxorl%ebx,%ebxcallput_queuenone:retput_queue将ASCII码放到?put_queue//可见，取出的ASCII码放入队列就完事put_queue:pushl%ecxpushl%edxmovl_table_list,%edxmovlhead(%edx),%ecx1:movb%al,buf(%edx,%ecx)incl%ecxandl$size-1,%ecxcmpltail(%edx),%ecx//头指针==尾指针(缓冲区满)je3fshrdl$8,%ebx,%eaxje2fshrl$8,%ebxjmp1b2:movl%ecx,head(%edx)movlproc_list(%edx),%ecxtestl%ecx,%ecxje3f

movl$0,(%ecx)//task_struct的第一个域就是状态3:popl%edxpopl%ecxret在kernel/chr_drv/tty_io.c中structtty_queue*table_list[]={&tty_table[0].read_q,&tty_table[0].write_q;...};edx指向tty_table[0](console)head指向队列头部把ebx:eax中最多8个字节放到队列con.read_qdo_tty_interrupt要做什么?

到目前为止还差什么?在kernel/chr_drv/tty_io.c中voiddo_tty_interrupt(inttty)//上面传来的是0{copy_to_cooked(tty_table+tty);}对了…“回显”push$0在kernel/chr_drv/tty_io.c中voidcopy_to_cooked(structtty_struct*tty){signedcharc;while(!EMPTY(tty->read_q)&&!FULL(tty->secondry)){GETCH(tty->read_q,c);

if(I_UCLC(tty))c=tolower(c);//大写变小写

...copy_to_cooked//一定是拷贝到另一个队列中do_tty_interrupt要做什么?

一定还有许多if…在kernel/chr_drv/tty_io.c中voidcopy_to_cooked(structtty_struct*tty){if(I_UCLC(tty))c=tolower(c);//大写变小写

if(L_ISIG(tty)){

if(c==INTR_CHAR(tty)){//^Ctty_intr(tty,INTMASK);//向进程发送中断信号

continue;}}

if(L_ECHO(tty)){//回显

PUTCH(c,tty->write_q);tty->write(tty);}//立刻显示到屏幕上

PUTCH(c,tty->secondary);//完成copy_to_cooked}//前面的while

wake_up(&tty->c_list);进行规范化处理!键盘中断整理…

漫长的键盘处理到此基本结束，现在整理一下键盘中断处理put_queueread_qsecondarydo_tty_interruptcopy_to_cookedwrite_qcon_write控制台输入输出整理…

键盘、显示器在一个tty_struct，两者紧密关联read_write.cchar_dev.ctty设备写(tty_write)字符设备接口(crw_table[])系统调用(write)write_q队列显示器写(con_write)keyboard.S显示器tty设备读(tty_read)read_q队列console.c主机键盘secondary回显tty_io.c关于队列的一点补充

总结“显示器写”和“键盘读”可以发现:问题的一切集中在操作read_q，write_q和secondary上操作这三个队列的接口是:PUTCH…structtty_queue{unsignedlonghead;unsignedlongtail;charbuf[TTY_BUF_SIZE];};#defineEMPTY(a)((a).head==(a).tail)#defineFULL(a)(!LEFT(a))#defineLEFT(a)(((a).tail-(a).head-1)&(TTY_BUF_SIZE-1))#defineINC(a)((a)=((a)+1)&(TTY_BUF_SIZE-1)#definePUTCH(c,queue)(void)({(queue).buf[(queue).head]=(c);INC((queue).head);})#defineGETCH(queue,c)(void)({c=(queue).buf[(queue).tail];INC((queue).tail);})为了故事的完整，有必要看一看!tty与console

键盘+显示器=console=tty_table[0]，其他tty呢?write_q队列主机显示器read_q队列主机键盘回显主机控制台:write_q队列read_q队列回显串行终端:终端显示器终端键盘通信、显示、键盘处理固化程序串行终端设备rs_io.c串行终端需要增加一层通信软件!I/O与终端设备总结控制器和纸带是计算的核心但我们更需要的交互(I/O)如何实现交互?首先需要了解I/O的工作原理从用户如何I/O开始用户发送一个命令(read)系统调用read被展开成给一些寄存器发送命令的代码发送完命令以后…CPU轮询，CPU干其它事情并等中断中断方案最常见相比其他设备，CPU太快了从哪里开始Linux控制台读写过程看看Linux终端的I/O处理许多人把终端当成完整计算机写控制台写显存；读控制台键盘中断…操作系统OperatingSystem第10章文件系统Chapter10:FileSystem文件的引入字符序列(字符流)磁盘上的文件的样子扇区集合用户眼里文件的样子文件:建立了字符流到盘块集合的映射关系将2-12字符删去test.c中的2-12字符对应盘块789读入、修改、写出三种基本映射关系012345678910111213141516171819202122232425262728293031test.cftrmaillist盘块连续分配01234567891011121314151617181920212223242526272829303110-1917test.c盘块链式分配盘块索引分配012345678910111213141516171819202122232425262728293031test.c文件和文件系统的差别在哪里?文件系统中有很多文件catboatestdatamailconthex文件所有文件放在一层(一个大集合)枯燥乏味直至跑掉怎么办?集合划分catboatestdatamailconthex用户1用户2用户3问题依然存在:N/u，扩展性仍然差怎么管理?划分的基础上继续划分将划分后的集合再进行划分:

k次划分后，每个集合中的文件数为O(logkN)树状目录catbohexadatamailvarmydatacont此种树状结构扩展性好、表示清晰，最常用需要描述“文件的集合”，引入概念:目录怎么进行“文件集合”物理表述?目录的实现存放“文件集合”catbohexadatamailvarmydatacont将文件内容(盘块)放在一起…显然不行将文件内容指针(即文件头)放在一起应该是可以的，是否合适需要系统的看待问题…操作系统:当然需要系统的看待问题!继续思考:有了树状目录后会出现什么问题?出现了路径名:/my/data/a用来定位文件a路径名路径的解析:输入/my/data/a，获得文件a的文件头再根据文件头定位文件内容路径的解析(NameResolution)输入/my/data/a，获得文件a的文件头从哪里开始?想一想?顶层目录(根目录/)目录是什么?应该也是一