（不定期更新）OS笔记

发表于 更新于 分类于 本文字数： 2.9k 阅读时长 ≈ 3 分钟

只提供理论部分，供期末复习用。

Computer System Overview

偏计组，考试不考。

  • Fetch-Execute.
  • Interruption: program flow chart, ISR (Interrupt Handler) level.

Operating System Overview

OS: a program that controls the execution of application programs, and acts as an interface between applications and the computer hardware.

Interrupts: Early computer models did not have this capability. This featuregives the OS more flexibility in relinquishing control to, and regaining control from, user programs.

Process Description and Control

process

交替执行(interleave)、策略(stategy)、死锁(deadlock).

definition:

  • 一个正在执行(running, executing)的程序。
  • 一个正在计算机上执行的程序实例
  • 能分配给处理器并由处理器执行的实体
  • 由一组执行的指令、一个当前状态和一组相关的系统资源表征的活动单元。

component:

  • ID
  • State

Threads

Thread: lightweighted process.

Linux has no kernel threads while Windows does, the advantanges of no threads are lightweighted and easy to manage.

Concurrency

terminology

  • atomic operation
  • critical section
  • deadlock
  • livelock
  • mutual exclusion
  • race condition
  • starvation

单道程序的特点：

  • 封闭性
  • 连续性
  • 可再现性

多道程序的特点：

  • 失去封闭性
  • 间断性
  • 不可再现性

algorithm

dekker

  • 存在活锁。
  • 规定了进程执行的顺序，不灵活。
  • 程序实现复杂，难以验证。

peterson

hardware disabling

disadvantage:

  • Processor is limited in its ability to interleave programs.
  • disabling interrupts on one processor will not guarantee mutual exclusion in multi-processors environment。

special instruction

优点：进程数目不限、简单易证、支持多临界区。

缺点：忙时等待、饥饿、死锁。

Semaphores

terminology

  • 二元信号量
  • 计数信号量
  • 互斥量
  • 强信号量
  • 弱信号量

operation

  • semwait: 申请一个资源/等待一个条件
  • semsignal: 释放一个资源/产生一个条件
  • 如果前两者在一个进程出现，称为互斥；如果不在一个进程出现，称为同步
  • 对于semwait，先处理同步，再处理互斥

step

  • determine the number of processes
  • analysis of the nature of the problem
  • define the semaphore and initialize the value of the semaphore
  • calling semwait and semsignal in the process
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Semaphore(a,b,c)
{
  a = 1;
  b = 2;
  c = 3;
}

void p_1...p_n()
{
  // do sth
}

void main()
{
  Parbegin(p(1),p(2), p3(3), ... p(n));
}

problems

生产者消费者问题：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void producer() {
  while (1) {
    produce();
    semwait(empty);
    semwait(mutex);
    // put item in store
    semsignal(mutex);
    semsignal(product);
  }
}
void consumer() {
  while(1) {
    semwait(product);
    semwait(mutex);
    // take item from store
    semsignal(mutex);
    semsignal(empty);
    use();
  }
}

读者写者问题：

rw，ww之间互斥 rr之间互斥（条件竞争）

读者优先：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int counter = 0；

void reader() {
  int m;
  semwait(mutex2);
  counter++;
  m = counter; // because counter maybe updated
  semsignal(mutex2);
  if (m == 1) semwait(mutex1); // the first to read, compete with write
  read();
  semwait(mutex2);
  counter--;
  m = counter;
  semsignal(mutex2);
  if (m == 0) semsignal(mutex1);
}

void writer() {
  semwait(mutex1);
  write();
  semsignal(mutex1);
}

读写平等：

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
Semphore mutex =1; //文件互斥量
Semphore readmutex=1; //读进程计数互斥量
Semphore queue=1; //读进程与写进程排队互斥量

int readcount=0;

void reader()
{
  int m=0;
  semwait(queue);
  semwait(readmutex);
  readcount+=1;
  m= readcount;
  semsignal(readmutex);
  if (m==1) semwait(mutex)
  semsignal(queue)
  read();
  semwait(readmutex)
  readcount-=1;
  m = readcount;
  semsigal(readmutex)
  if (m==0) semsignal(mutex)
}
Void writer()
{
  semwait(queue);
  semwait(mutex);
  write();
  semsignal(mutex);
  semsignal(queue);
}