基础知识_操作系统

操作系统基础知识与常见题目。

进程与线程的区别

  • 进程是系统进行资源调度和分配的独立单位;而线程是CPU调度和分配的基本单位。
  • 进程间相互独立,享有独立的资源;一个进程内的多个线程可以共享资源,但对于其他进程内的线程是不可见的。
  • 进程间可以通过管道、FIFO、消息队列、信号量、共享内存、信号、套接字等IPC机制来通信;线程间可以直接访问全局变量等共享的内存,但需要一定的同步和互斥手段。
  • 切换线程的开销要比切换进程的开销小很多。
  • 一个进程中可以有多个线程。
  • 进程与线程的关系可以看成下面这样:
    1
    2
    3
    o |======
    |======
    |------

一个进程可以创建多少线程,和什么有关?

  • 通过ulimit -a 查看线程的栈大小,然后用户空间的内存除以栈大小是可创建线程的最大数量。

守护进程、孤儿进程与僵尸进程

  • 守护进程:守护进程就是在后台运行,不与任何终端关联的进程,通常情况下守护进程在系统启动时就在运行,它们以root用户或其他特殊用户运行,并能处理一些系统级的任务。
  • 孤儿进程:父进程退出,而它的一个或多个子进程还在运行,那么那些子进程将成为孤儿进程。孤儿进程将被父进程(一般是进程号为1的init进程所收养,并由父进程对它们完成状态收集工作。
  • 僵尸进程:一个进程使用fork创建子进程,如果子进程退出,而父进程并没有调用wait或waitpid获取子进程的状态信息,那么子进程的进程描述符仍然保存在系统中并占用系统资源,这种进程称之为僵尸进程。

进程终止的五种方式

  • 正常退出
  • 从main函数返回
  • 调用exit
  • 调用_exit
  • 异常退出
  • 调用abort 产生SIGABOUT信号
  • 由信号终止 ctrl+c SIGINT

五种IO模型

  • 阻塞IO、非阻塞IO、IO复用、信号驱动IO、异步IO

页面置换算法

  • 最佳置换算法(opt),这是一个无法实现的理论上最优的算法,因为每次缺页时需要判断哪个页面在之后最长时间内都不会被访问。
    假如按照如下顺序访问内存页:7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1。

    1
    2
    3
    4
    5
    6
    7
    访问页面	7	0	1	2	0	3	0	4	2	3	0	3	2	1	2	0	1	7	0	1
    物理块1 7 7 7 2 2 2 2 2 7
    物理块2 0 0 0 0 4 0 0 0
    物理块3 1 1 3 3 3 1 1
    缺页否 √ √ √ √ √ √ √ √ √

    缺页9次,置换6次。
  • 先进先出置换算法(FIFO),这也是最简单的页面置换算法,基本思想是:当需要淘汰一个页面时,总是选择驻留时间最长的页面进行淘汰,即按照先入先出的规则来淘汰。

    1
    2
    3
    4
    5
    6
    7
    访问页面	7	0	1	2	0	3	0	4	2	3	0	3	2	1	2	0	1	7	0	1
    物理块1 7 7 7 2 2 2 4 4 4 0 0 0 7 7 7
    物理块2 0 0 0 3 3 3 2 2 2 1 1 1 0 0
    物理块3 1 1 1 0 0 0 3 3 3 2 2 2 1
    缺页否 √ √ √ √ √ √ √ √ √ √ √ √ √ √ √

    缺页15次,置换12次
  • 最近最久未使用算法(LRU)

    1
    2
    3
    4
    5
    6
    7
    访问页面	7	0	1	2	0	3	0	4	2	3	0	3	2	1	2	0	1	7	0	1
    物理块1 7 7 7 2 2 4 4 4 0 1 1 1
    物理块2 0 0 0 0 0 0 3 3 3 0 0
    物理块3 1 1 3 3 2 2 2 2 2 7
    缺页否 √ √ √ √ √ √ √ √ √ √ √ √

    缺页12次,置换9次

死锁产生的四个条件

  • 互斥:某种资源一次只允许一个实体访问。
  • 占有且等待:一个进程或线程本身占有了一定资源,同时还有资源未得到满足,正在等待其他进程释放资源。
  • 不可抢占:别人已经占用了资源,你无法因为自己需要就将资源抢过来。
  • 循环等待:发生死锁时,有一个这样的进程链:p1在等待p2占用的资源,p2在等待p3占用的…pn在等待p1占用的资源。

处理死锁的四个方法

  • 预防死锁
    破坏产生死锁的一个或几个条件。

  • 避免死锁
    银行家算法

  • 死锁的检测
    死锁定理:当某状态的资源分配图是不可完全简化的,说明发生了死锁。

  • 死锁的解除
    1.抢占资源
    2.终止进程

银行家算法

三个经典的同步问题

生产者消费者问题

1.用记录型信号量解决

  • 由于生产者消费者可能会同时访问缓冲池,所以需要一个mutex信号量来实现对缓冲池的互斥访问。
  • 为了实现同步,可以设置empty,full两个信号量,分别表示空缓冲池和满缓冲池的数量。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    int in=0,out=0;
    item buffer[n];
    semaphore mutex=1,empty=n,full=0;

    void producer(){
    do{
    producer an item nextp;
    ...
    wait(empty); //使empty减1;
    wait(mutex); //同步互斥一块出现时同步在前。
    buffer[in]=nextp;
    in=(in+1)%n;
    signal(mutex); //mutex+1;
    signal(full);
    }while(true)
    }

    void consumer(){
    do{
    wait(full);
    wait(mutex);
    nextc=buffer[out];
    out=(out+1)%n;
    signal(mutex);
    signal(empty);
    consummer the item in mutex;
    ...
    }while(true);
    }

    //注意每个程序中的wait不能颠倒,否则可能引起进程死锁。
哲学家进餐问题
读者写者问题

欢迎与我分享你的看法。
转载请注明出处:http://taowusheng.cn/