剑指Offer——知识点储备-操作系统基础

操作系统

操作系统什么情况下会出现死锁？

产生死锁的必要条件

• （1）互斥条件：即某个资源在一段时间内只能由一个进程占有，不能同时被两个或两个以上的进程占有，这种独占资源如CD-ROM驱动器，打印机等，必须在占有该资源的进程主动释放它以后，其他进程才能占有该资源，这是资源本身的属性决定的。
• （2）不可抢占条件：进程所获得资源在未使用完毕之前，资源申请者不能强行将资源从占用者手中夺取，而只能由该资源的占有者进程自行释放。
• （3）占有且申请条件：进程至少已经占有一个资源，但又申请新的资源。由于该资源已被另外进程占有，此时该进程阻塞；但是它在等待新资源之时，仍继续占用已有的资源。
• （4）循环等待条件：存在一个进程等待序列{P1，P2，……，Pn},其中P1等待P2所占有的某一部分资源，P2等待P3所占有的某一资源，……，而Pn等待P1所占有的某一资源，形成一个进程循环等待环。

死锁预防：

• （1）打破互斥条件：即允许进程同时访问某些资源。但是，有的资源是不允许被同时访问的，如打印机。（这是资源本身属性所决定的，所以这种办法并无实用价值。）
• (2)打破不可抢占条件：即允许进程强行从占有者那里获取某些资源。就是说，当一个进程已占有了某些资源，它又申请新的资源，但不能立即被满足时，它必须释放所占有的全部资源，以后再重新申请。它所释放的资源可以分配给其它进程。这就相当于该进程占有的资源被隐藏的占有了。这种预防死锁的方法实现起来困难，会降低系统性能。
• （3）打破占有且申请条件：可以实现资源预先分配策略。即进程在运行前一次性的向系统申请它所需要的全部资源。如果某个进程所需要的全部资源不能得到满足，则不分配任何资源，此进程暂不运行，只有当系统能够满足当前进程的全部资源需求时，才能一次性的将所申请的资源全部分配给该进程，由于运行的进程已占有了它所需要的全部资源，所以不会发生占有资源又申请资源的现象，因此不会发生死锁。
  
  但是，这种策略也有如下缺点：
  
  1）在许多情况下，一个进程在执行之前不可能知道它所需要的全部资源，这是由于进程的执行时是动态的，不可预测的。
  
  2）资源利用率低：无论所分资源何时用到，一个进程只能占用所需资源的全部资源后才能执行。即使有些资源最后才被该进程用到一次，但该进程在生存期间却一直占有它们，造成长期占着不用的状况。这显然是一种极大的资源浪费。
  
  3）降低了进程的并发性，因为资源有限，又加上存在浪费，能分配到所需全部资源的进程个数就必然少了。
• (4)打破循环等待条件:实行资源有序分配策略。采用这种策略，即把资源事先分类编号，按号分配，使进程在申请占有资源时不会形成环路。所有进程对资源的请求必须严格按照资源序号递增的顺序提出。进程占用（应该改成用完）了小号资源，才能申请大号资源，就不会产生环路，从而预防死锁。这种策略与前面相比，资源利用率和系统吞吐量都有很大提高。
  
  但是也存在以下缺点：
  
  1）限制了进程对资源的请求，同时给系统中所有资源合理编号也是件难事，并增加了系统的开销。
  
  2）为了遵循按编号申请的次序，暂不使用的资源也需要提前申请，从而增加了进程对资源占用时间。

死锁避免：

• 1）避免一个线程同时获取多个锁；
• 2）避免一个线程在锁内同时占用多个资源，尽量保证每个锁只占用一个资源；
• 3）尝试使用定时锁，使用lock.tryLock(timeout)来代替使用内部锁机制；
• 4）对于数据库锁，加锁解锁必须在一个数据库连接里，否则会出现解锁失败的情况；

实际的应用方法

• （1）安全序列
• （2）银行家算法

如何理解分布式锁？

分布式锁是控制分布式系统之间同步访问共享资源的一种方式。在分布式系统中，常常需要协调他们的动作。如果不同的系统或是同一个系统的不同主机之间共享一个或一组资源，那么访问这些资源的时候，往往需要互斥来防止彼此干扰来保证一致性，在这种情况下，需要使用到分布式锁。

进程间通信有哪几种方式？

注意：进程间通信是通过操作系统，而线程间通信是基于进程的，不需要经过操作系统。

- （1）管道：管道可用于具有亲缘关系进程间的通信，允许一个进程和另外一个与它有共同祖先的进程之间进行通信。

- （2）命令管道：命名管道克服了管道没有名字的限制，因此，除具有管道所具有的功能外，它还允许无亲缘关系进程间通信，命名管道在文件系统中有对应的文件名。命名管道通过命令mkfifo或系统调用mkfifo来创建。

- （3）信号：信号是比较复杂的通信方式，用于通知接收进程有某种事件发生，除了用于进程间通信外，进程还可以发送信号给进程本身。

- （4）消息队列：消息队列是消息的连接表，包括Posix消息队列、systern V消息队列。有足够权限的进程可以向队列中添加消息，被赋予读权限的进程则可以读队列中的消息、消息队列克服了信号承载信息量少，管道只能承载无格式字节流以及缓存区大小受限等缺陷。

- （5）共享内存：使得多个进程可以访问同一块内存空间，是最快可用IPC形式。是针对其他通信机制运行效率较低而设计的。往往与其他通信机制，如与信号量结合使用，来达到进程间的同步及互斥。

- （6）内存映射;内存映射允许多个进程间通信，每一个使用该机制的进程通过把一个共享的文件映射到自己的进程地址空间来实现它。

- （7）信号量：主要作为进程间以及同一进程不同线程之间的同步手段。

- （8）套接字（socket）更为一般的进程间通信机制，可用于不同机器之间的进程通信。

线程同步与阻塞的关系？同步一定阻塞吗？阻塞一定同步吗？

线程同步与阻塞的关系

- （1）线程同步与阻塞没有一点关系。

- （2）同步和异步关注的是消息通信机制。所谓同步，就是在发出一个调用时，在没有得到结果之前，该调用就不返回。但是一旦调用返回，就得到返回值。而异步则是相反，在调用发出之后，这个调用直接返回了，所以没有返回结果。换句话说，当一个异步过程调用发出后，调用者不会立刻得到结果，而是在调用发出后，被调用者通过状态，通知调用者，或者回调函数处理这个调用。

- （3）阻塞和非阻塞关注的是程序在等待调用结果（消息，返回值）的状态。阻塞调用是指调用结果返回之间，当前线程会被挂起，调用线程只能在得到结果之后才会返回。非阻塞调用指在不能立即得到结果之前，调用不会阻塞当前线程。

进程和线程之间的区别

进程是执行着的应用程序，而线程是进程内部的一个执行序列。

- （1）地址空间和其他资源：进程间相互独立，同一进程的各线程间资源共享，某进程内的线程在其他进程不可见。

- （2）通信：进程间通信IPC（一种标准的unix通信机制，可见上面进程间的通信），线程间可以直接读写进程数据段（如全局变量）来进行通信–需要进程同步和互斥的辅助，来保证数据的一致性。

- （3）切换：线程比进程切换快的多；

- （4）调度：进程是运行中的程序（例如某个应用：qq、微信、支付宝），而线程是进程内部的一个执行序列（比如：qq中的某一个操作，聊天写数据，查看聊天记录……）