Sơ lược về Edsger Wybe Dijkstra và Đèn hiệu

Xem chủ đề cũ hơn Xem chủ đề mới hơn Go down

Sơ lược về Edsger Wybe Dijkstra và Đèn hiệu

Bài gửi  doquoctrung(I22A) on 31/3/2013, 09:32

* Sơ lược Edsger Wybe Dijkstra:



- Edsger Wybe Dijkstra (phát âm tiếng Hà Lan: [ˈɛtsxər ˈwibə ˈdɛɪkstra] ( nghe); 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. 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.
- 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.
* Đèn hiệu:
- Trong khoa học máy tính, đèn báo là một biến được bảo vệ hoặc một kiểu dữ liệu trừu tượng tạo ra sự trừu tượng hoá đơn giản nhưng hữu dụng để kiểm soát truy cập của nhiều tiến trình đến một tài nguyên chung trong môi trường lập trình song song.
Một cách nhìn về đèn báo là một bản ghi có bao nhiêu đơn vị của một tài nguyên có thể sử dụng, gắn với các tác vụ điều chỉnh bản ghi đó một cách an toàn (nghĩa là không tạo ra race condition) khi yêu cầu hoặc giải phóng các đơn vị và đợi đến khi một đơn vị rảnh rỗi nếu cần. Đèn báo là một công cụ hữu ích để chống race condition và khoá chết, tuy nhiên việc sử dụng nó không đảm bảo rằng chương trình không gặp phải các vấn đề trên. Đèn báo cho phép một số lượng tuỳ ý tài nguyên gọi là đèn báo đếm (counting semaphore) trong khi đèn báo bị giới hạn trong giá trị 0 và 1 được gọi là đèn báo nhị phân (binary semaphores).
Khái niệm đèn báo được phát minh bởi nhà nghiên cứu người Hà Lan Edsger Dijkstra,[1] and the concept has found widespread use in a variety of operating systems.
Trong khoa học máy tính, đèn báo là một biến được bảo vệ hoặc một kiểu dữ liệu trừu tượng tạo ra sự trừu tượng hoá đơn giản nhưng hữu dụng để kiểm soát truy cập của nhiều tiến trình đến một tài nguyên chung trong môi trường lập trình song song.
Một cách nhìn về đèn báo là một bản ghi có bao nhiêu đơn vị của một tài nguyên có thể sử dụng, gắn với các tác vụ điều chỉnh bản ghi đó một cách an toàn (nghĩa là không tạo ra race condition) khi yêu cầu hoặc giải phóng các đơn vị và đợi đến khi một đơn vị rảnh rỗi nếu cần. Đèn báo là một công cụ hữu ích để chống race condition và khoá chết, tuy nhiên việc sử dụng nó không đảm bảo rằng chương trình không gặp phải các vấn đề trên. Đèn báo cho phép một số lượng tuỳ ý tài nguyên gọi là đèn báo đếm (counting semaphore) trong khi đèn báo bị giới hạn trong giá trị 0 và 1 được gọi là đèn báo nhị phân (binary semaphores).
Khái niệm đèn báo được phát minh bởi nhà nghiên cứu người Hà Lan Edsger Dijkstra,[1] and the concept has found widespread use in a variety of operating systems.
- Ý nghĩa cài đặt:
-Đèn báo đếm được trang bị hai thao tác, kí hiệu là V và P. Thao tác V tăng đèn báo S và thao tác P giảm nó. Ý nghĩa của chúng được giải thích bên dưới. Ngoặc vuông chỉ ra các thao tác nguyên tử, nghĩa là các thao tác không thể chia nhỏ dưới góc nhìn của các tiến trình khác.




Giá trị của đèn báo S là số đơn vị của tài nguyên còn rỗi. Thao tác P chờ đợi tích cực hoặc ngủ cho đến khi tài nguyên được bảo vệ trở nên rảnh rỗi, khi đó nó ngay lập tức yêu cầu. Thao tác V ngược lại: làm cho tài nguyên rảnh rỗi trở lại sau khi một tiến trình đã sử dụng xong.

- Đèn báo và mutex:
- Mutex về căn bản giống như đèn báo nhị phân và đôi khi sử dụng cùng một cách cài đặt. Tuy nhiên khái niệm "mutex" thường được sử dụng để mô tả một cấu trúc ngăn cản hai tiến trình cũng thực hiện một đoạn mã hoặc truy cập một dữ liệu cùng lúc. Khái niệm đèn báo nhị phân thường mô tả cấu trúc dùng để hạn chế truy cập vào một tài nguyên.
- Trong nhiều trường hợp một mutex có khái niệm "chủ": duy nhất tiến trình khoá mutex được quyền mở nó. Ngược lại đèn báo nói chung không đặt ra ràng buộc này, điều mà ví dụ người sản xuất - người tiêu dùng ở trên dựa vào.

doquoctrung(I22A)

Tổng số bài gửi : 17
Join date : 09/03/2013

Xem lý lịch thành viên

Về Đầu Trang Go down

Xem chủ đề cũ hơn Xem chủ đề mới hơn Về Đầu Trang


 
Permissions in this forum:
Bạn không có quyền trả lời bài viết