Bài giảng Hệ điều hành - Chương 5: Quản lý tiến trình

 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 nhauMộ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ăngDù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ăngLuâ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ăngGiả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ăngGiả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ăngSemaphore:	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ênLờ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);	}	}