資源分配和獨立運行的基本單位

前趨圖
Pi->Pj 直接前趨，直接后繼
初始結(jié)點徘跪，終止結(jié)點
結(jié)點的重量->執(zhí)行時間

程序順序執(zhí)行的特征
順序性模软，封閉性雁仲，可再現(xiàn)性

程序的并發(fā)執(zhí)行
只有不存在前趨關(guān)系的程序之間才有可能并發(fā)執(zhí)行
特征：
間斷性，失去封閉性匙铡，不可再現(xiàn)性（運行環(huán)境會受到其它程序的影響）

進程
程序段图甜，相關(guān)數(shù)據(jù)段，PCB->進程實體->簡稱進程
PCB是進程存在的唯一標(biāo)志鳖眼。
但實際上進程是進程實體的運行過程（動態(tài)的概念），系統(tǒng)進行資源分配和調(diào)度的一個獨立單位嚼摩。
特征：
動態(tài)性钦讳，并發(fā)性，獨立性枕面，異步性

進程的狀態(tài)
就緒態(tài)愿卒，就緒隊列
執(zhí)行態(tài)
阻塞態(tài)，正在執(zhí)行的進程由于發(fā)生某事件（I/O阻塞潮秘，申請緩沖區(qū)失敗等）琼开，根據(jù)阻塞原因不同會設(shè)置多個阻塞隊列。
創(chuàng)建態(tài)枕荞，申請空白PCB->填寫用于控制和管理進程的信息->分配運行時所必須的資源->轉(zhuǎn)入就緒狀態(tài)并插入就緒隊列
若資源尚未滿足就還是處于就緒態(tài)
終止態(tài)柜候，等待操作系統(tǒng)的善后處理（在操作系統(tǒng)中保留一個記錄，用于保存狀態(tài)碼和計時統(tǒng)計數(shù)據(jù)躏精，供其它進程收集渣刷，其它進程完成信息提取后，操作系統(tǒng)就刪除該進程）->將PCB清零矗烛，并將PCB空間返回系統(tǒng)
pic

用原語實現(xiàn)進程控制辅柴。
原語采用關(guān)中斷和開中斷指令來執(zhí)行。

掛起瞭吃，激活
靜止?fàn)顟B(tài)
引起掛起狀態(tài)的原因（掛起傾向于主動（不想讓它執(zhí)行）碌嘀，阻塞傾向與被動（它沒法執(zhí)行））：
終端用戶的需要，父進程請求歪架，負(fù)荷調(diào)節(jié)的需要股冗，操作系統(tǒng)的需要
pic

PCB的作用
1.作為獨立運行基本單位的標(biāo)志
2.能實現(xiàn)間斷性運行方式（CPU現(xiàn)場信息）
3.提供進程管理所需的信息（找到響應(yīng)的程序和數(shù)據(jù)）
4.提供進程調(diào)度所需的信息（處于何種狀態(tài)）
5.實現(xiàn)與其它進程的同步與通信

PCB中的信息
1.進程標(biāo)識符
外部標(biāo)識符（方便用戶（進程）對進程的訪問），內(nèi)部標(biāo)識符（方便系統(tǒng)對進程的使用牡拇，序號）魁瞪，
2.處理機狀態(tài)
也稱為處理機的上下文，主要由處理機的各種寄存器中的內(nèi)容組成
通用寄存器（用戶可視寄存器）惠呼，指令計數(shù)器导俘，程序狀態(tài)字，用戶棧指針
3.進程調(diào)度信息
進程狀態(tài)剔蹋，進程優(yōu)先級旅薄，進程調(diào)度所需的其它信息（與調(diào)度算法有關(guān)，如進程已執(zhí)行的時間），事件（阻塞原因)
4.進程控制信息
程序和數(shù)據(jù)的地址少梁，進程同步和通信的機制（消息隊列指針洛口，信號量等），資源清單凯沪，鏈接指針（下一個進程的PCB的首地址）

PCB的組織方式
線性方式
鏈接方式
（執(zhí)行指針第焰，就緒隊列指針，阻塞隊列指針妨马，空閑隊列指令）
索引方式
（執(zhí)行指針挺举，就緒表指針->就緒索引表，阻塞表指針）

進程的創(chuàng)建
父進程烘跺，子進程湘纵，進程家族
子進程可以繼承父進程所擁有的資源
子進程被撤銷時要歸還資源
父進程撤銷時其子進程也全部撤銷
PCB中設(shè)置了家族關(guān)系表項
（Windows中不存在這樣的層次關(guān)系，而是用句柄來指示進程間的控制關(guān)系）

引起進程創(chuàng)建的事件
1.用戶登錄2.作業(yè)調(diào)度3.提供服務(wù)（前三個都是系統(tǒng)內(nèi)核創(chuàng)建）4.應(yīng)用請求（由用戶程序自己創(chuàng)建）

進程創(chuàng)建原語Create
申請空白PCB-》為新進程分配所需資源-》初始化PCB-》將PCB插入就緒隊列滤淳。

進程的終止
引起進程終止的事件
1.正常結(jié)束
2.異常結(jié)束
越界錯梧喷，保護錯，非法指令脖咐，特權(quán)指令錯铺敌，運行超時，等待超時文搂，算術(shù)運算錯适刀，I/O故障
3.外界干預(yù)
操作員或操作系統(tǒng)干預(yù)，父進程請求煤蹭，父進程終止
撤銷原語
從PCB集合中找到終止進程的PCB-》若進程正在運行則剝奪CPU分配給其它進程-》終止其所有子進程-》歸還資源給父進程或系統(tǒng)-》刪除PCB

進程的阻塞與喚醒
向系統(tǒng)請求共享資源失敗笔喉，等待某種操作完成，新數(shù)據(jù)尚未到達(dá)硝皂，等待新任務(wù)的到達(dá)

進程常挚！調(diào)用阻塞原語block將自己阻塞
阻塞是進程自身的一種主動行為

有關(guān)進程調(diào)用喚醒原語wakeup

掛起
OS！調(diào)用掛起原語suspend
OS稽物！調(diào)用激活原語active

進程的同步
進程間的制約關(guān)系
1.間接相互制約關(guān)系（共享系統(tǒng)資源）——進程互斥問題（對臨界資源的訪問需要互斥的進行）
2.直接相互制約關(guān)系（相互合作）——進程同步問題

臨界資源
進入?yún)^(qū)->臨界區(qū)->退出區(qū)->剩余區(qū)
進程互斥地進入自己的臨界區(qū)

同步機制應(yīng)遵循的規(guī)則
空閑讓進奄毡，忙則等待，有限等待贝或，讓權(quán)等待（當(dāng)進程不能進入自己的臨界區(qū)時吼过，應(yīng)立即釋放處理機）

硬件同步機制
1.關(guān)中斷
簡單高效，不適用多處理機咪奖，只適用于操作系統(tǒng)內(nèi)核進程（因為關(guān)中斷開中斷只能在內(nèi)核態(tài)執(zhí)行）
2.Test-and-Set指令實現(xiàn)互斥
該指令使用硬件實現(xiàn)的盗忱，下面只是它的C語言描述

boolean TS(boolean *lock){
      boolean old;
      old=*lock;
      *lock=TURE;
      return old;
}
do{
  ...
  while TS(&lock); //當(dāng)lock為false時，說明空閑羊赵，才能跳出這個循
                   //環(huán)趟佃，并且被設(shè)置為Ture
  critical section;
  lock=FALSE; //退出區(qū)
  remainder section;
}while(TRUE);

不滿足讓權(quán)等待

3.Swap指令實現(xiàn)進程互斥
和上一個差不多，弄了個key代替old

void swap(boolean *a,boolean *b)
{
   boolean temp;
   temp=*a;
   *a=*b;
   *b=temp;
}
do{
  key=TRUE;
  do{
      swap(&lock,&key);
  }while(key!=FALSE);
  critical section;
  lock=FALSE;
  remainder section;
}while(TURE);

不滿足讓權(quán)等待

以上的方法，當(dāng)資源忙碌時闲昭，其它訪問進程必須不斷進行測試罐寨，處于“忙等”狀態(tài)，不符合讓權(quán)等待原則序矩。

信號量機制
1.整型信號量 忙等
表示資源數(shù)目的整型量S
除了初始化外鸯绿，僅能通過兩個標(biāo)準(zhǔn)的原子操作P，V來訪問

wait(S){
     while(S<=0);
     S--;
}
signal(S){
     S++;
}

2.記錄型信號量 不用忙等
value表示資源數(shù)目簸淀，list表示用于鏈接所有等待訪問該資源的進程的鏈表指針

typedef struct{
   int value;
   struct process_control_block *list;
}semaphore;

wait(semaphore *S){
   S->value--;
   if(S->value<0) block(S->list);
   //S->value的絕對值表示該信號鏈表中已阻塞的進程的數(shù)目
}
signal(semaphore *S){
   S->value++;
   if(S->value<=0) wakeup(S->list);
}

可以用記錄型信號量實現(xiàn)系統(tǒng)資源的申請和釋放楞慈，進程互斥，進程同步啃擦。
S->value的初值為1則轉(zhuǎn)化為互斥信號量

互斥

semaphore mutex=1;
P1(){
     ...
     P(mutex);
     臨界區(qū)
     V(mutex);
     ...
}
P2(){
     ...
     P(mutex);
     臨界區(qū)
     V(mutex);
     ...
}

對于不同的臨界資源需要設(shè)置不同的互斥信號量。

同步
設(shè)置同步信號量S饿悬，初值為0
在前操作后面執(zhí)行V（S）
在后操作之前執(zhí)行P（S）

3.AND型信號量
需要獲得兩個或更多的共享資源
對若干個臨界資源的分配采取原子操作方式令蛉，要么全給，要么一個也不給

4.信號量集
資源分配下限值ti（Si<ti時就不分配了）狡恬，資源需求值di

Swait(S1,t1,d1,...,Sn,tn,dn);
Ssignal(S1,d1,...,Sn,dn);

幾種特殊情況
Swait(S,d,d)
Swait(S,1,1)記錄型信號量 S=1互斥信號量
Swait(S,1,0)相當(dāng)于一個開關(guān)珠叔，當(dāng)S>=1時允許多個進程進入，當(dāng)S=0時組織任何進程進入

信號量的應(yīng)用
1.利用信號量實現(xiàn)進程互斥

wait(mutex);
臨界區(qū)弟劲；
signal(mutex);

2利用信號量實現(xiàn)前趨關(guān)系

管程機制
信號量機制中祷安，大量的同步操作分散在各個進程中，不僅給系統(tǒng)管理帶來麻煩兔乞，還會因為同步操作的使用不當(dāng)造成死鎖汇鞭。
管程：（代表共享資源的數(shù)據(jù)結(jié)構(gòu)）以及（由對該共享數(shù)據(jù)結(jié)構(gòu)實施操作的一組過程所組成的資源管理程序）共同構(gòu)成了一個操作系統(tǒng)的資源管理模塊。
確保每次僅有一個進程進入管程庸追，執(zhí)行這組過程霍骄，使用共享資源
特性：模塊化，抽象數(shù)據(jù)類型淡溯，信息掩蔽

進程在使用管程時可能會被阻塞或掛起读整，引入條件變量來指示其被阻塞或掛起的原因
x.wait：正在調(diào)用管程的進程因x條件需要被阻塞或掛起，調(diào)用x.wait將自己插入到x條件的等待隊列上咱娶，并釋放管程米间，直到x條件發(fā)生變化
x.signal：正在調(diào)用管程的進程發(fā)現(xiàn)x條件發(fā)生了變化，調(diào)用x.signal膘侮，重新啟動一個因x條件而阻塞或掛起的進程（重新啟動的這個進程可以等待當(dāng)且進程完成或阻塞屈糊，也可以換當(dāng)前進程等待）

經(jīng)典進程同步問題
p60

進程通信
1.共享存儲器系統(tǒng)
互斥訪問共享空間
（1）基于共享數(shù)據(jù)結(jié)構(gòu)的通信方式
如生產(chǎn)者-消費者中的有界緩沖區(qū)
僅適合傳遞少量數(shù)據(jù)，屬于低級通信
（2）基于共享存儲區(qū)的通信方式
向系統(tǒng)申請獲得共享存儲區(qū)中的一個分區(qū)喻喳，然后附加到自己的地址空間另玖，讀寫完成后，再歸還給共享存儲區(qū)。高級通信谦去。

2.管道通信系統(tǒng)
pipe文件：連接一個讀進程和一個寫進程以實現(xiàn)它們之間通信的一個共享文件
字符流
互斥慷丽，同步，確定對方是否存在
某一時間段內(nèi)只能實現(xiàn)單向傳輸
沒寫滿就不允許讀鳄哭，沒讀空就不允許寫
一旦數(shù)據(jù)被讀出要糊，該數(shù)據(jù)就被管道拋棄了，這意味著讀進程只能有一個妆丘。

3.消息傳遞系統(tǒng)
以格式化的消息為單位
將通信的數(shù)據(jù)封裝在消息中
利用操作系統(tǒng)提供的一組通信命令（原語）
屬于高級通信方式
直接通信方式
1）對稱尋址方式 顯式提供雙方的標(biāo)識符
send(receiver, message);
receive(sender, message);
2）非對稱尋址方式
send(P, message);
receive(id, message);接收來自任何進程的消息锄俄，id變量作為完成通信后的返回值指示發(fā)送方的id或名字

定長消息格式/變長消息格式
單向/雙向通信鏈路（建立連接）

間接通信方式（郵箱）
send(mailbox, message);
receive(mailbox, message);
私用/公用/共享郵箱

直接消息傳遞系統(tǒng)實例
消息緩沖隊列機制
消息緩沖區(qū)

typedef struct message_buffer{
   int sender;
   int size;
   char *text;
   struct message_buffer *next; //指向下一個消息緩沖區(qū)
}

在PCB中增加

struct message_buffer *mq; //消息隊列隊首指針（放要接收的消息緩沖區(qū)）
semaphore mutex; //消息隊列互斥信號量
semaphore sm; //消息隊列資源信號量

發(fā)送原語

void send(receiver, a){  //receiver為接收進程標(biāo)識符，a為發(fā)送區(qū)首址
   getbuf(a.size, i);  //根據(jù)a.size申請消息緩沖區(qū)
   i.sender=a.sender;
   i.size=a.size;
   copy(i.text, a.text);
   i.next=0;
   getid(PCBset, receiver.j);  //獲得接收進程內(nèi)部的標(biāo)識符
   wait(j.mutex);
   insert(&j.mq, i); //掛到消息隊列上去
   signal(j.mutex);
   signal(j.sm); //sm標(biāo)識隊列中有沒有消息
}

接收原語

void receive(b){
    j=internal name;
    wait(j.sm);   //沒有消息就等著
    wait(j.mutex);
    remove(j.mq, i);
    signal(j.mutex);
    b.sender=i.sender;
    b.size=i.size;
    copy(b.text, i.text);
    releasebuf(i);  //釋放消息緩沖區(qū)
}

4.客戶機-服務(wù)器系統(tǒng)

線程
比進程更小的基本單位
減少程序在并發(fā)執(zhí)行時所付出的時空開銷勺拣，使OS具有更好的并發(fā)性奶赠。
進程的兩個特征
1調(diào)度和分配的基本單位
2擁有資源的基本單位
現(xiàn)在將這兩個特征分開，作為擁有資源的基本單位的進程不再作為調(diào)度和分派的基本單位药有，因為擁有資源會導(dǎo)致調(diào)度和分配開銷很大
線程作為調(diào)度和分派的基本單位
線程控制塊TCB
還可以將一個進程的多個線程分配到不同處理機上
執(zhí)行狀態(tài)毅戈，就緒狀態(tài)，阻塞狀態(tài)