折扣爆料
折扣好货实时更新
并发是指宏观上在一段时间内能同时运行多个程序,而并行则指同一时刻能运行多个指令。
并行需要硬件支持,如多流水线或者多处理器。
操作系统通过引入进程和线程,使得程序能够并发运行。
共享是指系统中的资源可以被多个并发进程共同使用。
有两种共享方式:互斥共享和同时共享。
互斥共享的资源称为临界资源,例如打印机等,在同一时间只允许一个进程访问,需要用同步机制来实现对临界资源的访问。
虚拟技术把一个物理实体转换为多个逻辑实体。
利用多道程序设计技术,让每个用户都觉得有一个计算机专门为他服务。
主要有两种虚拟技术:时分复用技术和空分复用技术。例如多个进程能在同一个处理器上并发执行使用了时分复用技术,让每个进程轮流占有处理器,每次只执行一小个时间片并快速切换。
异步指进程不是一次性执行完毕,而是走走停停,以不可知的速度向前推进。
但只要运行环境相同,OS需要保证程序运行的结果也要相同。
进程控制、进程同步、进程通信、死锁处理、处理机调度等。
内存分配、地址映射、内存保护与共享、虚拟内存等。
文件存储空间的管理、目录管理、文件读写管理和保护等。
完成用户的 I/O 请求,方便用户使用各种设备,并提高设备的利用率。
主要包括缓冲管理、设备分配、设备处理、虛拟设备等。
如果一个进程在用户态需要使用内核态的功能,就进行系统调用从而陷入内核,由操作系统代为完成。
Linux 的系统调用主要有以下这些:
Task | Commands |
进程控制 | fork(); exit(); wait(); |
进程通信 | pipe(); shmget(); mmap(); |
文件操作 | open(); read(); write(); |
设备操作 | ioctl(); read(); write(); |
信息维护 | getpid(); alarm(); sleep(); |
安全 | chmod(); umask(); chown(); |
大内核是将操作系统功能作为一个紧密结合的整体放到内核。
由于各模块共享信息,因此有很高的性能。
由于操作系统不断复杂,因此将一部分操作系统功能移出内核,从而降低内核的复杂性。移出的部分根据分层的原则划分成若干服务,相互独立。
在微内核结构下,操作系统被划分成小的、定义良好的模块,只有微内核这一个模块运行在内核态,其余模块运行在用户态。
因为需要频繁地在用户态和核心态之间进行切换,所以会有一定的性能损失。
由 CPU 执行指令以外的事件引起,如 I/O 完成中断,表示设备输入/输出处理已经完成,处理器能够发送下一个输入/输出请求。此外还有时钟中断、控制台中断等。
由 CPU 执行指令的内部事件引起,如非法操作码、地址越界、算术溢出等。
在用户程序中使用系统调用。
类型 | 源头 | 响应方式 | 处理机制 |
中断 | 外设 | 异步 | 持续,对用户应用程序是透明的 |
异常 | 应用程序意想不到的行为 | 同步 | 杀死或重新执行意想不到的应用程序指令 |
系统调用 | 应用程序请求操作提供服务 | 异步或同步 | 等待和持续 |
栈区(stack)— 由编译器自动分配释放 ,存放函数的参数值,局部变量的值等。其操作方式类似于数据结构中的栈。
堆区(heap) — 一般由程序员分配释放, 若开发者不释放,则会在程序结束时可能由OS回收 。
数据结构中这两个完全就不放一块来讲,数据结构中栈和队列才是好基友,我想新手也很容易区分。
我想需要区分的情况肯定不是在数据结构话题下,而大多是在 OS 关于不同对象的内存分配这块上。
简单讲的话,在 C 语言中:
int a[N]; // go on a stackint* a = (int *)malloc(sizeof(int) * N); // go on a heap
分布式锁,是控制分布式系统之间同步访问共享资源的一种方式。在分布式系统中,常常需要协调他们的动作。如果不同的系统或是同一个系统的不同主机之间共享了一个或一组资源,那么访问这些资源的时候,往往需要互斥来防止彼此干扰来保证一致性,在这种情况下,便需要使用到分布式锁。
进程与线程:
进程是资源分配的基本单位,用来管理资源(例如:内存,文件,网络等资源)
进程控制块 (Process Control Block, PCB) 描述进程的基本信息和运行状态,所谓的创建进程和撤销进程,都是指对 PCB 的操作。(PCB是描述进程的数据结构)
上面是4 个程序创建了 4 个进程,这 4 个进程可以并发地执行。
线程是独立调度的基本单位。
一个进程中可以有多个线程,它们共享进程资源。
QQ 和浏览器是两个进程,浏览器进程里面有很多线程,例如 HTTP 请求线程、事件响应线程、渲染线程等等,线程的并发执行使得在浏览器中点击一个新链接从而发起 HTTP 请求时,浏览器还可以响应用户的其它事件。
(一)拥有资源
进程是资源分配的基本单位,但是线程不拥有资源,线程可以访问隶属进程的资源。
(二)调度
线程是独立调度的基本单位,在同一进程中,线程的切换不会引起进程切换,从一个进程内的线程切换到另一个进程中的线程时,会引起进程切换。
(三)系统开销
由于创建或撤销进程时,系统都要为之分配或回收资源,如内存空间、I/O 设备等,所付出的开销远大于创建或撤销线程时的开销。类似地,在进行进程切换时,涉及当前执行进程 CPU 环境的保存及新调度进程 CPU 环境的设置,而线程切换时只需保存和设置少量寄存器内容,开销很小。
(四)通信方面
进程间通信 (IPC) 需要进程同步和互斥手段的辅助,以保证数据的一致性。而线程间可以通过直接读/写同一进程中的数据段(如全局变量)来进行通信。
就绪状态(ready):等待被调度
运行状态(running)
阻塞状态(waiting):等待资源
需要注意的是:
相信很多人都听说过进程调度的算法,但是不同环境的调度算法目标不同,因此需要针对不同环境来讨论调度算法。
批处理系统没有太多的用户操作,在该系统中,调度算法目标是保证吞吐量和周转时间(从提交到终止的时间)。
短作业优先 shortest job first(SJF),按估计运行时间最短的顺序进行调度。长作业有可能会饿死,处于一直等待短作业执行完毕的状态。因为如果一直有短作业到来,那么长作业永远得不到调度。
最短剩余时间优先 shortest remaining time next(SRTN),按估计剩余时间最短的顺序进行调度。
交互式系统有大量的用户交互操作,在该系统中调度算法的目标是快速地进行响应。
时间片轮转算法的效率和时间片的大小有很大关系。因为进程切换都要保存进程的信息并且载入新进程的信息,如果时间片太小,会导致进程切换得太频繁,在进程切换上就会花过多时间。
为每个进程分配一个优先级,按优先级进行调度。
为了防止低优先级的进程永远等不到调度,可以随着时间的推移增加等待进程的优先级。
通常,如果一个进程需要执行 100 个时间片,如果采用时间片轮转调度算法,那么需要交换 100 次。
多级队列是为这种需要连续执行多个时间片的进程考虑,它设置了多个队列,每个队列时间片大小都不同,例如 1,2,4,8,..。进程在靠前个队列没执行完,就会被移到下一个队列。这种方式下,之前的进程只需要交换 7 次。
每个队列优先权也不同,最上面的优先权最高。因此只有上一个队列没有进程在排队,才能调度当前队列上的进程。
可以将这种调度算法看成是时间片轮转调度算法和优先级调度算法的结合。
实时系统要求一个请求在一个确定时间内得到响应。
分为硬实时和软实时,前者必须满足绝对的截止时间,后者可以容忍一定的超时。
对临界资源进行访问的那段代码称为临界区。
为了互斥访问临界资源,每个进程在进入临界区之前,需要先进行检查。
entry section critical section; exit section
同步:多个进程按一定顺序执行;
互斥:多个进程在同一时刻只有一个进程能进入临界区。
down 和 up 操作需要被设计成原语,不可分割,通常的做法是在执行这些操作的时候屏蔽中断。
如果信号量的取值只能为 0 或者 1,那么就成为了 互斥量(Mutex) ,0 表示临界区已经加锁,1 表示临界区解锁。
typedef int semaphore;semaphore mutex = 1;void P1() { down(&mutex); // 临界区 up(&mutex);}void P2() { down(&mutex); // 临界区 up(&mutex);}
通常,使用一个缓冲区来保存数据,只有缓冲区没有满,生产者才可以放入数据;只有缓冲区不为空,消费者才可以拿走数据。
因为缓冲区属于临界资源,因此需要使用一个互斥量 mutex 来控制对缓冲区的互斥访问。
为了同步生产者和消费者的行为,需要记录缓冲区中数据的数量。数量可以使用信号量来进行统计,这里需要使用两个信号量:empty 记录空缓冲区的数量,full 记录满缓冲区的数量。其中,empty 信号量是在生产者进程中使用,当 empty 不为 0 时,生产者才可以放入数据;full 信号量是在消费者进程中使用,当 full 信号量不为 0 时,消费者才可以取走数据。
这里需要注意,不能先对缓冲区进行加锁,再测试信号量。也就是说,不能先执行 down(mutex) 再执行 down(empty)。如果这么做了,那么可能会出现这种情况:生产者对缓冲区加锁后,执行 down(empty) 操作,发现 empty = 0,此时生产者睡眠。消费者不能进入临界区,因为生产者对缓冲区加锁了,也就无法执行 up(empty) 操作,empty 永远都为 0,那么生产者和消费者就会一直等待下去,造成死锁。
#define N 100typedef int semaphore;semaphore mutex = 1;semaphore empty = N;semaphore full = 0;void producer() { while(TRUE){ int item = produce_item(); // 生产一个产品 // down(&empty) 和 down(&mutex) 不能交换位置,否则造成死锁 down(&empty); // 记录空缓冲区的数量,这里减少一个产品空间 down(&mutex); // 互斥锁 insert_item(item); up(&mutex); // 互斥锁 up(&full); // 记录满缓冲区的数量,这里增加一个产品 }}void consumer() { while(TRUE){ down(&full); // 记录满缓冲区的数量,减少一个产品 down(&mutex); // 互斥锁 int item = remove_item(); up(&mutex); // 互斥锁 up(&empty); // 记录空缓冲区的数量,这里增加一个产品空间 consume_item(item); }}
管程 (Monitors,也称为监视器) 是一种程序结构,结构内的多个子程序(对象或模块)形成的多个工作线程互斥访问共享资源。
使用信号量机制实现的生产者消费者问题需要客户端代码做很多控制,而管程把控制的代码独立出来,不仅不容易出错,也使得客户端代码调用更容易。
管程是为了解决信号量在临界区的 PV 操作上的配对的麻烦,把配对的 PV 操作集中在一起,生成的一种并发编程方法。其中使用了条件变量这种同步机制。
c 语言不支持管程,下面的示例代码使用了类 Pascal 语言来描述管程。示例代码的管程提供了 insert() 和 remove() 方法,客户端代码通过调用这两个方法来解决生产者-消费者问题。
monitor ProducerConsumer integer i; condition c; procedure insert(); begin // ... end; procedure remove(); begin // ... end;end monitor;
管程有一个重要特性:在一个时刻只能有一个进程使用管程。进程在无法继续执行的时候不能一直占用管程,否者其它进程永远不能使用管程。
管程引入了 条件变量 以及相关的操作:wait() 和 signal() 来实现同步操作。对条件变量执行 wait() 操作会导致调用进程阻塞,把管程让出来给另一个进程持有。signal() 操作用于唤醒被阻塞的进程。
允许多个进程同时对数据进行读操作,但是不允许读和写以及写和写操作同时发生。
Rcount:读操作的进程数量(Rcount=0)
CountMutex:对于Rcount进行加锁(CountMutex=1)
WriteMutex:互斥量对于写操作的加锁(WriteMutex=1)
Rcount = 0;semaphore CountMutex = 1;semaphore WriteMutex = 1;void writer(){ while(true){ sem_wait(WriteMutex); // TO DO write(); sem_post(WriteMutex); }}// 读者优先策略void reader(){ while(true){ sem_wait(CountMutex); if(Rcount == 0) sem_wait(WriteMutex); Rcount++; sem_post(CountMutex); // TO DO read(); sem_wait(CountMutex); Rcount--; if(Rcount == 0) sem_post(WriteMutex); sem_post(CountMutex); }}
五个哲学家围着一张圆桌,每个哲学家面前放着食物。哲学家的生活有两种交替活动:吃饭以及思考。当一个哲学家吃饭时,需要先拿起自己左右两边的两根筷子,并且一次只能拿起一根筷子。
靠前种方案:
下面是一种错误的解法,考虑到如果所有哲学家同时拿起左手边的筷子,那么就无法拿起右手边的筷子,造成死锁。
#define N 5 // 哲学家个数void philosopher(int i) {// 哲学家编号:0 - 4 while(TRUE) { think(); // 哲学家在思考 take_fork(i); // 去拿左边的叉子 take_fork((i + 1) % N); // 去拿右边的叉子 eat(); // 吃面条中…. put_fork(i); // 放下左边的叉子 put_fork((i + 1) % N); // 放下右边的叉子 }}
第二种方案:
对拿叉子的过程进行了改进,但仍不正确.
#define N 5 // 哲学家个数while(1){ take_fork(i); // 去拿左边的叉子 if(fork((i+1)%N)) { // 右边叉子还在吗 take_fork((i + 1) % N);// 去拿右边的叉子 break; // 两把叉子均到手 } else { // 右边叉子已不在 put_fork(i); // 放下左边的叉子 wait_some_time(); // 等待一会儿 }}
第三种方案:
等待时间随机变化。可行,但非万全之策.
#define N 5 // 哲学家个数while(1) { take_fork(i); // 去拿左边的叉子 if(fork((i+1)%N)) { // 右边叉子还在吗 take_fork((i + 1) % N);// 去拿右边的叉子 break; // 两把叉子均到手 } else { // 右边叉子已不在 put_fork(i); // 放下左边的叉子 wait_random_time( ); // 等待随机长时间 }}