操作系统基础问题
1. 操作系统如何处理Hello World程序
1、用户告诉操作系统执行Helloworld程序。
2、操作系统找到程序相关信息，检查其类型是否为可执行文件。并通过程序首部信息确定可执行文件的位置和对应的磁盘块地址。
3、操作系统创建一个新的进程，将执行文件映射到该进程中，表示由该进程执行helloworld程序。
4、操作系统为程序设置CPU上下文环境并调到程序开始处。
5、执行程序的第一条指令，发生缺页异常。因为此时代码和数据还没有读入内存。
6、操作系统分配一页物理内存，将代码从磁盘读入内存。
7、程序执行puts函数，在显示器上写字符串
8、操作系统将字符串送给一个控制显示器的进程
9、控制设备的进程告诉设备的窗口系统它要显示字符串，窗口系统确定是合法操作后将字符串转化为像素，写入设备的存储映像区
10、 视频硬件将像素转化为显示器可接收的一组控制/数据信号
11、 显示器解释信号，激发液晶屏
12、 我们看到了HelloWorld
2. CPU状态之间的转换
用户态到内核态： 只能通过中断/异常/陷入机制
内核态到用户态： 设置程序状态字PSW
3. 中断处理流程（中断是一种异步操作）
1、设备发出中断信号
2、硬件通过PSW和PC保存现场，保存在堆栈中
3、根据中断码查找中断向量表
4、把中断处理程序入口地址推送给寄存器
5、执行中断处理程序
6、回到之前断点继续运行
4. 操作系统特点
并发性、共享性、虚拟性、随机性。
并发性：处理多个同时性的活动。单CPU实际上多个程序轮流执行。
共享性：操作系统与多个用户的程序共同使用计算机的资源，（共享有限的系统资源）
虚拟性：一个物理实体映射为多个对应的逻辑实体，提高资源利用率
随机性：对以不可预测次序发生的事件进行响应并处理
5. 什么是进程
1) 进程是指在系统中正在运行的一个应用程序，程序一旦运行就是进程；
2) 进程可以认为是程序执行的一个实例，进程是系统进行资源分配的最小单位，且每个进程拥有独立的地址空间；
3) 一个进程无法直接访问另一个进程的变量和数据结构，如果希望一个进程去访问另一个进程的资源，需要使用进程间的通信，比如：管道、消息队列等
4) 线程是进程的一个实体，是进程的一条执行路径；比进程更小的独立运行的基本单位，线程也被称为轻量级进程，一个程序至少有一个进程，一个进程至少有一个线程；
进程是程序的一次执行，该程序可以与其他程序并发执行；
进程有运行、阻塞、就绪三个基本状态；
进程调度算法：先来先服务调度算法、短作业优先调度算法、非抢占式优先级调度算法、抢占式优先级调度算法、高响应比优先调度算法、时间片轮转法调度算法；
5. OS进程调度及典型调度算法
进程调度的功能
记录系统中的所有进程的状态、优先级数和资源的需求情况
确定调度算法，决定将CPU分配给哪个进程多少时间
分配处理机给进程，进行CPU现场的保护和移交
调度的层次
一个作业从提交开始直到完成，往往要经历以下三级调度，如图所示。
1、作业调度。又称高级调度，.
其主要任务是按一定的原则从外存上处于后备状态的作业中挑选一个（或多个）作业，给它（们）分配内存、输入/输出设备等必要的资源，并建立相应的进程，以使它（们）获得竞争处理机的权利。简言之，就是内存与辅存之间的调度。对于每个作业只调入一次、调出一次。
多道批处理系统中大多配有作业调度，而其他系统中通常不需要配置作业调度。作业调度的执行频率较低，通常为几分钟一次。
2、中级调度。又称内存调度。
引入中级调度是为了提高内存利用率和系统吞吐量。为此，应使那些暂时不能运行的进程，调至外存等待，把此时的进程状态称为挂起状态。当它们已具备运行条件且内存又稍有空闲时，由中级调度来决定，把外存上的那些已具备运行条件的就绪进程，再重新调入内存，并修改其状态为就绪状态，挂在就绪队列上等待。
3、进程调度。又称为低级调度
其主要任务是按照某种方法和策略从就绪队列中选取一个进程，将处理机分配给它。进程调度是操作系统中最基本的一种调度，在一般操作系统中都必须配置进程调度。进程调度的频率很高，一般几十毫秒一次。
进程调度方式
非抢占式方式
系统一旦把处理机分配给就绪队列中优先级最高的进程后，该进程就一直执行下去，直至完成；或者发生某事件而不得不放弃处理机。通常用于批处理系统。
抢占式方式
当一个进程正在执行时，系统可以基于某种策略剥夺CPU给其他进程。剥夺的原则有：优先权原则、短进程优先原则和时间片原则。一般用在分时系统和实时系统中。
调度的基本准则
CPU利用率。尽可能使CPU处于忙碌状态
系统吞吐量。表示单位时间CPU完成作业的数量，短作业消耗的处理机时间较短
周转时间。从作业提交到作业完成经历的时间。
等待时间。进程处于等处理机状态时间之和，从提交到开始执行，等待时间越长，用户满意度越低。
响应时间。指从用户提交请求到系统首次产生响应所用的时间。在交互式系统尤其明显，调度策略应尽可能降低响应时间，使响应时间处在用户能接受的范围之内。
PS：不可能同时满足所有用户和系统的要求， 采取哪种策略要看具体情况，比如实时性或者交互性；另一方面要考虑整体效率，还有算法的开销。
进程调度算法
1、先来先服务调度算法（FCFS）
思想：
既可用于作业调度也可用于进程调度。
在进程调度中采用FCFS算法时，则每次调度是从就绪队列中选择一个最先进入该队列的进程，为之分配处理机，使之投入运行，该进程一直运行到完或发生某事件而阻塞后才放弃处理机。–非抢占式
当在作业调度中采用该算法时，每次调度都是从后备作业队列中选择一个或多个最先进入该队列的作业，将它们调入内存，为它们分配资源，创建进程，然后放入就绪队列；
特点：
有利于长作业，不利于短作业；有利于CPU繁忙的作业，不利于I/O繁忙的作业。
2、短作业（进程）优先调度算法（SJF、SPF）
思想：
可以分别用于作业调度和进程调度。
短进程（SPF）调度算法则是从就绪队列中选出一个估计运行时间最短的进程，将处理机分配给它，使它立即执行并一直执行到完成，或发生某事件被阻塞放弃处理机。—非抢占式
短作业优先（SJF）的调度算法是从后备作业队列中选择一个或若干个估计运行时间最短的作业，将它们调入内存运行；
特点：
比FCFS改善平均周转时间和平均带权周转时间，提高系统吞吐量；对长作业不利，没能根据紧迫程度来划分执行的优先级，难以准确估计 作业或进程的执行时间。
以上两种主要用于批处理系统，批处理是指用户将一批作业提交给操作系统后就不再干预，由操作系统控制它们自动运行。
3、优先权调度算法
思想：
当该算法用于进程调度时，将把处理机分配给就绪进程队列中优先级最高的进程投入运行。分为非抢占式优先级算法和抢占式优先级算法。
当该算法用于作业调度时，系统从后备作业队列中选择若干个优先级最高的，且系统能满足资源要求的作业装入内存运行；
优先权类型：
静态优先级：在进程创建时确定进程优先级，在进程整个运行期间保持不变
动态优先级：在创建进程时创立一个优先级，但在其生命周期内优先级可以动态变化，以获得更好的调度性能。
确定优先级的依据：
（1）进程的类型：通常系统进程高于一般用户进程；交互型的用户进程高于批处理作业对应的进程
（2）进程对资源的需求：进程的估计运行时间及内存需求量少的进程，优先级应较高，有利于缩小平均周转时间
（3）根据用户需求：用户根据自己作业的紧迫程度来指定一个合适的优先级
4、时间片轮转调度算法
思想：
系统将就绪进程按到达的顺序排成一个队列，按FCFS原则，进程调度程序总是选择就绪队列中的第一个进程执行，且只运行一个时间片。时间用完后，即使此进程并未完成，仍然将处理机分配给下一个就绪的进程，将此进程返回到就绪队列的末尾，等候重新运行。
主要适用于分时系统。操作系统以时间片为单位，轮流为每个终端用户服务。
时间片的长短通常由以下因素确定：系统的响应时间、就绪队列中的进程数目和系统的处理能力。
5、多级反馈队列调度算法（集合了前几种算法的优点）重点
思想：
设置n个就绪队列，优先级从1到n依次递减，即第1级队列优先级最高
每个队列的时间也不相同，优先级高的队列，时间片越短，即从1到n时间片越来越多
一个新进程进入内存后，先插入第一级队列的末尾，按照FCFS的原则等待调度。如果某个进程可在一个时间片内完成，那么结束此进程；如果某进程在一个时间片内无法完成，就把此进程转入下一级队列的末尾，按照FCFS原则等待调度，一直到第n-1级队列。当一个很长的进程从第1级一直到第n级队列，那么它在第n级队列按照时间片轮转的方式等待调度。
仅当第1级队列为空时，调度程序才调度第2级队列中的进程执行，依次类推。如果处理机正在处理第i级的队列的某进程，又有新的进程进入优先级更高的队列（第1——i -1），则此时新的进程抢占处理机，原本正在执行第i级此进程停止运行，放到第i级就绪队列的末尾，把处理机分配给更高优先级的进程
优势：
短作业优先
短批处理作业周转时间较短
长批处理作业不会长期得不到执行
6、高响应比优先调度算法
思想：
高响应比优先调度算法主要用于作业调度，该算法是对FCFS调度算法和SJF调度算法的一种综合平衡，同时考虑每个作业的等待时间和估计的运行时间。
在每次进行作业调度时，先计算后备作业队列中每个作业的响应比，从中选出响应比最高的作业投入运行。
● 当作业的等待时间相同时，则要求服务时间越短，其响应比越高，有利于短作业。
● 当要求服务时间相同时，作业的响应比由其等待时间决定，等待时间越长，其响应比越高，因而它实现的是先来先服务。
● 对于长作业，作业的响应比可以随等待时间的增加而提高，当其等待时间足够长时，其响应比便可升到很高，从而也可获得处理机。克服了饥饿状态，兼顾了长作业。
6. 进程与线程的区别
进程是资源分配的最小单位，线程是操作系统进行执行和调度的最小单位
1) 同一进程的线程共享本进程的地址空间，而进程之间则是独立的地址空间；
2) 同一进程内的线程共享本进程的资源，但是进程之间的资源是独立的；
3) 一个进程崩溃后，在保护模式下不会对其他进程产生影响，但是一个线程崩溃整个进程崩溃，所以多进程比多线程健壮；
4) 进程切换，消耗的资源大。所以涉及到频繁的切换，使用线程要好于进程；
5) 两者均可并发执行；
6) 每个独立的进程有一个程序的入口、程序出口。但是线程不能独立执行，必须依存在应用程序中，由应用程序提供多个线程执行控制。
7、进程和线程的选择
8、进程状态转换图
就绪→执行：当一个就绪进程获得处理器时，其状态由就绪变为执行；
执行→就绪：当一个运行中的进程被剥夺处理器时，如用完系统分给他的时间片、出现更高优先级别的其他进程，其状态由执行变为就绪；
执行→阻塞：当一个运行进程因某事件发生而无法执行时，如申请资源被占用、启动I/O传输未完成，其状态由执行变为阻塞；
阻塞→就绪：所等待事件发生时，如申请资源、I/O传输完成，其状态由阻塞变为就绪。
9、 进程的创建过程？需要哪些函数？需要哪些数据结构?
1) fork函数创造的子进程是父进程的完整副本，复制了父亲进程的资源，包括内存的内容task_struct内容；
2) vfork创建的子进程与父进程共享数据段，而且由vfork创建的子进程将先于父进程运行；
3) linux上创建线程一般使用的是pthread库，实际上linux也给我们提供了创建线程的系统调用，就是clone；
10、 子进程和父进程怎么通信？
1) 在Linux系统中实现父子进程的通信可以采用pipe()和fork()函数进行实现；
2) 对于父子进程，在程序运行时首先进入的是父进程，其次是子进程，在此我个人认为，在创建父子进程的时候程序是先运行创建的程序，其次在复制父进程创建子进程。fork()函数主要是以父进程为蓝本复制一个进程，其ID号和父进程的ID号不同。对于结果fork出来的子进程的父进程ID号是执行fork()函数的进程的ID号。
3) 管道：是指用于连接一个读进程和一个写进程，以实现它们之间通信的共享文件，又称pipe文件。
4) 写进程在管道的尾端写入数据，读进程在管道的首端读出数据。
11、进程和作业的区别？
1) 进程是程序的一次动态执行，属于动态概念；
2) 一个进程可以执行一个或几个程序，同一个程序可由几个进程执行；
3) 程序可以作为一种软件资源长期保留，而进程是程序的一次执行；
4) 进程具有并发性，能与其他进程并发执行；
5) 进程是一个独立的运行单位；
12、 死锁是什么？必要条件？如何解决？
所谓死锁，是指多个进程循环等待它方占有的资源而无限期地僵持下去的局面。很显然，如果没有外力的作用，那麽死锁涉及到的各个进程都将永远处于封锁状态。当两个或两个以上的进程同时对多个互斥资源提出使用要求时，有可能导致死锁。
产生死锁的4个必要条件：
互斥条件：系统存在临界资源，存在一个资源每次只能被一个进程使用，若别的进程也要使用该资源，需要等待知道其占用者用完释放。 这是锁的固有属性
保持与等待条件：部分分配，允许进程在不释放其已经分得的资源的情况下请求并等待分配别的资源
不可抢占条件：有些系统资源是不可抢占的，系即当某个进程已经获得这种资源后，系统是不能强行收回，其他进程也不能强行夺走，只能由自身使用完释放。
循环等待条件：若干个进程形成环形链，链中的每一个进程都在等待该链中下一个进程所占用的资源。
死锁的预防需要至少破坏死锁的4个必要条件之一，而死锁的避免不去刻意破坏4个必要条件，而是通过对资源的分配策略施加较少的限制条件，来避免死锁的产生。
死锁预防方法：
1、允许进程强行从占有者那里夺取某些资源，破坏不可抢占条件，
2、进程在运行前一次性地向系统申请它所需要的全部资源。，破坏了保持与等待条件 3、把资源事先分类编号，按号分配，使进程在申请，占用资源时不会形成环路，破坏了循环等待条件
死锁避免：银行家算法
13、 处理死锁的基本方法
*死锁预防：通过设置某些限制条件，去破坏死锁的四个条件中的一个或几个条件，来预防发生死锁。但由于所施加的限制条件往往太严格，因而导致系统资源利用率和系统吞吐量降低。严重损害系统性能。因而在避免死锁时，要施加较弱的限制，从而获得较满意的性能。
*死锁避免：允许前三个必要条件，但通过明智的选择，确保永远不会到达死锁点，因此死锁避免比死锁预防允许更多的并发。允许进程动态的申请资源。所以在进行分配资源时预先计算资源分配的安全性。若此次分配不会导致系统进入不安全状态，将资源分配给进程。否则，进程等待。经典算法是银行家算法
*死锁检测：不须实现采取任何限制性措施，而是允许系统在运行过程发生死锁，但可通过系统设置的检测机构及时检测出死锁的发生，并精确地确定于死锁相关的进程和资源，然后采取适当的措施，从系统中将已发生的死锁清除掉。
*死锁解除：与死锁检测相配套的一种措施。当检测到系统中已发生死锁，需将进程从死锁状态中解脱出来。常用方法：撤销或挂起一些进程，以便回收一些资源，再将这些资源分配给已处于阻塞状态的进程。死锁检测盒解除有可能使系统获得较好的资源利用率和吞吐量，但在实现上难度也最大。
死锁解除方法：
1、利用抢占恢复。
在某些情况下，可能会临时将某个资源从它的当前所有者那里转移到另一个进程中。这种做法很可能需要人工干预，主要做法是否可行需取决于资源本身的特性。
2、利用滚回恢复
他们就可以周期性的对进程进行检查点检查。
进程的检查点检查就是讲进程的状态希尔一个文件以备以后重启。实际上是将该进程复位到一个更早的状态。那时它还没有取得所需的资源，接着就把这个资源分配给其他死锁进程。3、通过杀死进程恢复
最直接简单的方式就是杀死一个或若干个进程。
一种方法是杀掉环中的一个进程。如果不行的话就继续杀死别的进程。
有时候选择一个环外的进程也是可行的。
尽可能报证杀死的进程可以从头再来而不带来副作用。另一方面更新数据库的进程第二次运行时并非总是安全的。这是需要注意的。
14、鸵鸟策略
假设的前提是，这样的问题出现的概率很低。比如，在操作系统中，为应对死锁问题，可以采用这样的一种办法。当系统发生死锁时不会对用户造成多大影响，或系统很少发生死锁的场合采用允许死锁发生的鸵鸟算法，这样一来可能开销比不允许发生死锁及检测和解除死锁的小。如果死锁很长时间才发生一次，而系统每周都会因硬件故障、编译器错误或操作系统错误而崩溃一次，那么大多数工程师不会以性能损失或者易用性损失的代价来设计较为复杂的死锁解决策略，来消除死锁。鸵鸟策略的实质：出现死锁的概率很小，并且出现之后处理死锁会花费很大的代价，还不如不做处理，OS中这种置之不理的策略称之为鸵鸟策略（也叫鸵鸟算法）。
15、银行家算法
银行家算法的基本思想是分配资源之前，判断系统是否是安全的；若是，才分配。它是最具有代表性的避免死锁的算法。
算法内容：
每一个线程进入系统时，它必须声明在运行过程中，所需的每种资源类型最大数目，其数目不应超过系统所拥有每种资源总量，当线程请求一组资源系统必须确定有足够资源分配给该进程，若有在进一步计算这些资源分配给进程后，是否会使系统处于不安全状态，不会（即若能在分配资源时找到一个安全序列），则将资源分配给它，否则等待
设进程cusneed提出请求REQUEST [i]，则银行家算法按如下规则进行判断。
(1)如果REQUEST [cusneed] [i]<= NEED[cusneed][i]，则转（2)；否则，出错。
(2)如果REQUEST [cusneed] [i]<= AVAILABLE[i]，则转（3)；否则，等待。
(3)系统试探分配资源，修改相关数据：
AVAILABLE[i]-=REQUEST[cusneed][i];
ALLOCATION[cusneed][i]+=REQUEST[cusneed][i];
NEED[cusneed][i]-=REQUEST[cusneed][i];
(4)系统执行安全性检查，如安全，则分配成立；否则试探险性分配作废，系统恢复原状，进程等待。
16、IPC进程间通信方式有几种，他们之间的区别是什么？
1) 管道
管道，通常指无名管道。只能进行单向数据流的通信，一方使用一个端口，另一端使用另一个端口。要进行双向通信，需要建立两个管道。
① 半双工的，具有固定的读端和写端；
② 只能用于具有亲属关系的进程之间的通信；
③ 可以看成是一种特殊的文件，对于它的读写也可以使用普通的read、write函数。但是它不是普通的文件，并不属于其他任何文件系统，只能用于内存中。
④ Int pipe(int fd[2]);当一个管道建立时，会创建两个文件描述符，要关闭管道只需将这两个文件描述符关闭即可。
2) FiFO（有名管道）
① FIFO可以在无关的进程之间交换数据，与无名管道不同；
② FIFO有路径名与之相关联，它以一种特殊设备文件形式存在于文件系统中；
③ Int mkfifo(const char* pathname,mode_t mode);
下面三种是IPC通信方式。内核为每一个IPC对象维护一个数据结构
3) 消息队列
① 消息队列，是消息的连接表，存放在内核中。一个消息队列由一个标识符来标识；
② 系统V消息队列是随内核持续的，只有在内核重起或者显示删除一个消息队列时，该消息队列才会真正被删除。因此系统中记录消息队列的数据结构（struct ipc_ids msg_ids）位于内核中，系统中的所有消息队列都可以在结构msg_ids中找到访问入口。
③ 具有写权限的进程按照一定的规则向消息队列添加新信息，对消息队列有读权限的进程可以从消息队列读取信息。
④ 消息队列是面向记录的，其中的消息具有特定的格式以及特定的优先级；
⑤ 消息队列独立于发送与接收进程。进程终止时，消息队列及其内容并不会被删除；
⑥ 消息队列可以实现消息的随机查询
4) 信号量
信号量主要执行两个操作;假设信号量为SV，
P(SV)进入临界区，如果SV值大于0，则减1，如果SV为0，则挂起进程
V(SV)离开临界区，如果有其他进程因等待SV而挂起，则唤醒之，如果没有，则SV加1。
信号量的使用；
#include <sys/sem.h>
int semget(key_t key,int num_sems,int sem_flags);创建一个新的信号量集，或者获取一个已经存在的信号量。返回值为信号量标识符，失败返回-1设置errno
Int semop(int sem_id,struct sembuf* sem_ops,size_t num_sem_ops);改变信号量的值，即执行P、V操作
Int semctl(int sem_id,int sem_num,int command，…)允许调用者对信号量直接控制。
信号量是一个计数器，信号量用于实现进程间的互斥与同步，而不是用于存储进程间通信数据；
信号量用于进程间同步，若要在进程间传递数据需要结合共享内存；
信号量基于操作系统的PV操作，程序对信号量的操作都是原子操作；
5) 共享内存
① 共享内存，指两个或多个进程共享一个给定的存储区；
② 共享内存是最快的一种进程通信方式，因为进程是直接对内存进行存取；
③ 因为多个进程可以同时操作，所以需要进行同步；
④ 信号量+共享内存通常结合在一起使用。
17、共享内存需要2次拷贝，管道或消息队列需要4次拷贝
共享内存是最快的IPC形式。一旦这样的内存映射到共享他的进程的地址空间，这些进程间的数据传递不在涉及到内核，换句话说进程不再通过执行进入内核的系统调用后来传递彼此的数据。只需要内存访问函数。
1.服务器从输入文件读，该文件的数据由内核读入自己的内存空间
2.服务器往一个管道、FIFO或消息队列以一条消息的形式写入这些数据。这些IPC形式的通常需要把这些数据从进程复制到内核
3.客户从该IPC通道读出这些数据，这通常要把这些数据从内核复制到进程
4最后，将这些数据从由write函数的第二个参数指定的客户缓冲区复制到输出文件。
共享内存区是内存的一块特殊区域，可以让他同时映射到服务器和客户端的进程空间。
从共享内存区读取数据是只需要内存访问函数来进行，不涉及内核空间拷贝到用户空间。
内存访问函数
将文件或设备空间映射到共享内存区
Void *mmap(void *addr,size_t len,int prot,int flags,int fd,off_t offest) 成功返回映射到内存区的起始地址
Mmap分配内存空间是以页为单位
取消mmap函数建立的映射
Int munmap(void *addr,size_t len) //addr,映射内存的起始地址，len映射到进程空间的字节数。
返回值，成功返回0
18、共享内存的实现
在Linux中，每个进程都有属于自己的进程控制块（PCB）和地址空间（Addr Space），并且都有一个与之对应的页表，负责将进程的虚拟地址与物理地址进行映射，通过内存管理单元（MMU）进行管理。两个不同的虚拟地址通过页表映射到物理空间的同一区域，它们所指向的这块区域即共享内存。
共享内存的通信原理示意图：
对于上图我的理解是：当两个进程通过页表将各自的虚拟地址映射到同一块物理地址，即共享内存，这块内存可以被两个进程同时看到。这样当一个进程进行写操作，另一个进程读操作就可以实现进程间通信。但是，我们要确保一个进程在写的时候不能被读，因此我们使用信号量来实现同步与互斥。
对于一个共享内存，实现采用的是引用计数的原理，当进程脱离共享存储区后，计数器减一，挂架成功时，计数器加一，只有当计数器变为零时，才能被删除。当进程终止时，它所附加的共享存储区都会自动脱离。
1) 两个不同进程A、B共享内存的意思是，同一块物理内存被映射到进程A、B各自的进程地址空间。进程A可以即时看到进程B对共享内存中数据的更新，反之亦然。由于多个进程共享同一块内存区域，必然需要某种同步机制，互斥锁和信号量都可以。
2) 共享内存是通过把同一块内存分别映射到不同的进程空间中实现进程间通信。而共享内存本身不带任何互斥与同步机制，但当多个进程同时对同一内存进行读写操作时会破坏该内存的内容，所以，在实际中，同步与互斥机制需要用户来完成。
3) （1）共享内存就是允许两个不想关的进程访问同一个内存
（2）共享内存是两个正在运行的进程之间共享和传递数据的最有效的方式
（3）不同进程之间共享的内存通常安排为同一段物理内存
（4）共享内存不提供任何互斥和同步机制，一般用信号量对临界资源进行保护。
（5）接口简单
19、信号量
由迪杰斯特拉提出。
如果p/v在同一个进程，解决互斥问题。
如果p/v在不同进程，解决同步问题
信号量值的含义：
S>0 S表示可用资源的个数
S=0 表示无可用资源，无等待进程
S<0 |S| 表示等待队列中进程个数
信号量结构示意：
Struct sem{
Int value;//表示信号量值
Point queue;//表示等待队列
};
P、V伪代码
当一个进程需要申请资源时，需要执行P操作
P（S）//原子性操作
{
S.value--;//先将信号量计数值减一
If(S.value<0)//代表先前已经没有资源可用
{
该进程状态置为等待状态
将该进程PCB插入相应等待队列S.queue的末尾。
}
}
进程使用完资源归还时，执行V操作
V（S） //原子操作
{
S.value++;//如果先前value小于0，代表queue中有等待进程
If(S.value<=0)
{
唤醒相应等待队列queue中的一个进程
改变其状态为就绪态
插入就绪队列
}
}
20、消息队列
消息队列提供了一个进程向另一个进程传递二进制数据块的方法。
每个数据块都被认为是有一个类型，接受者进程接受的数据块可以有不同的类型值。接受程序可以根据消息类型有选择的接收数据。每条数据都有一个最大长度限制。
消息队列也有管道一样的不足，就是每个消息的最大长度是有上限的（MSGMAX=16384）。每个消息队列总的字节数是由上限的（MSGMNB）。系统可以创建消息队列的总数也有一个上限（MSGMNI）
可以通过： cat /proc/sys/kernel/msgmax来查看不同值
消息队列里存放数据的形式以链表进行。链表每个节点可以拥有不同类型不同大小的数据。
查看消息队列用 ipcs
删除消息队列用ipcrm -q msqid
消息结构体
Struct Msg{
Long type; //用来标识每一条消息
Chat text[512]; //传递消息的内容
};
21、IPC的函数原型及用法
消息队列：
1、__创建消息队列或打开已有消息队列
Int msgget(key_t key,int msgflag); 返回msgid
Key用来标识一个消息队列，如果创建消息队列msgflag设置为0666|IPC_CREAT
可以给key传递一个IPC_PRIVATE参数，这样无论这个信号量是否存在，semget都将创建一个新的信号量。
2、__设置消息队列属性（查看数据，删除消息队列）
Int msgctl(int msgid,int cmd,struct msqid_ds *buf);
Cmd有以下三种，
IPC_PMID 删除消息队列
IPC_STAT 获取消息队列的状态
IPC_SET 设置消息队列
3、__向消息队列读写数据
把一条消息加入消息队列
Int msgsnd(int msgid, const void *msgp,size_t msgsz,int msgflag);
Msgp指向我们要发送的消息结构，转为void*类型
Struct Msg{
Long type; //用来标识每一条消息
Chat text[sz]; //传递消息的内容
};
Msgsz一般设置为text的大小
从消息队列中接收消息
Int msgrcv(int msgid,void *msgp,size_t msgsz,long msgtype,int msgflag);
共享内存
1、创建共享内存
Int shmget（key_t key，size_t size,int shmflag）;
Key 共享内存段名字
Size 共享内存大小
函数返回shmid,共享内存标识码。
2、将共享内存段连接到自身进程地址空间
Void* shmat(int shmid,const void* shmaddr,int shmflag);//
Eg： char *buf=shmat(shmid,NULL,0);
Shmaddr指定连接的地址。一般设置为NULL，内核自动选择一个地址
Shmaddr不为空且shmflag设置了SHM_RND标记，则连接地址会自动向下调整为SHMLBA的整数倍
3、将共享内存段与当前进程脱离
Int shmdt(sonst void *shmaddr);
4、用来访问或删除一个消息队列
Int shmctl(int shmid,int cmd,struct shmid_ds *buf)
Buf保存着共享内存的模式状态和访问权限的数据结构。
Shmctl(shmid，IPC_RMID,NULL);这个cmd可以使用消息队列的cmd
信号量
1、用来创建和访问一个信号量
Int semget(key_t key，int nsems,int semflag);
Key是信号集的名字，nsems是信号集中信号量的个数。成功返回一个信号标识码semid
2、用于控制信号量集
Int semctl(int semid,int semnum,int cmd)
Cmd有SETVAl 设置信号集中信号量的计数值。
GETVAL 获取信号量集合中信号量的计数值
也包含消息队列三种cmd
3、用来创建和访问一个信号量集
Int semop（int semid,struct sembuf *sops,unsigned nsops）
Sops 对信号量集合中多个信号量进行操作
Nsops 信号量的个数
22、线程同步的方式？怎么用？
1) 线程同步是指多线程通过特定的设置来控制线程之间的执行顺序，也可以说在线程之间通过同步建立起执行顺序的关系；
2) 主要四种方式，临界区、互斥对象、信号量、事件对象；其中临界区和互斥对象主要用于互斥控制，信号量和事件对象主要用于同步控制；
3) 临界区：通过对多线程的串行化来访问公共资源或一段代码，速度快、适合控制数据访问。在任意一个时刻只允许一个线程对共享资源进行访问，如果有多个线程试图访问公共资源，那么在有一个线程进入后，其他试图访问公共资源的线程将被挂起，并一直等到进入临界区的线程离开，临界区在被释放后，其他线程才可以抢占。
4) 互斥对象：互斥对象和临界区很像，采用互斥对象机制，只有拥有互斥对象的线程才有访问公共资源的权限。因为互斥对象只有一个，所以能保证公共资源不会同时被多个线程同时访问。当前拥有互斥对象的线程处理完任务后必须将线程交出，以便其他线程访问该资源。
5) 信号量：它允许多个线程在同一时刻访问同一资源，但是需要限制在同一时刻访问此资源的最大线程数目。在用CreateSemaphore()创建信号量时即要同时指出允许的最大资源计数和当前可用资源计数。一般是将当前可用资源计数设置为最 大资源计数，每增加一个线程对共享资源的访问，当前可用资源计数就会减1 ，只要当前可用资源计数是大于0 的，就可以发出信号量信号。但是当前可用计数减小 到0 时则说明当前占用资源的线程数已经达到了所允许的最大数目，不能在允许其他线程的进入，此时的信号量信号将无法发出。线程在处理完共享资源后，应在离 开的同时通过ReleaseSemaphore （）函数将当前可用资源计数加1 。在任何时候当前可用资源计数决不可能大于最大资源计数。
6) 事件对象：通过通知操作的方式来保持线程的同步，还可以方便实现对多个线程的优先级比较的操作。
23、页和段的区别？
1) 页是信息的物理单位，分页是由于系统管理的需要。段是信息的逻辑单位，分段是为了满足用户的要求。其中0~11位为页内地址，即每页的大小为4KB;
2) 页的大小固定且由系统决定，段的长度不固定，决定于用户所编写的程序，通常由编译程序在对源程序紧进行编译时，根据信息的性质来划分。
3) 分页的作业的地址空间是一维的，程序员只需要利用一个记忆符，即可表示一个地址。
4) 分段的作业地址空间则是二维的，程序员在标识一个地址时，既需要给出段名，又需要给出段的地址值。
24、线程和进程的区别？线程共享的资源是什么？
1) 一个程序至少有一个进程，一个进程至少有一个线程
2) 线程的划分尺度小于进程，使得多线程程序的并发性高
3) 进程在执行过程中拥有独立的内存单元，而多个线程共享内存，从而极大地提高了程序的运行效率
4) 每个独立的线程有一个程序运行的入口、顺序执行序列和程序的出口。但是线程不能够独立执行，必须依存在应用程序中，由应用程序提供多个线程执行控制
5) 多线程的意义在于一个应用程序中，有多个执行部分可以同时执行。但操作系统并没有将多个线程看做多个独立的应用，来实现进程的调度和管理以及资源分配
6) 一个进程中的所有线程共享该进程的地址空间，但它们有各自独立的（/私有的）栈(stack)，Windows线程的缺省堆栈大小为1M。堆(heap)的分配与栈有所不同，一般是一个进程有一个C运行时堆，这个堆为本进程中所有线程共享，windows进程还有所谓进程默认堆，用户也可以创建自己的堆。
线程私有：线程栈，寄存器，程序寄存器
共享：堆，地址空间，全局变量，静态变量
进程私有：地址空间，堆，全局变量，栈，寄存器
共享：代码段，公共数据，进程目录，进程ID
25、线程进程的区别体现在几个方面
1.因为进程拥有独立的堆栈空间和数据段，所以每当启动一个新的进程必须分配给它独立的地址空间，建立众多的数据表来维护它的代码段、堆栈段和数据段，系统开销比较大，而线程不一样，线程拥有独立的堆栈空间，但是共享数据段，它们彼此之间使用相同的地址空间，共享大部分数据，切换速度也比进程快，效率高，但是正由于进程之间独立的特点，使得进程安全性比较高，也因为进程有独立的地址空间，一个进程崩溃后，在保护模式下不会对其它进程产生影响，而线程只是一个进程中的不同执行路径。一个线程死掉就等于整个进程死掉。
2.体现在通信机制上面，正因为进程之间互不干扰，相互独立，进程的通信机制相对很复杂，譬如管道，信号，消息队列，共享内存，套接字等通信机制，而线程由于共享数据段所以通信机制很方便。。
3.属于同一个进程的所有线程共享该进程的所有资源，包括文件描述符。而不同过的进程相互独立。
4.线程必定也只能属于一个进程，而进程可以拥有多个线程而且至少拥有一个线程；
26、进程与线程的选择取决以下几点
1、需要频繁创建销毁的优先使用线程；因为对进程来说创建和销毁一个进程代价是很大的。
2、线程的切换速度快，所以在需要大量计算，切换频繁时用线程，还有耗时的操作使用线程可提高应用程序的响应
3、因为对CPU系统的效率使用上线程更占优，所以可能要发展到多机分布的用进程，多核分布用线程；
4、并行操作时使用线程，如C/S架构的服务器端并发线程响应用户的请求；
5、需要更稳定安全时，适合选择进程；需要速度时，选择线程更好。
27、页面置换算法（LRU算法）
LRU算法：最近最少使用，简单来说就是将数据块中，每次使用过的数据放在数据块的最前端，然后将存在的时间最长的，也就是数据块的末端的数据剔除掉这就是LRU算法
LRU是一种页面置换算法，在对于内存中但是又不用的数据块，叫做LRU，操作系统会根据那些数据属于LRU而将其移出内存而腾出空间来加载另外的数据
如果进程被调度，该进程需要使用的外存页（数据）不存在于内存数据块中，这个现象就叫做缺页。如果这个数据此时不在，就会将这个数据从加入到数据块首部
数据块插入与剔除：每次有新数据到来时，会将其放入数据块首部，当数据每次被访问时，将这个数据插入数据块的首部如果数据块满了，每次新进的数据都会将数据块尾部的数据挤出数据块
1) 用一个数组来存储数据，给每一个数据项标记一个访问时间戳，每次插入新数据项的时候，先把数组中存在的数据的时间戳自增，并将新数据时间戳置为0插入到数组中。每次访问数组中的数据项的时候，将被访问的数据项时间戳置为0。当数组空间已经满时，将时间戳最大的数据项淘汰；
2) 利用一个链表来实现，每次新插入数据的时候将新数据插入到链表头部；每次缓存命中，则将数据移动到链表头部；那么当链表满时，就将链表尾部的数据丢弃；
3) 利用链表和hashmap。当需要插入新的数据项 的时候，如果新数据命中，则把该节点放到链表头部，如果不存在，则将新数据放在链表头部。若缓存满了，则将链表尾部的节点删除。
28、Linux常用命令
1) ls命令，不仅可以查看linux文件包含的文件，而且可以查看文件权限；
2) cd命令，切换当前目录到dirName
3) pwd命令，查看当前工作目录路径；
4) mkdir命令，创建文件夹
5) rm命令，删除一个目录中的一个或多个文件或目录
6) rmdir命令，从一个目录中删除一个或多个子目录项，
7) mv命令，移动文件或修改文件名
8) cp命令，将源文件复制至目标文件，或将多个源文件复制至目标目录
9) cat命令，显示文件内容；
