03. 行程觀念 (Process Concept)

3.1行程概念(Process Concept)

CPU所有的運作項目:

    -整批式(Batch)系統執行工作 (jobs)

    -分時(Time-shared)系統執行使用者(user)程式(programs),或稱為任務(task)

行程是操作系統結構的基礎;是一次程序的執行;是一個程序及其數據在處理機上順序執行時所發生的活動;是程序在一個數据集合上運行的過程,它是系统進行資源分配和調度的一個獨立單位。

 

概述:

多道程序在執行時,需要共享系统資源,從而導致各程序在執行過程中出現相互制約的關係,程序的執行表現出間斷性的特徵。這些特徵都是在程序的執行過程中發生的,是動態的過程,而傳统的程序本身是一组指令的集合,是一个靜態的概念,無法描述程序在内存中的執行情况,即我們無法從程序的字面上看出它何時執行,何时停頓,也無法看出它與其它執行程序的關係,因此,程序這個静態概念已不能如實反映程序並發執行過程的特徵。為了深刻描述程序動態執行過程的性質,人們引入“行程(Process)”概念。

行程須由:CPU、記憶體、I/O、files、預設數據來合作完成。

 

概念:

行程是60年代初首先由麻省理工學院的MIT的MULTICS系统和IBM公司的CTSS/360系统引入的。

行程是一個具有獨立功能的程序關於某個數据集合的一次運行活動。它可以申請和擁有系统資源,是一個動態的概念,是一個活動的實體。它不只是程序的代碼,還包括當前的活動,通過程序計數器的值和處理寄存器的内容來表示。

 

定義:

狭義定義:併發執行的程序在執行過程中分配和管理資源的基本單位。

廣義定義:行程是一個具有一定獨立功能的程序關於某個數据集合的一次運行活動。它是操作系统動態執行的基本單元,在傳统的操作系统中,行程既是基本的分配單元,也是基本的執行單元。

主要兩點

行程的概念主要有兩點:

一、行程是一個實體。每一個行程都有它自己的地址空間,一般情况下,包括文本區域(text region)、數据區域(data region)和堆栈(stack region)。文本區域存儲處理器執行的代碼;數据區域存儲變量和行程執行期間使用的動態分配的内存;堆棧區域存儲著活動過程調用的指令和本地變量。

二、行程是一個“執行中的程序”。程序是一個有生命的實體,只有處理器賦予程序生命時,它才能成為一個活動的實體,我们稱其為行程。

行程是操作系统中最基本、重要的概念。是多道程序系统出現後,為了刻劃系统内部出现的動態情况,描述系统内部各道程序的活動規律引進的一個概念,所有多道程序設計操作系统都建立在行程的基礎上。

 

原因:

操作系统引入行程的概念的原因:

從理論角度看,是對正在運行的程序過程的抽象;

從實現角度看,是一種數據結構,目的在於清晰地刻畫動態系统的内在規律,有效管理和調度進入計算機系统主存儲器運行的程序。

 

特徵:

動態性:行程的實質是程序在多道程序系统中的一次執行過程,行程是動態產生,動態消亡的。

併發性:多個行程可同存於内存中,能在一段时間内同时運行。

獨立性:行程是一個能獨立運行的基本單位,同时也是系统分配資源和調度的獨立單位;

異步性:由於行程間的相互制约,使行程具有執行的間斷性,即行程按各自獨立的、不可預知的速度向前推進

結構特徵:行程由程序、數据和行程控制塊三部分组成。

多個不同的行程可以包含相同的程序:一個程序在不同的數据集裡就構成不同的行程,能得到不同的結果;但是執行過程中,程序不能發生改變。

 

内容:

一個計算機系统行程包括(或者說“擁有”)下列數據:

那個程序的可運行機器碼的一個在存儲器的映像。 分配到的存儲器(通常包括虛擬内存的一個區域)。存儲器的内容包括可運行代碼、特定於行程的數據(輸入、輸出)、調用堆栈、堆栈(用於保存運行時運數中途產生的數據)。 分配給該行程的资源的操作系统描述符,諸如文件描述符(Unix術语)或文件句柄(Windows)、數據源和數據终端。 安全特性,諸如行程擁有者和行程的權限集(可以容許的操作)。 處理器狀態(内文),諸如寄存器内容、物理存儲器寻址等。當行程正在運行時,狀態通常儲存在寄存器,其他情况在存儲器。

 

切換:

Windows 和Windows Vista 體系结構

進行行程切換就是從正在運行的行程中收回處理器,然後再使待運行行程來占用處理器

這裡所說的從某個行程收回處理器,實質上就是把行程存放在處理器的寄存器中的中間數據找個地方存起來,從而把處理器的寄存器騰出来讓其他行程使用。那麼被中止運行行程的中間數據存在何處好呢?當然這個地方應該是行程的私有堆栈。

讓行程來占用處理器,實質上是把某個行程存放在私有堆栈中寄存器的數據(前一次本行程被中止時的中間數據)再恢復到處理器的寄存器中去,並把待運行行程的斷點送入處理器的程序指針PC,於是待運行行程就開始被處理器運行了,也就是這個行程已經占有處理器的使用權了。

這就像多個同學要分時使用同一張課桌一樣,所謂要收回正在使用課桌同學的課桌使用權,實質上就是讓他把屬於他的東西拿走;而賦予某個同學課桌使用權,只不過就是讓他把他的東西放到課桌上罷了。

在切換時,一個行程存儲在處理器各寄存器中的中間數據叫做行程的上下文,所以行程的 切換實質上就是被中止運行行程與待運行行程上下文的切換。在行程未占用處理器時,行程的上下文是存儲在行程的私有堆栈中的。

 

3.1.1行程(The Process)

 

  • 行程指的是正在執行的程式。
  • 行程不只是程式碼 ,有時也稱為本文區(text section)。
  • 它包含代表目前運作的程式計數器 (program counter)數值和處理器(processor)的暫存器(registrers)內容。
  • 行程堆疊 (stack):存放暫用資料 (副程式的參數、返回位址,及暫時性變數)
  • 資料區間(data section):包含全域變數(global variables)
  • 堆積 (heap):堆積就是在行程執行期間動態配置的記憶體

      

 
 

3.1.2行程狀態(Process State)

一個行程的生命期可以劃分為一組狀態,系統根據PCB結構中的狀態值控制行程。行程在生命消失前處於且僅處於三種基本狀態之一。

行程的基本狀態有三種:就緒、執行、等待(阻塞)。

1.就緒狀態:當行程已分配到除CPU以外的所有必要資源後,只要在獲得CPU,便可立即執行,行程這時的狀態稱為就緒狀態。處於該狀態的行程構成緒列隊。

2.執行狀態:行程正在處理器上運行的狀態,該行程已獲得必要的資源,也獲得了處理器,用戶程序正在處理器上運行。

3.等待(阻塞)狀態:正在執行的行程由於發生某事件而暫時無法繼續執行時,變放棄處理器而處於暫停狀態,即行程的執行收到阻塞,成為阻塞狀態,也成為等待狀態。

行程在執行時會改變其狀態。

行程的狀態 (state)部份是指該行程目前的動作,每一個行程可能會處於以下數種狀態之一:
  • 新產生(new):該行程正在產生中。
  • 執行(running):指令正在執行。
  • 等待(waiting):等待某件事件的發生(譬如輸出入完成或接收到一個信號)。
  • 就绪(ready):該行程正等待指定一個處理器。
  • 结束(terminated):該行程完成執行。

 

3.1.3行程控制表(Process Control Block (PCB))

每一個行程在作業系統之中都對應著一個行程控制表 (Process control block (PCB))也可稱為任務控制表 (task control block)

  • 行程狀態(Process state):running、waiting
  • 程式計數器(Program counter):指出行程接著要執行的指令位址
  • CPU暫存器(CPU registers):所有暫存器內容
  • CPU排班法則相關資訊(CPU scheduling information):行程的優先順序 (Priorities)、排班佇列(scheduling queue)指標以及其它的排班參數
  • 記憶體管理資訊(Memory-management information):分配給行程的記憶體
  • 帳號資訊(Accounting information):CPU和實際時間的使用數量、時限、帳號工作或行程號碼。
  • 輸入/輸出狀態資訊(I/O status information):配置給行程的輸入/輸出裝置,開啟檔案的串列

   

 

控制:

行程控制是行程管理中最基本的功能。它用於創建一個新行程,終止一個已完成的行程,或者去終止一個因出現某事件而使其無法運行下去的行程,還可負責行程運行中的狀態轉換。

 

創建行程:

1.引起創建行程的事件

在多道程序環境中,只有(作為)行程(時)才能在系統中運行。因此,為使程序能運行,就必須為它創建行程。導致一個行程去創建另一個行程的典型事件,可以有以下四類:

1) 用戶登錄

在分時系統中,用戶在終端鍵入登錄命令後,如果是合法用戶,系統將為該終端建立一個行程,並把它插入到就緒隊列中。

2)作業調度

在批處理系統中,當作業調度程序按照一定的算法調度到某作業時,便將該作業裝入到內存,為它分配必要的資源,並立即為它創建行程,再插入到就緒隊列中。

3)提供服務

當運行中的用戶程序提出某種請求後,系統將專門創建一個行程來提供用戶所需要的服務,例如,用戶程序要求進行文件打印,操作系統將為它創建一個打印行程,這樣,不僅可以使打印行程與該用戶行程並發執行,而且還便於計算出為完成打印任務所花費的時間。

4)應用請求

在上述三種情況中,都是由系統內核為它創建一個新行程,而這一類事件則是基於應用行程的需求,由它創建一個新的行程,以便使新行程以並發的運行方式完成特定任務。

2.行程的創建過程

一旦操作系統發現了要求創建新行程的事件後,便調用行程創建原語Creat()按下述步驟創建一個新行程。

1) 申請空白PCB。為新行程申請獲得唯一的數字標識符,並從PCB集合中索取一個空白PCB。

2) 為新行程分配資源。為新行程的程序和數據以及用戶棧分配必要的內存空間。顯然,此時操作系統必須知道新行程所需要的內存大小。

3) 初始化行程控制塊。 PCB的初始化包括:

①初始化標識信息,將系統分配的標識符和父行程標識符,填入新的PCB中。

②初始化處理機狀態信息,使程序計數器指向程序的入口地址,使棧指針指向棧頂。

③初始化處理機控制信息,將行程的狀態設置為就緒狀態或靜止就緒狀態,對於優先級,通常是將它設置為最低優先級,除非用戶以顯式的方式提出高優先級要求。

4) 將新行程插入就緒隊列,如果行程就緒隊列能夠接納新行程,便將新行程插入到就緒隊列中。

行程终止:

1.引起行程终止的事件

1)正常結束

在任何計算機系統中,都應該有一個表示行程已經運行完成的指示。例如,在批處理系統中,通常在程序的最後安排一條Hold指令或終止的系統調用。當程序運行到Hold指令時,將產生一個中斷,去通知OS本行程已經完成。

2)異常結束

在行程運行期間,由於出現某些錯誤和故障而迫使行程終止。這類異常事件很多,常見的有:越界錯誤,保護錯,非法指令,特權指令錯,運行超時,等待超時,算術運算錯,I/O故障。

3)外界干預

外界干預並非指在本行程運行中出現了異常事件,而是指行程應外界的請求而終止運行。這些干預有:操作員或操作系統干預,父行程請求,父行程終止。

2. 行程的终止過程

如果系統發生了上述要求終止行程的某事件後,OS便調用行程終止原語,按下述過程去終止指定的行程。

1)根據被終止行程的標識符,從PCB集合中檢索出該行程的PCB,從中讀出該行程狀態。

2)若被終止行程正處於執行狀態,應立即終止該行程的執行,並置調度標誌為真。用於指示該行程被終止後應重新進行調度。

3)若該行程還有子孫行程,還應將其所有子孫行程予以終止,以防他們成為不可控的行程。

4)將被終止的行程所擁有的全部資源,或者歸還給其父行程,或者歸還給系統。

5)將被終止行程(它的PCB)從所在隊列(或鍊錶)中移出,等待其它程序來蒐集信息。

 

等待(阻塞)喚醒:

1.引起行程等待(阻塞)和喚醒的事件

1)請求系統服務

當正在執行的行程請求操作系統提供服務時,由於某種原因,操作系統並不立即滿足該行程的要求時,該行程只能轉變為阻塞狀態來等待,一旦要求得到滿足後,行程被喚醒。

2)啟動某種操作

當行程啟動某種操作後,如果該行程必須在該操作完成之後才能繼續執行,則必須先使該行程阻塞,以等待該操作完成,該操作完成後,將該行程喚醒。

3)新數據尚未到達

對於相互合作的行程,如果其中一個行程需要先獲得另一(合作)行程提供的數據才能運行以對數據進行處理,則是要其所需數據尚未到達,該行程只有(等待)阻塞,等到數據到達後,該行程被喚醒。

4)無新工作可做

系統往往設置一些具有某特定功能的系統行程,每當這種行程完成任務後,便把自己阻塞起來以等待新任務到來,新任務到達後,該行程被喚醒。

2.行程阻塞過程

正在執行的行程,當發現上述某事件後,由於無法繼續執行,於是行程便通過調用阻塞原語block把自己阻塞。可見,行程的阻塞是行程自身的一種主動行為。進入block過程後,由於此時該行程還處於執行狀態,所以應先立即停止執行,把行程控制塊中的現行狀態由執行改為阻塞,並將PCB插入阻塞隊列。如果系統中設置了因不同事件而阻塞的多個阻塞隊列,則應將本行程插入到具有相同事件的阻塞(等待)隊列。最後,轉調度程序進行重新調度,將處理機分配給另一就緒行程,並進行切換,亦即,保留被阻塞行程的處理機狀態(在PCB中),再按新行程的PCB中的處理機狀態設置CPU環境。

3. 行程喚醒過程

當被阻塞的行程所期待的事件出現時,如I/O完成或者其所期待的數據已經到達,則由有關行程(比如,用完並釋放了該I/O設備的行程)調用喚醒原語wakeup(),將等待該事件的行程喚醒。喚醒原語執行的過程是:首先把被阻塞的行程從等待該事件的阻塞隊列中移出,將其PCB中的現行狀態由阻塞改為就緒,然後再將該PCB插入到就緒隊列中。

調度算法:

進程的調度算法包括:

FcFs(First come First served 先進先出法)、

RR(round—Robin循環分時)、

sjf最短工作優先(shortest—job—first—scheduling)

最短剩餘時間優先(shortest—remaining—time—first)

優先權限高優先

多層次演算法

多層次反饋隊列演算法

多處理器演算法

 

 

3.2行程排班(Process Scheduler)

多元程式規劃系統(Multiprogramming)的主要目的,是隨時有一個行程在執行,藉以提高CPU的使用率。

分時系統(Time Sharing)的目的是將CPU在不同行程之間不斷地轉換,以便讓使用者可以在自己的行程執行時與它交談。

為了達到這個目的,行程排班(Scheduler)為CPU上執行程式選擇一個可用的行程。

 

3.2.1排班佇列(Scheduling Queues)

行程進入系統時,是放在工作佇列(Job queue)之中,此佇列是由系統中所有的行程所組成。位於主記憶體中且就緒等待執行的行程是保存在一個所謂就緒佇列 (Ready aueue)的串列。這個佇列一般都是用鏈接串列的方式儲存。在就緒佇列前端保存著指向這個串列的第一個和最後一個PCB的指標。

 

一個新的行程最初是置於就緒佇列中。就一直在就緒佇列中等待,直到選來執行。一但這個行程配置CPU並且進行執行,則會有若干事件之一可能發生:

  • 行程可發出I/0要求,然後置於一個I/0佇列中
  • 行程可產生出一個新的子行程並等待後者的結束
  • 行程可強行地移離CPU(如用中斷的結果一樣),然後放回就緒佇列中

 

 

3.2.2排班程式(Schedulers)

Short-term Scheduler(or CPU Scheduler):從記憶體中選出一個已經準備就緒的行程,並且將CPU分配給它

Long-term Scheduler(Job Scheduler):從Spooled (行程池)中選出行程並且將它們載入記憶體內以便執行

中程排班程式 (Medium-term Scheduler):背後的最主要觀念就是有時可以將行程從記憶體中有效地移開(並且從對CPU的競爭中移開)、並減低多元程式規劃的程度(Multiprogramming)

 

 

3.2.3內容轉換(Context Switch)

轉換CPU至另一項行程時必須將舊行程的狀態儲存(State Save)起來,然後再載入新行程的儲存狀態(還原狀態:State Restore),這項任務稱為內容轉換(Context Switch)

 

3.3行程的操作 (Operations on Processes)

 

系統中的各個行程可以並行(Concurrently)地執行,而且也要能動態地產生或刪除。

作業系統必須提供行程產生和結束的功能。

 

3.3.1行程的產生(Process Creation)

一個行程的執行期間,可以利用產生行程的系統呼叫來產生數個新的行程。

原先的行程就叫做父行程 (Parent Process),而新的行程則叫做子行程(Children Process)。

每一個新產生的行程可以再產生其它的行程,這可以形成一幅行程樹 (Tree of Processes)。

 

 

 

3.3.2行程的結束(Process Termination)

 

一個行程在執行完最後一個敘述(Statement),以及使用系統呼叫 exit() 要求作業系統將自己刪除時結束。

這個行程的所有資源 (包體記憶體、虛擬記憶體、開啟檔案,以及輸入輸出緩衝區) 都由作業系統收回。

一個父行程可以基於若干理由將子行程中止︰

  • 子行程已經使用超過配置的資源數量
  • 指派給子行程的工作已經不再需要
  • 父行程結束,而作業系統不允許子行程在父行程結束之後繼續執行

 

3.4行程間通訊(Interprocess Communication)

合作行程(Cooperating Process):

  • 資訊共享(Information Sharing): 數個使用者可能對相同的一項資訊(例如,公用檔案)有興趣,因此須提供一個環境允許使用者能同時使用這些資源。
  • 加速運算(Computation Speedup): 如果希望某一特定工作執行快一點,則可以分成一些子工作, 每一個子工作都可以和其它子工作平行地執行。
  • 模組化(Modularity): 以模組的方式來建立系統,把系統功能分配到數個行程。
  • 方便性(Convenience):即使是單一使用者也可能同時執行數項工作。

 

 

3.4.1共用記憶體系統(Shared-Memory Systems)

為了闡述合作行程的觀念,讓我們來看「生產者-消費者」的問題。

生產者(Producer)行程產生資訊,消費者(Consumer)行程消耗掉這些資訊。

 

3.4.2訊息傳遞系統(Message-Passing Systems)

訊息傳遞提供行程互相溝通和彼此同步而不需要共享相同的位址空間

訊息傳遞設施提供至少兩種操作:send(訊息) 和 receive(訊息)

通訊鏈操作方法(send/receive):

  • 直接或間接聯繫(Direct or Indirect Communication)
  • 同步或非同步聯繫(Synchronous or Asynchronous Communication)
  • 自動或明確的緩衝作用(Automatic or Explicit Buffering)

 

3.4.2.1  命名(Naming)

直接聯繫 (Direct Communication)方法中,每一個要傳送或接收訊息的行程必須先確定聯繫接收者或傳送者的名稱。n在這個體系之中,send 與 receive的基本運算定義如下:

 

  • send (P, message)傳送一個訊息(message)至行程P。

 

  • receive (Q, message)自行程Q接收一個訊息(message)。

 

間接式聯繫(Indirect Communication)之中,需藉著信箱(mailbox,也叫作埠,port)來傳送與接收訊息。這種 send 與 receive 的基本運算之定義如下:
  • send (A, message)  將訊息 (message)傳送至信箱A。
  • receive (A, message) 自信箱A接收一個訊息 (message)。

 

3.4.2.2  同步化(Synchronization)

訊息傳遞可以是等待(Blocking)也稱為同步 (Synchronous)

  • 等待傳送 (Blocking Send):傳送行程等待著,直到接收行程或信箱接收訊息。
  • 等待接收 (Blocking Receive):接收者等待,直到有效訊息出現。

 

非等待(Nonblocking)也稱為非同步 (Asynchronous)

  • 非等待傳送 (Nonblocking Send):傳送行程送出訊息及重新操作。
  • 非等待接收 (Nonblocking Receive):接收者收到有效訊息或無效資料。

 

3.4.2.3  緩衝器(Buffering)

不論是直接或間接連繫,經由通訊行程交換的訊息是放在一個暫時的佇列(Temporary Queue)。

基本上,有三種製作這種佇列的方式︰

  • 零容量 (Zero Capacity)︰佇列的最長長度為 0,因此鏈(Link)中將不含有任何等候的訊息。
  • 有限的容量 (Bounded Capacity)︰佇列具有有限長度 n;因此最多有 n 個訊息存於其中。
  • 無限制的容量 (Unbounded Capacity)︰佇列具有無限長度的潛力;因此任何訊息能在佇列中等候,傳送者從不阻塞,而且傳送者也不需等候。

 

參考資料:行程觀念(中文)ppt、百度(進程觀念)