红豆zza

Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub. Quick StartCreate a new post1$ hexo new "My New Post" More info: Writing Run server1$ hexo server More info: Server Generate static files1$ hexo generate More info: Generating Deploy to remote sites1$ hexo deploy More info: Deployment

OS复习：同步与互斥[TOC] 同步与互斥概念在多道程序下，继承是并发执行，不同进程之间存在着不的相互制约关系；为协调进程之间的相互制约关系，引入进程同步概念，当我们计算1+2*3，加法进程一定是在乘法后的，但是OS具有异步性。 临界资源我们将一次只能给一个进程服务的资源称为临界资源 分为四部分：进入区、临界区、退出区、剩余区 1234567while(true){ entry section //进入区：进入临界区资源，在进入区要检查可否进入临界区，若能进入临界区，则应设置正在访问临界区的标志，以阻止其他进程同时进入临界区 critical section //临界区： 进程访问临界资源的那段代码，又称临界段 esxit section //退出区： 将正在访问临界区的标志清除 remainder section //剩余区} 同步同步也称直接制约关系，指为完成某种人物而建立的两个或多个进程，这些进程因为要协调它们的运行词语而等待、传递信息所产生的制约关系。同步关系源于进程之间的相互合作。 互斥互斥是间接制约关系。当一个进 ...

CPU调度 为什么要进行CPU调度 调度算法？ 这里我们重点了解一些调度算法 调度概念进程对于CPU个数，资源不足，那么进程之间就会争夺CPU资源。怎么分配资源合理呢？ 我们要求按照公平、高效的原则，选择进程将CPU分配给它 调度层次我们有三级调度层次：作业调度（高级）、内存调度（中级）、进程调度（低级） 作业调度：从外存尚处于后备队列的作业挑选一些，给它们分配内存、IO设备资源，并建立相应的进程；简而言之，作业调度是内存和辅存间的调度；每个作业只出入一次；一般多道批处理系统有作业调度，其他不需要 内存调度：将暂时不能运行的进程调至外存等待，进程处于挂起态。进程们此时已有运行条件，当内存稍有空闲就决定将哪些挂起进程重新调入内存，将其状态改为就绪态。目的为了提高内存利用率和系统吞吐量 进程调度：选择CPU分配，频率很高，几十ms一次 三者之间关系如下： 作业调度为进程活动准备 内存调度处于作业调度和进程调度之间 作业调度次数最少，内存调度其次，进程调度频率最高 进程调度最基本，不可或缺 调度实现调度器：就是实现调度CPU的程序，三部分组成 排队器：将所有就进程组织成一个或多个 ...

OS复习：进程与线程进程的所有内容都非常重要，本文尽可能详细梳理一遍 这一章包括以下内容，本文只整理进程与线程： 进程与线程 CPU调度 同步与互斥 死锁 进程与线程什么是是进程？为什么要有进程？进程如何解决我们考虑的问题 什么是进程在多道程序下，多个程序并发执行，为描述和控制程序的并发执行，我们引入进程的概念（这样解释还是抽象） 我们让每个程序独立运行，给他配备一个专门数据结构，PCB（Process Control Block），用来描述进程的基本情况和运行状态；因此，创建进程就是创建PCB；撤销进程，就是撤销PCB 呃 进程还可以有如下解释： 正在执行程序的实例（好比你的代码是菜谱，我现在进程就是要根据菜谱正在做的菜） 是程序及其数据从磁盘加载到内存，在CPU上执行的过程 是具有独立功能程序在一个数据集合上运行过程 它也是进程实体的运行过程，是系统进行资源分配和调度的基本单位 这里资源是值CPU、存储器、其他设备服务某个进程的时间，强调的是时间 它有以下一些特征： 动态：有一定生命周期，是动态产生、变化和消亡 并发 独立 异步： 进程里有哪些东西PCB进程控制块。进程 ...

OS复习：OS概述目录虚拟化、并发化、持久化 OS概述：概念、特征、批处理、分时实时、中断和系统调用 进程： 内存管理： 文件系统： IO设备： 鉴于本人大二上在没有先修计组的前提下，稀里糊涂的选了操作系统，所以基础和考研跨考的同学相当。离期末考还有一个月，选择速通 若想认真学习OS的同学，建议先修计组，参考jyy老师的课 第一章： OS基本概述1.1 基本概念OS是控制管理系统软硬件，合理阻止调度计算机的工作与资源分配，为用户和软件提供方便接口与环境的程序几何、 OS也是状态机 特征并发和共享是操作系统基本特征； 并发：同一时间间隔执行多个任务；通过CPU分时实现，多道程序交替运行 共享：互斥共享、同时访问（分时共享） 虚拟： 将逻辑上的映射到计算机硬件实体，常见有虚拟处理器，虚拟存储器（内存管理），虚拟设备（IO设备） 异步 ：由于资源有限，进程的执行并不是一贯到底，走走停停，拥有不可预知速度 目标和功能：作为资源管理者我们OS接下来四章学习内容就是围绕以下展开 进程管理：运行多个进程时，进程何时创建？何时撤销？何时管理？如何避免冲突？如何合理共享？所以我们要解决的问题包括： ...

题选：图的最短路径算法，A*算法求解最短路径的算法有很多，而A*算法无疑是其中最高效率、适用性更强的算法之一。 概括来说 A*算法=贪心最优搜索+BFS+优先队列=贪心+Dijkstra+优先队列 A*算法的核心在于估价函数 f=g+h，其效率取决于H函数的设计 1.贪心最优搜索贪心是启发式算法，在寻找图中最短路径时能高效找到局部最优解，但无法保证全局最优解 具体的实现思想：从起点s出发，寻找i点（i点是距离终点t最近的邻居节点） 如何找距离终点最近的邻居节点i？如何估计i到t的距离？ BFS+优先队列；我们用曼哈顿距离估算最短距离。 然而，这样的贪心算法无法确保我们假定的最优解存在。我们分情况讨论： 在无障碍网格中，贪心结果是最优解。因为曼哈顿距离一定存在 在有障碍网格图中，曼哈顿距离不一定存在，可能i节点在走曼哈顿距离时碰壁，回头绕路。因此，在有障碍网格图中，我们不能确保贪心得到存在的最优解。 然而，无障碍网格图要求这是个连通图，这样大量图无法适用于贪心法。 总结来看：贪心最优搜索，只看终点，不看起点，错了不能改正，没有回头路，而且曼哈顿距离无法绕过障碍 2.Dijkstra（ ...

算法分析 简介 观察 数学模型 增长顺序分类 算法理论 内存 简介为什么要做算法分析： 预测性能 比对算法 提供保证 避免性能错误最主要是避免性能bug 成功算法的例子：FFT快速傅里叶变换（这好像高斯以前手稿提过，认为含金量，故未发表，大物课上有提到） 暴力算法：n**2FFT：n log n 当我们做算法分析时，应该考虑程序是否能适应大规模数据。性能是否足够（速度、内存） 观察3-sum:给定n个整型数据，有多少组（每组三个元素）元素和为0 javac测算运行时间的函数：12345678public static void main(String[] args){ int[] a = In.readInts(args[0]); Stopwatch stopwatch = new Stopwatch(); StdOut.println(ThreeSum.count(a)); double time = stopwatch.elapsedTime();} 我们发现对于不同的数据，程序运行时间大致为aN*b ,b=lg ratio 其中b的影响因子有： 算法 ...