He dieu hanh 5
Chia sẻ bởi Mr Quân |
Ngày 29/04/2019 |
65
Chia sẻ tài liệu: He dieu hanh 5 thuộc Bài giảng khác
Nội dung tài liệu:
Chương 5: Quản lý tiến trình
Khái niệm tiến trình
Các trạng thái của tiến trình
Cài đặt tiến trình
Tiểu trình
Lập lịch các tiến trình
Đồng bộ hóa tiến trình
Khái niệm tiến trình
Trong hệ thống đa chương có thể thể thực hiện nhiều tác vụ đồng thời.
Việc thực hiện đồng thời này được hiện bằng cách chuyển đổi CPU qua lại giữa các chương trình. Điều này tạo cảm giác có nhiều chương trình thực hiện đồng thời.
Trong hệ thống như vậy tất cả phần mềm được tổ chức thành một số tiến trình.
Một tiến trình là một chương trình đang được xử lý, sở hữu con trỏ lệnh , tập các thanh ghi, biến và để hoàn thành nhiệm vụ của mình một tiến trình phải sử dụng các tài nguyên máy tính như CPU, bộ nhớ chính, các tập tin và thiết bị nhập xuất.
Khái niệm tiến trình (tt)
Ý tưởng là có thể xem như mỗi tiến trình sở hữu một CPU ảo cho riêng mình, nhưng trong thực tế chỉ có một bộ xử lý thật sự được chuyển đổi qua lại giữa các tiến trình.
Hệ điều hành chịu trách nhiệm sử dụng một thuật toán điều phối để quyết định thời điểm cần dừng một tiến trình để thực hiện một tiến trình khác
Các trạng thái của tiến trình
Trạng thái của một tiến trình tại một thời điểm được xác định bằng hoạt động hiện thời của tiến trính đó.
Tại một thời điểm một tiến trình có thể nhận một trong các trạng thái sau đây:
Mới tạo: Tiến trình đang được tạo lập.
Running: các chỉ thị của tiến trình đang được xử lý.
Blocked: Tiến trình chờ được cấp phát một tài nguyên hay chờ một sự kiện nào đó xảy ra.
Ready: Tiến trình chờ cấp phát CPU để xử lý.
Kết thúc : Tiến trình hoàn tất xử lý.
Các trạng thái của tiến trình
Mô hình chuyển đổi giữa các trạng thái:
Các trạng thái của tiến trình (tt)
(1) Tiến trình mới tạo được đưa vào hệ thống.
(2) Bộ lập lịch cấp phát cho tiến trình một khoảng thời gian sử dụng CPU
(3) Tiến trình kết thúc
(4) Tiến trình yêu cầu một tài nguyên nhưng chưa được đáp ứng hoặc phải chờ thao tác nhập xuất.
(5) Bộ lập lịch thu hồi CPU và cấp phát cho tiến trình khác
(6) Tài nguyên mà tiến trình yêu cầu đã được cấp phát hay thao tác nhập xuất đã hoàn tất.
Cài đặt 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 như sau:
Chỉ danh của tiến trình: Để phân biệt các tiến trình
Trạng thái tiến trình: Xác định hoạt động hiện hành của tiến trình
Ngữ cảnh của tiến trình: quản lý các tài nguyên của tiến trình:
Trạng thái CPU : nội dung các thanh ghi.
Bộ nhớ chính: Danh sách cácô nhớ được cấp phát cho tiến trình.
Tài nguyên sử dụng: Danh sách các tài nguyên hệ thống mà tiến trình đang sử dụng.
Tài nguyên tạo lập: Danh sách tài nguyên do tiến trình tạo lập.
Cài đặt tiến trình(tt)
Thông tin giao tiếp: 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:
Tiến trình cha: Tiến trình tạo lập tiến trình này.
Tiến trình con: Các tiến trình do tiến trình này tạo lập.
Độ ưu tiên: Giúp bộ lập lịch lựa chọn tiến trình được cấp pháp CPU.
Thông tin thống kê: thống kê về hoạt động của tiến trình: thời gian sử dụng CPU, thời gian chờ.
Tiểu trình
Trong hệ điều hành mỗi tiến trình có không gian địa chỉ và có một dòng xử lý, nhưng đôi khi người sử dụng mốn có nhiều dòng xử lý cùng chia xẻ trong cùng không gian địa chỉ và các dòng xử lý này hoạt động song song tương tư như các tiến trình phân biệt khác.
Mỗi dòng xử lý phân biệt này gọi là một tiểu trình.
Mỗi tiểu trình xử lý tuần tự đoạn mã của minh và sở hữu con trỏ lệnh tập các thanh ghi, stack riêng. Các tiểu trình chia sẻ CPU như các tiến trình độc lập.
Một tiến trình có thể sở hữu nhiều tiểu trình .
Các tiểu trình trong một tiến trình có thể chia sẻ tài nguyên của tiến trình cha ( các biến toàn cục)
Lập lịch tiến trình
Trong hệ thống đa nhiệm tại một thời điểm có thể nhiều tiến trình đồng thời sẵn sàng để xử lý. Mục tiêu là chuyển đổi CPU qua lại các tiến trình thường xuyên.
Để thực hiện điều này hệ điều hành phải lựa chọn tiến trình kếtiếp để xử lý. Bộ lập lịch sẽ sử dụng thuật toán để thực hiện.
Mục tiêu của bộ lập lịch: Hệ điều hành xây dựng nhiều chiến lược khác nhau thực hiện lập lịch nhưng phải đạt các mục tiệu như sau:
Sự công bằng: Các tiến trình chia sẻ CPU một cách công bằng. Không tiến trình nào chờ vô hạn mới được cấp pháp CPU
Tính hiệu quả: Hệ thống phải tận dụng CPU 100% thời gian
Thời gain đáp ứng hợp lý: Cực tiểu hóa thời gian hồi đáp cho cac tương tác của người sử dụng.
Lập lịch tiến trình(tt)
Thời gian lưu lại hệ thống : Cực tiểu hóa thời gian hoàn tất các tác vụ xử lý theo lô.
Thông lượng tối đa: Cực đại hóa số công việc được xử lý trong một đơn vị thời gian
Tất cả mục tiêu trên thường không thỏa hết vì chính bản thân chúng có sự mâu thuẫn với nhau.
Lập lịch tiến trình:
Hệ điều hành tổ chức một danh sách chứa các tiến trình đang sẵng sàng
Hệ điều hành sẽ chọn một tiến trình trong danh sách sẵng sàng để cấp phát CPU.
Các chiến lược lập lịch tiến trình:
Lập lịch tiến trình(tt)
Chiến lược FIFO
CPU được cấp phát cho tiến trình đầu tiên trong danh sách sẵn sàng- là tiến trình được đưa vào hệ thống sớm nhất.
Ví dụ:
Lập lịch tiến trình(tt)
Chiến lược FIFO:
Thứ tự cấp phát CPU cho các tiến trình:
Thời gian chờ được xử lý của P1 : 0
Thời gian chờ được xử lý của P2 : 24-1=23
Thời gian chờ được xử lý của P3 : 24+3 -2 =25
Thời gian chờ trung bình là : (0+ 23+ 25)/3 =16 milisecondes
Thời gian chờ trung bình không đạt cực tiểu và xảy ra hiện tượng tích luỹ thời gian tất cả tiến trình phải chờ một tiến trình có yêu cầu thời dài kết thúc.
Lập lịch tiến trình(tt)
Chiến lược Round Robin:
Trong chiến lược này danh sách sẵn sàng được sử dụng như danh sách vòng. Bộ điều lập lịch lần lượt cấp phát cho từng tiến trình trong danh sách một khoảng thời gian sử dụng CPU gọi là Quantum
Khi một tiến trình sử dụng hết thời gian Quantum dành cho nó thì hệ điều hành thu hồi CPU cấp cho tiến trình khác trong danh sách.
Nếu tiến trình bị Blocked hoặc kết thúc trước khi hết Quantum thì hệ điều hành cũng hu hồi CPU.
Nếu một tiến trình sử dụng hết Quantum mà chưa xử lý xong sẽ được đưa vào cuối danh sách sẵng sàng để chờ cấp phát CPU lần sau.
Lập lịch tiến trình(tt)
Ví dụ:
Với Quantum = 4 thứ tự cấp phát CPU như sau:
Thời gian chở xử lý P1: 0
Thời gian chờ xử lý P2 : 4-1=3
Thời gian chờ xử lý P3: 7-2 = 5
Thời gian chờ xử lý P1 lần sau: 10-4=6
Thời gian chờ trung bình : (0+3+5+6)/3 =4.66 Milisecondes
Lập lịch tiến trình(tt)
Thời gian của Q quá bé thì chuyển đổi CPU giữa các tiến trình quá nhiều khiến việc sử dụng CPU không hiệu quả.
Nếu Q quá lớn thì tăng thời gian hồi đáp và giảm khả năng tương tác của hệ thống
Chiến lược gán độ ưu tiên
Mỗi tiến trình được gán một độ ưu tiên tương ứng, tiến trình nào có độ ưu tiên cao hơn sẽ được chọn cấp phát CPU đầu tiên.
Độ ưu tiên được định nghĩa trong nội tại hoặc từ bên ngoài.
Chiến lược độ ưu tiên không độc quyền: Khi một tiến trình được đưa vào danh sách sẵn sàng , độ ưu tiên của nó được so sánh với độ ưu tiên của tiến trình đang xử lý. Bộ lập lịch sẽ thu hồi CPU từ tiến trình hiện hành để cấp phát cho tiến trình mới nếu độ ưu tiên của nó cao hơn độ ưu tiên của tiến trình hiện hành
Chiến lược độ ưu tiên độc quyền: CPU vẫn được cấp phát cho tiến trình hiện hành mặc dù tiến trình mới vào có độ ưu tiên ccao hơn độ ưu tiên của tiến trình hiện hành.
Lập lịch tiến trình(tt)
Ví dụ : Chiến lược độ ưu tiên độc quyền
Thứ tự cấp phát CPU như sau:
Lập lịch tiến trình(tt)
Ví dụ : Chiến lược độ ưu tiên không độc quyền
Thứ tự cấp phát CPU như sau:
Lập lịch tiến trình(tt)
Với chiến lược này tiến trình có độ ưu tiên thấp sẽ đợi CPU vô hạn. Để tránh trường hợp này thì bộ lập lịch phải giảm dần độ ưu tiên của các tiến trình sau một chu kỳ thời gian.
Chiến lược công việc ngắn nhất được thực hiện trước:
Đây là thuật giải dành cho hệ thống xử lý theo lô, khi mà thời gian chạy của mỗi công việc được biết trước.
Giả sử a, b, c, d lần lượt là thời gian của 4 công việc . Nếu cho 4 công việc này chạy theo thứ tự đó thì thời gian chạy trung bình là :
(4a+3b+2c+d ) /4 .
Dễ dàng thấy là nếu chọn công việc ngắn cho chạy trước thì giá trị thời gian chạy trung bình là nhỏ nhất.
Đồng bộ hóa tiến trình
Sự liên lạc giữa các tiến trình
Trong môi trường đa nhiệm các tiến trình không chạy độc lập mà thường xuyên có nhu cầu trao đổi thông tin với nhau.
Nguyên tắc chung trao đổi thông tin giữa các tiến trình: Sử dụng vùng nhớ được chia sẻ, Trao đổi thông điệp.
Vấn đề nảy sinh : xảy ra hiện tượng đua nhau sử dụng vùng nhớ chia xẻ dẫn đến kết quả không chính xác - Cần phải đồng bộ hóa tiến trình.
Điều kiện đua: Nếu có nhiều tiến trình đọc , ghi dữ liệu vào vùng nhớ dùng chung và kết quả cuối cùng phụ thuộc thời điểm tiến trình nào chạy thật sự gọi là điều kiện đua.
Vùng găng:
Để tránh điều kiện đua, nếu hệ điều hành không cho phép có nhiều tiến trình đọc hoặc ghi vào vùng nhớ lưu trữ chung tại cùng một thời điểm cần phải đạt sự loại trừ lẫn nhau
Một phần nào đó của chương trình mà tại đó thực hiện truy cập đến vùng nhớ dùng chung gọi là vùng găng
Đồng bộ hóa tiến trình(tt)
Để tránh điều kiện đua thì hệ điều hành phải được thiết kế sao cho không cho phép 2 hay nhiều hơn tiến trình đồng thời trong vùng găng.
Bốn điều kiện cần đảm bảo để thiết kế hệ điều hành cho phép nhiều tiến trình sử dụng vùng nhớ dùng chung một cách đúng đắn và hiệu quả:
(1) Không cho phép có nhiều hơn một tiến trình đồng thời trong vùng găng.
(2) Khi lập trình các tiến trình không được phép có bất kỳ giả định nào về tốc độ CPU và số lượng CPU.
(3) Không cho phép một tiến trình ở ngoài vùng găng của mình làm Blocked một tiến trình khác.
(4) Không cho phép bất kỳ một tiến trình nào đợi thời gian quá lâu mới có thể vào vùng găng của mình.
Đồng bộ hóa tiến trình(tt)
Các phương pháp thực hiện loại trừ nhau vào vùng găng
Dùng biến khóa:
Hệ điều hành sử dụng một biến dùng chung, gọi là biến khóa lock được khởi tạo =0. Khi một tiến trình muốn vào vùng găng, nó thực hiện kiểm tra biến lock
int lock =0;
if (lock==0)
{ lock =1;
tiến trình trong vùng găng;
}
else
{ tiến trình đợi cho đến khi lock =0
}
Hãy thảo luận giải pháp
Đồng bộ hóa tiến trình(tt)
Các phương pháp thực hiện loại trừ nhau vào vùng găng
Luân phiên ngặt:
Ý tưởng: Dùng một biến dùng chung turn=0; và mỗi tiến trình có đoạn mã sau:
whie (TRUE) while(TRUE)
{ {
while (turn !=0); while(turn !=1);
Tronggăng(); TrongGăng();
turn=1; turn =0;
ngoàigăng(); NgoàiGăng();
} }
Hãy thảo luận!
Đồng bộ hóa tiến trình(tt)
Các phương pháp thực hiện loại trừ nhau vào vùng găng
Giải pháp Peterson
#define FALSE 0
#define TRUE 1
#define N 2
int turn;
int interested[N]; /* khởi gán bằng FALSE*/
void Vàogăng(int Process)
{
int other;
other = 1- Process;
interested[Process]= TRUE;
turn = Process;
while (turn ==Process && interested[other] ==TRUE);
}
Đồng bộ hóa tiến trình(tt)
Các phương pháp thực hiện loại trừ nhau vào vùng găng
void RaGăng(int Process)
{
interested[Process]=FALSE;
}
Khi một tiến trình nào đó muốn vào vùng găng thi gọi hàm Vàogăng và truyền tham số là số hiệu tiến trình.
Khi tiến trình muốn ra khỏi vùng găng nó gọi hàm RaGăng
Hãy thảo luận!
Đồng bộ hóa tiến trình(tt)
Các phương pháp thực hiện loại trừ nhau vào vùng găng
Giải pháp gọi lời gọi hệ thống SLEEP và WAKEUP
Mặc dù giải pháp Peterson là chấp nhận được vì thỏa mãn 4 điều kiện nhưng bị hàn chế:
1. Khi một tiến trình đợi vào vùng găng tiến trình vẫn sử dụng thời gian CPU – Lãng phí CPU.
2. Khi đưa ra khái niệm độ ưu tiên cho các tiến trình giải pháp Peterson không đáp ứng được. (xét trường hợp tiến trình có độ ưu tiên thấp hơn trong vùng găng và tiến trình có độ ưu tiên cao đợi vào vùng găng.)
Giải pháp gọi lời gọi hệ thống SLEPP vào WAKEUP sẽ làm blocked tiến trình đợi vào vùng găng.
Đồng bộ hóa tiến trình(tt)
Các phương pháp thực hiện loại trừ nhau vào vùng găng
SLEEP: Chuyển tiến trình gọi nó về trạng thái blocked cho đến khi tiến trình khác gởi đến nó tín hiệu đổi trạng thái ( WAKEUP)
WAKEUP(Process) : Chuyển tiến trình Process về trạng thái Ready (tiến trình đã gọi SLEEP trước đó)
Xét bài toán : “Sản xuất – tiêu thụ “: Có hai tiến trình SảnXuất và TiêuThụ dùng chung buffer có kích thước cố định. Tiến trình SảnXuất đặt sản phẩm vào buffer nếu buffer còn trống. Tiến trình TiêuThụ lấy sản phẩm từ buffer nếu buffer khác rỗng.
#define N 100
int count=0;
void SảnXuất(void)
{
int item;
Đồng bộ hóa tiến trình(tt)
Các phương pháp thực hiện loại trừ nhau vào vùng găng
while (TRUE)
{
SảnXuấtSảnPhẩm(&Item);
if (count == N) SLEEP();
ĐặtSảnPhẩm(Item);
count++;
if (count == 1) WAKEUP(TieuThụ);
}
}
Đồng bộ hóa tiến trình(tt)
Các phương pháp thực hiện loại trừ nhau vào vùng găng
void TiêuThụ(void)
{
int Item;
while( TRUE)
{
if (count == 0) SLEEP();
LấySảnPhẩm(&Item);
count--;
if (count == N-1) WAKEUP (SảnXuất);
TiêuThụsảnPhẩm(Item);
}
}
Hãy thảo luận !
Đồng bộ hóa tiến trình(tt)
Các phương pháp thực hiện loại trừ nhau vào vùng găng
Hệ thống có thể dẫn đến tình trạng Deadlock.
Do sử dụng biến dùng chung count không được thực hiện theo thao tác nguyên tử. Kết quả là tín hiệu WAKEUP bị mất khi tiến trình được WAKEUP chưa thật sự SLEEP.
Cần duy trì một biến đếm cho mỗi tiến trình để đếm tín hiệu WAKEUP được gởi đến từ tiến trình khác . Mỗi khi gọi SLEEP tiến trình kiểm tra biến đếm , nếu biến đếm >0 thì giảm biến đếm xuống 1 và tiến trình vẫn không bị blocked.
Đó chính là ý tưởng để xây dựng khái niệm Semaphore
Đồng bộ hóa tiến trình(tt)
Các phương pháp thực hiện loại trừ nhau vào vùng găng
Semaphore:
Semaphore là một kiểu nguyên không âm. Một semaphore s =0 chỉ ra rằng không tín hiệu WAKEUP nào được gởi đến. Có hai thao tác nguyê tử trên semaphore được định nghĩa như sau:
DOWN(s) : if (s >0) s=s-1;
else SLEEP();
UP(s): if ( s >0 ) s=s+1;
else nếu có một hoặc nhiều tiến trình đang bị Blocked trên semaphore s . Hệ điều hành chọn ngẫu nhiên một tiến trình cho phép thoát khỏi trạng thái Blocked.
ngược lại: không có tiến trình nào Blocked trên s thì: s= s+1 ;
Trong khi đó s vẫn =0.
Đồng bộ hóa tiến trình(tt)
Tất cả công đoạn kiểm tra giá trị s, thay đổi s, gọi SLEEP được tích hợp thành một thao tác duy nhất không phân chia được- gọi là thao tác nguyên tử .
Một semaphore s được khởi tạo =1 và được sử dụng bởi nhiều tiến trình để đảm bảo chỉ một trong chúng là vào được vùng găng tại một thời điểm gọi là semaphore nhị phân. Vì vậy mỗi tiến trình chỉ cần gọi toán tử DOWN(s) trước khi vào vùng găng và gọi UP(s) sau khi ra khỏi vùng găng thì có thể đảm bảo được sự loại trừ lẫn nhau.
các loại semaphore khác gọi là semaphore đồng bộ hóa, nó đảm bảo một dãy các sự kiện nào đó là xuất hiện hoặc không xuất hiện.
Đồng bộ hóa tiến trình(tt)
Áp dụng Semaphore để giải quyết bài toán Sản suất – tiêu thụ
#define N 100
typedef int Semaphore;
Semaphore Mutex = 1;
Semaphore Empty =N;
Semaphore Full = 0;
void SảnXuất (void)
{
int Item;
while(TRUE)
{
sảnXuấtSảnPhẩm(&Item);
down(&Empty);
down(&Mutex);
Đồng bộ hóa tiến trình(tt)
ĐặtSảnPhẩm(Item);
up(&Mutex);
up(&Full);
}
}
void TiêuThụ (void)
{ int Item;
while(TRUE)
{ down(&Full);
down(&Mutex);
LấySảnPhẩm(&Item);
up(&Mutex);
up(&Empty);
TiêuThụsảnPhẩm(Item);
}
}
Đồng bộ hóa tiến trình(tt)
Áp dụng Semaphore để giải quyết bài toán cổ điển
Bài toán” Bữa ăn tối của các nhà hiền triết”
Có 5 nhà hiền triết ngồi quanh một bàn tròn trong một bữa ăn tối. Mỗi người có một dĩa mì Spaghetti. Mỗi người cần phải có 2 nĩa để có thể ăn mì. Giữa 2 dĩa có một nĩa.
Giả định rằng cuộc đời của nhà hiền triết chỉ luân phiên nhau 2 hành vi: ăn và suy nghĩ. Khi nhà hiền triết cảm thấy đói ông ta muốn lấy 2 nĩa bên trái và phải theo thứ tự nào đó. Nếu lấy được cả 2 nĩa ông ta bắt đầu ăn. Sau đó đặt nĩa xuống và tiếp tục suy nghĩ.
Yêu cầu viết chương trình cho mỗi nhà hiền triết sao cho không bị “kẹt”.
Đồng bộ hóa tiến trình(tt)
Tìm lỗi đoạn chương trình sau:
#define N 5
void HiềnTriết (int i)
{
while(TRUE)
{
SuyNghĩ();
LấyNĩa(i);
LấyNĩa((i+1)%N); // Nhà hiền triết I lấy nĩa bên trái, phải
Ă n();
ĐặtNĩa(i);
ĐặtNĩa((i+1)%N);
}
}
Đồng bộ hóa tiến trình(tt)
Lời giải 1
#define N 5
typedef int Semaphore;
Semaphore Mutex=1;
void HiềnTriết (int i)
{ while(TRUE)
{ SuyNghĩ();
down(&Mutex);
LấyNĩa(i);
LấyNĩa((i+1)%N); // Nhà hiền triết I lấy nĩa bên trái, phải
Ă n();
ĐặtNĩa(i);
ĐặtNĩa((i+1)%N);
up(&Mutex);
}
}
Đồng bộ hóa tiến trình(tt)
Lời giải trên đúng nhưng không tối ưu tài nguyên
Lời giải 2
#define N 5
#define LEFT (i-1)%N
#define RIGHT (i+1)%N
#define THINKING 0
#define HUNGRY 1
#define EATING 2
typedef int Semaphore;
int State [N};
Semaphore Mutex=1;
Semaphore S[N];// Khởi gán =0
Đồng bộ hóa tiến trình(tt)
void HiềnTriết (int i)
{ while(TRUE)
{ SuyNghĩ();
LấyNĩa(i);// Lấy nĩa trái và phải
Ă n();
ĐặtNĩa(i);
}
}
void LấyNĩa (int i)
{ down (&Mutex);
State[i]=HUNGRY;
Test(i);
up(&Mutex);
down(&S[i]);
return ;
}
Đồng bộ hóa tiến trình(tt)
void ĐặtNĩa (int i)
{ down (&Mutex);
State[i]=THINKING;
Test(LEFT);
Test(RIGHT);
up(&Mutex);
return ;
}
void Test (int i)
{ if( State[i]==HUNGRY && State[LEFT]!=EATING && State[RIGHT]!=EATING)
{ State[i]=EATING;
up(&S[i]);
}
}
Đồng bộ hóa tiến trình(tt)
Áp dụng Semaphore để giải quyết bài toán cổ điển
Bài toán” Độc giả và nhà văn”
Một cơ sở dữ liệu mà tiến trình muốn đọc(độc giả) hoặc ghi lên đó (nhà văn) . Hệ thống cho phép đồng thời có nhiều tiến trình đọc cơ sở dữ liệu nhưng chỉ duy nhất một tiến trình ghi lên CSDL tại một thời điểm. Khi có một tiến trình ghi lên CSDL thì không có tiến trình nào được phép truy cập đến CSDL kể cả tiến trình đọc .
Yêu cầu: Lập trình cho hai tiến trình “Độc giả “ và “nhà văn”
Đồng bộ hóa tiến trình(tt)
Áp dụng Semaphore để giải quyết bài toán cổ điển
Bài toán” Độc giả và nhà văn”
Một cơ sở dữ liệu mà tiến trình muốn đọc(độc giả) hoặc ghi lên đó (nhà văn) . Hệ thống cho phép đồng thời có nhiều tiến trình đọc cơ sở dữ liệu nhưng chỉ duy nhất một tiến trình ghi lên CSDL tại một thời điểm. Khi có một tiến trình ghi lên CSDL thì không có tiến trình nào được phép truy cập đến CSDL kể cả tiến trình đọc .
Yêu cầu: Lập trình cho hai tiến trình “Độc giả “ và “nhà văn”
Seamphore Mutex =1;
Semaphore Db=1;// Truy cập vào DBF của tiến trình Writer
int rc; // Đếm số tiến trình đọc
Đồng bộ hóa tiến trình(tt)
void Reader (void )
{ while (TRUE)
{ down (Mutex);
rc= rc+1;
if ( rc==1)
down(db);
up(Mutex);
ReadDBF();
down(Mutex);
rc=rc-1;
if (rc==0)
up(db);
up(Mutex);
}
}
Đồng bộ hóa tiến trình(tt)
void Writer (void )
{ while (TRUE)
{ CreateData();
down(db);
WriteData();
up(db);
}
}
Khái niệm tiến trình
Các trạng thái của tiến trình
Cài đặt tiến trình
Tiểu trình
Lập lịch các tiến trình
Đồng bộ hóa tiến trình
Khái niệm tiến trình
Trong hệ thống đa chương có thể thể thực hiện nhiều tác vụ đồng thời.
Việc thực hiện đồng thời này được hiện bằng cách chuyển đổi CPU qua lại giữa các chương trình. Điều này tạo cảm giác có nhiều chương trình thực hiện đồng thời.
Trong hệ thống như vậy tất cả phần mềm được tổ chức thành một số tiến trình.
Một tiến trình là một chương trình đang được xử lý, sở hữu con trỏ lệnh , tập các thanh ghi, biến và để hoàn thành nhiệm vụ của mình một tiến trình phải sử dụng các tài nguyên máy tính như CPU, bộ nhớ chính, các tập tin và thiết bị nhập xuất.
Khái niệm tiến trình (tt)
Ý tưởng là có thể xem như mỗi tiến trình sở hữu một CPU ảo cho riêng mình, nhưng trong thực tế chỉ có một bộ xử lý thật sự được chuyển đổi qua lại giữa các tiến trình.
Hệ điều hành chịu trách nhiệm sử dụng một thuật toán điều phối để quyết định thời điểm cần dừng một tiến trình để thực hiện một tiến trình khác
Các trạng thái của tiến trình
Trạng thái của một tiến trình tại một thời điểm được xác định bằng hoạt động hiện thời của tiến trính đó.
Tại một thời điểm một tiến trình có thể nhận một trong các trạng thái sau đây:
Mới tạo: Tiến trình đang được tạo lập.
Running: các chỉ thị của tiến trình đang được xử lý.
Blocked: Tiến trình chờ được cấp phát một tài nguyên hay chờ một sự kiện nào đó xảy ra.
Ready: Tiến trình chờ cấp phát CPU để xử lý.
Kết thúc : Tiến trình hoàn tất xử lý.
Các trạng thái của tiến trình
Mô hình chuyển đổi giữa các trạng thái:
Các trạng thái của tiến trình (tt)
(1) Tiến trình mới tạo được đưa vào hệ thống.
(2) Bộ lập lịch cấp phát cho tiến trình một khoảng thời gian sử dụng CPU
(3) Tiến trình kết thúc
(4) Tiến trình yêu cầu một tài nguyên nhưng chưa được đáp ứng hoặc phải chờ thao tác nhập xuất.
(5) Bộ lập lịch thu hồi CPU và cấp phát cho tiến trình khác
(6) Tài nguyên mà tiến trình yêu cầu đã được cấp phát hay thao tác nhập xuất đã hoàn tất.
Cài đặt 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 như sau:
Chỉ danh của tiến trình: Để phân biệt các tiến trình
Trạng thái tiến trình: Xác định hoạt động hiện hành của tiến trình
Ngữ cảnh của tiến trình: quản lý các tài nguyên của tiến trình:
Trạng thái CPU : nội dung các thanh ghi.
Bộ nhớ chính: Danh sách cácô nhớ được cấp phát cho tiến trình.
Tài nguyên sử dụng: Danh sách các tài nguyên hệ thống mà tiến trình đang sử dụng.
Tài nguyên tạo lập: Danh sách tài nguyên do tiến trình tạo lập.
Cài đặt tiến trình(tt)
Thông tin giao tiếp: 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:
Tiến trình cha: Tiến trình tạo lập tiến trình này.
Tiến trình con: Các tiến trình do tiến trình này tạo lập.
Độ ưu tiên: Giúp bộ lập lịch lựa chọn tiến trình được cấp pháp CPU.
Thông tin thống kê: thống kê về hoạt động của tiến trình: thời gian sử dụng CPU, thời gian chờ.
Tiểu trình
Trong hệ điều hành mỗi tiến trình có không gian địa chỉ và có một dòng xử lý, nhưng đôi khi người sử dụng mốn có nhiều dòng xử lý cùng chia xẻ trong cùng không gian địa chỉ và các dòng xử lý này hoạt động song song tương tư như các tiến trình phân biệt khác.
Mỗi dòng xử lý phân biệt này gọi là một tiểu trình.
Mỗi tiểu trình xử lý tuần tự đoạn mã của minh và sở hữu con trỏ lệnh tập các thanh ghi, stack riêng. Các tiểu trình chia sẻ CPU như các tiến trình độc lập.
Một tiến trình có thể sở hữu nhiều tiểu trình .
Các tiểu trình trong một tiến trình có thể chia sẻ tài nguyên của tiến trình cha ( các biến toàn cục)
Lập lịch tiến trình
Trong hệ thống đa nhiệm tại một thời điểm có thể nhiều tiến trình đồng thời sẵn sàng để xử lý. Mục tiêu là chuyển đổi CPU qua lại các tiến trình thường xuyên.
Để thực hiện điều này hệ điều hành phải lựa chọn tiến trình kếtiếp để xử lý. Bộ lập lịch sẽ sử dụng thuật toán để thực hiện.
Mục tiêu của bộ lập lịch: Hệ điều hành xây dựng nhiều chiến lược khác nhau thực hiện lập lịch nhưng phải đạt các mục tiệu như sau:
Sự công bằng: Các tiến trình chia sẻ CPU một cách công bằng. Không tiến trình nào chờ vô hạn mới được cấp pháp CPU
Tính hiệu quả: Hệ thống phải tận dụng CPU 100% thời gian
Thời gain đáp ứng hợp lý: Cực tiểu hóa thời gian hồi đáp cho cac tương tác của người sử dụng.
Lập lịch tiến trình(tt)
Thời gian lưu lại hệ thống : Cực tiểu hóa thời gian hoàn tất các tác vụ xử lý theo lô.
Thông lượng tối đa: Cực đại hóa số công việc được xử lý trong một đơn vị thời gian
Tất cả mục tiêu trên thường không thỏa hết vì chính bản thân chúng có sự mâu thuẫn với nhau.
Lập lịch tiến trình:
Hệ điều hành tổ chức một danh sách chứa các tiến trình đang sẵng sàng
Hệ điều hành sẽ chọn một tiến trình trong danh sách sẵng sàng để cấp phát CPU.
Các chiến lược lập lịch tiến trình:
Lập lịch tiến trình(tt)
Chiến lược FIFO
CPU được cấp phát cho tiến trình đầu tiên trong danh sách sẵn sàng- là tiến trình được đưa vào hệ thống sớm nhất.
Ví dụ:
Lập lịch tiến trình(tt)
Chiến lược FIFO:
Thứ tự cấp phát CPU cho các tiến trình:
Thời gian chờ được xử lý của P1 : 0
Thời gian chờ được xử lý của P2 : 24-1=23
Thời gian chờ được xử lý của P3 : 24+3 -2 =25
Thời gian chờ trung bình là : (0+ 23+ 25)/3 =16 milisecondes
Thời gian chờ trung bình không đạt cực tiểu và xảy ra hiện tượng tích luỹ thời gian tất cả tiến trình phải chờ một tiến trình có yêu cầu thời dài kết thúc.
Lập lịch tiến trình(tt)
Chiến lược Round Robin:
Trong chiến lược này danh sách sẵn sàng được sử dụng như danh sách vòng. Bộ điều lập lịch lần lượt cấp phát cho từng tiến trình trong danh sách một khoảng thời gian sử dụng CPU gọi là Quantum
Khi một tiến trình sử dụng hết thời gian Quantum dành cho nó thì hệ điều hành thu hồi CPU cấp cho tiến trình khác trong danh sách.
Nếu tiến trình bị Blocked hoặc kết thúc trước khi hết Quantum thì hệ điều hành cũng hu hồi CPU.
Nếu một tiến trình sử dụng hết Quantum mà chưa xử lý xong sẽ được đưa vào cuối danh sách sẵng sàng để chờ cấp phát CPU lần sau.
Lập lịch tiến trình(tt)
Ví dụ:
Với Quantum = 4 thứ tự cấp phát CPU như sau:
Thời gian chở xử lý P1: 0
Thời gian chờ xử lý P2 : 4-1=3
Thời gian chờ xử lý P3: 7-2 = 5
Thời gian chờ xử lý P1 lần sau: 10-4=6
Thời gian chờ trung bình : (0+3+5+6)/3 =4.66 Milisecondes
Lập lịch tiến trình(tt)
Thời gian của Q quá bé thì chuyển đổi CPU giữa các tiến trình quá nhiều khiến việc sử dụng CPU không hiệu quả.
Nếu Q quá lớn thì tăng thời gian hồi đáp và giảm khả năng tương tác của hệ thống
Chiến lược gán độ ưu tiên
Mỗi tiến trình được gán một độ ưu tiên tương ứng, tiến trình nào có độ ưu tiên cao hơn sẽ được chọn cấp phát CPU đầu tiên.
Độ ưu tiên được định nghĩa trong nội tại hoặc từ bên ngoài.
Chiến lược độ ưu tiên không độc quyền: Khi một tiến trình được đưa vào danh sách sẵn sàng , độ ưu tiên của nó được so sánh với độ ưu tiên của tiến trình đang xử lý. Bộ lập lịch sẽ thu hồi CPU từ tiến trình hiện hành để cấp phát cho tiến trình mới nếu độ ưu tiên của nó cao hơn độ ưu tiên của tiến trình hiện hành
Chiến lược độ ưu tiên độc quyền: CPU vẫn được cấp phát cho tiến trình hiện hành mặc dù tiến trình mới vào có độ ưu tiên ccao hơn độ ưu tiên của tiến trình hiện hành.
Lập lịch tiến trình(tt)
Ví dụ : Chiến lược độ ưu tiên độc quyền
Thứ tự cấp phát CPU như sau:
Lập lịch tiến trình(tt)
Ví dụ : Chiến lược độ ưu tiên không độc quyền
Thứ tự cấp phát CPU như sau:
Lập lịch tiến trình(tt)
Với chiến lược này tiến trình có độ ưu tiên thấp sẽ đợi CPU vô hạn. Để tránh trường hợp này thì bộ lập lịch phải giảm dần độ ưu tiên của các tiến trình sau một chu kỳ thời gian.
Chiến lược công việc ngắn nhất được thực hiện trước:
Đây là thuật giải dành cho hệ thống xử lý theo lô, khi mà thời gian chạy của mỗi công việc được biết trước.
Giả sử a, b, c, d lần lượt là thời gian của 4 công việc . Nếu cho 4 công việc này chạy theo thứ tự đó thì thời gian chạy trung bình là :
(4a+3b+2c+d ) /4 .
Dễ dàng thấy là nếu chọn công việc ngắn cho chạy trước thì giá trị thời gian chạy trung bình là nhỏ nhất.
Đồng bộ hóa tiến trình
Sự liên lạc giữa các tiến trình
Trong môi trường đa nhiệm các tiến trình không chạy độc lập mà thường xuyên có nhu cầu trao đổi thông tin với nhau.
Nguyên tắc chung trao đổi thông tin giữa các tiến trình: Sử dụng vùng nhớ được chia sẻ, Trao đổi thông điệp.
Vấn đề nảy sinh : xảy ra hiện tượng đua nhau sử dụng vùng nhớ chia xẻ dẫn đến kết quả không chính xác - Cần phải đồng bộ hóa tiến trình.
Điều kiện đua: Nếu có nhiều tiến trình đọc , ghi dữ liệu vào vùng nhớ dùng chung và kết quả cuối cùng phụ thuộc thời điểm tiến trình nào chạy thật sự gọi là điều kiện đua.
Vùng găng:
Để tránh điều kiện đua, nếu hệ điều hành không cho phép có nhiều tiến trình đọc hoặc ghi vào vùng nhớ lưu trữ chung tại cùng một thời điểm cần phải đạt sự loại trừ lẫn nhau
Một phần nào đó của chương trình mà tại đó thực hiện truy cập đến vùng nhớ dùng chung gọi là vùng găng
Đồng bộ hóa tiến trình(tt)
Để tránh điều kiện đua thì hệ điều hành phải được thiết kế sao cho không cho phép 2 hay nhiều hơn tiến trình đồng thời trong vùng găng.
Bốn điều kiện cần đảm bảo để thiết kế hệ điều hành cho phép nhiều tiến trình sử dụng vùng nhớ dùng chung một cách đúng đắn và hiệu quả:
(1) Không cho phép có nhiều hơn một tiến trình đồng thời trong vùng găng.
(2) Khi lập trình các tiến trình không được phép có bất kỳ giả định nào về tốc độ CPU và số lượng CPU.
(3) Không cho phép một tiến trình ở ngoài vùng găng của mình làm Blocked một tiến trình khác.
(4) Không cho phép bất kỳ một tiến trình nào đợi thời gian quá lâu mới có thể vào vùng găng của mình.
Đồng bộ hóa tiến trình(tt)
Các phương pháp thực hiện loại trừ nhau vào vùng găng
Dùng biến khóa:
Hệ điều hành sử dụng một biến dùng chung, gọi là biến khóa lock được khởi tạo =0. Khi một tiến trình muốn vào vùng găng, nó thực hiện kiểm tra biến lock
int lock =0;
if (lock==0)
{ lock =1;
tiến trình trong vùng găng;
}
else
{ tiến trình đợi cho đến khi lock =0
}
Hãy thảo luận giải pháp
Đồng bộ hóa tiến trình(tt)
Các phương pháp thực hiện loại trừ nhau vào vùng găng
Luân phiên ngặt:
Ý tưởng: Dùng một biến dùng chung turn=0; và mỗi tiến trình có đoạn mã sau:
whie (TRUE) while(TRUE)
{ {
while (turn !=0); while(turn !=1);
Tronggăng(); TrongGăng();
turn=1; turn =0;
ngoàigăng(); NgoàiGăng();
} }
Hãy thảo luận!
Đồng bộ hóa tiến trình(tt)
Các phương pháp thực hiện loại trừ nhau vào vùng găng
Giải pháp Peterson
#define FALSE 0
#define TRUE 1
#define N 2
int turn;
int interested[N]; /* khởi gán bằng FALSE*/
void Vàogăng(int Process)
{
int other;
other = 1- Process;
interested[Process]= TRUE;
turn = Process;
while (turn ==Process && interested[other] ==TRUE);
}
Đồng bộ hóa tiến trình(tt)
Các phương pháp thực hiện loại trừ nhau vào vùng găng
void RaGăng(int Process)
{
interested[Process]=FALSE;
}
Khi một tiến trình nào đó muốn vào vùng găng thi gọi hàm Vàogăng và truyền tham số là số hiệu tiến trình.
Khi tiến trình muốn ra khỏi vùng găng nó gọi hàm RaGăng
Hãy thảo luận!
Đồng bộ hóa tiến trình(tt)
Các phương pháp thực hiện loại trừ nhau vào vùng găng
Giải pháp gọi lời gọi hệ thống SLEEP và WAKEUP
Mặc dù giải pháp Peterson là chấp nhận được vì thỏa mãn 4 điều kiện nhưng bị hàn chế:
1. Khi một tiến trình đợi vào vùng găng tiến trình vẫn sử dụng thời gian CPU – Lãng phí CPU.
2. Khi đưa ra khái niệm độ ưu tiên cho các tiến trình giải pháp Peterson không đáp ứng được. (xét trường hợp tiến trình có độ ưu tiên thấp hơn trong vùng găng và tiến trình có độ ưu tiên cao đợi vào vùng găng.)
Giải pháp gọi lời gọi hệ thống SLEPP vào WAKEUP sẽ làm blocked tiến trình đợi vào vùng găng.
Đồng bộ hóa tiến trình(tt)
Các phương pháp thực hiện loại trừ nhau vào vùng găng
SLEEP: Chuyển tiến trình gọi nó về trạng thái blocked cho đến khi tiến trình khác gởi đến nó tín hiệu đổi trạng thái ( WAKEUP)
WAKEUP(Process) : Chuyển tiến trình Process về trạng thái Ready (tiến trình đã gọi SLEEP trước đó)
Xét bài toán : “Sản xuất – tiêu thụ “: Có hai tiến trình SảnXuất và TiêuThụ dùng chung buffer có kích thước cố định. Tiến trình SảnXuất đặt sản phẩm vào buffer nếu buffer còn trống. Tiến trình TiêuThụ lấy sản phẩm từ buffer nếu buffer khác rỗng.
#define N 100
int count=0;
void SảnXuất(void)
{
int item;
Đồng bộ hóa tiến trình(tt)
Các phương pháp thực hiện loại trừ nhau vào vùng găng
while (TRUE)
{
SảnXuấtSảnPhẩm(&Item);
if (count == N) SLEEP();
ĐặtSảnPhẩm(Item);
count++;
if (count == 1) WAKEUP(TieuThụ);
}
}
Đồng bộ hóa tiến trình(tt)
Các phương pháp thực hiện loại trừ nhau vào vùng găng
void TiêuThụ(void)
{
int Item;
while( TRUE)
{
if (count == 0) SLEEP();
LấySảnPhẩm(&Item);
count--;
if (count == N-1) WAKEUP (SảnXuất);
TiêuThụsảnPhẩm(Item);
}
}
Hãy thảo luận !
Đồng bộ hóa tiến trình(tt)
Các phương pháp thực hiện loại trừ nhau vào vùng găng
Hệ thống có thể dẫn đến tình trạng Deadlock.
Do sử dụng biến dùng chung count không được thực hiện theo thao tác nguyên tử. Kết quả là tín hiệu WAKEUP bị mất khi tiến trình được WAKEUP chưa thật sự SLEEP.
Cần duy trì một biến đếm cho mỗi tiến trình để đếm tín hiệu WAKEUP được gởi đến từ tiến trình khác . Mỗi khi gọi SLEEP tiến trình kiểm tra biến đếm , nếu biến đếm >0 thì giảm biến đếm xuống 1 và tiến trình vẫn không bị blocked.
Đó chính là ý tưởng để xây dựng khái niệm Semaphore
Đồng bộ hóa tiến trình(tt)
Các phương pháp thực hiện loại trừ nhau vào vùng găng
Semaphore:
Semaphore là một kiểu nguyên không âm. Một semaphore s =0 chỉ ra rằng không tín hiệu WAKEUP nào được gởi đến. Có hai thao tác nguyê tử trên semaphore được định nghĩa như sau:
DOWN(s) : if (s >0) s=s-1;
else SLEEP();
UP(s): if ( s >0 ) s=s+1;
else nếu có một hoặc nhiều tiến trình đang bị Blocked trên semaphore s . Hệ điều hành chọn ngẫu nhiên một tiến trình cho phép thoát khỏi trạng thái Blocked.
ngược lại: không có tiến trình nào Blocked trên s thì: s= s+1 ;
Trong khi đó s vẫn =0.
Đồng bộ hóa tiến trình(tt)
Tất cả công đoạn kiểm tra giá trị s, thay đổi s, gọi SLEEP được tích hợp thành một thao tác duy nhất không phân chia được- gọi là thao tác nguyên tử .
Một semaphore s được khởi tạo =1 và được sử dụng bởi nhiều tiến trình để đảm bảo chỉ một trong chúng là vào được vùng găng tại một thời điểm gọi là semaphore nhị phân. Vì vậy mỗi tiến trình chỉ cần gọi toán tử DOWN(s) trước khi vào vùng găng và gọi UP(s) sau khi ra khỏi vùng găng thì có thể đảm bảo được sự loại trừ lẫn nhau.
các loại semaphore khác gọi là semaphore đồng bộ hóa, nó đảm bảo một dãy các sự kiện nào đó là xuất hiện hoặc không xuất hiện.
Đồng bộ hóa tiến trình(tt)
Áp dụng Semaphore để giải quyết bài toán Sản suất – tiêu thụ
#define N 100
typedef int Semaphore;
Semaphore Mutex = 1;
Semaphore Empty =N;
Semaphore Full = 0;
void SảnXuất (void)
{
int Item;
while(TRUE)
{
sảnXuấtSảnPhẩm(&Item);
down(&Empty);
down(&Mutex);
Đồng bộ hóa tiến trình(tt)
ĐặtSảnPhẩm(Item);
up(&Mutex);
up(&Full);
}
}
void TiêuThụ (void)
{ int Item;
while(TRUE)
{ down(&Full);
down(&Mutex);
LấySảnPhẩm(&Item);
up(&Mutex);
up(&Empty);
TiêuThụsảnPhẩm(Item);
}
}
Đồng bộ hóa tiến trình(tt)
Áp dụng Semaphore để giải quyết bài toán cổ điển
Bài toán” Bữa ăn tối của các nhà hiền triết”
Có 5 nhà hiền triết ngồi quanh một bàn tròn trong một bữa ăn tối. Mỗi người có một dĩa mì Spaghetti. Mỗi người cần phải có 2 nĩa để có thể ăn mì. Giữa 2 dĩa có một nĩa.
Giả định rằng cuộc đời của nhà hiền triết chỉ luân phiên nhau 2 hành vi: ăn và suy nghĩ. Khi nhà hiền triết cảm thấy đói ông ta muốn lấy 2 nĩa bên trái và phải theo thứ tự nào đó. Nếu lấy được cả 2 nĩa ông ta bắt đầu ăn. Sau đó đặt nĩa xuống và tiếp tục suy nghĩ.
Yêu cầu viết chương trình cho mỗi nhà hiền triết sao cho không bị “kẹt”.
Đồng bộ hóa tiến trình(tt)
Tìm lỗi đoạn chương trình sau:
#define N 5
void HiềnTriết (int i)
{
while(TRUE)
{
SuyNghĩ();
LấyNĩa(i);
LấyNĩa((i+1)%N); // Nhà hiền triết I lấy nĩa bên trái, phải
Ă n();
ĐặtNĩa(i);
ĐặtNĩa((i+1)%N);
}
}
Đồng bộ hóa tiến trình(tt)
Lời giải 1
#define N 5
typedef int Semaphore;
Semaphore Mutex=1;
void HiềnTriết (int i)
{ while(TRUE)
{ SuyNghĩ();
down(&Mutex);
LấyNĩa(i);
LấyNĩa((i+1)%N); // Nhà hiền triết I lấy nĩa bên trái, phải
Ă n();
ĐặtNĩa(i);
ĐặtNĩa((i+1)%N);
up(&Mutex);
}
}
Đồng bộ hóa tiến trình(tt)
Lời giải trên đúng nhưng không tối ưu tài nguyên
Lời giải 2
#define N 5
#define LEFT (i-1)%N
#define RIGHT (i+1)%N
#define THINKING 0
#define HUNGRY 1
#define EATING 2
typedef int Semaphore;
int State [N};
Semaphore Mutex=1;
Semaphore S[N];// Khởi gán =0
Đồng bộ hóa tiến trình(tt)
void HiềnTriết (int i)
{ while(TRUE)
{ SuyNghĩ();
LấyNĩa(i);// Lấy nĩa trái và phải
Ă n();
ĐặtNĩa(i);
}
}
void LấyNĩa (int i)
{ down (&Mutex);
State[i]=HUNGRY;
Test(i);
up(&Mutex);
down(&S[i]);
return ;
}
Đồng bộ hóa tiến trình(tt)
void ĐặtNĩa (int i)
{ down (&Mutex);
State[i]=THINKING;
Test(LEFT);
Test(RIGHT);
up(&Mutex);
return ;
}
void Test (int i)
{ if( State[i]==HUNGRY && State[LEFT]!=EATING && State[RIGHT]!=EATING)
{ State[i]=EATING;
up(&S[i]);
}
}
Đồng bộ hóa tiến trình(tt)
Áp dụng Semaphore để giải quyết bài toán cổ điển
Bài toán” Độc giả và nhà văn”
Một cơ sở dữ liệu mà tiến trình muốn đọc(độc giả) hoặc ghi lên đó (nhà văn) . Hệ thống cho phép đồng thời có nhiều tiến trình đọc cơ sở dữ liệu nhưng chỉ duy nhất một tiến trình ghi lên CSDL tại một thời điểm. Khi có một tiến trình ghi lên CSDL thì không có tiến trình nào được phép truy cập đến CSDL kể cả tiến trình đọc .
Yêu cầu: Lập trình cho hai tiến trình “Độc giả “ và “nhà văn”
Đồng bộ hóa tiến trình(tt)
Áp dụng Semaphore để giải quyết bài toán cổ điển
Bài toán” Độc giả và nhà văn”
Một cơ sở dữ liệu mà tiến trình muốn đọc(độc giả) hoặc ghi lên đó (nhà văn) . Hệ thống cho phép đồng thời có nhiều tiến trình đọc cơ sở dữ liệu nhưng chỉ duy nhất một tiến trình ghi lên CSDL tại một thời điểm. Khi có một tiến trình ghi lên CSDL thì không có tiến trình nào được phép truy cập đến CSDL kể cả tiến trình đọc .
Yêu cầu: Lập trình cho hai tiến trình “Độc giả “ và “nhà văn”
Seamphore Mutex =1;
Semaphore Db=1;// Truy cập vào DBF của tiến trình Writer
int rc; // Đếm số tiến trình đọc
Đồng bộ hóa tiến trình(tt)
void Reader (void )
{ while (TRUE)
{ down (Mutex);
rc= rc+1;
if ( rc==1)
down(db);
up(Mutex);
ReadDBF();
down(Mutex);
rc=rc-1;
if (rc==0)
up(db);
up(Mutex);
}
}
Đồng bộ hóa tiến trình(tt)
void Writer (void )
{ while (TRUE)
{ CreateData();
down(db);
WriteData();
up(db);
}
}
* Một số tài liệu cũ có thể bị lỗi font khi hiển thị do dùng bộ mã không phải Unikey ...
Người chia sẻ: Mr Quân
Dung lượng: |
Lượt tài: 1
Loại file:
Nguồn : Chưa rõ
(Tài liệu chưa được thẩm định)