浮泛之舟

进程与线程 真并行与假并行 并行与并发 并发Concurrent：设有两个活动a1和a2，如果在某一指定的时间t，无论a1和a2是在同一处理机上还是在不同的处理机上执行，只要a1和a2都处在各自的起点和终点之间的某一处，则称a1和a2是并发执行的。 并行Parallel：如果考虑两个程序,它们在同一时间度量下同时运行在不同的处理机上，则称这两个程序是并行执行的。 对于并发执行：程序的并发执行是指若干个程序（或程序段）同时在系统中运行，这些程序（或程序段）的执行在时间上是重叠的。所谓执行在时间上是重叠的，是指执行一个程序（或程序段）的第一条指令是在执行另一个程序（或程序段）的最后一条指令完成之前开始。 程序并发执行时的特征： 间断性：并发程序具有“执行—暂停—执行”这种间断性的活动规律。 非封闭性：多个程序共享系统中的资源，这些资源的状态将由多个程序来改变，致使程序之间相互影响。 不可再现性：在初始条件相同的情况下，程序的执行结果依赖于执行的次序。 前驱图 程序在运行过程中会有相应的数据依赖，如B的执行必须依赖于A，也就是A必须在B之前完成，写作A->B。 前趋图是一个有向无循 ...

进程和线程 Java语言内置了多线程支持：一个Java程序实际上是一个JVM进程，JVM进程用一个主线程来执行main()方法，在main()方法内部，我们又可以启动多个线程。此外，JVM还有负责垃圾回收的其他工作线程等。 因此，对于大多数Java程序来说，我们说多任务，实际上是说如何使用多线程实现多任务。 和单线程相比，多线程编程的特点在于：多线程经常需要读写共享数据，并且需要同步。 多线程并发的法宝：外互斥、内可见 内存模型 每个进程会把虚拟内存空间分成4个段(代码段, 数据端，堆，栈) 代码段：用来存放进程(应用App)的代码指令。 数据端：用来存放全局变量的内存。 堆：调用os的malloc/free 来动态分配的内存。 栈：用来存放局部变量，函数参数，函数调用与跳转。 每个进程(应用App)相当于一个容器，所有应用App里面需要的资源和机制都在进程里面。 线程是OS独立调度执行的单元，OS调度执行的单位就是线程，线程需要以进程作为容器和使用进程相关的环境。 每个线程共享进程的代码段内存空间，所以我们编写多线程代码的时候，可以在任何线程调用任何函数。 每个线程共享进程的数据段 ...

递归下降 d文法 文法是对语言结构的定义和描述，也就是通过形式化的表述来规定语言结构的规则。 文法，是语言的规则。文法讨论的范围较宽，此处仅关注词法和语法。 词法 词法是指语言中的词汇及其属性和含义的规则。它规定了一个语言中的"词"是如何构成的。 例如有一个语法单元：变量名，定义其为由大于0个小写字母组成的字符串,那么就可以写成 尖括号内表示一个语法成分 右箭头表示左侧的部分由右侧的部分组成 竖线 “|” 表示可以选择右边的规则可以选取竖线两侧的任一种情况。 这种表示方式赋予了词法的递归性质，即可以不断定义更长的词法 由此就可以得到变量名的构成规则。 语法 语法是指描述语言中句子结构和组织方式的规则。它规定了一个语言中的"句"是如何构成的。 例如下面的例子： 通过这个规则我们知道,句子是一个主语加上一个谓语连在一起构成的。其中主语可能是i也可能是you，谓语可能是smile，可能是laugh。 字符串解析 程序做的绝大多数事情都是在解析字符串，有了词法和语法后，有了解析的规则。那么，该如何使用合适的结构和方法来降低复杂性呢？ Tok ...

存储 存储资源是一种宝贵的资源，无论存储器有多大，程序最终都能将其耗尽。 静态存储器SRAM：读写速度块、生产成本高、多用作Cache 动态存储器DRAM：读写速度慢、集成度高、生产成本低、多用作主存储器 存储组织 存储组织：在存储技术和CPU寻址技术许可的范围内组织合理的存储结构。 合理结合不同的存储器，达到各层次的存储器都处于均衡的繁忙状态的理想效果（命中率），营造又快又大的错觉。 典型的层次式存储组织：访问速度越来越慢，容量越来越大，价格越来越便宜 存储管理 存储管理的功能： 存储分配和回收：存储管理的主要内容 关注其算法和相应的数据结构 地址变换： 可执行文件生成中的链接技术 程序加载时的重定位技术 进程运行时硬件和软件的地址变换技术和机构 存储共享和保护：代码和数据共享，对地址空间的访问权限（读、写、执行）。 存储器扩充：涉及存储器的逻辑组织和物理组织； 由==应用程序控制：覆盖== 由==OS控制：交换==（整个进程空间），请求调入和预调入（部分进程空间） 编译、链接、装入 怎么从代码到可执行文件。 gcc的工作 GCC编译器驱动程序读取源程 ...

bootloader 计算机启动是一个很矛盾的过程：必须先运行程序，然后计算机才能启动，但是计算机不启动就无法运行程序！ 它来自一句谚语：“pull oneself up by one‘s bootstraps”：“拽着鞋带把自己拉起来”。 为什么 操作系统最重要的部分是操作系统内核，因为内核需要直接与硬件交互来管理各个硬件，从而利用硬件的功能为用户进程提供服务。为了启动操作系统，就需要将内核程序在计算机上运行起来。 一个程序要能够运行，其必须能够被CPU 直接访问，所以不能放在磁盘上。 另一方面，内存RAM 是易失性存储器，掉电后将丢失全部数据，所以不可能将内核代码保存在内存中。 因此，内核有可能放置的位置只能是CPU 能够直接访问的非易失性存储器——ROM 或FLASH中。 但是，直接把操作系统内核放置在这样的非易失存储器上会有一些问题： 这种CPU 能直接访问的非易失性存储器的存储空间一般会映射到CPU可寻址空间的某个区域，这个是在硬件设计决定的。 这个区域的大小是有限的，如果功能比较简单的操作系统还能够放在其中，对于较大的普通操作系统显然不够。 如果操作系统内核 ...

课程介绍 操作系统的设计原理体现了软硬件的最新发展： 计算机体系结构：巨型机、大型机、微机、工作站、多核、XPU等 程序设计方法：并发、面向对象、结构化 每个阶段解决每个阶段的能力：系统级编程能力 Lab顺序： 系统调用 内存管理 进程管理 系统调用 文件系统（用户态） 管道的实现 实现小系统 OS基础 OS是一组管理计算机硬件资源的软件集合，它向计算机程序提供共性的服务。 屏蔽复杂性：抽象。需要创建、实现和管理抽象。 为什么要有OS而不是直接运行汇编代码：无法手动管理底层硬件巨大的复杂性，由OS进行管理 什么是内核 “内核”指的是一个提供硬件抽象层、磁盘及文件系统控制、多任务等功能的系统软件。内核是操作系统最基本的部分。 直接对硬件操作是复杂的，内核通过提供接口，隐藏了下层的操作复杂度，激励性了硬件抽象。内核是一个操作系统的核心。它负责管理系统的进程、内存、设备驱动程序、文件和网络系统等等，决定着系统的性能和稳定性。是连接应用程序和硬件的桥梁。 宏内核 内核的功能都集中在一起，运行在内核进程中，模块之间的交互直接通过方法调用 微内核 微内核中，内核只提供最核心的功能， ...

课程概述 不同类型的网络的依存： 互联网：物理的、技术的网络：服务器的关系 万维网：基于互联网的信息网络：网页的关系 技术的发展对网络有多种作用： 催化了各种网络的发展： 规模变大，范围变广 新型网络的涌现 使得分析和理解大规模网络的行为成为可能： 行为数据与网络运行伴生 海量数据分析的能力：计算设施、算法工具 讨论网络的语言：图论+博弈论 图论 网络的结果分析：需要使用图论来建立相应的模型 边的成因：为什么节点会形成关系 边的意义：不同位置的边的不同作用：关系的强度 节点的重要性：由结构特点带来的节点的权力/权重 结构的划分、结构的平衡 连通性分为结构（连接本事）层面和行为（个体行动对系统中其他个体的可能影响）层面 桥：删除后两个端点不再联通 捷径：删除后两个端点的距离至少为3。定义捷径的跨度为删除捷径后两点的距离。 强联系与弱联系 网络在现代社会有重要的作用。如何衡量关系的强弱？ 三元闭包原则 社交网络中的不是好朋友的两个人： 两个人的共同朋友越多，越有可能成为朋友：量的考虑 两个人与共同好朋友的关系越密切，越有可能成为好朋友：质的考虑 定义三元闭包：若 ...

CPU设计 概述 本次我设计的verilogMIPS微系统支持简单的异常、中断处理，支持执行COCO文档的中文指令集中的所有指令，共76条。 采用多个模块进行设计。所采用模块化设计为： CPU Stall Unit ：阻塞单元，判断是否进行阻塞 IFU：指令单元，接受指令地址PC来给出当前周期处理的指令 GRF：寄存器模块，通过该模块统一进行32个寄存器的读写 NPC：计算下一条指令的地址，接受jump，branch等指令来支持跳转操作 Branch Control：分支跳转模块，判断是否该跳转 Error Control：Trap型异常控制模块，判断是否异常 ALU：进行运算操作，该ALU操作码为4为 DU：外村数据管理单元，管理和存储器数据之间的交互 CP0：负责进行简单的异常中断控制 ControlUnit：指令控制单元，通过接受op和func来发出指令，控制数据通路中的MUX Bridge：负责与外设进行交互，管理数据的存取和使能信号 Timer：计时器外设，共有两个，可以释放外部中断信号 支持指令 支持76条指令， ...

CPU设计 概述 本次我设计的verilog流水线CPU支持50条指令。 采用多个模块进行设计。 所采用模块化设计为： IFU：指令单元，接受指令地址PC来给出当前周期处理的指令 GRF：寄存器模块，通过该模块统一进行32个寄存器的读写 NPC：计算下一条指令的地址，接受jump，branch等指令来支持跳转操作 ALU：进行运算操作，该ALU操作码为4为 DM：内存组，通过内置的RAM实现 Branch Control：分支跳转模块，判断是否该跳转 Stall Unit ：阻塞单元，判断是否进行阻塞 ControlUnit：指令控制单元，通过接受op和func来发出指令，控制数据通路中的MUX 支持指令 支持50条指令，基本支持了中文指令集文档上除了系统调用、异常外的所有指令。为： R指令：add,addu,sub,subu,and,or,xor,nor,sll,sllv,srl,srlv,sra,srav,slt,sltu I指令：addi,addiu,slti,sltiu,andi,ori,xori,lui,beq,bne,bgez,bgtz,blez,bltz J指令： ...

CPU设计 概述 本次我设计的verilog单周期CPU支持n条指令，因为这一周太忙了，别的指令没有来的及测试，只完成了规定的指令。只能说，理论上应该都支持如下的指令。 采用多个模块进行设计。 所采用模块化设计为： IFU：指令单元，接受指令地址PC来给出当前周期处理的指令 GRF：寄存器模块，通过该模块统一进行32个寄存器的读写 NPC：计算下一条指令的地址，接受jump，branch等指令来支持跳转操作 ALU：进行运算操作，该ALU操作码为4为 DM：内存组，通过内置的RAM实现 Branch Control：分支跳转模块，判断是否该跳转 ControlUnit：指令控制单元，通过接受op和func来发出指令，控制数据通路中的MUX 本次CPU的架构和P3作业中搭建的CPU架构类似，可以参考的架构为：在此基础上添加了处理条件控制单元BC、阻塞判断单元SU。 支持指令 支持40条指令，为： R指令：add,addu,sub,subu,and,or,xor,nor,sll,sllv,srl,srlv,sra,srav,slt,sltu I指令：addi,addiu,slti ...