本文共 1276 字,大约阅读时间需要 4 分钟。
生产者消费者问题
数据存到有界缓冲区bounded-buffer中,设置count记录缓冲区的数据量,如果缓冲区满count=size,让生产者睡眠;如果缓冲区为空count=0,让消费者睡眠。
解决方法:
(1)用信号量(semaphore)
需要三个信号量:full记录充满缓冲区数目,empty记录空的缓冲区数目。mutex用来保证任意时刻只有一个进程读写缓冲区变量。
(2)用互斥量(mutex)
是没有信号量基数能力的简化版,仅适用于管理共享资源或一小段代码。互斥量处于两态之一的变量:解锁和加锁
(3)用消息传递(message passing)
(4)用屏障(barrier)
临界资源:一次只能被一个进程访问的共享资源。
衡量调度的标准:吞吐量(系统每小时完成的作业量)和周转时间(批处理作业用时)
进程调度算法
(1)实时系统一般用非抢占式——先来先服务
交互式系统用抢占式:
(2)轮传时间片:时间片设置太长会让短交互的时间过长,时间片设置太短切换开销大,降低CPU效率
(3)优先级调度
(4)多级队列
(5)最短进程优先
(6)彩票调度
2.1.1 单一连续分配
单用户单进程时把内存分为系统区和用户区两部分。
2.1.2 固定分区分配法
给不同程序固定大小的内存空间
2.1.3 动态分区分配算法
动态分区空闲链:双向链表,节点需记录可
(1)首次适应(FF算法)
每次都从头开始顺序查找适合的内存区(容易造成表头碎片化,后期优化成循环适应,每次分配都从上次检索结束的位置开始查内存)
(2)最佳适应(BF算法)
把分区空闲链的节点按大小排序,每次选大小最相近的内存区
(3)快速适应(QF算法)
把整个内存分成多个空闲链表,每个空闲链表存储一种容量的空闲区。每次都能快速找到空闲链表。
操作系统如何管理进程的内存空间?
虚拟内存为何出现?程序/进程内存超过了物理内存的容量,且一台机器往往要跑多个程序/进程。
虚拟内存技术实现前提——程序的局部性原理:CPU访问存储器时,无论是存取指令还是存取数据,所访问的存储单元都趋向于聚集在一个较小的连续区域中。
高速缓存的替换时机 VS 主存缺页的替换时机:
虚拟内存的置换算法(和高速缓存的置换算法一样)
2.2.1 FIFO
利用一个双向链表保存数据,当来了新的数据之后便添加到链表末尾,如果Cache存满数据,则把链表头部数据删除,然后把新的数据添加到链表末尾。
在访问数据的时候,如果在Cache中存在该数据的话,则返回对应的value值;否则返回-1。如果想提高访问效率,可以利用hashmap来保存每个key在链表中对应的位置。
2.2.2 LFU(least recently used)
2.2.3 LRU(least recently used)
转载地址:http://ibrsi.baihongyu.com/