Quan Ly Tien Trinh (tt)

Tài nguyên găng (Critical Resource)

v Tài nguyên găng?

§   Nh ững tài nguyên đý ợc HĐH chia s ẻ cho nhi ều ti ến trình ho ạt đ ộng đ ồng th ời dùng chung mà có nguy cõ tranh ch ấp gi ữa các ti ến trình này khi s ử d ụng chúng.

Có 2 tiến trình P1 vs P2 cùng thao tác rút tiền từ 1 tài khoản.

  IF (Tai khoan – tien rut >= 0)

          Tai khoan :=  Tai khoan – tien rut

  else

          Thong bao loi

Đoạn găng(Critical Section)

v Các đoạn code trong các chýõng trình dùng để truy cập đến tài nguyên găng đýợc gọi là đoạn găng.

Yêu cầu của công tác điều độ tiến trình qua đoạn găng

v  Tại 1 thời điểm chỉ cho phép 1 tiến trình nằm trong đoạn găng, các tiến trình khác có nhu cầu vào đoạn găng phải chờ

v  Tiến trình chờ ngoài đoạn găng không đýợc ngăn cản các tiến trình khác vào đoạn găng

v  Không có tiến trình nào phải chờ lâu để đýợc vào đoạn găng

v  Đánh thức các tiến trình trong hàng đợi để tạo điều kiện cho nó vào đoạn găng khi tài nguyên găng đýợc giải phóng

3. Điều độ tiến trình qua đoạn găng

3.1. Giải pháp phần cứng

v  Dùng cặp chỉ thị STI(setting interrupt) và CLI (clean interrupt)

Ví dụ:

Procedure P(i: integer)

   begin

        repeat

                CLI;

                        <đoạn găng của p>;

                STI;

                        <Đoạn không găng>;

        until .F.

   end;

 

v Dùng chỉ thị TSL(Test and set)

Function TestAnhSetLock(Var i:integer):boolean

Begin

   if i=0 then

       begin

              i:=1;

              TestAnhSetLock:=true

       end;

   else

       TestAnhSetLock:=false

End;

 

Procedure P(lock: integer);

   begin

       repeat

              while (TestAnhSetLock(lock)) do;

              <đoạn găng của p>;

              lock:=0

              <Đoạn không găng>;

       until .F.

   end;

 

 

3.2. Giải pháp dùng biến khóa

v  Dùng biến khóa chung

Procedure P(lock: integer);

   begin

        repeat

                while       lock=1 do;

                Lock=1

                <đoạn găng của p>;

                lock:=0

                <Đoạn không găng>;

        until .F.

   end;

 

 

 

v   Dùng biến khóa riêng

Var lock1, lock2: byte;

begin

lock1:=0; lock2:=1

          p1: repeat

                   while          lock2=1 do;

                   Lock1:=1

                   <đoạn găng của p>;

                   lock1:=0

                   <Đoạn không găng>;

               until .F.

          p2: repeat

                   while          lock1=1 do;

                   Lock2:=1

                   <đoạn găng của p>;

                   lock2:=0

                   <Đoạn không găng>;

               until .F.

 

end

 

 

 

3.3. Giải pháp đýợc hỗ trợ bởi HĐH và ngôn ngữ lập trình

v  Dùng Semaphore(đèn báo)

§    Semaphore S là 1 biến nguyên, khởi gán bằng 1 giá trị không âm, là khả năng phục vụ của tài nguyên găng týõng ứng với nó

§    Ứng với S có 1 hàng đợi F(s) lýu các tiến trình đang chờ trên S

§    Thao tác Down giảm S 1 đõn vị, Up tăng S 1 đõn vị

§    Mỗi tiến trình trýớc khi vào đoạn găng cần gọi Down để giảm S và kiểm tra nếu S>=0 thì đýợc vào đoạn găng

§    Mỗi tiến trình khi ra khỏi đoạn găng phải gọi Up để tăng S lên 1 đõn vị và ktra nếu S <=0 thì đýa 1 tiến trình trong F(s) vào đoạn găng

 

Procedure Down(S);

Begin

   S:=S-1;

If s<0 then

Begin

  Status(p)=waiting;

  Enter(p,F(s));

end

End;

 

Procedure Up(S);

Begin

   S:=S+1;

If s<=0 then

Begin

  Exit(Q,F(S));

  Status(Q)=ready;

  Enter(Q,ready-list);

end

End;

 

 

Program MultualExclution;

Const

   n=2;

Var

   s:semaphore;

{---------------------}

Procedure P(i:Integer);

Begin

   REpeat

        Down(s); {kiem tra va xac lap quyen vao doan gang}

        <Doan gang>;

        Up(s);

        <Doan khong gang>;

   Until .F.;

End;

{---------------------}

BEGIN

   S:=1;

   ParBegin

        P(1);

        P(2);

   ParEnd;

END.

 

Ví dụ 2 :

Có 6 tiến trình

       A     B     C     D    E     F

Độ ýu tiên

       1     1     2     4     2     5

Thời gian thực hiện

       4     2     2     2     1     1

 

Giải pháp dùng Monitor

****Wait(c)

 

Procedure Wait(c);

Begin

   Status(p)=blocked;

   Enter(p,f(c));

End;

 

****Signal(c)

 

 

Begin

   If f(c) <> Null Then

        Begin

                Exit(Q,f(c));     {Q la tien trinh cho tren C}

                Status(Q)=ready;

                Enter(Q,ready-list);

        End;

End;

 

 

Monitor <Ten monitor>

Condition  <Danh sach cac bien dieu kien>;

{----------------------------}

   Procedure Action1();             {thao tac 1}

   Begin

       .....

   End;

   {--------------------}

       Procedure Actionn();  {thao tac n}

       Begin

              .....

       End;

   {--------------------}

End monitor;

 

 

 

Program MultualExclution;

Monitor ... Endmonitor;    {monitor duoc dinh nghia nhu tren}

{-----------------------}

BEGIN

    ParBegin

          P1:Repeat

                   <Doan khong gang cua P1>;

                   <>monitor>.Actioni;              {Doan gang cua P1};

                   <Doan khong gang cua P1>;

             Until .F.

          P2:Repeat

                   <Doan khong gang cua P2>;

                   <monitor>.Actionj;                {Doan gang cua P1};

                   <Doan khong gang cua P2>;

             Until .F.

    ParEnd

END.

{-----------------------}

Giải pháp trao đổi Message

 

Procedure P(i:Integer);

Begin

    Repeat

          Send(process controler, request message);

          Receive(process controler, accept message);

          <Doan gang cua P>;

          Send(process controler, end message);

          <Doan khong gang cua P>;         

    Until .F.

End;

 

Bài toán điều phối

Giải pháp Semaphore

Program Producer/Consumer;

Var  Full,Empty,Mutex:Semaphore;

{-------------------------}

Procedure Producer();

Begin

   Repeat

       <Tao du lieu>;

       Down(Empty);  {kiem tra xem bufer con cho trong?}

       Down(Mutex);  {kiem tra va xac lap quyen truy xuat Buffer}

       <Dat du lieu vao Buffer>;

       Up(Mutex);   {ket thuc truy xuat buffer}

       Up(Full);       {da co 1 phan tu du lieu trong Buffer}

   Until .F.

End;

{-------------------------}

 

Procedure Consumer();

Begin

   Repeat

       Down(Full);  {con phan tu du lieu trong Buffer}

       Down(Mutex);     {kiem tra va xac lap quyen truy xuat Buffer}

       <Nhan du lieu tu dem>;

       Up(Mutex);   {ket thuc truy xuat Buffer}

       Up(Empty);   {da lay 1 phan tu du lieu trong Buffer}

   Until .F.

End;

 

BEGIN

   Full=0;Empty=3;Mutex=1;

   Producer();

   Consumer();

END.

 

Giải pháp Monitor

Program Producer/Consumer;

Monitor ProducerConsumer;

Condition Full,Empty;

Var   Count:Integer; {da lay 1 phan tu du lieu Buffer}

   N:Integer;     {so phan tu cua Buffer}

{------------------------}

Procedure Enter();

Begin

   If Count=N Then Wait(Full);        {neu Buffer day thi doi}

   <Dat du lieu vao dem>;               {Buffer rong}

   Count:=Count+1;

   If Count=1 Then Signal(Empty);  {neu Buffer khong rong thi}

End;                                 {bao cho consumer biet}

{------------------------}

Procedure Remove();

Begin

   If Count=0 Then Wait(Empty);    {neu Buffer rong thi doi day}

   <Nhan du lieu tu den>;

   Count:=Count-1;

   If Count=N-1 Then Signal(Full);  {neu Buffer khong day thi}

End;                                 {bao cho producer}

Endmonitor;

{------------------------}

 

 

BEGIN

   Count=0;N=3;

ParBegin

Procedure Producer();

Begin

   Repeat

        <Tao du lieu>;

        Producer/Consumer.Enter;

   Until .F.

End;

{------------------------}

Procedure Consumor();

Begin

   Repeat

        Producer/Consumer.Remove;

        <Xu ly du lieu>;

   Until .F.

End;

ParEnd

END.

{------------------------}

Message

Program Producer/Consumer;

Var

       Buffersize:integer;     {kich thuoc Buffer}

       M,m:Message;

{-------------------------}

BEGIN

   Bufersize=N;

ParBegin

Procedure Producer();

Begin

   Repeat

       <Tao du lieu>;

       Receive(Consumer,m);

       <Tao thong diep du lieu>;

       Send(Consumer,m);

   Until .F.

End;

{-------------------------}

 

Procedure Consumer()

Var I:integer;

Begin

   For I:=0 to N Do Send(Producer,m);

     Repeat

       Receive(Producer,m);

       <Lay du lieu tu thong diep>;

       Send(Producer,m);

       <Xu ly du lieu>;

     Until .F.

End.

Parend

END.

Quan Ly Tien Trinh

 

 

Tiến trình ?

* Tiến trình là một bộ phận của một chýõng trình đang thực hiện, đýợc sở hữu 1 con trỏ lệnh, tập các thanh ghi và các biến

•      Để hoàn thành tác vụ của mình, một tiến trình có thể cần đến một số tài nguyên nhý CPU, bộ nhớ chính, các tập tin và thiết bị nhập/xuất.

v   Tiến trình bao gồm 3 thành phần: Code, Data, Stack

§     Code: Thành phần câu lệnh thực hiện

§     Data: Thành phần dữ liệu

§     Stack: Thành phần lýu thông tin tạm thời

v   Các câu lệnh trong code chỉ dùng data và stack riêng của mình ngoại trừ các vùng dùng chung

v   Tiến trình đýợc hệ thống phân biệt bằng số hiệu pid (proccess indentification)

 

Các loại tiến trình

-> Tiến trình tuần tự

    Là các tiến trình mà điểm khởi tạo của nó là điểm kết thúc của tiến trình trýớc đó.

Mô Hình Tiến Trình

    *Tạo hiện týợng song song giả.

      *Chia chýõng trình thành nhiều tiến trình.

    HĐH chia chýõng trình thành nhiều tiến trình, khởi tạo và đýa vào hệ thống nhiều tiến trình của một chýõng trình hoặc của nhiều chýõng trình khác nhau, cấp phát đầy đủ tài nguyên (trừ processor) cho tiến trình và đýa các tiến trình sang trạng trái sẵn sàng. HĐH bắt đầu cấp processor cho một tiến trình trong số các tiến trình ở trạng thái sẵn sàng để tiến trình này hoạt động, sau một khoảng thời gian nào đó HĐH thu hồi processor của tiến trình này để cấp cho một tiến trình sẵn sàng khác, sau đó HĐH lại thu hồi processor từ tiến trình mà nó vừa cấp để cấp cho tiến trình khác, có thể là tiến trình mà trýớc đây bị HĐH thu hồi processor khi nó chýa kết thúc, và cứ nhý thế cho đến khi tất cả các tiến trình mà HĐH khởi tạo đều h/động và k/thúc đýợc.

    Trong mô hình tiến trình này, khoảng thời gian chuyển processor từ tiến trình này sang tiến trình khác hay khoảng thời gian giữa hai lần đýợc cấp phát processor của 1 tiến trình là rất nhỏ nên hệ thống có cảm giác các tiến trình hoạt động song song nhau ( song song giả )

Mô Hình Tiến Trình

 Ýu điểm:

                - Tiết kiệm bộ nhớ.

                - Khai thác tối ýu tài nguyên máy.

 

    - Tiết kiệm đýợc bộ nhớ vì không phải nạp tất cả chýõng trình vào bộ nhớ mà chỉ nập các tiến trình cần thiết nhất, sau đó tùy theo yêu cầu mà có thể nạp tiếp các tiến trình khác.

     - Cho phép các chýõng trình hoạt động song song nên tốc độ xử lý của toàn hệ thống tăng lên và khai thác tối đa thời gian xử lý của processor.

<ví dụ minh họa quá trình chuyển processor giữa các tiến trình sẵn sàng>

Tiểu trình và tiến trình ?

 

* Thông thýờng mỗi tiến trình có 1 không  gian địa chỉ và 1 dòng xử lý

v  Mong muốn có nhiều dòng xử lý cùng chia sẻ 1 không gian địa chỉ và các dòng xử lý hoạt động song song nhý các tiến trình độc lập

v  Xuất hiện HĐH có cõ chế thực thi mới gọi là tiểu trình

 

* Tiểu trình là một đõn vị xử lý cõ bản trong hệ thống, týõng tự giống tiến trình. Tức là nó cũng phải xử lý tuần tự các chỉ thị máy của nó, nó cũng sở hữu con trọ lệnh, một tập các thanh ghi và một không gian stack riêng.

Tiểu trình và tiến trình ?

   Một tiến trình đõn có thể bao gồm nhiều tiểu trình. Các tiểu trình trong một tiến trình chia sẻ một không gian địa chỉ chung nên có thể chia sẻ các biến toàn cục của tiến trình và truy xuất lên các vùng nhớ stack của nhau.

Các Trạng Thái Của Tiến Trình

v Tiến trình hai trạng thái

                    

Các Trạng Thái Của Tiến Trình

v Tiến trình ba trạng thái

                    

Các Trạng Thái Của Tiến Trình

v Tiến trình bốn trạng thái

             

Các Trạng Thái Của Tiến Trình

v Tiến trình năm trạng thái

                    

Cấu Trúc Dữ Liệu Của Khối Quản Lý Tiến Trình

   Hệ điều hành quản lý các tiến trình trong hệ thống thông qua khối quản lý tiến trình (process control block -PCB). PCB là một vùng nhớ lýu trữ các thông tin mô tả cho tiến trình.

 

* Với các thành phần chủ yếu bao gồm :

 

v     Định danh của tiến trình (1) : giúp phân biệt các tiến trình

v       Trạng thái tiến trình (2): xác định hoạt động hiện hành của tiến trình.

v       Ngữ cảnh của tiến trình (3): mô tả các tài nguyên tiến trình đang trong qu� trình, hoặc để phục vụ cho hoạt động hiện tại, hoặc để làm cõ sở phục hồi hoạt động cho tiến trình, bao gồm các thông tin về:

v       Trạng thái CPU: bao gồm nội dung các thanh ghi, quan trọng nhất là con trỏ lệnh IP lýu trữ địa chỉ c�u lệnh kế tiếp tiến trình sẽ xử lý. Các thông tin này cần đýợc lýu trữ khi xảy ra một ngắt, nhằm có thể cho phép phục hồi hoạt động của tiến trình đ�ng nhý trýớc khi bị ngắt.

v       Bộ xử lý: dùng cho máy có cấu hình nhiều CPU, xác định số hiệu CPU mà tiến trình đang sử dụng.

v       Bộ nhớ chính: danh sách các khối nhớ đýợc cấp cho tiến trình.

v       Tài nguyên sử dụng: danh sách các tài mguyên hệ thống mà tiến trình đang sử dụng.

v       Tài nguyên tạo lập: danh sách các tài nguyên đýợc tiến trình tạo lập.

v       Thông tin giao tiếp (4): phản ánh các thông tin về quan hệ của tiến trình với các tiến trình khác trong hệ thống :

v       Tiến trình cha: tiến trình tạo lập tiến trình này .

v       Tiến trình con: các tiến trình do tiến trình này tạo lập .

v       Độ ýu tiên : giúp bộ điều phối c� th�ng tin để lựa chọn tiến trình đýợc cấp CPU.

v       Thông tin thống kê (5): đ�y là những thông tin thống kê về hoạt động của tiến trình, nhý thời gian đã sử dụng CPU,thời gian chờ. Các thông tin này có thể có ích cho công việc đ�nh gi� tình hình hệ thống và dự đo�n c�c tình huống týõng lai.

Các Thao Tác Điều Khiển Tiến Trình

    a. Khởi tạo tiến trình

v  HĐH gán PID và đýa vào danh sách quản lý của hệ thống

v  Cấp phát không gian bộ nhớ

v  Khởi tạo các thông tin cần thiết cho khối điều khiển tiến trình:  Các PID của TT cha (nếu có), thông tin trạng thái, độ ýu tiên, ngữ cảnh của processor

v  Cung cấp đầy đủ các tài nguyên (trừ processor)

v  Đýa tiến trình vào danh sách TT nào đó: ready list, suspend list, waiting list

Các Thao Tác Điều Khiển Tiến Trình

   b. Kết thúc tiến trình HĐH thực hiện các thao tác:

v Thu hồi tài nguyên đã cấp phát cho tiến trình

v Loại bỏ tiến trình ra khỏi danh sách  quản lý của hệ thống

v Hủy bỏ khối điều khiển tiến trình

Các Thao Tác Điều Khiển Tiến Trình

    c. Thay đổi trạng thái của tiến trình HĐH thực hiện:

v  Lýu ngữ cảnh của processor

v  Cập nhật PCB (process control block) của tiến trình sao cho phù hợp với trạng thái của tiến trình

v  Di chuyển PCB của tiến trình đến 1 hàng đợi thích hợp

v  Chọn tiến trình khác để cho phép nó thực hiện

v  Cập nhật PCB của tiến trình vừa thực hiện

v  Cập nhật thông tin liên quan đến quản lý bộ nhớ

v  Khôi phục lại ngữ cảnh của processor

 

Tài nguyên găng (Critical Resource)

v Tài nguyên găng?

§   Những tài nguyên đýợc HĐH chia sẻ cho nhiều tiến trình hoạt động đồng thời dùng chung mà có nguy cõ tranh chấp giữa các tiến trình này khi sử dụng chúng

v Tài nguyên găng có thể là tài nguyên phần cứng hoặc phần mềm, có thể là tài nguyên phân chia đýợc hoặc không phân chia đýợc

Đoạn găng(Critical Section)

v Các đoạn code trong các chýõng trình dùng để truy cập đến tài nguyên găng đýợc gọi là đoạn găng.

v Để hạn chế lỗi có thể xảy ra do sử dụng tài nguyên găng, tại 1 thời điểm HĐH chỉ cho 1 tiến trình nằm trong đoạn găng

v HĐH có cõ chế điều độ tiến trình qua đoạn găng

Yêu cầu của công tác điều độ tiến trình qua đoạn găng

v  Tại 1 thời điểm chỉ cho phép 1 tiến trình nằm trong đoạn găng, các tiến trình khác có nhu cầu vào đoạn găng phải chờ

v  Tiến trình chờ ngoài đoạn găng không đýợc ngăn cản các tiến trình khác vào đoạn găng

v  Không có tiến trình nào phải chờ lâu để đýợc vào đoạn găng

v  Đánh thức các tiến trình trong hàng đợi để tạo điều kiện cho nó vào đoạn găng khi tài nguyên găng đýợc giải phóng

 

a. Các giải pháp phần cứng

Dùng cặp chỉ thị STI(setting interrupt)

và CLI (clean interrupt)

 

Ví dụ:

Procedure P(i: integer)

    begin

          repeat

                   CLI;

                             <đoạn găng của p>;

                   STI;

                             <Đoạn không găng>;

          until .F.

    end;

Thank you for listening!