《码农翻身》之计算机世界

  1. 云栖社区>
  2. 博客>
  3. 正文

《码农翻身》之计算机世界

黄小斜 2018-07-29 16:21:11 浏览594
展开阅读全文
版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/a724888/article/details/81272328

《码农翻身》读书笔记之计算机世界

微信公众号【Java技术江湖】一位阿里 Java 工程师的技术小站。(关注公众号后回复”Java“即可领取 Java基础、进阶、项目和架构师等免费学习资料,更有数据库、分布式、微服务等热门技术学习视频,内容丰富,兼顾原理和实践,另外也将赠送作者原创的Java学习指南、Java程序员面试指南等干货资源)

wAAACH5BAEKAAAALAAAAAABAAEAAAICRAEAOw==

计算机世界(计算机体系、操作系统,网络基础,数据库等内容)

这是我的后端读书笔记系列文章的第一篇,选取的是最近刚刚圈粉的知名博主刘欣创作的《码农翻身》。这篇文章只是第一部分。

本文作为后端系列的开篇之作还是有其意义的,很好地为我们总结了计算机体系,操作系统,网络和数据库等知识。

本文内容主要根据知名博主刘欣一作《码农翻身》的内容总结而来,本书的内容风趣幽默,讲解计算机理论原理也是十分透彻,由于书中常常以小故事的形式出现,为了方便学习和回顾,我把它们进行了一些改编和整理,便于自己和跟多人阅读。

本篇文章主要讲述的书中的第一章“计算机的世界你不懂”。

本文首发于我的个人博客:https://h2pl.github.io/

同时发表在csdn技术博客上:https://blog.csdn.net/a724888

也欢迎来我的GitHub中交流学习:https://github.com/h2pl/

我是一个线程

这是一个线程的一生,平凡而忙碌的一生。(生命周期)

1 线程一出生就有一个线程号,并且有自身的调用栈和数据,也维护了自己的寄存器(虚拟的)。

2 线程被调度到的时候享有一个时间片,事实上也是让cpu的计数器指向该线程所在的内存位置,然后执行操作。时间片用完,会进行线程切换,执行下一个线程。

3 线程可能要执行cpu密集型运算,有时候可能打满cpu,可以通过kill结束线程。

4 线程池可以维护一个线程集合,避免线程运行完直接被回收,而是可以重新利用线程结构去执行其他命令,避免额外的创建开销。

5 数据库连接池也是类似的逻辑,在客户端维护与数据库的多个连接,避免了重复创建连接的开销(TCP连接)

6 多线程执行时,为了避免切换过程中其他线程修改了共享区域的内存,往往需要进行加锁,避免对同一段内存,打开文件以及其他共享数据进行不安全的访问、(同一进程的线程共享进程的资源)

7 多线程访问在某些情况下会造成死锁,满足死锁的四个条件即可。(资源互斥访问,请求对方资源,保持和等待,不可剥夺)
操作系统解决死锁的方式也有四种。

死锁预防,可以使用线程id的hashcode进行比较,大的先访问,小的再访问。

TCP/IP协议的实现

作者借着大明内阁的背景,讲述抗清将领袁崇焕是如何构建起TCP/IP协议的故事(误)

1 物理层:要想富,先铺路,两点通信,首先物理上要相连,可能是通过道路(双绞线,光纤),也可以是通过空气传播(电磁波)。物理上的介质解决了,于是人们开始解决具体数据传输。

2 链路层:帧是链路层的基本传输单位,它就是对比特流的一个封装,实际上都是0101的组合,链路层完成了基本的差错校验,并且支持通过mac地址寻址,在小范围低层次内的通信上得心应手。

链路层可以分为虚电路和分组交换两种,虚电路需要维护这个通信信道,开销大,并且闲置时浪费,而分组交换则是点到点的协议,不必关心中间状态,只需保证两端通信可靠即可。

3 网络层:在分组交换的基础上,ip协议出现了,ip协议通过ip路由将数据包转发到指定ip主机,不保证可靠传输,只是将数据包按照ip协议封装,并且经常需要切割成链路层MTU支持的分片。

4 传输层:TCP传输层在ip基础上保证了可靠传输,通过滑动窗口实现了ARQ自动重传,并使用窗口实现流水线传输,计时器实现超时重传,通过ack序号进行确认,并且缓存还没有被确认的包。除此之外,还维护了拥塞窗口,以及差错校验等特性。

CPU阿甘

CPU阿甘永远不懂什么叫作爱

1 CPU的运算速度极快,而平时他必须从内存中获取指令,内存比他慢100倍,而硬盘比他慢100w倍。

2 操作系统是连接和管理所有硬件资源的软件,cpu的调度当然也由操作系统来把控,BIOS负责中断向量表生成,硬件检测和初始化工作以及操作系统的加载。BIOS运行某个中断,于是CPU会把操作系统从硬盘装载到内存中。

当然这个硬盘一般指系统盘,系统盘会有一个分区表存储分区信息,启动时被加载,同时超级块中包含了文件系统信息,操作系统根据超级块的信息才能建立inode和磁盘块的映射表。

3 CPU一般运行的单位是进程,PCB保存进程信息,操作系统通过pcb的信息完成内存定位,寄存器刷新,上下文切换等工作。然后让cpu从内存中开始执行程序。

4 CPU通过IO总线访问IO,但是CPU和IO的速度实在天差地别,所以可以使用中断或者DMA的方式进行通知,避免cpu等待IO。

高速缓存与流水线

5 程序虽然复杂,但是在CPU看来都是顺序,分支,循环等组成的。

6 由于CPU和缓存仍然存在100倍的速度差距,使用缓存可以缓存内存中的热点数据,让cpu优先访问缓存,这里用到了局部性原理,并且,二级缓存三次缓存等也逐渐出现,以弥合性能上的差距。

7 流水线也是CPU的一个大改进。由于CPU需要进行1访存,2翻译代码成为机器码,3执行代码,4写回内存,这些步骤往往可以分开来执行,而不必等整个流程都跑完,比如写入内存的时候可以执行另一个进程的译码工作,诸如此类,流水线作业一直都是计算机改进性能的一大秘方。

我是一个进程

1 最早的操作系统只支持单道程序。cpu执行完一个程序再执行下一个,当有io等耗时操作,速度可想而知。于是操作系统开始支持多道程序,核心就是需要操作系统进行进程切换,这里的进程就是对运行时程序及数据的抽象,通过PCB进行控制。

2 进程出现以后,需要考虑内存分配的问题,如果顺序地为每个进程都分配一块内存,那么当某个进程结束时就会产生内存碎片。

3 作为一个分时系统,操作系统会把时间分割成时间片,每个进程获得一个时间片执行任务,然后让另一个进程执行。分时系统很好地避免了进程执行耗时操作所带来的低效问题,并且可以实现并发,当然多核的处理器还可以实现并行。

每个进程都以为自己独享cpu,但实际上只是因为cpu切换速度太快了以至于他们自己都没有察觉到。

内存地址转换

4 由于每个进程都要分配一段内存,如果地址分配不当,很有可能出现两个进程的内存重叠,于是一般需要让内存地址重定位,避免这样的情况。如果是在程序中修改指令,更改内存地址,叫做静态重定位,非常麻烦,不利于开发。

5 如果是动态重定位,则不需要用户干预,使用基址寄存器可以让内存地址定向到实际物理地址(通过偏移量实现)。于是cpu每次访存时都需要先通过基址寄存器进行地址转换。

在此基础上,还需要再加一个寄存器,用于标识该程序的长度,避免访问到其他进程的内存。计算机把这两个寄存器加上基址转换的算法包装在一个叫做MMU的单元里,由cpu访问。

内存管理机制

1 每个进程都需要分配内存,但是有些程序需要分配很多内存,比如游戏,但是并不是一直需要访问到所有内存,毕竟内存大小有限,而且32位CPU只能寻址4g内存。所以,操作系统支持分块装入内存,把需要用到的进程数据先装入内存,而不是一次性全部装载。

2 为了确定每一块内存的大小,操作系统规定了页面和页框,页框规定物理内存的分块大小,页面则对应的是虚拟内存分块的大小,两者间是一一对应的关系。程序一般只会运行在某几个页面中,我们只需要装载这部分页面即可,对于32位的机器一般使用4k大小的页面,页面和磁盘上的页一一对应。

虚拟内存和分页

3 既然我们只需要将一部分数据装载进内存,那么进程可以分配的虚拟空间其实就可以比较大了,比如4gb。每个进程都可以有超大的空间,平时我们把这些数据存在硬盘中,需要的时候再把他们调度进内存。

当然,这些虚拟空间我们也使用页面来进行划分,大小和物理内存中的页框一样,既然虚拟内存的页面需要和物理内存的页框形成映射,那么操作系统就需要维护一个页表,来映射虚拟页面和物理页面。

4 页表和页表缓存

除了维护页表外操作系统还需要考虑很多问题,一个是,需要知道哪些页面已被加载而哪些没有,页表装载页面时,需要找到空余的空间,同时可能需要进行页面置换。

缺页中断会触发缺页处理程序,完成页面的加载或者置换。从页面到物理地址,需要先通过页表找到自己的页号,同时根据自己的偏移量和页号,执行MMU提供的地址转换功能,获得市级的物理地址。

由于只维护一个页表对于查询效率和维护难度来说,都不是很好,于是操作系统一般会维护多级页表,加快页面的映射和读取过程,同时,由于页表保存在内存中,cpu和内存仍然存在较大速度差,一般会使用TLB页面缓存,缓存一部分常用的页面(局部性原理),以便加快转换速度。

5 分段+分页的段页式内存管理

分页很好地解决了内存的局部装载问题,虚拟内存也很好地解决了程序分配大内存的问题,程序可以安心地使用0开始的虚拟内存地址,真正的地址转换交给页表和mmu来做就可以了。

然而每个进程的内存虽然独立,但是等装载到内存中时,他们的逻辑意义并没有得到保护,比如两个进程可以访问对方内存,并且程序的内存段没有逻辑意义。

于是为了程序员更容易编程和开发,并且保护数据,操作系统提出了分段,程序的内存可以有逻辑分段,以便区分堆区,栈区,共享数据区等等,同时避免访问到其他的内存。如果访问到了会抛出段错误。

为了实现这样的机制,操作系统只能另外维护一个段表,来标识段号和偏移量,结合两种机制,即提高了效率,也保证了逻辑性。段页式管理一般需要通过段表得到一个线性地址,再通过页表得到最终的物理地址。

操作系统在为程序分配虚拟内存时,会在页表上标注该程序所在的磁盘地址,等到执行时,会通过页面调度算法加载该代码所在的几个页面。

我是一块硬盘

1 硬盘的速度很慢,但是断电不丢失数据,并且可以存储大容量数据。

2 内部结构比较复杂,不细说了,通过旋转磁盘可以让磁头指向你指定的扇区,然后开始读取数据。转速快的磁盘访问速度自然也更快一点。

3 文件

虽然通过磁盘我们已经可以定位数据了,但是例如一个文档,需要保存图片和文字,这些内容分布在不同的磁盘位置。
于是我们需要定义一个文件概念,用来标识所有这一些内容。

文件的存放有三种方式,我们把磁盘的最小单位叫做磁盘块。

3.1 文件包含的磁盘块在磁盘上顺序存储,这种方式在磁盘上随机访问的速度很快。但是磁盘块被删除后就不会再被使用,利用率很低。

3.2 使用链式分配可以把所有空闲空间连起来,但是随机访问的效率低下。

3.3 采用索引块很好地解决了这个问题,访问文件时先找到索引节点,通过索引节点找到所包含的磁盘块在哪,索引节点里有指向磁盘块的指针。

4 inode节点

inode节点是文件的索引节点,保存了文件的元数据,除了文件名以外,当然还包含了指向真正存储位置的指针。并且,当一个索引节点不足以保存所有指针时,可以让索引节点指向的磁盘块中存储inode节点不足以存放的指针。这就叫做间接块。

目录也是一个文件,所以他也是一个inode节点,该节点存储着目录的元数据,对应磁盘块里存储着目录下真正的内容,也就是目录下文件名和对应inode节点的映射表。通过该映射表才能在目录下访问这些文件。

访问/tmp/a.txt的过程如下,首先从根目录inode开始,访问其磁盘块,获取根目录的inode表,然后访问tmp目录的inode节点,找到对应a.txt的inode节点,最后访问对应的磁盘块即可。

由于访问文件的操作十分复杂,分为多个步骤,只要一个出错就容易导致文件系统崩溃,于是必须进行日志记录,以便进行回滚和重做。这叫日志文件系统。

5 空闲块管理

我们需要把磁盘的空闲块统一管理,以便分配新文件,用链式法显然低效,操作系统一般用位图法来表示磁盘块是否空闲,位图法用每个bit来标识硬盘是否空闲,非常的方便。

文件系统

上面所说的文件访问,inode节点,以及空闲块管理,磁盘交互等操作,都需要一个完整的系统来实现,操作系统把这个系统成为文件系统,磁盘安装了文件系统以后,操作系统才能通过文件系统的方式来操作磁盘块。

一块硬盘安装文件系统后可以分为多个区,每个区又可以分为多个部分。分区可以分为主分区和逻辑分区。

6.1 主分区的首部分包含MBR。MBR是主引导记录的意思,里面包引导代码和磁盘分区表。

6.2 引导代码用于引导计算机执行引导程序加载内核,分区表则用于记录每个分区的起始位置(比如C,D,E,F盘的起始位置)。

除了主分区以外,其他分区也会为引导快。

6.3 当然每个分区下还会被分城多个块组。快组中的超级块尤为重要,他记录了文件系统的关键信息,比如磁盘块总数,每个块的大小,块个数,inode个数等,也就是说,超级块包含了文件系统访问时需要的信息,文件系统通过访问超级块,就可以知道文件对应的inode以及块的情况了。

6.4 既然超级块如此重要,于是磁盘就把它和快组描述信息单独放到一个块组中,与其他真正存储数据的快组区分开来。
超级块中还包含了inode位图和磁盘块位图,可以快速定位inode和磁盘块,以及inode表。所以安装一个文件系统,就是改写其超级块的信息就可以了,文件在快组中的具体存储方式也会根据超级块的元数据来改变。

操作系统启动过程

操作系统的引导和启动过程绝对是非常有趣却很少人能完全理解的。

BIOS是固化在主板上的芯片,用于在启动时进行环境监测,以及中断服务初始化,执行初始引导过程等工作。

正常情况下计算机开机时会让BIOS完成自检,然后将内核代码装载进入内存,让CPU执行引导程序,完成内核的初始化,然后把控制权交给操作系统(也就是内核)即可完成系统启动。

以下来自百科

系统引导指的是将操作系统内核装入内存并启动系统的过程。

系统引导通常是由一个被称为启动引导程序的特殊代码完成的,它位于系统ROM中,用来完成定位内核代码在外存的具体位置、按照要求正确装入内核至内存并最终使内核运行起来的整个系统启动过程。

该过程中,启动引导程序要完成多个初始化过程,当这些过程顺利完成后才能使用系统的各种服务。这些过程包括初始引导、内核初始化、全系统初始化。

初始引导

初始引导过程主要由计算机的BIOS完成。BIOS是固化在ROM中的基本输入输出系统(Basic Input/Output System),其内容存储在主板ROM芯片中,主要功能是为内核运作环境进行预先检测。其功能主要包括中断服务程序、系统设置程序、上电自检(Power On Self Test,POST)和系统启动自举程序等。中断服务程序是系统软硬件间的一个可编程接口,用于完成硬件初始化;系统设置程序用来设置CMOS RAM中的各项参数,这些参数通常表示系统基本情况、CPU特性、磁盘驱动器等部件的信息等,开机时按Delete键即可进入该程序界面;上电自检POST所做的工作是在计算机通电后自动对系统中各关键和主要外设进行检查,一旦在自检中发现问题,将会通过鸣笛或提示信息警告用户;系统启动自举程序是在POST完成工作后执行的,它首先按照系统CMOS设置中保存的启动顺序搜索磁盘驱动器、CD-ROM、网络服务器等有效的驱动器,读入操作系统引导程序,接着将系统控制权交给引导程序,并由引导程序装入内核代码,以便完成系统的顺序启动。

内核初始化

操作系统内核装入内存后,引导程序将CPU控制权交给内核,此时内核才可以开始执行。内核将首先完成初始化功能,包括对硬件、电路逻辑等的初始化,以及对内核数据结构的初始化,如页表(段表)等。

我是一个键盘(初探IO设备)

1 IO总线负责管理一切IO设备,包括块设备和字符设备,块设备类似硬盘,字符设备类似鼠标,键盘。

2 任何一个IO设备在访问时都会占据IO总线,操作系统会给每个IO设备一个编号,称作IO端口便于CPU知道谁是谁。

3 当然也可以使用内存映射IO的方式,访问内存时直接映射到IO设备上。

4 IO的访问方式:

4.1 轮询肯定不行,CPU等待IO执行太慢了。

4.2 中断可以比较比较好低解决字符设备,响应及时,但是块设备的数据流如果每个字节都发出中断,那就是个灾难,操作系统的中断由中断控制器负责管理。

DMA很好地解决了块设备访问的问题,块设备通过DMA硬件命令完成IO操作,把数据搬到内存中然后再通知CPU,它速度很快,但是确实会独占IO总线。

数据库的奇妙之旅(数据库入门)

1 数据库的起源来自于无纸化办公,最早使用文本文件就可以很好地保存数据了,但是由于数据的冗余与不一致,以及每次修改都要修改一个文件等问题,主键建立齐了数据查询中间层的概念。

2 数据查询中间层负责执行查询语句,进行语句的解析和处理,然后再去访问底层的文件系统,这样子用户只需要使用简单的查询语句就可以完成数据访问,同时我们可优化物理层,并不影响上层的使用。这里的查询语句就是sql。

3 并发访问会带来冲突与数据不一致等问题,对于数据库来说也是一样,于是数据库也提出了事务这样的概念,保证一个事务中的操作是原子性的,而事务需要支持回滚,其实现原理就是基于undo日志完成的,undo日志用于记录原始数据以便回滚,同时,redo日志记录事务操作,以便保证事务能够重做,两个日志合起来一起确保其持久性和一致性。

4 为了保证数据库的访问安全,必须对数据库用户的权限加以限制,一般的数据库都会有这样的功能。

搞清楚Socket

1 IP协议就是把数据从一台主机跋山涉水运送到另一台主机,但是这种服务非常不可靠,丢包,重复,超时,无序等情况频繁出现,所以称为”尽力而为”的ip服务

2 ip层只管运数据,可靠传输就得让传输层让实现了,于是TCP协议使用滑动窗口机制保证了自动重发,累计确认,分组缓存,流量控制等等特性。同时还提供拥塞控制机制以及差错检验功能。

3 如果要让程序员自己实现tcp传输协议,那简直是不可能,于是大牛们把TCP/IP协议栈实现在操作系统内核中,并且提供一个叫做socket的api接口,以便用户进行操作实现网络编程。

4 socket就是一个插座的意思,包括ip和port两部分,分别确定主机以及进程。因为进程重启后可能进程号就变了,所以一般进程要监听固定的port,以便让请求方访问到他提供的服务。

5 内核中对socket的实现可以用几行伪代码来描述。

clientfd=socket();
connect(clientfd,服务端的ip+port);
send(clientfd,数据);
receive(clientfd,。。);
close(clientfd);

建立连接首先要先打开一个socket,内核为其创建一个数据结构,clientfd是一个文件描述符,用于描述用户的客服端socket数据结构,通过该socket进行连接,connect执行三次握手,然后进行访问,发送读写请求。

服务端的代码有所不同

listenfd = socket();
bind(listenfd, 服务端ip+端口号)
listen(listenfd,。。);
while(true) {
    connfd = accept(listenfd,。。)
    send(clientfd,数据);
    receive(clientfd,。。);
}

首先我们创建一个socket,进行端口号监听,listen方法与接入该socket的请求进行交互,完成三次握手。

并且我们通过accept方法得到一个完整的socket文件描述符,该socket已经完成了三次握手,并且绑定了客户端与服务端的ip+port,服务端通过这样的一个fd表就可以知道哪些fd对应哪些请求了。

从1加到100,计算机是怎么工作的

1 CPU和内存在运算中发挥巨大作用,CPU内部包括运算器和寄存器,运算器负责实现加法运算,寄存器负责寄存数据。CPU不能直接在内存中完成运算操作,而要先把数据读到寄存器中来。

当然,事实上CPU可以完成内存值与寄存器值的运算操作。

2 从高级语言到机器语言,要经过编译,再翻译成汇编语言,通过汇编器编程机器语言,机器语言直接与译码器交互,完成指令的运算。

(一个翻译家族的发家史)编译原理最入门

1 最早的计算机语言直接使用二进制进行开发。每个二进制指令对应一个操作或者一个值

2 后来提出了汇编语言,使用单词组成的命令代替了二进制的010101。汇编语言和二进制代码基本可以完成一对一映射,所以使用汇编器就可以简单滴进行翻译了。

3 高级语言的出现,使得开发语言更加贴近自然语言,代码进行编译,生成中间代码,再变成汇编,最后成为机器码。

4 编译原理是非常复杂的一个课程,但是简单说来,主要包括几点

4.1 词法分析(找出单词),一般先把代码砍成一个个的片段,每个片段叫token,空格会被删除,然后建立一个符号表,对于每个片段,都会有对应的一个类型。

4.2 语法分析(英语中的主谓宾定状补),根据上面的Token以及符号表,基于上下文无关语法的理论,可以把Token按照语法规则组成一个树,这个树中的表达式可以是递归定义的,每个表达式都可以拆成表达式+任一类型。

4.3 语义分析(句子是否合理通顺),根据语法树,开始进行语义分析,看看标识符的类型和作用域是不是正确,是否合法等等。

4.4 中间代码生成,代码优化,最终代码生成
首先生成通用的中间代码,然后进行代码的优化,最后翻译成汇编语言。

编程世界的那把锁

1 不管是线程间,进程间,还是数据库,服务之间,都会出现多个客户同时访问一个服务的情况,共享区域的并发访问会产生线程安全问题。

2 多线程要访问共享资源,需要进行加锁,避免并发问题,但是我们需要保证加锁的操作是原子性的,比如set lock = true时获得锁,但是有可能两个线程一起完成了这个操作。

为了避免这种情况,可以使用原子操作实现,也就是CAS操作,它基于硬件实现,保证指令在一个机器指令中完成,多线程只有一个能够加锁成功。

3 但是事实上,这样的机制只保证单CPU时有效,多CPU时就必须要加总线锁,避免其他核心访问内存。当然CAS操作也实现了锁总线。除此之外,cas还有ABA问题,通过版本号可以解决。

cas只支持单个变量的原子性操作,而Java中的原子引用类型让cas操作可以直接修改引用地址,完成多个变量的同时操作。

4 改进的自旋锁,自旋锁避免线程切换,不断请求CPU时间片,如果自旋锁不能重入,那么代码就会产生死锁,所以必须实现计数器来记录锁的拥有者,保证锁可重入。

信号量和生产者消费者问题

1 使用锁可以控制资源的互斥访问,但是并不保证顺序,使用信号量可以让线程之间同步,保证顺序访问。

2 信号量分为signal操作以及wait操作,操作的是一个值state,小于1时执行wait会阻塞,大于0时执行wait可以运行并且把state减一,notify会把state加1,并且通知正在wait的线程。

3 操作系统用简单的代码实现了信号量,但是它本身就存在并发问题,怎么能保证别人的线程安全呢,原来啊,内核保证信号量操作时会屏蔽中断,不允许程序切换。于是保证了操作的原子性。

4 使用自旋检测state比较浪费cpu,于是我们让wait执行失败的线程阻塞在内核为该信号量维护的阻塞队列中,等待signal唤醒它们。

生产者与消费者问题

5 使用信号量实现生产者,消费者模型。

生产者消费者模型其实有两个要点。
1 队列是空还是满的两个状态。
2 多线程访问队列的前提是拿到了锁。

所以我们需要三个变量,empty(队列的空位个数),empty设为5,队列为满full,full(队列放置物品的个数)设为0,是否获取到锁,锁的值是1。

生产者

while(true)
{
    wait(empty);
    wait (lock);
    生产
    signal(lock);
    signal(full);

}

过程:

1 首先等待队列出现空位,当empty>0时可以执行。

2 然后等待lock锁,如果获取不到锁就阻塞。

3 生产

4 执行完之后首先释放锁

5 然后把full加一,以便消费者可以得知队列不为空

消费者

while(true)
{
    wait(full);
    wait (lock);
    消费
    signal(lock);
    signal(empty);
}

首先等待队列出现货物,当full>0时可以执行。

然后等待lock锁,加锁才能对队列操作。

消费

执行完后释放锁

把empty加一,通知生产者又可以继续生产了。

6 总结一下生产者和消费者模型的实现主要包含两个要素,
首先队列要满足条件,比如不空或者不满。

其次,队列在满足条件的前提下还要保证队能获取到锁,因为队列一次只能被一个线程访问。

7 Java中封装了阻塞队列BlockingQueue使用put和take方法就可以实现生产者,消费者模型了。非常简单。

当然,blockingqueue不是使用信号量实现的,而是使用Lock加condition的方式进行实现,lock就是队列的锁,而condition分别是notempty和nofull两种状态,当不满足该条件时线程等待,满足时才会继续进行加锁操作。

8 实际上,使用synchronized关键字配合wait和notify一样可以实现生产者和消费者模型

。synchronized关键字的作用就是加锁,锁对象是队列,我们一样可以用notempty和notfull表示两种情况,这里可以使用boolean,满足条件时尝试使用synchronized加锁,然后执行操作,接着释放锁,并且改变条件,通知阻塞的线程。

加法器与补码

1 计算机中二进制的位是基本运算单位,计算机使用加法器实现一部分逻辑电路,为了把减法变成加法,计算机使用补码来表示二进制数,最高位的0和1表示正负,剩下的位表示数值,比如0001代表1。

2 正数的补码是自己,而负数的补码是自己的各位(除了符号位)取反加一。比如1001本来是-1,它的补码就是1110+1=1111了。补码相加,无论是正数还是负数,都能得到正确的结果。

3 由于1000和0000都可以代表0,而1000的补码是1000,符号位应该是1+1,就会变成5位二进制数,所以这个数被特殊处理,1000的补码被规定为-8。而0000才是真正的0。

递归的那些事

1 递归往往可以将复杂问题用简单的代码写出来,只要你限制了边界条件,并且让递归的规模逐渐减小,就可以得到最终结果。

2 比如斐波那契数列,f(n) = f(n - 1) * n,由于返回值是
f(n - 1) * n,所以我们必须跟踪f(n)方法的栈帧,不断新栈帧直到运行结束,再从栈帧顶部一帧帧地返回。当栈深度过大,就会出现栈溢出。

3 尾递归的斐波那契数列可表示为:f(n,result) = f(n - 1,n * result)。最后获得result即可,递归调用中把result放在函数参数中,并且每次调用都得到一个明确的结果,于是程序可以复用栈帧,不断地更新result变量,知道结束即可。

网友评论

登录后评论
0/500
评论
黄小斜
+ 关注