Thảo luậ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 được nhận giải thưởng.
Alan Mathison Turing (23 tháng 6, 1912 – 7 tháng 6, 1954) là một nhà toán học, logic học và mật mã học người Anh thường được xem là cha đẻ của ngành khoa học máy tính. Phép thử Turing (Turing test) là một trong những cống hiến của ông trong ngành trí tuệ nhân tạo: thử thách này đặt ra câu hỏi rằng máy móc có khi nào đạt được ý thức và có thể suy nghĩ được hay không. Ông đã hình thức hóa khái niệm thuật toán và tính toán với máy Turing, đồng thời đưa ra phiên bản của "Turing", mà ngày nay được đông đảo công chúng chấp nhận, về luận đề Church-Turing, một luận đề nói rằng tất cả những gì tính được bằng thuật toán đều có thể tính được bằng máy Turing.

Trong Đệ nhị thế chiến, Turing đã từng làm việc tại Bletchley Park, trung tâm giải mật mã của Anh, và một thời là người chỉ huy của Hut 8, một bộ phận của Anh có trách nhiệm giải mật mã của hải quân Đức. Ông đã sáng chế ra nhiều kỹ thuật phá mật mã của Đức, trong đó có phương pháp nối các máy giải mã lại với nhau thành một bộ bombe, một máy điện-cơ để tìm ra công thức cài đặt cho máy Enigma.

Sau chiến tranh, ông công tác tại Phòng thí nghiệm Vật lý Quốc gia (National Physical Laboratory), và đã tạo ra một trong những đồ án thiết kế đầu tiên của máy tính có khả năng lưu trữ chương trình (stored-program computer), nhưng nó không bao giờ được kiến tạo thành máy. Năm 1947 ông chuyển đến Đại học Victoria tại Manchester để làm việc, đa số trên phần mềm cho máy Manchester Mark I, lúc đó là một trong những máy tính hiện đại đầu tiên, và trở nên quan tâm tới sinh học toán học. Ông đã viết bài báo về cơ sở hóa học của sự tạo hình,[1] và ông cũng đã dự đoán được các phản ứng hóa học dao động chẳng hạn như phản ứng Belousov–Zhabotinsky, được quan sát thấy lần đầu tiên trong thập niên 1960.

Yêu cầu của giải pháp loại trừ tương hỗ theo William Stalling.
- Tại 1 thời điểm chỉ có một process trong vùng tranh chấp.
- Process ở ngoài vùng tranh chấp không được ngăn cản process khác vào vùng tranh chấp.
- Không có process chờ đợi vô hạn định(starvation) để vào vùng tranh chấp.
- Không phụ thuộc vào tốc độ tương đối hay số lượng các process.
- Process chỉ ở trong vùng tranh chấp trong 1 khoảng thời gian nhất định.

- Đồng bộ hóa các tiến trình nhằm mục đích đảm bảo tính nhất quán, tính đúng đắn về tài nguyên dùng chung của các tiến trình.
VD máy tính: Lấy bài toán sản xuất tiêu thụ làm ví dụ. Hàm sleep(1) nhằm mục đích đồng bộ hóa các tiến trình, chờ một khoảng để khi show buffer ra ngoài màn hình biến “in” đã tăng lên 1 => đảm bảo tính đúng đắn của dữ liệu. Nếu không có sleep(1), tại thời điểm đó biến in vẫn còn lưu giá trị cũ.
VD thực tế: khi thầy giáo viết lên bảng 1 câu chưa hoàn tất “Biên dịch khác với phiên”. Một bạn sinh viên đã lấy máy ảnh chụp lại nội dung đó và không chờ cho đến khi thầy giáo kết thúc “Biên dịch khác với phiên dịch” => Không nhất quán về dữ liệu.

- Ngoài ra, nhờ đồng bộ hóa các tiến trình mà các tiến trình hoạt động phối hợp với nhau mượt hơn, êm ả hơn → Tránh gây ra tình trạng kẹt tiến trình (deadlock).
VD máy tính: Khi máy tính vận hành nhiều tiến trình cùng một thời điểm. Nếu hệ điều hành không đứng ra đồng bộ (yêu cầu chương trình này đứng chờ cho đến khi một chương trình khác hoàn thành) mà cho tiến trình hoạt động tự do, chiếm CPU sẽ dẫn đến trình trạng treo máy.
VD thực tế: Mỗi một xe máy trên đường là một tiến trình, cùng nhau sử dụng tài nguyên dùng chung là mặt đường. Nếu không có công an giao thông (hệ điều hành) đứng ra điều phối, hướng dẫn đường đi khi đông xe thì sẽ bị kẹt xe => Đồng bộ để bảo vệ tài nguyên là rất quan trọng.

Đoạn tương tranh là đoạn mã chương trình, điều khiển công việc của tiến trình có tính chất, mà khi thể hiện đoạn mã đó tác động tới tài nguyên dùng 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).

Phát biểu bài toán:
Giả sử Bộ nhớ đệm(Buffer) bao gồm nhiều khoang (Items) được tiến hành Producer lần lượt đưa các sản phẩm S1, S2,... vào.
Tiến trình Consumer lần lượt lấy sản phẩm ra theo dúng thứ tự.
Công việc của Procuder phải đồng bộ với Consumer: Không được đưa sản phẩm vào khi Buffer đầy, không được lấy ra khi chưa có

- 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.

KN: Đ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 nhưng đặc biệt ở chổ nó chứa các lệnh liên quan đến tài nguyên dùng chung, với các tiến trình khác (đọc hay sửa nội dung, tài nguyên dùng chung).

Vấn đề đoạn tương tranh(critical-section Problem)

-giả sứ có n tiến trình(P0,P1, P2...Pn). Mỗi tiến trình có 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 ĐTT của nó thì không có tiến trình 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à 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).

Giải quyết vấn đề tương tranh phải thỏa các điều kiện sau:

-Loại trừ lẫn nhau (Mutual Exclusion): Mỗi thời điểm chỉ có 1 tiến trình vận hành trong đoạn tương tranh.

-Tiến triển(Progress). Không có tiến trình nào phải chờ vô hạn tại đoạn Đăng nhập của nó.