Định nghĩa đèn hiệu với 2 tác nguyên Wait(chờ) và Signal(báo hiệu)

dangthihoangly(I12A) 30/3/2013, 14:15

Định nghĩa kiểu Đèn hiệu:
- Đèn hiệu là phương tiện đồng bộ hoá được E.W. Dijkstra đề xuất năm 1965.
- Đèn hiệu được mô tả bằng một biến kiểu nguyên với 2 tác nguyên là Wait (Chờ) và Signal (Báo hiệu):
typedef int semaphore.

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

signal (semaphore S)
{
S ++;
}

- Việc kiểm tra S<= 0 và giảm S(trong Wait) hoặc tăng S(trong Signal) phải được thực hiện trọn vẹn (không xảy ra ngắt trong thời gian thi hành), do đó Wait và Signal được gọi là các tác nguyên (Atomic Operations).

dangthihoangly(I12A) 30/3/2013, 14:15

- Ví dụ có n tiến trình { P0 , P1 ,....., Pn-1 }. Mỗi tiến trình có đoạn mã gọi là Đoạn tương tranh trong đó tiến trình có thể truy cập và thay đổi vùng nhớ, tập tin hay tài nguyên chung.
- Tính Loại trừ lẫn nhau hay Loại trừ tương hỗ (Mutual Exclusion) về phương diện thời gian: Khi có 1 tiến trình đang ở trong Đoạn tương tranh của nó thì không có tiến trình nào khác trong nhóm cũng tại đoạn như vậy, nghĩa là: Mỗi thời điểm chỉ có 1 tiến trình được phép truy cập hoặc thay đổi tài nguyên chung.
- Các tiến trình tương tranh có cấu trúc mã bao gồm Entry Section (Đoạn Đăng nhập), Critical Section (Đoạn Tương tranh), Exit Section (Đoạn Đăng xuất) và các Remainder Section (Đoạn Còn lại).

ChauQuangCam (I22B) 30/3/2013, 15:17

Khái niệm đèn hiệu
- Đèn hiệu là phương tiện đồng bộ hoá được E.W. Dijkstra đề xuất năm 1965.
- Đèn hiệu được mô tả bằng một biến kiểu nguyên với 2 tác nguyên là Wait (Chờ) và Signal (Báo hiệu):

typedef int semaphore; // Định nghĩa kiểu Đèn hiệu
wait (semaphore S)
{
while ( S <= 0 ); // Chờ bận nếu S<=0
S --; // Giảm S đi 1
}

signal (semaphore S)
{
S ++; // Tăng S lên 1
}

-Việc kiểm tra S <= 0 và giảm S (trong Wait) hoặc tăng S (trong Signal) phải được thực hiện trọn vẹn (không xảy ra ngắt trong thời gian thi hành), do đó Wait và Signal được gọi là các tác nguyên (Atomic Operations).

Thảo luận Bài 7 - Page 2 Ssfff

LêAnhNgữ(I22A) 30/3/2013, 15:45

Semaphore
-Định nghĩa: Semaphore là một cờ hiệu trong thực thi đa tuyến, nếu một tuyến cần sử dụng tài nguyên nó sẽ thông báo với semaphore.
-Khởi đầu Semaphore mang giá trị dương. Tuyến yêu cầu sử dụng tài nguyên bằng cách gọi hàm sem_wait(), semaphore sẽ kiểm tra giá trị của mình xem có >0 hay không.
-Nếu Semaphore vẫn còn >0, nó sẽ tự động làm giảm giá trị đi 1 và cho phép tuyến sử dụng tài nguyên.
-Nếu giá trị Semaphore <=0 hệ thống sẽ tạm thời dừng tuyến.
-Khi một tuyến sử dụng xong tài nguyên nó gọi hàm sem_post() để trả quyền sử dụng tài nguyên lại cho Semaphore cấp phát cho lần sử dụng khác.
Ứng dụng Semaphore:
-Bài toán nổi tiếng về tranh chấp tài nguyên dễ hiểu nhất là bài toán “sản xuất – tiêu thụ”.
-Hai tuyến chạy song song nhau. Một tuyến chịu trách nhiệm sản xuất ra sản phẩm. Một tuyến lấy sản phẩm ra để tiêu thụ.

P/s: Ngoài thực tế Semaphore truyền tín hiệu Cờ, sử dụng trong các buổi tập huấn Đoàn, hội, đội.

LêAnhNgữ(I22A) 30/3/2013, 15:49

BuiThucTuan(I22B) đã viết:Edsger Wybe Dijkstra (phát âm tiếng Hà Lan: [ˈɛtsxər ˈwibə ˈdɛɪkstra]; 11 tháng 5, 1930 tại Rotterdam – 6 tháng 8, 2002 tại Nuenen), là nhà khoa học máy tính Hà Lan. Ông được nhận giải thưởng Turing cho các đóng góp có tính chất nền tảng trong lĩnh vực ngôn ngữ lập trình Không lâu trước khi chết, ông đã được nhận giải Bài báo ảnh hưởng lớn trong lĩnh vực tính toán phân tán của ACM dành cho bài báo đã khởi đầu cho ngành con Tự ổn định
Tiểu sử:
Dijkstra học vật lý lý thuyết tại Đại học Leiden, nhưng ông đã nhanh chóng nhận ra rằng ông quan tâm đến lập trình hơn.
Thời kỳ đầu, ông làm việc tại Trung tâm toán học, Viện nghiên cứu quốc gia về toán học và khoa học máy tính tại Amsterdam, ông còn giữ chức vị giáo sư tại Đại học Kỹ thuật Eindhoven, Hà Lan. Đầu thập kỷ 1970, ông làm cộng tác nghiên cứu tại Burroughs Corporation, sau đó giữ vị trí Schlumberger Centennial Chair ngành Khoa học máy tính tại Đại học Texas tại Austin, Mỹ. Ông nghỉ hưu năm 2000.
Trong các đóng góp của ông cho ngành khoa học máy tính có thuật toán đường đi ngắn nhất, còn được biết với tên Thuật toán Dijkstra, hệ điều hành THE và cấu trúc semaphore để phối hợp hoạt động của nhiều bộ vi xử lý và nhiều chương trình. Một khái niệm khác trong lĩnh vực tính toán phân tán đã được khởi đầu nhờ Dijkstra là self-stabilization - một cách khác để đảm bảo tính đáng tin cậy của hệ thống. Thuật toán Dijkstra được sử dụng trong SPF, Shortest Path First, dùng trong giao thức định tuyến OSPF, Open Shortest Path First.
Ông còn nổi tiếng với đánh giá thấp về lệnh GOTO trong lập trình máy tính. Bài báo năm 1968 "A Case against the GO TO Statement" (EWD215) được xem là một bước quan trọng tiến tới việc lệnh GOTO bị thay thế dần trên quy mô lớn bởi các cấu trúc lập trình chẳng hạn như vòng lặp while. Phương pháp này còn được gọi là Lập trình có cấu trúc. Dijkstra đã rất hâm mộ ngôn ngữ lập trình ALGOL 60, và đã làm việc trong nhóm cài đặt trình biên dịch đầu tiên cho ngôn ngữ này.
Từ những năm 1970, mối quan tâm chính của Dijkstra là kiểm định hình thức (formal verification). Quan niệm phổ biến thời đó là người ta nên đưa ra một chứng minh toán học về tính đúng đắn của chương trình sau khi đã viết chương trình đó. Dijkstra đã phản đối rằng các chứng minh thu được rất dài và nặng nề, và rằng chứng minh đó không đem lại hiểu biết về việc chương trình đã được phát triển như thế nào. Một phương pháp khác là dẫn xuất chương trình (program derivation), để "phát triển chứng minh và chương trình một cách đồng thời". Người ta bắt đầu bằng một đặc tả toán học về những gì mà một chương trình cần phải thực hiện, sau đó áp dụng các biến đổi toán học đối với đặc tả đó cho đến khi nó được chuyển thành một chương trình chạy được. Chương trình thu được khi đó được gọi là "đúng đắn theo cách xây dựng" (correct by construction).
Dijkstra còn nổi tiếng với các bài luận của ông về lập trình; ông là người đầu tiên tuyên bố rằng việc lập trình có đặc điểm cố hữu là khó khăn và phức tạp đến mức các lập trình viên cần phải khai thác mọi kỹ thuật và các phương pháp trừu tượng hóa có thể để hy vọng có thể quản lý được độ phức tạp của nó một cách thành công. Ông còn nổi tiếng với thói quen viết tay cẩn thận các bản thảo bằng bút máy. Các bản thảo này được gọi là EWD, do Dijkstra đánh số chúng bằng tiết đầu tố EWD. Ông thường phân phát các bản phô-tô của bản EWD mới cho các đồng nghiệp của mình; những người nhận được lại phô-tô và tiếp tục phân phát các bản sao, bằng cách đó các bản EWD được phát tán khắp cộng đồng khoa học máy tính quốc tế. Các chủ đề chính là về khoa học máy tính và toán học, ngoài ra còn có các báo cáo công tác, thư và các bài phát biểu. Hơn 1300 bài EWD đã được quét thành ảnh, số lượng được chuyển thành dạng điện tử để phục vụ nghiên cứu ngày càng tăng, chúng được lưu trữ và cung cấp trực tuyến tại Đại học Texas[2].
Dijkstra đã là một trong những người tiên phong trong nghiên cứu về tính toán phân tán. Có người còn cho là một số bài báo của ông đã thiết lập ngành nghiên cứu này. Cụ thể, bài báo "Self-stabilizing Systems in Spite of Distributed Control" của ông đã khởi đầu ngành con Self-stabilization.
Dijkstra còn được ghi nhận là cả đời chỉ sở hữu duy nhất một chiếc máy tính (vào cuối đời) và họa hoằn mới thực sự sử dụng nó [3], để đi đôi với quan niệm của ông rằng khoa học máy tính trừu tượng hơn chứ không chỉ là lập trình, quan niệm này được thể hiện trong nhiều câu nói nổi tiếng chẳng hạn như "Khoa học máy tính đối với máy tính cũng như thiên văn học đối với kính thiên văn" (Computer Science is no more about computers than astronomy is about telescopes.)[4]
Ông qua đời tại Nuenen, Hà Lan vào ngày 6 tháng 8, năm 2002 sau một thời gian dài bị ung thư. Năm sau, giải thưởng PODC Influential Paper Award in distributed computing (bài báo ảnh hưởng trong lĩnh vực tính toán phân tán) của tổ chức ACM (Association for Computing Machinery) đã được đổi tên thành Giải thưởng Dijkstra để vinh danh ông.

Chân dung Edsger Wybe Dijkstra nhà khoa học máy tính Hà Lan
Thảo luận Bài 7 - Page 2 77935788

ChauQuangCam (I22B) 30/3/2013, 16:17

Mã của tiến trình Xei có cấu trúc như sau:
Semaphore mutex = 1; //đèn hiệu nhị phân, có hai trạng thái
//0: đèn màu đỏ
//1: đèn màu xanh
While(1)
{
Đi đến cầu;
Wait(mutex); //chờ đèn xanh
Lên cầu; //đoạn tương tranh, đèn màu đỏ
Qua cầu; //đoạn tương tranh, đèn màu đỏ
Signal(mutex); //đèn chuyển sang màu xanh
Đi tiếp;
Quay về theo đường khác;
}
Do chiếc cầu yếu nên mỗi thời điểm chỉ có 1 xe được phép qua cầu. Những xe khác khi đi đến đầu cầu sẽ ngủ tại lệnh wait(mutex) vì đèn đỏ. Sau khi một xe đã lên cầu và qua cầu xong thì lệnh signal(mutex) được thực hiện, tăng đèn mutex lên 1, đèn chuyển sang màu xanh. Một xe sau sẽ được đánh thức và lên cầu. Trong trường hợp này vùng tranh chấp là cây cầu.

nguyenthithutrang (I11C) 30/3/2013, 16:17

TruongNhuNgoc (I22A) đã viết:- Mục đích của đồng bộ hóa công việc các tiến trình là:
+ Đảm bảo tính nhất quán của tải nguyên dùng chung.
+ Tránh được hiện tượng Deadlock (Hiện tượng kẹt tiến trình).
- Ví dụ: Một trường học chỉ có 1 phòng lab (tài nguyên dùng chung), lớp có giờ học trước thì được vào phòng lab học trước, các lớp còn lại phải chờ đến khi lớp học trước đó hết giờ mới được vào phòng lab học.

Thêm ví dụ về đồng bộ hóa tiến trình
Đồng bộ tập ảnh
Để đồng bộ (import) phim và ảnh từ máy ảnh của điện thoại, bạn nhấn đúp chuột vào mục Import pictures and videos. Windows sẽ tự động tìm kiếm ảnh có trong thư viện ảnh chụp (camera roll). Bạn cũng có thể bổ sung các từ khóa (tag) nếu muốn, sau đó nhấn OK để bắt đầu quá trình đồng bộ.
Bạn có thể chọn thêm tùy chọn xóa hẳn ảnh trong thư viện ảnh chụp trên máy, hay vẫn duy trì chúng trên điện thoại. Khi mọi dữ liệu được đồng bộ vào máy tính, một cửa sổ Explorer sẽ xuất hiện để thông báo cho bạn những ảnh nào đã được chép vào máy tính.

PhamQuocCuong (I22A) 30/3/2013, 16:25

 Có 5 triết gia ngồi quanh 1 bàn tròn.
 Mỗi triết gia có 1 đĩa thức ăn, khi ăn cần 2 nĩa.
 Hoạt động của triết gia: luân phiên giữa suy nghĩ và ăn
 Khi triết gia đói: cần nĩa trái và nĩa phải đồng thời, nếu có 2 nĩa thì ăn.
 Sau khi ăn thì trả 2 nĩa và típ tục suy nghĩ.
 Nếu 5 triết gia đồng thời cầm nĩa trái, chờ nĩa phài : deadlock.
 Nếu 5 triết gia đồng thời trả nĩa trái, suy nghĩ, đồng thời cầm nĩa phải: Starvation

Thảo luận Bài 7 - Page 2 97d384e84eeddc7dbef91210d39cd66e_54436408.740pxdiningphilosophers

Thảo luận Bài 7 - Page 2 97d384e84eeddc7dbef91210d39cd66e_54436408.740pxdiningphilosophers

Thảo luận Bài 7 - Page 2 21d9ab9df48e9e190569c65d1bc4e2da_54436753.screenshot1

Thảo luận Bài 7 - Page 2 5b052f40b36a498a8fdf4ae0e7fbb8e8_54436792.screenshot2

nguyenthithutrang (I11C) 30/3/2013, 16:26

dangthihoangly(I12A) đã viết:Khai báo :
Semaphore semEmpty=10, semFull=0, critsec=1;

Thuật giải dành cho nhà sản xuất :producer

Wait(semEmpty);
Wait(critsec);
Đưa sản phẩm vào bộ nhớ đệm
Signal(semFull);
Signal(critsec);

Thuật giải dành cho nhà tiêu thụ : Consumer

Wait(semFull);
Wait(critsec);
Lấy sp ra khỏi bộ nhớ đệm
Signal(semEmpty);
Signal(critsec);

Lập trình bài toán sản xuất tiêu thụ được đồng bộ bằng 2 đèn hiệu SemEmpty và SemFull.

Producer:
Wait (SemEmpty);
Wait (Mutex);
Buffer [in] = sp mới; //xếp sản phẩm vào bộ đệm
in = (in + 1) % BUFFER-SIZE;
Signal (SemFull);
Signal(Mutex);
Consumer:
Wait (SemFull);
Wait (Mutex);
p = Buffer [out] //lấy sản phẩm ra khỏi bộ đệm
out = (out + 1) % BUFFER-SIZE;
Signal (SemEmpty);
Signal (Mutex);
Lưu ý:
Giá trị ban đầu của Mutex là 1.
Giá trị ban đầu của SemFull là 0.
Giá trị ban đầu của SemEmpty là BUFFER_SIZE.

NgoVanTuyen(I22B) 30/3/2013, 16:28

- Đoạn tương tranh :Xét một hệ có n tiến trình P0,P1, ...,Pn, mỗi tiến trình có một đoạn mã lệnh, nếu như trong đoạn mã này các tiến trình thao tác trên các biến chung,đọc ghi file... (tổng quát: thao tác trên dữ liệu chung) thì đoạn mã lệnh đó là đoạn tương tranh.
- Tính Loại trừ lẫn nhau hay Loại trừ tương hỗ (Mutual Exclusion) về phương diện thời gian: Khi có 1 tiến trình đang ở trong ĐTT của nó thì không có tiến trình nào khác trong nhóm cũng tại đoạn như vậy, nghĩa là: Mỗi thời điểm chỉ có 1 tiến trình được phép truy cập và/hoặc thay đổi tài nguyên chung.
- Các tiến trình tương tranh có cấu trúc mã bao gồm Entry Section (Đoạn Đăng nhập), Critical Section (Đoạn Tương tranh), Exit Section (Đoạn Đăng xuất) và các Remainder Section (Đoạn Còn lại)

NgoVanTuyen(I22B) 30/3/2013, 16:31

Ví dụ ở một công ty có sản xuất 1 sản phẩm nào đó, có nhà sản xuất và nhà tiêu thụ.Nhà sản xuất khi sản xuất xong sản phẩm sẽ đưa vào kho chứa hàng --> Khi đó nhà tiêu thụ sẽ đưa sản phẩm trong kho hàng đi tiêu thụ. Để hoạt động sản xuất trơn tru, tiến trình trong chu trình sản xuất thì không được xếp sản phẩm khi chưa hoàn chỉnh vào kho chưa hàng và không được để xảy ra việc có 2 nhà sản xuất cùng ghi vào 1 lúc.

nguyenthithutrang (I11C) 30/3/2013, 16:36

dangthihoangly(I12A) đã viết:ví dụ về bài toán Đồng bộ hóa :
Giả sử có hai tiến trình P1 và P2 thực hiện công việc của các kế toán, và cùng chia sẻ một vùng nhớ chung lưu trữ biến taikhoan phản ánh thông tin về tài khoản. Mỗi tiến trình muốn rút một khoản tiền tienrut từ tài khoản:

if (taikhoan - tienrut >=0)

taikhoan = taikhoan - tienrut;

else

error(� khong the rut tien ! �);

Giả sử trong tài khoản hiện còn 800, P1 muốn rút 500 và P2 muốn rút 400. Nếu xảy ra tình huống như sau :

Sau khi đã kiểm tra điều kiện (taikhoan - tienrut >=0) và nhận kết quả là 300, P1 hết thời gian xử lý mà hệ thống cho phép, hệ điều hành cấp phát CPU cho P2.

P2 kiểm tra cùng điều kiện trên, nhận được kết quả là 400 (do P1 vẫn chưa rút tiền) và rút 400. Giá trị của taikhoan được cập nhật lại là 400.

Khi P1 được tái kích hoạt và tiếp tục xử lý, nó sẽ không kiểm tra lại điều kiện (taikhoan - tienrut >=0)-vì đã kiểm tra trong lượt xử lý trước- mà thực hiện rút tiền. Giá trị của taikhoan sẽ lại được cập nhật thành -100. Tình huống lỗi xảy ra !

Các tình huống tương tự như thế - có thể xảy ra khi có nhiều hơn hai tiến trình đọc và ghi dữ liệu trên cùng một vùng nhớ chung, và kết quả phụ thuộc vào sự điều phối tiến trình của hệ thống.

Thanks bạn nhé, 1 ví dụ rất thực tế giúp dễ hiểu bài hơn Smile

truongtph.i11c 30/3/2013, 16:45

Admin đã viết:Thảo luận những vấn đề liên quan đến Bài 7.

Giải thưởng Turing (A. M. Turing Award) là giải thưởng thường niên của Hiệp hội Khoa học Máy tính Association for Computing Machinery cho các cá nhân hoặc một tập thể với những đóng góp quan trọng cho cộng đồng khoa học máy tính. Giải thưởng thường được coi như là giải Nobel cho lĩnh vực khoa học máy tính. Giải thưởng được đặt theo tên của nhà bác học Alan Mathison Turing, nhà toán học người Anh, người được coi là cha đẻ của lý thuyết khoa học máy tính và trí tuệ nhân tạo. Từ năm 2007, giải thưởng có giá trị $250.000, được đồng tài trợ bởi Intel và Google.

Người nhận giải thưởng đầu tiên năm 1966, là Alan Perlis của viện Carnegie Institute of Technology. Năm 2006, Frances E. Allen của IBM là người phụ nữ đầu tiên và duy nhất cho đến nay được nhận giải thưởng.

Danh sách những người nhận giải:

1966_Alan J. Perlis: Cho những ảnh hưởng trong các kỹ thuật lập trình và xây dựng chương trình dịch
1967_Maurice V. Wilkes Giáo sư Wilkes" được biết tới như là người thiết kế và xây dựng EDSAC, máy tính đầu tiên với hàm nội chứa (internally stored). Ông là đồng tác giả với Wheeler và Gill của tập sách "Preparation of Programs for Electronic Digital Computers" xuất bản 1951
1968_Richard Hamming: Cho các đóng góp về các phương pháp số, các hệ thống tự mã hóa, phát hiện và sửa lỗi sai
1969_Marvin Minsky: Trí tuệ nhân tạo
1970_James H. Wilkinson: Cho những nghiên cứu về phân tích số cho việc sử dung các máy tính số tốc độ cao, những đóng góp về Đại số tuyến tính và phân tích lỗi ngược
1971_John McCarthy: Cho những đóng góp về Trí tuệ nhân tạo "The Present State of Research on Artificial Intelligence"
1972_Edsger W. Dijkstra: Là người đóng góp chủ yếu cho ngôn ngữ lập trình ALGOL. Ông cũng nổi tiếng với thuật toán Dijkstra
1973_Charles W. Bachman: Cho những đóng góp đáng chú ý của ông về công nghệ database
1974_Donald E. Knuth: Với những cống hiến cho việc phân tích giải thuật và thiết kế ngôn ngữ lập trình, và đặc biệt với tác phẩm kinh điển Nghệ thuật lập trình "The Art of Computer Programming"
1975_Allen Newell và Herbert A. Simon: Với những đóng góp quan trọng cho chuyên ngành trí tuệ nhân tạo , tâm lý học về nhận thức chủ quan (psychology of human cognition), và xử lý chuỗi
1976_Michael O. Rabin và Dana S. Scott: Với bài báo "Finite Automata and Their Decision Problem" (Automat hữu hạn và bài toán quyết định) đã giới thiệu các ý tưởng về máy phi bất định nondeterministic machines, đã làm sáng tỏ rất nhiều khái niệm có giá trị.
1977_John Backus John Backus: đã đóng góp nhiều công sức cho việc thiết kế các hệ thống ngôn ngữ lập trình bậc cao, tiêu biểu là FORTRAN, và các bài báo phôi thai cho các thủ tục hình thức của đặc tả các ngôn ngữ lập trình
1978_Robert W. Floyd: Có ảnh hưởng sâu sắc đến các phương pháp luận của việc xây dựng hiệu quả các phần mềm tin cậy, đặt nền móng cho nhiều chuyên ngành hẹp của khoa học máy tính: lý thuyết phân tích ngữ pháp, ngữ nghĩa của các ngôn ngữ lập trình, tự động kiểm tra chương trình program verification, tự động tổng hợp chương trình, và phân tích giải thuật
1979_Kenneth E. Iverson: Với những nỗ lực tiên phong trong ngôn ngữ lập trình và các ký pháp toán học tạo nên một lĩnh vực chuyên ngành máy tính mớilaf APL, cho những đóng góp của ông về thực hiện hệ tương tác, đào tạo sự dụng APL, và lý thuyết và ứng dụng ngôn ngữ lập trình
2000_Andrew Chi-Chih Yao: Đóng góp về lý thuyết tính toán, pseudorandom number generation, cryptography, và communication complexity.
2001_Ole-Johan Dahl và Kristen Nygaard: Những ý tưởng cơ bản về lập trình hướng đối tượng.
2002_Ronald L. Rivest, Adi Shamir và Leonard M. Adleman: Những đóng góp về mã hóa khóa công khai public-key cryptography, RSA (mã hóa).
2003_Alan Kay: Với các ý tưởng cội nguồn về các ngôn ngữ lập trình hướng đối tượng vàSmalltalk.
2004_Vinton G. Cerf và Robert E. Kahn: Đóng góp cho internetworking, bao gồm thiết kế và triển khai các giao thức Internet' TCP/IP.
2005_Peter Naur: Với những đóng góp về thiết kế ngôn ngữ lập trình.
2006_Frances E. Allen: Những đóng góp về lý thuyết và thực nghiệm tối ưu hóa các kỹ thuật chương trình dịch.
2007_Edmund M. Clarke, E. Allen Emerson và Joseph Sifakis: Phát triển kiểm tra mô hình Model-Checking.
2008_Flag of the United StatesBarbara Liskov: Những đóng góp cho cơ sở lý thuyết và thực tiễn của ngôn ngữ lập trình và thiết kế hệ thống, đặc biệt về trừu tượng hóa dữ liệu, khả năng chịu lỗi và tính toán phân tán
2009_Flag of the United StatesCharles P. Thacker: Tiên phong trong thiết kế và hiện thực Alto, mô hình máy tính cá nhân đầu tiên, và những đóng góp của ông với Ethernet và máy tính bảng cá nhân.

Trích: http://vi.wikipedia.org/wiki/Gi%E1%BA%A3i_Turing.

ChauQuangCam (I22B) 30/3/2013, 16:46

Đoạn tương tranh là đoạn mã của tiến trình, khi thực hiện thì ảnh hưởng đến vùng tranh chấp.
Ví dụ:
Ở nhà chỉ có 1 máy tính cho mọi người dùng chung, vậy máy tính chính là Vùng Tranh Chấp. Tại thời điểm người thứ nhất sử dụng đến khi sử dụng xong đó là Đoạn Tương Tranh, trong thời gian Đoạn Tương Tranh xảy ra thì người thứ 2 sẽ không thể làm việc được với máy tính.

DangXuanCanh_14(I22B) 30/3/2013, 16:46

Edsger Wybe Dijkstra: sinh ngày11, tháng 5,năm 1930 tại Rotterdam – Mất ngày 6, tháng 8, năm2002 tại Nuenen, là nhà khoa học máy tính Hà Lan. Ông được nhận giải thưởng Turing cho các đóng góp có tính chất nền tảng trong lĩnh vực ngôn ngữ lập trình. Không lâu trước khi chết, ông đã được nhận giải Bài báo ảnh hưởng lớn trong lĩnh vực tính toán phân tán của ACM dành cho bài báo đã khởi đầu cho ngành con Tự ổn định. Sau khi ông qua đời, giải thưởng thường niên này đã được đổi tên thành giải thưởng ACM Edsger W. Dijkstra.
Tiểu Sử:Edsger Wybe Dijkstra.
Dijkstra học vật lý lý thuyết tại Đại học Leiden, nhưng ông đã nhanh chóng nhận ra rằng ông quan tâm đến lập trình hơn.
Thời kỳ đầu, ông làm việc tại Trung tâm toán học, Viện nghiên cứu quốc gia về toán học và khoa học máy tính tại Amsterdam, ông còn giữ chức vị giáo sư tại Đại học Kỹ thuật Eindhoven, Hà Lan. Đầu thập kỷ 1970, ông làm cộng tác nghiên cứu tại Burroughs Corporation, sau đó giữ vị trí Schlumberger Centennial Chair ngành Khoa học máy tính tại Đại học Texas tại Austin, Mỹ. Ông nghỉ hưu năm 2000.
Trong các đóng góp của ông cho ngành khoa học máy tính có thuật toán đường đi ngắn nhất, còn được biết với tên Thuật toán Dijkstra, hệ điều hành THE và cấu trúc semaphore để phối hợp hoạt động của nhiều bộ vi xử lý và nhiều chương trình. Một khái niệm khác trong lĩnh vực tính toán phân tán đã được khởi đầu nhờ Dijkstra là self-stabilization - một cách khác để đảm bảo tính đáng tin cậy của hệ thống. Thuật toán Dijkstra được sử dụng trong SPF, Shortest Path First, dùng trong giao thức định tuyến OSPF, Open Shortest Path First.
Ông còn nổi tiếng với đánh giá thấp về lệnh GOTO trong lập trình máy tính. Bài báo năm 1968 "A Case against the GO TO Statement" (EWD215) được xem là một bước quan trọng tiến tới việc lệnh GOTO bị thay thế dần trên quy mô lớn bởi các cấu trúc lập trình chẳng hạn như vòng lặp while. Phương pháp này còn được gọi là Lập trình có cấu trúc. Dijkstra đã rất hâm mộ ngôn ngữ lập trình ALGOL 60, và đã làm việc trong nhóm cài đặt trình biên dịch đầu tiên cho ngôn ngữ này.
Từ những năm 1970, mối quan tâm chính của Dijkstra là kiểm định hình thức (formal verification). Quan niệm phổ biến thời đó là người ta nên đưa ra một chứng minh toán học về tính đúng đắn của chương trình sau khi đã viết chương trình đó. Dijkstra đã phản đối rằng các chứng minh thu được rất dài và nặng nề, và rằng chứng minh đó không đem lại hiểu biết về việc chương trình đã được phát triển như thế nào. Một phương pháp khác là dẫn xuất chương trình (program derivation), để "phát triển chứng minh và chương trình một cách đồng thời". Người ta bắt đầu bằng một đặc tả toán học về những gì mà một chương trình cần phải thực hiện, sau đó áp dụng các biến đổi toán học đối với đặc tả đó cho đến khi nó được chuyển thành một chương trình chạy được. Chương trình thu được khi đó được gọi là "đúng đắn theo cách xây dựng" (correct by construction).
Dijkstra còn nổi tiếng với các bài luận của ông về lập trình; ông là người đầu tiên tuyên bố rằng việc lập trình có đặc điểm cố hữu là khó khăn và phức tạp đến mức các lập trình viên cần phải khai thác mọi kỹ thuật và các phương pháp trừu tượng hóa có thể để hy vọng có thể quản lý được độ phức tạp của nó một cách thành công. Ông còn nổi tiếng với thói quen viết tay cẩn thận các bản thảo bằng bút máy. Các bản thảo này được gọi là EWD, do Dijkstra đánh số chúng bằng tiết đầu tố EWD. Ông thường phân phát các bản phô-tô của bản EWD mới cho các đồng nghiệp của mình; những người nhận được lại phô-tô và tiếp tục phân phát các bản sao, bằng cách đó các bản EWD được phát tán khắp cộng đồng khoa học máy tính quốc tế. Các chủ đề chính là về khoa học máy tính và toán học, ngoài ra còn có các báo cáo công tác, thư và các bài phát biểu. Hơn 1300 bài EWD đã được quét thành ảnh, số lượng được chuyển thành dạng điện tử để phục vụ nghiên cứu ngày càng tăng, chúng được lưu trữ và cung cấp trực tuyến tại Đại học Texas.
Dijkstra đã là một trong những người tiên phong trong nghiên cứu về tính toán phân tán. Có người còn cho là một số bài báo của ông đã thiết lập ngành nghiên cứu này. Cụ thể, bài báo "Self-stabilizing Systems in Spite of Distributed Control" của ông đã khởi đầu ngành con Self-stabilization.
Dijkstra còn được ghi nhận là cả đời chỉ sở hữu duy nhất một chiếc máy tính (vào cuối đời) và họa hoằn mới thực sự sử dụng nó , để đi đôi với quan niệm của ông rằng khoa học máy tính trừu tượng hơn chứ không chỉ là lập trình, quan niệm này được thể hiện trong nhiều câu nói nổi tiếng chẳng hạn như "Khoa học máy tính đối với máy tính cũng như thiên văn học đối với kính thiên văn" (Computer Science is no more about computers than astronomy is about telescopes.)
Ông qua đời tại Nuenen, Hà Lan vào ngày 6 tháng 8, năm 2002 sau một thời gian dài bị ung thư. Năm sau, giải thưởng PODC Influential Paper Award in distributed computing (bài báo ảnh hưởng trong lĩnh vực tính toán phân tán) của tổ chức ACM (Association for Computing Machinery) đã được đổi tên thành Giải thưởng Dijkstra để vinh danh ông.

nguyenthithutrang (I11C) 30/3/2013, 16:46

TruongNhuNgoc (I22A) đã viết:Khái niệm đèn hiệu:
- Đèn hiệu là phương tiện đồng bộ hoá được E.W. Dijkstra đề xuất năm 1965.
- Đèn hiệu được mô tả bằng một biến kiểu nguyên với 2 tác nguyên là Wait (Chờ) và Signal (Báo hiệu):

typedef int semaphore; // Định nghĩa kiểu Đèn hiệu
wait (semaphore S)
{
while ( S <= 0 ); // Chờ bận nếu S<=0
S --; // Giảm S đi 1
}

signal (semaphore S)
{
S ++; // Tăng S lên 1
}

- Việc kiểm tra S <= 0 và giảm S (trong Wait) hoặc tăng S (trong Signal) phải được thực hiện trọn vẹn (không xảy ra ngắt trong thời gian thi hành), do đó Wait và Signal được gọi là các tác nguyên (Atomic Operations).

Đèn hiệu nhị phân để đảm bảo tính loại trừ lẫn nhau.
Đèn hiệu nhị phân chỉ có 2 trạng thái (xanh và đỏ - 1 và 0).
VD: Giả sử có 1 cây cầu ở đầu cầu có 1 cái đèn, trên đoạn đường đến cầu có các oto (vd oto1, oto2...) và cầu chỉ có tải trọng 1 chiếc oto đi qua tại 1 thời điểm khi duy chuyển qua cầu, đèn báo có 2 trạng thái 0 và 1 (xanh và đỏ), đèn xanh xe oto được phép đi, đỏ oto còn lại phải chờ đến lượt, giống như trạng thái wait(s);, signal(s).
- Đèn hiệu được mô tả bằng một biến kiểu nguyên với 2 tác nguyên là Wait (Chờ) và Signal (Báo hiệu):
typedef int semaphore; // Định nghĩa kiểu Đèn hiệu
wait (semaphore S) {
while ( S <= 0 ); // Chờ bận nếu S<=0
S --; // Giảm S đi 1
}

signal (semaphore S) {
S ++; // Tăng S lên 1
}
- Việc kiểm tra S <= 0 và giảm S (trong Wait) hoặc tăng S (trong Signal) phải được thực hiện trọn vẹn (không xảy ra ngắt trong thời gian thi hành), do đó Wait và Signal được gọi là các tác nguyên (Atomic Operations).

nguyenthithutrang (I11C) 30/3/2013, 16:54

TruongNhuNgoc (I22A) đã viết:- Mục đích của đồng bộ hóa công việc các tiến trình là:
+ Đảm bảo tính nhất quán của tải nguyên dùng chung.
+ Tránh được hiện tượng Deadlock (Hiện tượng kẹt tiến trình).
- Ví dụ: Một trường học chỉ có 1 phòng lab (tài nguyên dùng chung), lớp có giờ học trước thì được vào phòng lab học trước, các lớp còn lại phải chờ đến khi lớp học trước đó hết giờ mới được vào phòng lab học.

Nhu cầu của việc đồng bộ hóa
Trong một hệ thống cho phép các tiến trình liên lạc với nhau, bao giờ hệ điều hành cũng cần cung cấp kèm theo những cơ chế đồng bộ hóa để bảo đảm hoạt động của các tiến trình đồng hành không tác động sai lệch đến nhau vì các lý do sau đây:
Yêu cầu độc quyền truy xuất (Mutual exclusion)
Các tài nguyên trong hệ thống được phân thành hai loại: tài nguyên có thể chia sẻ cho phép nhiều tiến trình đồng thời truy xuất, và tài nguyên không thể chia sẻ chỉ chấp nhận một ( hay một số lượng hạn chế ) tiến trình sử dụng tại một thời điểm. Tính không thể chia sẻ của tài nguyên thường có nguồn gốc từ một trong hai nguyên nhân sau đây:
• Đặc tính cấu tạo phần cứng của tài nguyên không cho phép chia sẻ.
Nếu nhiều tiến trình sử dụng tài nguyên đồng thời, có nguy cơ xảy ra các kết quả không dự đoán được do hoạt động của các tiến trình trên tài nguyên ảnh hưởng lẫn nhau.
Để giải quyết vấn đề, cần bảo đảm tiến trình độc quyền truy xuất tài nguyên, nghĩa là hệ thống phải kiểm soát sao cho tại một thời điểm, chỉ có một tiến trình được quyền truy xuất một tài nguyên không thể chia sẻ.
Yêu cầu phối hợp (Synchronization)
Nhìn chung, mối tương quan về tốc độ thực hiện của hai tiến trình trong hệ thống là không thể biết trước, vì điều này phụ thuộc vào nhiều yếu tố động như tần suất xảy ra các ngắt của từng tiến trình, thời gian tiến trình được cấp phát bộ xử lý… Có thể nói rằng các tiến trình hoạt động không đồng bộ với nhau. Như ng có những tình huống các tiến trình cần hợp tác trong việc hoàn thành tác vụ, khi đó cần phải đồng bộ hóa hoạt động của các tiến trình , ví dụ một tiến trình chỉ có thể xử lý nếu một tiến trình khác đã kết thúc một công việc nào đó …

truongtph.i11c 30/3/2013, 17:01

Trong một hệ thống cho phép các tiến trình liên lạc với nhau, bao giờ hệ điều hành cũng cần cung cấp kèm theo những cơ chế đồng bộ hóa để bảo đảm hoạt động của các tiến trình đồng hành không tác động sai lệch đến nhau vì các lý do sau đây:
Yêu cầu độc quyền truy xuất (Mutual exclusion)
Các tài nguyên trong hệ thống được phân thành hai loại: tài nguyên có thể chia sẻ cho phép nhiều tiến trình đồng thời truy xuất, và tài nguyên không thể chia sẻ chỉ chấp nhận một ( hay một số lượng hạn chế ) tiến trình sử dụng tại một thời điểm. Tính không thể chia sẻ của tài nguyên thường có nguồn gốc từ một trong hai nguyên nhân sau đây:
• Đặc tính cấu tạo phần cứng của tài nguyên không cho phép chia sẻ.
Nếu nhiều tiến trình sử dụng tài nguyên đồng thời, có nguy cơ xảy ra các kết quả không dự đoán được do hoạt động của các tiến trình trên tài nguyên ảnh hưởng lẫn nhau.
Để giải quyết vấn đề, cần bảo đảm tiến trình độc quyền truy xuất tài nguyên, nghĩa là hệ thống phải kiểm soát sao cho tại một thời điểm, chỉ có một tiến trình được quyền truy xuất một tài nguyên không thể chia sẻ.
Yêu cầu phối hợp (Synchronization)
Nhìn chung, mối tương quan về tốc độ thực hiện của hai tiến trình trong hệ thống là không thể biết trước, vì điều này phụ thuộc vào nhiều yếu tố động như tần suất xảy ra các ngắt của từng tiến trình, thời gian tiến trình được cấp phát bộ xử lý… Có thể nói rằng các tiến trình hoạt động không đồng bộ với nhau. Như ng có những tình huống các tiến trình cần hợp tác trong việc hoàn thành tác vụ, khi đó cần phải đồng bộ hóa hoạt động của các tiến trình , ví dụ một tiến trình chỉ có thể xử lý nếu một tiến trình khác đã kết thúc một công việc nào đó …

DangXuanCanh_14(I22B) 30/3/2013, 17:09

NguyenQuocHuy (I22B) đã viết:Giả sửa có 3 tiến trình P1, P2 và P3 có mã tương ứng là S1, S2 và S3

Semaphore synch = 0;

P1 P2 P3
S1 wait(synch); wait(synch);
signal(synch, 2); S2 S3

Tại thời điểm ban đầu: synch=0,
- Khi tiến trình P2 được thực hiện, thì P2 sẽ bị khóa tại hàm wait(synch) do synch=0 cho đến khi synch>0.
- Khi tiến trình P3 được thực hiện, thì P3 sẽ bị khóa tại hàm wait(synch) do synch=0 cho đến khi synch>0.
- Khi P1 thực hiện ,S1 được thi hành xong thì lệnh signal(synch, 2); dc thực thi, tức là tăng giá trị của synch lên 2.
- Khi đó synch>0 ,tiến trình P2 được thực hiện và hàm wait(synch) sẽ giảm giá trị synch xuống 1 đơn vị (synch=1).
Đồng thời P3 được thực hiện và hàm wait(synch) sẽ giảm giá trị synch xuống 1 đơn vị (synch=0).
->P2 và P3 cùng thực hện.
=>P1 đi trước P2 và P3.

Mình thấy bài này của bạn đã hoàn chỉnh.

DangXuanCanh_14(I22B) 30/3/2013, 17:33

#define N 5
#define LEFT (i-1)%N
#define RIGHT (i+1)%N
#define THINKING 0
#define HUNGRY 1
#define EATING 2
typedef unsigned int semaphore;
int state[N];
semaphore mutex = 1;
semaphore s[N];
void Sinhvien (int i)
{
while (còn cơm)
{
think(); //công đoạn 1
take_forks(i); //công đoạn 2, có thể bị kẹt 1 thời gian
eat(); put_forks(i); //công đoạn 3
}
}
void take_forks(int i)
{
down(&mutex); //đảm bảo 0 tranh chấp khi lấy đủa
state[i] = HUNGRY; //ghi nhận trạng thái đang cố gắng lấy đủa
test(i); //kiểm tra lấy được không ? nếu được s[i] → 1
up(&mutex); //đánh thức các SV khác để họ truy xuất đủa
down(&s[i]); //cố gắng và cơm & gắp thức ăn, có thể bị kẹt
}
void test (int i)
{
if (state[i] == HUNGRY //SV i muốn lấy đủa
&& state[LEFT] != EATING //SV bên trái chưa lấy
&& state[RIGHT] != EATING) //SV bên phải chưa lấy
{
state[i] = EATING; //ghi nhận SV i đã lấy được đủa
up(&s[i]); //tăng s[i] → 1
}
}
void put_forks (int i)
{
down(&mutex); //đảm bảo 0 tranh chấp khi lấy đủa
state[i] = THINKING; //ghi nhận trạng thái không dùng đủa
test(LEFT); //kiểm tra lấy được không ? nếu được đánh thức
//SV LEFT dậy để và cơm và gắp thức ăn
test(RIGHT); //kiểm tra lấy được không ? nếu được đánh thức
//SV RIGHT dậy để và cơm và gắp thức ăn
up(&mutex); //đánh thức các SV khác để họ truy xuất đủa
}

NguyenTuHuy(I22A) 30/3/2013, 17:37

ở một công ty có sản xuất 1 sản phẩm nào đó, có nhà sản xuất và nhà tiêu thụ.Nhà sản xuất khi sản xuất xong sản phẩm sẽ đưa vào kho chứa hàng --> Khi đó nhà tiêu thụ sẽ đưa sản phẩm trong kho hàng đi tiêu thụ. Để hoạt động sản xuất trơn tru, tiến trình trong chu trình sản xuất thì không được xếp sản phẩm khi chưa hoàn chỉnh vào kho chưa hàng và không được để xảy ra việc có 2 nhà sản xuất cùng ghi vào 1 lúc.

ChauQuangCam (I22B) 30/3/2013, 18:47

- Đoạn tương tranh là đoạn mã trong chương trình,điều khiển công việc của tiến trình. Có tính chất là khi thực hiện đoạn mã đó thì tác động tới tài nguyên dùng chung với tiến trình khác.

- Giả sử có n tiến trình { P0, P1 , ... , Pn-1 }. Mỗi tiến trình có đoạn mã gọi là Đoạn tương tranh ( ĐTT ) trong đó tiến trình có thể truy cập và thay đổi vùng nhớ, tập tin hay tài nguyên chung.

- Tính Loại trừ lẫn nhau hay Loại trừ tương hỗ (Mutual Exclusion) về phương diện thời gian: Khi có 1 tiến trình đang ở trong ĐTT của nó thì không có tiến trình nào khác trong nhóm cũng tại đoạn như vậy, nghĩa là: Mỗi thời điểm chỉ có 1 tiến trình được phép truy cập và/hoặc thay đổi tài nguyên chung.

- Các tiến trình tương tranh có cấu trúc mã bao gồm Entry Section (Đoạn Đăng nhập), Critical Section (Đoạn Tương tranh), Exit Section (Đoạn Đăng xuất) và các Remainder Section (Đoạn Còn lại).

+ thầy kêu 5 bạn lên nộp bài thì sẽ chỉ có 1 bạn được kêu đầu tiên nộp bài trước và 4 bạn kia phải chờ,không thể 2 bạn cùng nhau lên nộp bài cùng lúc được nếu không thì sẽ không đảm bảo được tín loại trừ lẫn nhâu và đảm bảo được tín đồng bộ.
+ 2 bạn lên bảng sữa bài tập thì chỉ có 1 bạn được lên sữa trước và bạn kia phải chờ cho đến khi nào bạn này sữa xong thì mới được lên.

NguyenVanSang(I22A) 30/3/2013, 19:13

- Giả sử có n tiến trình { P0 , P1 , ... , Pn-1 }. Mỗi tiến trình có đoạn mã gọi là Đoạn tương tranh ( ĐTT ) trong đó tiến trình có thể truy cập và thay đổi vùng nhớ, tập tin hay tài nguyên chung.
- Tính Loại trừ lẫn nhau hay Loại trừ tương hỗ (Mutual Exclusion) về phương diện thời gian: Khi có 1 tiến trình đang ở trong ĐTT của nó thì không có tiến trình nào khác trong nhóm cũng tại đoạn như vậy, nghĩa là: Mỗi thời điểm chỉ có 1 tiến trình được phép truy cập và/hoặc thay đổi tài nguyên chung.
- Các tiến trình tương tranh có cấu trúc mã bao gồm Entry Section (Đoạn Đăng nhập), Critical Section (Đoạn Tương tranh), Exit Section (Đoạn Đăng xuất) và các Remainder Section (Đoạn Còn lại).

NguyenThiBichTram (I22A) 30/3/2013, 19:35

Vấn đề deadlock : dead lock là hiện tượng một tiến trình chiếm hữu tài nguyên lâu dài làm cho các tiến trình có nhu cầu sử dụng tài nguyên này luôn ở trạng thái waiting mãi mãi .

- Mô hình hệ thống : trong một hệ thống , các tiến trình từ khi được gọi đến khi kết thúc sẽ qua các giai đoạn sau :
+Yêu cầu tài nguyên (request): nếu yêu cầu không được giải quyết ngay (vd khi tài nguyên đang được tiến trình khác sử dụng) thì tiến trình yêu cầu phải đợi cho đến khi nhận được tài nguyên.
+Sử dụng tài nguyên (use)
+Giải phóng tài nguyên (release)

- Mô tả Deadlock: Dead lock xảy ra với 4 điều kiện sau xảy ra đồng thời :
+ Ngăn chặn(loại trừ) lẫn nhau : vì chỉ có 1 tiến trình đc ở trong găng
+ Giữ và đợi (Hold and wait)
+ Không có ưu tiên(độc quyền)(No preemption): tiến trình thực hiện mãi mà ko dừng để giải phóng tài nguyên cho tiến trình khác
+ Chờ đợi vòng tròn(Circular Wait)

Trong mô hình RAG (Resource Allocation Graph )
Thảo luận Bài 7 - Page 2 Img008

_Nếu đồ thị không chu trình ko xảy ra deadlock.
_______Nếu đồ thị có chu trình
__________Nếu mỗi loại tài nguyên chỉ một cá thể thì chắc chắn xảy ra deadlock.
__________Nếu mỗi loại tài nguyên có một vài cá thể thì deadlock có thể xảy ra hoặc không.

Các phương pháp xử lý Deadlock
+ Ngăn ngừa hoặc tránh xa, đảm bảo rằng hệ thống sẽ không bao giờ đi vào trạng thái deadlock.
+ Cho phép hệ thống đi vào trạng thái deadlock rồi khôi phục lại.
+ Bỏ qua dead lock , coi như ko có dead trong hệ thống

Ngăn chặn deadlock : là đảm bảo ít nhất một trong bốn điều kiện không thể xuất hiện
a.Ngăn cản lẫn nhau – đảm bảo là hệ thống không có các file không thể chia sẻ.
Một tiến trình không bao giờ phải chờ tài nguyên có thể chia sẻ
Ví dụ: read-only files(vì file read only thì nhiều tiến trình truy xuất nó cũng không ảnh hưởng gì-nội dung file không thay đổi)
Một số tài nguyên là không thể chia sẻ
Ví dụ: chế độ toàn màn hình

b.Giữ và đợi cấp thêm tài nguyên – phải đảm bảo rằng mỗi khi một tiến trình yêu cầu một tài nguyên, nó không giữ bất kỳ tài nguyên nào khác.
Đòi hỏi tiến trình yêu cầu và được phân phối tất cả các tài nguyên của nó trước khi nó bắt đầu thực hiện, hoặc chỉ cho phép tiến trình yêu cầu các tài nguyên khi không có tài nguyên nào cả.

c.Không có ưu tiên: không đòi lại tài nguyên từ tiến trình đang giữ chúng_
Nếu một tiến trình đang giữ một số tài nguyên và yêu cầu tài nguyên khác mà không thể được phân phối ngay cho nó thì tất cả các tài nguyên nó đang giữ được giải phóng.
Các tài nguyên ưu tiên được thêm vào danh sách tài nguyên dành cho tiến trình đang chờ đợi.
Tiến trình sẽ được khởi động lại chỉ khi nó có thể lấy lại các tài nguyên cũ của nó cũng như các tài nguyên mới mà nó đang yêu cầu.

d.Chờ đợi vòng tròn – áp dụng một thứ tự tuyệt đối cho tất cả các loại tài nguyên: mỗi loại được gắn một số nguyên
Mỗi tiến trình yêu cầu các tài nguyên theo thứ tự tăng dần: chỉ có thể nhận được tài nguyên có trọng số cao hơn của bất kỳ tài nguyên nào nó đang giữ
Muốn có tài nguyên j, tiến trình phải giải phóng tất cả các tài nguyên có trọng số i > j (nếu có)

Tránh deadlock
Một số thông tin ưu tiên trong hệ thống :
-Mô hình hữu dụng nhất và đơn giản nhất yêu cầu mỗi tiến trình công bố số lượng tài nguyên lớn nhất của mỗi loại mà nó có thể cần đến.
-Giải thuật tránh deadlock luôn kiểm tra trạng thái phân phối tài nguyên để đảm bảo rằng sẽ không bao giờ có tình trạng chờ đợi vòng tròn.
-Trạng thái phân phối tài nguyên được xác định bởi số tài nguyên khả dụng (Available) và đã được phân phối (Allocation) cũng như số tài nguyên tối đa (max)tiến trình yêu cầu.

Giải thuật đồ thị cấp phát tài nguyên (đc dùng với tài nguyên đơn cá thể)
- Ngoài các cạnh yêu cầu và gán, chúng ta giới thiệu một loại cạnh mới được gọi là
cạnh thỉnh cầu (claim edge). Một cạnh thỉnh cầu Pi → Rj hiển thị quá trình Pi có thể yêu cầu tài nguyên Rj vào một thời điểm trong tương lai. Cạnh này tương tự cạnh yêu cầu về
phương hướng nhưng được hiện diện bởi dấu đứt khoảng. Khi quá trình Pi yêu cầu tài nguyên Rj, cạnh thỉnh cầu Pi → Rj chuyển tới cạnh yêu cầu. Tương tự, khi một tài nguyên Rj được giải phóng bởi Pi, cạnh gán Rj → Pi được chuyển trở lại thành cạnh
thỉnh cầu Pi → Rj. Chúng ta chú ý rằng các tài nguyên phải được yêu cầu trước trong hệ thống. Nghĩa là, trước khi Pi bắt đầu thực thi, tất cả các cạnh thỉnh cầu của nó phải xuất hiện trong đồ thị cấp phát tài nguyên. Chúng ta có thể giảm nhẹ điều kiện này bằng cách cho phép một cạnh Pi → Rj để được thêm tới đồ thị chỉ nếu tất cả các cạnh gắn liền với quá trình Pi là các cạnh thỉnh cầu. Giả sử rằng Pi yêu cầu tài nguyên Rj. Yêu cầu có thể được gán chỉ nếu chuyển cạnh yêu cầu Pi → Rj tới cạnh gán Rj→Pi không dẫn đến việc hình thành chu trình trong đồ thị cấp phát tài nguyên. Chú ý rằng chúng ta kiểm tra tính an toàn bằng cách dùng giải
thuật phát hiện chu trình. Một giải thuật để phát hiện một chu trình trong đồ thị này yêu cầu một thứ tự của n2 thao tác, ở đây n là số quá trình trong hệ thống.Nếu không có chu trình tồn tại, thì việc cấp phát tài nguyên sẽ để lại hệ thống trong trạng thái an toàn. Nếu chu trình được tìm thấy thì việc cấp phát sẽ đặt hệ thống trong trạng thái không an toàn. Do đó, quá trình Pi sẽ phải chờ yêu cầu của nó được thoả.

lehongphong(I22B) 30/3/2013, 21:19

4 ĐỒNG BỘ HÓA QUÁ TRÌNH
Quá trình thường cần liên lạc với các quá trình khác. Ví dụ, trên hệ điều
hành Linux, đối tượng ống nối (pipeline) được dùng để chuyển kết quả
của một lệnh thành dữ liệu vào của một lệnh kế tiếp. Nói cách khác, đối
tượng ống nối cho phép chuyển kết quả của một quá trình thành dữ liệu
vào của quá trình khác.
Một phương thức giao tiếp khác là các quá trình cùng đọc/ghi chung một
(hay nhiều) vùng dữ liệu chung. Trong hệ thống đa chương, các quá trình
thực hiện đồng hành thì ràng buộc về đồng nhất dữ liệu ảnh hưởng chính
đến kết quả thực hiện của các quá trình hợp tác nhau.
Ví dụ: với mô hình sản xuất-tiêu thụ (chương 3), khi quá trình tiêu thụ
đọc một biến trong vùng dữ liệu chung. Giá trị đọc được phụ thuôc vào
thứ tự đọc là trước hay sau khi ghi giá trị lên biến của quá trình sản xuất.
Trong chương này, ta đề cập đến các kỹ thuật thông dụng để đảm bảo
tính đồng nhất hay thứ tự của quá trình truy cập vùng dữ liệu chung của
các quá trình hợp tác với nhau.

4.1 Bài toán đồng bộ
Mô hình hợp tác giữa các quá trình trong chương 3 dựa trên giả định là
các quá trình thực hiện bất đồng bộ. Do vậy chúng có thể chia sẻ dữ liệu
cho nhau. Trong chương này, ta xét bài toán hợp tác của các quá trình với
vùng dữ liệu chung có kích thước giới hạn: print spooling.
Cụ thể, khi một quá trình cần in một tập tin, nó nhập tên tập tin vào một
thư mục đặc biệt spooler. Một quá trình khác, dịch vụ in, sẽ kiểm tra xem
có tập tin nào trong thư mục spooler không, nếu có dịch vụ sẽ thực hiện
in. Sau khi in xong, dịch vụ in sẽ xóa tên tập tin khỏi thư mục spooler. Giả sử thư mục spooler có nhiều mục vào được đánh số 0,1,2,…. Mỗi
mục vào giữ một tên tập tin. Đồng thời có 2 biến dùng chung:
- Biến out: trỏ đến tập tin kế tiếp được in
- Biến in: trỏ đến mục vào trống kế tiếp của thư mục spooler.
Hai biến này có thể được giữ trong một tập tin 2 từ mà có thể truy cập
được từ tất cả các quá trình.
Giả sử tại một thời điểm, các mục vào 0 đến 3 rỗng, mục vào 4 đến 6 là
có dữ liệu. Đồng thời, hai quá trình A, B sắp hàng một tập tin cần in.
Tiến trình thực hiện của 2 quá trình như sau:
- Quá trình A đọc biến in và gán giá trị đọc được, 7, vào biến cục bộ
của nó, next_free_slot. Giả sử đến thời điểm này, quá trình A hết thời
hạn thực hiện chu kỳ CPU. Nên hệ điều hành gọi thủ tục chuyển ngữ
cảnh để chuyển CPU cho quá trình B.
- Quá trình B đọc biến in, và cũng có được giá trị 7. Sau đó, B gán tên
tập tin cần in của nó vào mục vào 7, và tăng in lên 1 giá trị. Kế tiếp, B
chuyển sang tác vụ khác. - Đến lượt quá trình A quay lại tiếp tục thực hiện. A sẽ tiếp tục thực
hiện ngay sau tác vụ bị ngắt. A đọc biến next_free_slot, lấy giá trị 7.
Do vậy, A ghi tên tập tin cần in vào mục vào 7. Tên tập tin của B tại
mục vào này bị xóa. Kế tiếp, A tính next_free_slot +1 và ghi giá trị
tính được vào biến in.
- Lúc này, dịch vụ in thực hiện in theo giá trị có trong biến in. Kết quả,
quá trình B sẽ không nhận được kết quả ở máy in.
Qua ví dụ, ta thấy khi hai (hay nhiều) quá trình cùng đọc/ghivùng dữ liệu
chia sẻ thì kết quả thường phụ thuộc vào thứ tự thực hiện của các quá
trình, điều này được gọi là điều kiện cạnh tranh (race condition). Khi một
chương trình có chứa điều kiện cạnh tranh, việc kiểm tra có thể cho kết
quả đúng, nhưng khi thực hiện có thể có những kết quả ngoài dự đoán.
Đây chính là vấn đề cần giải quyết của bài toán đồng bộ.
Trong phần còn lại của chương, ta đề cập xác định rõ các vấn đề tranh
chấp và các kỹ thuật để giải quyết các vấn đề này.

Sponsored content

Thảo luận Bài 7

Định nghĩa đèn hiệu với 2 tác nguyên Wait(chờ) và Signal(báo hiệu)

Khái niệm Đoạn tương tranh và Loại trừ lẫn nhau

Khái niệm đèn hiệu và 2 ứng dụng của đèn hiệu.

Re: Thảo luận Bài 7

Re: Thảo luận Bài 7

Ví dụ: Xe qua Cầu

Re: Thảo luận Bài 7

Bài toán Dining Philosophers

Re: Thảo luận Bài 7

Những vấn đề và cấu trúc mã của đoạn tương tranh!

Ví dụ về đồng bộ hóa trong sản xuất tiêu thụ

Re: Thảo luận Bài 7

Giải thưởng Turing

Ví dụ về đoạn tương tranh và vùng tranh chấp

Thảo luận về Edsger Wybe Dijkstra

Re: Thảo luận Bài 7

Re: Thảo luận Bài 7

Nhu cầu đồng bộ hóa

Re: Thảo luận Bài 7

Bài toán 5 SV ăn cơm .Thuật giải dùng semaphore để giải quyết tranh chấp và đồng bộ.

ví dụ về đèn hiệu

Đoạn tương tranh và tính loại trừ lẫn nhau.

Khái niệm Đoạn tương tranh và Loại trừ lẫn nhau

Deadlock

re thảo luận bài 7

Re: Thảo luận Bài 7