Khác biệt giữa các bản “Queue”

Từ Từ điển công nghệ
(Khái niệm hàng đợi)
 
Dòng 6: Dòng 6:
  
 
Dựa vào quá trình đến và đòi hỏi của các tác vụ mà ta thường gặp những hàng đợi sau:
 
Dựa vào quá trình đến và đòi hỏi của các tác vụ mà ta thường gặp những hàng đợi sau:
  - <math>M/M/1/\infty</math>: quá trình đến Poisson, mỗi công việc đòi hỏi thời gian phục vụ tuân theo luật số mũ, chỉ có 1 máy chủ phục vụ các công việc, có vô hạn chỗ trong hàng đợi.
+
  - <math>M/M/1/\infty</math>: quá trình đến Poisson, mỗi công việc đòi hỏi thời gian phục vụ tuân theo luật số mũ,  
  - <math>G/G/k/N</math>: quá trình đến tuân theo luật tùy ý, thời gian phục vụ tuân theo luật tùy ý, có k máy chủ trong hàng đợi, tại mỗi thời điểm có thể có tối đa k tác vụ được thực hiện cùng lúc, và chỉ có N chỗ trong hàng đợi. Nếu một công việc mới xuất hiện trong khi đã có N công việc đang đợi, công việc mới sẽ bị bỏ qua.
+
chỉ có 1 máy chủ phục vụ các công việc, có vô hạn chỗ trong hàng đợi.
 +
  - <math>G/G/k/N</math>: quá trình đến tuân theo luật tùy ý, thời gian phục vụ tuân theo luật tùy ý, có k máy chủ  
 +
trong hàng đợi, tại mỗi thời điểm có thể có tối đa k tác vụ được thực hiện cùng lúc, và chỉ có N chỗ trong hàng  
 +
đợi. Nếu một công việc mới xuất hiện trong khi đã có N công việc đang đợi, công việc mới sẽ bị bỏ qua.
  
 
Dựa trên kiểu xếp hàng và kiểu phục vụ, ta có thể gặp những hàng đợi sau:
 
Dựa trên kiểu xếp hàng và kiểu phục vụ, ta có thể gặp những hàng đợi sau:
  - FIFO (First In First Out): đến trước xong trước, máy chủ thực hiện các công việc theo thứ tự xuất hiện.
+
  - FIFO (First In First Out): đến trước xong trước, máy chủ thực hiện các công việc theo thứ tự  
  - LIFO (Last In First Out) pre-emptive: đến sau xong trước, máy chủ ưu tiên các công việc đến sau cùng.
+
xuất hiện.
 +
  - LIFO (Last In First Out) pre-emptive: đến sau xong trước, máy chủ ưu tiên các công việc đến sau  
 +
cùng.
 
  - PS (Processor Sharing): máy chủ phục vụ cùng lúc tất cả các tác vụ, với cùng một vận tốc.
 
  - PS (Processor Sharing): máy chủ phục vụ cùng lúc tất cả các tác vụ, với cùng một vận tốc.
  - Thứ tự ưu tiên: mỗi tác vụ được gán cho một mức ưu tiên nào đó, máy chủ thực hiện các tác vụ theo thứ tự ưu tiên từ cao đến thấp.
+
  - Thứ tự ưu tiên: mỗi tác vụ được gán cho một mức ưu tiên nào đó, máy chủ thực hiện các tác vụ theo  
 +
thứ tự ưu tiên từ cao đến thấp.

Phiên bản lúc 03:30, ngày 31 tháng 5 năm 2007

Trong lý thuyết mạng và viễn thông, hàng đợi bao gồm:

- Quá trình đến: mô tả thời điểm xuất hiện của các tác vụ, các công việc cần làm.
- Đòi hỏi của các tác vụ: mỗi tác vụ có thể đòi hỏi thời gian phục vụ một cách ngẫu nhiên.
- Xếp hàng: mô tả cách thức sắp xếp các công việc trong hàng đợi.
- Phục vụ: mô tả thứ tự thực hiện các công việc của máy chủ.

Dựa vào quá trình đến và đòi hỏi của các tác vụ mà ta thường gặp những hàng đợi sau:

- <math>M/M/1/\infty</math>: quá trình đến Poisson, mỗi công việc đòi hỏi thời gian phục vụ tuân theo luật số mũ, 

chỉ có 1 máy chủ phục vụ các công việc, có vô hạn chỗ trong hàng đợi.

- <math>G/G/k/N</math>: quá trình đến tuân theo luật tùy ý, thời gian phục vụ tuân theo luật tùy ý, có k máy chủ 

trong hàng đợi, tại mỗi thời điểm có thể có tối đa k tác vụ được thực hiện cùng lúc, và chỉ có N chỗ trong hàng đợi. Nếu một công việc mới xuất hiện trong khi đã có N công việc đang đợi, công việc mới sẽ bị bỏ qua.

Dựa trên kiểu xếp hàng và kiểu phục vụ, ta có thể gặp những hàng đợi sau:

- FIFO (First In First Out): đến trước xong trước, máy chủ thực hiện các công việc theo thứ tự 

xuất hiện.

- LIFO (Last In First Out) pre-emptive: đến sau xong trước, máy chủ ưu tiên các công việc đến sau 

cùng.

- PS (Processor Sharing): máy chủ phục vụ cùng lúc tất cả các tác vụ, với cùng một vận tốc.
- Thứ tự ưu tiên: mỗi tác vụ được gán cho một mức ưu tiên nào đó, máy chủ thực hiện các tác vụ theo 

thứ tự ưu tiên từ cao đến thấp.