Thảo luận Bài 5

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

.1. Trình bày thuật giải điều phối FCFS.
Đến trước - Phục vụ trước (First-Come, First-Served Scheduling - FCFS)
- Đơn giản, dễ thực hiện.
- Các tiến trình trong Ready Queue được cấp CPU từ đầu dãy đến cuối dãy theo quy tắc FIFO (First-In, First-Out).
- Thời gian chờ trung bình khá lớn. (Vd: nộp bài kiểm tra cho Thầy: thì lần lượt nhóm từng 5 người lên theo thứ tự trên bảng -> 5 tiếp người tiếp theo sẽ chờ trong khoảng thời gian hơi lâu)
* Quy tắc FIFO (First-In, First-Out):
- Nguyên tắc :
+ Processor được cấp phát cho tiến trình đầu tiên trong danh sách sẵn sàng có yêu cầu, là tiến trình được đưa vào hệ thống sớm nhất.
+ FIFO được sử dụng trong điều phối độc quyền nên khi tiến trình được cấp processor nó sẽ sở hữu processor cho đến khi kết thúc xử lý hay phải đợi một thao tác vào/ra hoàn thành, khi đó tiến trình chủ động trả lại processor cho hệ thống.
VD: Việc phục vụ khách trong nhà hàng. Thực khách sẽ đến và gọi món ăn cho mình. Mỗi món ăn cần thời gian chuẩn bị khác nhau

2. Trình bày thuật giải điều phối PS.
- Mỗi tiến trình được cấp một số nguyên (Priority Number) dùng để ấn định Độ ưu tiên.
- CPU luôn dành cho tiến trình với độ ưu tiên cao hơn (Priority Number nhỏ hơn  Độ ưu tiên cao hơn ) với 2 phương án:
Có tiếm quyền ( Preemptive )
Không tiếm quyền ( Non-Preemptive )
- SJFS là trường hợp đặc biệt của PS với độ ưu tiên:
P= ( Khoảng CPU kế tiếp )

3. Trình bày thuật giải điều phối SJFS.
Ngắn hơn-Chạy trước (Shortest-Job-First Scheduling-SJFS)
- Đúng hơn phải được gọi là Shortest-Next-CPU-Burst, nghĩa là tiến trình có Khoảng CPU kế tiếp nhỏ hơn thì được chạy trước. Trong trường hợp bằng nhau, dùng thuật giải FCFS.
- Là giải thuật khá tối ưu, nhưng phải biết cách ước đoán khoảng CPU kế tiếp.
- SJFS không tiếm quyền (Non-Preemptive SJFS): Tiến trình hiện thời được thực hiện đến hết khoảng CPU của nó.
- SJFS có tiếm quyền (Preemptive SJFS): Tiến trình mới có Next CPU Burst nhỏ hơn khoảng thời gian CPU còn lại của tiến trình đang vận hành sẽ được chọn thay thế (Shortest Remaining First).

4. Trình bày thuật giải điều phối RRS.
- Như điều phối kiểu FCFS nhưng cho phép tiếm quyền khi tiến trình đang chạy bị hết thời lượng.
- Mỗi tiến trình được cấp 1 thời lượng CPU (Time Quantum), thường từ 10-100 mili giây. Sau khoảng thời gian này, nó bị tiếm quyền và được đưa vào cuối hàng chờ Ready. Tiến trình đầu tiên trong hàng chờ Ready được chọn kế tiếp.
- Nếu có n tiến trình và thời lượng là q , mỗi tiến trình nhận 1/n thời gian CPU bao gồm các đoạn không quá q đơn vị thời gian.

5. Trình bày thuật giải điều phối MQS.
- Hàng chờ Ready được phân cấp thành nhiều mức có độ ưu tiên khác nhau, ví dụ: Mức các tiến trình tương tác (Interactive) chạy ở mặt trước ( Foreground ) có độ ưu tiên cao nhất và Mức các tiến trình lô ( Batch ) vận hành trong hậu trường (Background ) .
- Mỗi hàng chờ có thuật giải điều phối riêng, ví dụ: Foreground dùng RRS, Background dùng FCFS.
- Quan hệ giữa các mức:
Ưu tiên cố định: Xong hết các tiến trình mức trên rồi mới chuyển xuống mức dưới. Đang chạy tiến trình mức dưới mà xuất hiện tiến trình mới mức cao hơn, tiến trình mức dưới sẽ bị tiếm quyền cho tiến trình mới có độ ưu tiên cao hơn ( Hệ Solaris 2 dùng cách này ) .
Phân bổ theo tỉ lệ thời lượng: ví dụ: 80% thời lượng CPU dành cho Foreground, 20 % cho Background.

6. Trình bày thuật giải điều phối MFQS.
- Như MQS nhưng cho phép Điều tiết tiến trình sang mức khác, ví dụ: những tiến trình hướng CPU được đưa xuống mức dưới, trong khi tiến trình hướng I/O hoặc chờ lâu được chuyển lên trên.
- MFQS đặc trưng bởi các thông số:
+ Số mức (số hàng chờ)
+ Thuật giải điều phối cho mỗi mức
+ Phương thức nâng cấp tiến trình
+ Phương thức hạ cấp tiến trình
+ Phương thức chọn hàng chờ (chọn mức) cho tiến trình mới

Bài 6 : Ngắn hơn-Chạy trước (Shortest-Job-First Scheduling-SJFS)

.Ngắn hơn-Chạy trước (Shortest-Job-First Scheduling-SJFS)
* SJFS không tiếm quyền (Non-Preemptive SJFS): Tiến trình hiện thời được thực hiện đến hết khoảng CPU của nó. (Có nghĩa là ko được ngắt CPU khi 1 tiến trình đang chạy).

Ví dụ: Ở lớp I12A, bình thường 18h vô lớp thì ai đến sớm thì có quyền ngồi chỗ tốt mà mình chọn ( thông thường bạn nào cận thì thường đi sớm để được ngồi bàn 1)
ví dụ 2: Thầy chọn 5 bạn để giải bài tập thì bạn nào lên trước thì được ưu tiên làm trước, và khi nào bạn 1 làm xong thì bạn thứ 2 mới được làm.


* SJFS có tiếm quyền (Preemptive SJFS): Tiến trình mới có Next CPU Burst nhỏ hơn khoảng thời CPU còn lại của tiến trình đang vận hành sẽ được chọn thay thế (Shortest - Remaining - First).

Ví dụ: Ở quán nhậu 404 Q.7 khi chúng ta tới đó ăn và kêu 10 món (đi đông nên kêu nhiều), bồi bàn tới ghi sổ và đưa cho anh đầu bếp làm 10 món. Đang làm được 4 món thì có thực khách bàn B gọi 7 món nhậu thì người đầu bếp chuyển sang làm thức ăn cho thực khách bàn B. Trong khi đang làm được 3 món ăn cho bàn B thì lại có thêm thực khách bàn C kêu 4 món thì anh đầu bếp sẽ quay sang làm 4 món cho bàn C. Trong khi làm được 2 món cho bàn C thì thực khách bàn D gọi 1 món thì anh đầu bếp quay sang làm 1 món cho thực khách bàn D.

Giải thích bài ví dụ về thuật toán Roud robin (RRS)

Câu 3: Bài tập Điều phối CPU với thuật giải Round-Robin Scheduling (RRS)
Đề bài: một hệ thống có 3 tiến trình với thời điểm đến và sử dụng CPU như sau:
a) Thể hiện biểu đồ Gantt ?
b) Tình thời gian chờ trung bình của tiến trình ?
Giải:



b. Tình thời gian chờ trung bình của tiến trình:
+ Thời gian chờ của các tiến trình: - P1=(40-5)-25=35-25=10 (ms)
- P1=(40-5)-25=35-25 =10 (ms)
- P2=(55-20)-15=35-15=20 (ms)
- P3=(50-30)-10=20-10=10 (ms)
+ Thời gian chờ trung bình của tiến trình:
(P1+P2+P3)/3=(10+20+10)/3=40/3=13.3(ms)



bài này ko hiểu cho lắm có ai giải thích tường tận từng dòng không...nhất là biểu đồ gantt???và cách vẽ

Trước tiên xin nói đề bài của bạn HaHoangCongTien80 (113A) bị thiếu một phần rất quan trọng đó là chưa cho Quantum, là đơn vị thời lượng hoạt động của tiến trình trước khi bị tiếm quyền. Đây là bài tập yêu cầu điều phối CPU theo với thuật giải Round-Robin Scheduling (RRS) nên không thể không cho quantum. Dựa vào bài làm thì ta thấy quantum= 10ms, và đây cũng là ví dụ thầy cho trên lớp.
Giải thích bài giải ( mình giải thích bằng lời cụ thể nhé, cho những bạn chưa hiểu dể thấy):
Đề bài cho 3 tiến trình, ứng với mỗi tiến trình là thời điểm đến và CPU Burst (tạm hiểu là thời gian để hoàn thành tiến trình):


Với Quantum=10ms, ký hiệu Quantum: q

Câu a)
Tại thời điểm 5, P1 vào thực thi, hết lượng q =10ms, P1 dừng thực thi. Lúc này thời điểm đang là 15 (P1 thực thi được 10ms/25ms). Ta có P2 có thời điểm đến là 20 và của P3 là 30. Như vậy trong hệ thống lúc này chỉ có P1 là có thời điểm đến nhổ nhất (15) nên P1 tiếp tục được gọi vào thực thi.
Hết lượng q=10, P1 bị tiếm quyền đưa vào cuối hàng đợi tại thời điểm 25 (P1 thực thi được 20ms/25ms). Trong khi P1 đang thực thi thì tại thời điểm 20 P2 được gọi vào hàng đợi, tại thời điểm 25 P1 bị chặn thì P2 vào thực thi.
P2 thực thi hết q=10ms thì bị chặn, thời điểm lúc này là 35.
Trong lúc P2 thực thi thì tại thời điểm 30 P3 được gọi vào hàng đợi. Nhưng bạn để ý lúc này trong hàng đợi đã có P1 được gọi vào lúc trước đó, vì thế P3 được gọi vào xếp sau P1.
Tại thời điểm 35 P2 bị chặn(P2 thực thi được 10ms/15ms), được đưa vào hàng đợi, và xếp sau P3 đã được đưa vào lúc trước. Trong hệ thống lúc này không còn tiến trình nào chờ nữa nên sẽ XÉT TRONG HÀNG ĐỢI.
Lúc này P1 đang đứng đầu hàng đợi nên được gọi thực thi. Vì P1 chỉ còn 5ms là thực thi xong nên chưa hết lượng q=10ms thì P1 đã kết thúc tại thời điểm 40.
Lúc này xét hàng đợi thấy P3 đứng đầu nên P3 được thực thi. Ta có CPU Burst của P3 =10, trùng với lượng q nên khi hết lượng q=10 thì P3 cũng kết thúc.
Trong hàng đợi chỉ còn P2 nên P2 thực thi, vì P2 đã thực thi đươc 10ms nên còn 5ms< q. Sau 5ms P2 kết thúc tại thời điểm 55

Câu b) Tính thời gian chờ trung bình của tiến trình:
Bạn áp dụng công thức của thầy cho trên lớp (Đây là thành quả của các khóa anh chị đi trước)
Tính thời gian chờ của tiến trình: P(i)= ( T2 - T1 ) - CPU Burst

Trong Đó: (i): là tiến trình thứ i
T2: Thời điểm kết thúc của tiến trình
T1: Thời điểm bắt đầu của tiến trình

ps: Bài hơi dài nhưng cụ thể, bạn nào có thấy sai chỗ nào thì chỉ giúp nha. Chúc mọi người học tốt..

Bốn tình huống ra quyết định của trình điều phối.


.
Bốn tình huống ra quyết định của trình điều phối.
1. Khi tiến trình chuyển từ Running sang Waiting (chờ I/O, chờ tiến trình con)
2. Khi tiến trình chuyển từ Running sang Ready( do ngắt xảy ra).
3. Khi tiến trình chuyển từ Waiting sang Ready( do kết thúc I/O).
4. Khi tiến trình kết thúc công việc.
Phân biệt điều phối tiếm quyền và điều phối không tiếm quyền:
• Điều phối không tiếm quyền( Non - Preemptive): sơ đồ điều phối chỉ tiến hành trong tình huống 1 và 4. Tiến trình giữ CPU cho đến khi kết thúc bình thường hoặc khi chuyển sang trạng thái Waiting( cách làm trong Windows 3.1 và Macintosh OS). Dùng khi máy không có Timer.
• Điều phối có tiếm quyền( Preemptive):sơ đồ điều phối tiến hành trong cả 4 tình huống.
• Giống nhau: cùng điều phối CPU( chọn tiến trình trong Ready Queue để cấp thời gian CPU( chuyển sang trạng thái Running)).
• Khác nhau:
 Preemptive Scheduling thì điều phối CPU có tiếm quyền còn Non – Preemptive Scheduling thì điều phối CPU không tiếm quyền.
 Non – Preemptive Scheduling: có nghĩa là khi có 1 tiến trình P1, P2, P3 xuất hiện thì nó sẽ thực hiện 1 phần của tiến trình P1, sau đó nó tiếm quyền và thực hiện 1 phần của tiến trình P2, sau đó nó tiếm quyền và thực hiện 1 phần của tiến trình P3. Cứ như vậy nó sẽ thực hiện xong các tiến trình.

Vì sao hệ điều hành phải có chức năng điều phối CPU. Năm tiêu chí điều phối CPU


.
1. Vì sao hệ điều hành phải có chức năng điều phối CPU?
Trong các hệ đa chương thực thi nhiều chương trình đồng thời làm tăng hiệu suất hệ thống.
Tại mỗi thời điểm, chỉ có một process được thực thi. Do đó, cần phải giải quyết vấn đề phân chia, lựa chọn process thực thi sao cho được hiệu quả nhất  chiến lược định thời CPU.

2.Năm tiêu chí điều phối CPU là những tiêu chí nào?
1. Công suất CPU (CPU Utilisation): Thực tế đạt từ 40% - 90% thời gian CPU. CPU càng bận càng tốt.
2. Thông suất hệ thống (Throughput): Số TT hoàn tất trong 1 đơn vị thời gian, ví dụ: 1 TT / giờ, 10 TT / giây.
3. Tổng thời gian làm việc (Turnaround Time): Kể từ khi bắt đầu đến khi kết thúc tiến trình (Bao gồm tổng thời gian chờ tại Ready Queue, tổng thời gian sử dụng CPU, tổng thời gian I/O, …).
4. Thời gian chờ (Waiting Time): Tổng thời gian chờ tại Ready Queue.
5. Thời gian đáp ứng (Response Time): Thời gian kể từ khi người dùng đặt yêu cầu cho đến khi có phản hồi đầu tiên.

Ý nghĩa khi vẽ 1 biểu đồ Gantt
.
1. Biểu đồ Gantt là gì?

Biểu đồ Gantt là đồ thị với những thanh nằm ngang để chỉ hoạt động ngược lại với ngày. Đây là công cụ để đo lường tiến độ thực hiện dự án so với kế hoạch đề ra.

Cách vẽ một biểu đồ Gantt:

* Vẽ đường thời gian của dự án/ chương trình từ đầu cho đến cuối dự án trên trục toạ độ (trục tung- nằm ngang);
* Trên trục hoành (ngược lại với trục tung) thể hiện các hoạt động cần được hoàn thành trong suốt dự án/ chương trình;
* Vẽ một thanh nằm ngang ở mỗi mức độ của hoạt động để chỉ khoảng thời gian thực hiện mỗi công việc.

TIP Đối với khoảng thời gian dự kiến thực hiện hoạt động có thể sử dụng một công thức để tính thời gian dự kiến:

Trong đó:
PT là thời gian dài nhất hoạt động có thể diễn ra
ET là thời gian ước tính cho hoạt động thực hiện
OT là thời gian ít nhất khi hoạt động diễn ra
ST là thời gian dự kiến và sử dụng ST trên biểu đồ

2. Tại sao biểu đồ Gantt có ý nghĩa?

Biểu đồ Gantt là một cách đơn giản và dễ hiểu để giám sát tiến độ của các hoạt động khi thực hiện dự án/ chương trình

3. Biểu đồ Gantt hỗ trợ như thế nào?

Biểu đồ Gantt hỗ trợ bạn theo 2 cách chính. Đầu tiên, chúng cung cấp cho bạn hình ảnh trực quan về các hoạt động và thời gian thực hiện. Thứ hai, chúng cho phép bạn truyền đạt động tin bằng một cách dễ dàng với các đồng nghiệp khác trong nhóm về trạng thái của dự án/ chương trình.

4. Biểu đồ Gantt được áp dụng ở đâu?

Biểu đồ Gantt được sử dụng cho bất kỳ dự án/ chương trình để xác định tiến độ và làm rõ mục tiêu. Chúng giúp liên kết giữa mọi người/ nguồn lực trong dự án cùng với nhiều hoạt động trong đó.

5. Biểu đồ Gantt có ý nghĩa khi nào?

Khi bạn đang quản lý một chương trình/ dự án có nhiều hoạt động phức tạp, biểu đồ Gantt được khuyên dùng, đặc biệt nếu bạn yêu cầu lao động đầu vào từ các nguồn khác nhau để hoàn thành các công việc này. Nó giúp bạn nắm rõ được mối quan hệ giữa các công việc, ví dụ khi các công việc thực hiện liên tiếp nhau, hoặc có thể được thực hiện song song.

6. Biểu đồ Gantt đem lại lợi ích cho ai?

Biểu đồ Gantt có lợi cho cả những người quản lý chương trình/ dự án và tất cả những ai tham gia thực hiện công việc trong dự án.

Năm tiêu chí điều phối CPU là ?

.1. Công suất CPU (CPU Utilisation): Thực tế đạt từ 40% - 90% thời gian CPU. CPU càng bận càng tốt.
2. Thông suất hệ thống (Throughput): Số TT hoàn tất trong 1 đơn vị thời gian, ví dụ: 1 TT / giờ, 10 TT / giây.
3. Tổng thời gian làm việc (Turnaround Time): Kể từ khi bắt đầu đến khi kết thúc tiến trình (Bao gồm tổng thời gian chờ tại Ready Queue, tổng thời gian sử dụng CPU, tổng thời gian I/O, …).
4. Thời gian chờ (Waiting Time): Tổng thời gian chờ tại Ready Queue.
5. Thời gian đáp ứng (Response Time): Thời gian kể từ khi người dùng đặt yêu cầu cho đến khi có phản hồi đầu tiên.

Định nghĩa và mục đích điều phí tiến trình
.Trong môi trường đa chương, có thể xảy ra tình huống nhiều tiến trình đồng thời sẵn sàng để xử lý. Mục tiêu của các hệ phân chia thời gian (time-sharing) là chuyển đổi CPU qua lại giữa các tiến trình một cách thường xuyên để nhiều người sử dụng có thể tương tác cùng lúc với từng chương trình trong quá trình xử lý.

Để thực hiện được mục tiêu này, hệ điều hành phải lựa chọn tiến trình được xử lý tiếp theo. Bộ điều phối sẽ sử dụng một giải thuật điều phối thích hợp để thực hiện nhiệm vụ này. Một thành phần khác của hệ điều hành cũng tiềm ẩn trong công tác điều phối là bộ phân phối (dispatcher). Bộ phân phối sẽ chịu trách nhiệm chuyển đổi ngữ cảnh và trao CPU cho tiến trình được chọn bởi bộ điều phối để xử lý.

Mục đích:
Bộ điều phối không cung cấp cơ chế, mà đưa ra các quyết định. Các hệ điều hành xây dựng nhiều chiến lược khác nhau để thực hiện việc điều phối, nhưng tựu chung cần đạt được các mục tiêu sau :

a) Sự công bằng ( Fairness) :

Các tiến trình chia sẻ CPU một cách công bằng, không có tiến trình nào phải chờ đợi vô hạn để được cấp phát CPU

b) Tính hiệu qủa (Efficiency) : Hệ thống phải tận dụng được CPU 100% thời gian.

c) Thời gian đáp ứng hợp lý (Response time) : Cực tiểu hoá thời gian hồi đáp cho các tương tác của người sử dụng

d) Thời gian lưu lại trong hệ thống ( Turnaround Time) : Cực tiểu hóa thời gian hoàn tất các tác vụ xử lý theo lô.

e) Thông lượng tối đa (Throughput ) : Cực đại hóa số công việc được xử lý trong một đơn vị thời gian.

Tuy nhiên thường không thể thỏa mãn tất cả các mục tiêu kể trên vì bản thân chúng có sự mâu thuẫn với nhau mà chỉ có thể dung hòa chúng ở mức độ nào đó.

Tóm tắt các giải thuật điều phối CPU

.1. Trình bày thuật giải điều phối FCFS.
Đến trước - Phục vụ trước (First-Come, First-Served Scheduling - FCFS)
- Đơn giản, dễ thực hiện.
- Các tiến trình trong Ready Queue được cấp CPU từ đầu dãy đến cuối dãy theo quy tắc FIFO (First-In, First-Out).
- Thời gian chờ trung bình khá lớn. (Vd: nộp bài kiểm tra cho Thầy: thì lần lượt nhóm từng 5 người lên theo thứ tự trên bảng -> 5 tiếp người tiếp theo sẽ chờ trong khoảng thời gian hơi lâu)
* Quy tắc FIFO (First-In, First-Out):
- Nguyên tắc :
+ Processor được cấp phát cho tiến trình đầu tiên trong danh sách sẵn sàng có yêu cầu, là tiến trình được đưa vào hệ thống sớm nhất.
+ FIFO được sử dụng trong điều phối độc quyền nên khi tiến trình được cấp processor nó sẽ sở hữu processor cho đến khi kết thúc xử lý hay phải đợi một thao tác vào/ra hoàn thành, khi đó tiến trình chủ động trả lại processor cho hệ thống.
VD: Việc phục vụ khách trong nhà hàng. Thực khách sẽ đến và gọi món ăn cho mình. Mỗi món ăn cần thời gian chuẩn bị khác nhau

2. Trình bày thuật giải điều phối PS.
- Mỗi tiến trình được cấp một số nguyên (Priority Number) dùng để ấn định Độ ưu tiên.
- CPU luôn dành cho tiến trình với độ ưu tiên cao hơn (Priority Number nhỏ hơn  Độ ưu tiên cao hơn ) với 2 phương án:
Có tiếm quyền ( Preemptive )
Không tiếm quyền ( Non-Preemptive )
- SJFS là trường hợp đặc biệt của PS với độ ưu tiên:
P= ( Khoảng CPU kế tiếp )

3. Trình bày thuật giải điều phối SJFS.
Ngắn hơn-Chạy trước (Shortest-Job-First Scheduling-SJFS)
- Đúng hơn phải được gọi là Shortest-Next-CPU-Burst, nghĩa là tiến trình có Khoảng CPU kế tiếp nhỏ hơn thì được chạy trước. Trong trường hợp bằng nhau, dùng thuật giải FCFS.
- Là giải thuật khá tối ưu, nhưng phải biết cách ước đoán khoảng CPU kế tiếp.
- SJFS không tiếm quyền (Non-Preemptive SJFS): Tiến trình hiện thời được thực hiện đến hết khoảng CPU của nó.
- SJFS có tiếm quyền (Preemptive SJFS): Tiến trình mới có Next CPU Burst nhỏ hơn khoảng thời gian CPU còn lại của tiến trình đang vận hành sẽ được chọn thay thế (Shortest Remaining First).

4. Trình bày thuật giải điều phối RRS.
- Như điều phối kiểu FCFS nhưng cho phép tiếm quyền khi tiến trình đang chạy bị hết thời lượng.
- Mỗi tiến trình được cấp 1 thời lượng CPU (Time Quantum), thường từ 10-100 mili giây. Sau khoảng thời gian này, nó bị tiếm quyền và được đưa vào cuối hàng chờ Ready. Tiến trình đầu tiên trong hàng chờ Ready được chọn kế tiếp.
- Nếu có n tiến trình và thời lượng là q , mỗi tiến trình nhận 1/n thời gian CPU bao gồm các đoạn không quá q đơn vị thời gian.

5. Trình bày thuật giải điều phối MQS.
- Hàng chờ Ready được phân cấp thành nhiều mức có độ ưu tiên khác nhau, ví dụ: Mức các tiến trình tương tác (Interactive) chạy ở mặt trước ( Foreground ) có độ ưu tiên cao nhất và Mức các tiến trình lô ( Batch ) vận hành trong hậu trường (Background ) .
- Mỗi hàng chờ có thuật giải điều phối riêng, ví dụ: Foreground dùng RRS, Background dùng FCFS.
- Quan hệ giữa các mức:
Ưu tiên cố định: Xong hết các tiến trình mức trên rồi mới chuyển xuống mức dưới. Đang chạy tiến trình mức dưới mà xuất hiện tiến trình mới mức cao hơn, tiến trình mức dưới sẽ bị tiếm quyền cho tiến trình mới có độ ưu tiên cao hơn ( Hệ Solaris 2 dùng cách này ) .
Phân bổ theo tỉ lệ thời lượng: ví dụ: 80% thời lượng CPU dành cho Foreground, 20 % cho Background.

6. Trình bày thuật giải điều phối MFQS.
- Như MQS nhưng cho phép Điều tiết tiến trình sang mức khác, ví dụ: những tiến trình hướng CPU được đưa xuống mức dưới, trong khi tiến trình hướng I/O hoặc chờ lâu được chuyển lên trên.
- MFQS đặc trưng bởi các thông số:
+ Số mức (số hàng chờ)
+ Thuật giải điều phối cho mỗi mức
+ Phương thức nâng cấp tiến trình
+ Phương thức hạ cấp tiến trình
+ Phương thức chọn hàng chờ (chọn mức) cho tiến trình mới

4 tình huống ra quyết định của trình điều phối và phân biệt Điều phối không tiếm quyền(Non - Preemtive)và Điều phối có tiếm quyền (Preemtive)

.A. Bốn tình huống ra quyết định của trình điều phối CPU:
* Các tình huống ra quyết định của trình điều phối:
1. Khi tiến trình chuyển từ Running sang Waiting (Chờ I/O. chờ tiến trình con)
2. Khi tiến trình chuyển từ Running sang Ready (do ngắt xảy ra)
3. Khi tiến trình chuyển từ Waiting sang Ready (khi kết thúc I/O)
4. Khi tiến trình kết thúc công việc.
* Sơ đồ điều phối chỉ tiến hành trong tình huống 1 và 4 được gọi là điều phối không tiếm quyền (Non-Preemptive): Tiến trình giữ CPU cho đến khi kết thúc bình thường hoặc khi chuyển sang trạng thái Waiting . Dùng khi máy không có Timer.
* Sơ đồ điều phối tiến hành trong cả 4 tình huống được gọi là điều phối có tiếm quyền (Preemptive).

B. Phân biệt điều phối có tiếm quyền và không có tiếm quyền:
- Giống nhau: cùng điều phối CPU (chọn tiến trình trong Ready Queue để cấp thời gian CPU (chuyển sang trạng thái Running)).
- Khác nhau: Preemptive Scheduling thì điều phối CPU có tiếm quyền còn Non-Preemptive Scheduling thì điều phối CPU không tiếm quyền.
- Non-Preemptive Scheduling: Có nghĩa là khi có 1 tiến trình P1,P2 xuất hiện thì nó sẽ thực hiện xong tiến trình P1 , sau đó mới thực hiện tiến trình P2 (cách làm trong Windows 3.1 và Macintosh OS)
- Preemptive Scheduling : có nghĩa là khi có 1 tiến trình P1,P2,P3 xuất hiện thì nó sẽ thực hiện 1 phần của tiến trình P1 , sau đó nó tiếm quyền và thực hiện 1 phần của tiến trình P2 , sau đó nó tiếm quyền và thực hiện 1 phần của tiến trình P3. Cứ như vậy nó sẽ thực hiện xong các tiến trình.

C. Chủ ý: Trong 4 tình huống ra quyết định của trình điều phổi CPU ở trên thì tình huống(Khi tiến trình chuyển từ Running sang Waiting (Chờ I/O. chờ tiến trình con) và Khi tiến trình kết thúc công việc.) là tình huống mà điều phổi không tiếm quyền(Không dùng CPU) vì lúc này chương trình tự nguyện trá CPU.Còn tình huống(Khi tiến trình chuyển từ Running sang Ready (do ngắt xảy ra) vá Khi tiến trình chuyển từ Waiting sang Ready (khi kết thúc I/O)) là tình huống mad điều phổi có tiếm quyền.Đây là mô hình hiện đại nhằm giúp CPU hoạt động hết hiệu suất của mình để làm giám thiếu tối đa thời gian chờ nhằm đáp ứng được hiệu quả công việc cao hơn.

So sánh sự giống nhau và khác nhau giữa giải thuật MQS và MFQS:

.- Giống nhau: Multilevel Queue Scheduling (Điều phối hàng chờ nhiều mức) và Multilevel Feedback Queue Scheduling (Điều phối hàng chờ nhiều mức có điều tiết) cùng sử dụng nhiều mức hàng chờ với độ ưu tiên khác nhau, mỗi hàng chờ có thể sử dụng thuật toán riêng.

- Khác nhau: Multilevel Feedback Queue Scheduling cho phép điều chuyển (điều tiết) tiến trình từ hàng chờ này sang hàng chờ kia (hạ cấp độ hay nâng cấp độ ưu tiên), nghĩa là mềm dẻo hơn Multilevel Queue Scheduling.
- Và đối với MQS thì khi các tiến trình được xếp vào hàng đợi thì không thay đổi được vị trí còn MFQS thì tiến trình có thể di chuyển từ mức này sang mức khác và ngược lại.

Ví dụ: Trong ga Hòa Hưng có 2 ô cửa bán vé, những người mua vé xếp hàng vào 2 cửa. cửa 1 là cho những người ưu tiên, cửa 2 là những người bình thường ,chỉ có 1 cô nhân viên bán vé thôi.

MQS: chỉ 1 cô bán vé chạy từ cửa này sang cửa kia, cửa nào có khách thì chạy sang cửa đó.
MFQS: có điều phối mềm dẻo nếu có sự ưu tiên, đẩy khách hàng từ cửa này sang cửa kia, giúp cho việc bán vé nhanh hơn.

Câu 3: Trình bày khái niệm đèn tín hiệu và 2 ứng dụng của đèn hiệu.

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

Ý nghĩa của hàm Wait áp dụng cho đèn hiệu S , Ý nghĩa của hàm signal


.Ý nghĩa của hàm Wait áp dụng cho đèn hiệu S :
Chờ cho đến khi giá trị của đèn hiệu S > = 1 sau đó qua được lệnh chờ này và giá trị của đèn tự động giảm đi 1.
Ý nghĩa của hàm signal : Đèn S tăng lên 1

Trình bày vấn đề và cấu trúc mã của đoạn tương tranh (Critical-Section Problem)

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

Thực thi bài toán sản xuất và tiêu thụ được đồng bộ bằng ba đèn hiệu

.HANDLE semEmpty, semFull; //hai đèn hiệu
CRITICAL_SECTION critSec;//Biến kiểu Mutex
void Producer(void * p)
{
while (1)
{
// ... Sản xuất (nextProduced)
// Chờ đến khi có chỗ trống
WaitForSingleObject(semEmpty, INFINITE);
EnterCriticalSection(&critSec);
//…Sắp sản phẩm vào Buffer
// Tăng (semFull) lên 1
ReleaseSemaphore(semFull, 1, NULL);
LeaveCriticalSection(&critSec);
SuspendThread(GetCurrentThread());
}
}
void Consumer()
{
int nextConsumed;
while (1)
{
// Chờ đến khi có sản phẩm
WaitForSingleObject(semFull, INFINITE);
EnterCriticalSection(&critSec);
nextConsumed=buffer[out];
out=(out+1)%BUFFER_SIZE;
// Tăng (semEmpty) lên 1
ReleaseSemaphore (semEmpty, 1, NULL);
LeaveCriticalSection(&critSec);
// ... Tiêu thụ (nextConsumed)
SuspendThread(GetCurrentThread());
}
}

- Biến semEmpty dùng để chứa mục quản của đèn hiệu quản lý số vùng trống trong bộ đệm.
- Biến semFull dùng để chứa mục quản của đèn hiệu quản lý số sản phẩm trong bộ đệm.
- CritSec là đối tượng đèn hiệu kiểu mutex dùng để bảo vệ đoạn tương tranh để đảm bảo tính loại trừ lẫn nhau trong công việc của các tiến trình với tài nguyên dùng chung.

Câu 3: Trình bày khái niệm đèn hiệu và 2 ứng dụng của nó

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

2 ứng dụng của đèn hiệu:

1. Giải quyết vấn đề VTT: Bằng đèn hiệu nhị phân
- Sử dụng đèn hiệu mutex với trạng thái ban đầu =1

+ Mã của tiến trình Pi bây giờ có cấu trúc:
Code:
typedef int semaphore;
semaphore mutex=1; // Binary Semaphore
while (1) // (Đèn hiệu nhị phân)
{
remainder section
wait (mutex);
critical section
signal (mutex);
remainder section
}
=> Loại trừ tương hỗ, đảm bảo trong 1 thời điểm chỉ có 1 tiến trình ở đoạn tương tranh.

2. Đảm bảo các tiến trình làm việc đúng thứ tự

Giả sử P1 có mã S1,P2 có mã S2,cần tổ chức sao cho S2 chỉ thi hành sau S1.
+Ta dùng đèn hiệu sau:
semaphore synch = 0;
Cấu trúc P1:
S1
signal (synch) ;
Cấu trúc P2:
wait(synch);
S2

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

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

Ví dụ: Xe qua cầu yếu

.Mã của tiến trình Xei có cấu trúc như sau:
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
Typedef int semaphore;
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 cầu 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.

Admin
- Hiểu tốt !
- Cần chú ý hình thức trình bày bài !

Câu 1 : Trình bày mục đích đồng bộ hóa công việc các tiến trình.Cho ví dụ minh họa?

.• Đả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ụ : bạn a lên bản viết một lá đơn phần họ tên ghi là nguyễn văn a và phần ký tên là lê văn b. lúc sau đó bạn b lên bảng sửa lại phần ký tên cho đúng là nguyễn văn a. lúc đó phái dưới lớp có bạn c lấy máy ảnh chụp lại cái bảng đang lúc bạn b đang sửa lại phần ký tên mới gi là nguyễn văn, dẫn đến nội dung sai lệch, không hoàn chỉnh và thiếu nhất quán. đáng lẽ bạn c phải chờ bạn b thực hiện song công việc là sửa phần ký tên là nguyễn văn a song rồi mới chụp thì nội dung mới đúng.

Admin
Hiểu đúng !

Tiểu Sử Của Nhà Khoa Học Máy Tính E.W. Dijkstra

._ Tên đầy đủ là Edsger Wybe Dijkstra, sinh ngày 11 tháng 5 năm 1930 tại Rotterdam, mất ngày 6 tháng 8 năm 2002 tại Nuenen sau một thời gian dài bị ung thư, ông 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).
_ 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.
_ 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".
_ Một năm sau khi ông mất, 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.
.

Câu 3: Trình bày Khái niệm đèn hiệu như 1 phương tiện đồng bộ hóa công việc các tiến trình.

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

Giải Turing


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

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- đã đó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
1980: C. Antony R. Hoare-Cho những đóng góp cơ bản về thiết kế và định nghĩa ngôn ngữ lập trình. Ông cũng là tác giả của giải thuật sắp xếp nổi tiếng Quick sortvà ngôn ngữ CSP
1981: Edgar F. Codd-Với những đóng góp nền tảng cho lý thuyết và vận dụng các hệ thống quản trị cơ sở dữ liệu, đặc biệt là cơ sở dữ liệu quan hệ
1982: Stephen A. Cook-Góp phần thúc đẩy và mở rộng việc nhận thức về độ phức tạp tính toán
1983: Ken Thompson và Dennis M. Ritchie-Với việc phát triển lý thuyết hệ điều hành và đặc biệt là hệ điều hành UNIX
1984: Niklaus Wirth-Cho việc phát triển các ngôn ngữ lập trình mới EULER, ALGOL-W, MODULA và PASCAL
1985: Richard M. Karp-Với những đóng góp liên tục về lý thuyết lập trình bao gồm việc phát triển các giải thuật hiệu quả cho luồng mạng và các bài toán tối ưu tổ hợp, định ra khả năng tính toán thời gian đa thức và các khái niệm về hiệu quả giải thuật, và đóng góp nổi bật về lý thuyết NP-đầy đủ NP-completeness
1986: John Hopcroft và Robert Tarjan-Cho những đóng góp căn bản về phân tích thiết kế cấu trúc dữ liệu và giải thuật
1987: John Cocke- Cho những đóng góp quan trọng trong việc thiết kế và lý thuyết hóa chương trình dịch, kiến trúc các hệ thống lớn và phát triển các tập lệnh đơn giản trong máy tính (RISC)
1988: Ivan Sutherland-Cho việc tiên phong trong lĩnh vực đồ họa computer graphics, khởi đầu với chương trình Sketchpad
1989: William (Velvel) Kahan-Cho những đóng góp cơ bản về phân tích sốnumerical analysis. Một trong những chuyên gia đầu ngành về tính toán dấu phẩy động floating-point.
1990: Fernando J. Corbató-Đi đầu trong việc tổ chức và dẫn dắt sự phát triển của các hệ thống máy tính mục đích chung, large-scale, chia sẻ thời gian và nguồn lực, CTSS vàMultics.
1991: Robin Milner-Cho ba thành tựu quan trọng: 1) LCF, cơ chế hóa Logic Scott's of của hàm khả tính (Computable Functions), 2) ML, ngôn ngữ đầu tiên có tính đa hình type inference cùng với kiểu "an toàn" type-safe và cơ chế bắt ngoại lệ exception-handling ; 3) Các hệ thống truyền thông giải tíchCCS, lý thuyết tông quát về tương tranh concurrency. Ông cũng đồng thời khái quát hóa full abstraction, nghiên cứu các mối quan hệ ngữ nghĩa thao tác. operational.
1992: Butler W. Lampson-Cho những đóng góp cho việc phát triển môi trường tính toán cá nhân và phân tán.
1993: Juris Hartmanis và Richard E. Stearns-Thiết lập nền tảng cho lý thuyết độ phức tạp tính toán.
1994: Edward Feigenbaum và Raj Reddy-Tiên phong trong việc xây dựng các hệ thống lớn về trí tuệ nhân tạo, chứng minh tầm quan trọng thực tiễn và khả năng thương mại của trí tuệ nhân tạo.
1995: Manuel Blum- Ghi nhận cho những đóng góp cơ bản về lý thuyết độ phức tạp tính toán và các ứng dụng trong cryptography và program checking.
1996: Amir Pnueli- Giới thiệu temporal logic vào khoa học máy tính và các hệ thống verification.
1997: Douglas Engelbart- Đóng góp về tính toán tương tác
1998: Jim Gray- Đóng góp về cơ sở dữ liệu và xử lý giao dịch
1999: Frederick P. Brooks, Jr. Những đóng góp về kiến trúc máy tính, hệ điều hành và kỹ nghệ phần mềm.
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: Barbara 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: Charles 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..

Câu 1 : Trình bày mục đích đồng bộ hóa công việc các tiến trình.Cho ví dụ minh họa?

.1/ Đồng bộ hóa tiến trình bao gồm:
+ Đồng bộ hóa cá tiến trình heavy với nhau.
+ Đồng bộ hóa cá tiến trình nhẹ.
+ Đồng bộ hó cá luồng bên trong tiến trình này với tiến trình khác.

Vì sao phải đồng bộ hóa tiến trình: Trong hệ thống có nhiều luồng hay tiến trình nhưng tài nguyên dùng chung thì chỉ có khả năng phục vụ vô hạn. Mà lại có nhiều tiến trình cần sử dụng tài nguyên này. Dẫn đến xung đột bế tắc, deadlock.
g
Mục đích: là giúp các tiến trình làm việc có trật tự, có trước có sau và có chờ lẫn nhau. Đồng thời tránh được deadlock.

VD: B đến rũ A đi chơi nhưng A đang bận làm 1 số việc. B muốn đi chơi với A thì phải chờ A làm xong hết mọi việc.

VD: Mỗi người trong lớp là 1 luồng nhẹ, 1 lớp là tiến trình heavy. Thầy gọi 1 số bạn lên bảng. Mọ người phải trật tự lên bảng từng người 1. Thấy là tiến trình hệ thống quản lý cá luồng này. Bạn nào muốn lên bảng phải chờ bạn lên trước làm xong thì mới được lên.

.Nhà khoa học Edsger Dijkstra
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.

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.

Định nghĩa đèn hiệu với 2 tác nguyên Wait và Signal.

.- Đè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).