Mô tả thuật toán queue bằng danh sách liên kết
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (1.34 MB, 23 trang ) TRƯỜNG ĐẠI HỌC CÔNG NGHỆ GIAO THÔNG VẬN TẢI Chương 3.Mô tả thuật toán:...................................................................................8 3.1 Biểu diễn cấu trúc dữ liệu hàm Queue:........................................................8 3.2 Các thao tác với thuật toán:.........................................................................9 3.3 Hoạt động của enqueue trong cấu trúc dữ liệu hàng đợi............................11 3.4 Hoạt động của dequeue trong cấu trúc dữ liệu hàng đợi............................11 Chương 4.Ứng dụng:...........................................................................................12 4.1 Khi lập lịch CPU........................................................................................12 4.2 Khi in ấn....................................................................................................12 4.3 Ứng dụng của queue trong Amazon Web Services...................................13 Lời cảm ơn............................................................................................................... Tài liệu tham khảo................................................................................................... Chương 1. Giới thiệu tổng quan về thuật toán Queue trong danh sách liên kết. 1.1 Giới thiệu thuật toán: -Trong khoa học máy tính , hàng đợi là một tập hợp các thực thể được duy trì theo trình tự và có thể được sửa đổi bằng cách thêm các thực thể ở một đầu của chuỗi và loại bỏ các thực thể khỏi đầu kia của chuỗi. Theo quy ước, phần cuối của chuỗi mà các phần tử được thêm vào được gọi là phần sau, phần đuôi hoặc phần sau của hàng đợi và phần cuối mà phần tử được loại bỏ được gọi là phần đầu hoặc phần trước của hàng đợi, tương tự như các từ được sử dụng khi mọi người xếp hàng để chờ đợi hàng hóa hoặc dịch vụ. -Hoạt động thêm một phần tử vào phía sau hàng đợi được gọi là enqueue và hoạt động loại bỏ một phần tử từ phía trước được gọi là dequeue . Các hoạt động khác cũng có thể được cho phép, thường bao gồm một hoạt động peek hoặc hoạt động front trả về giá trị của phần tử tiếp theo sẽ được xử lý mà không cần xử lý nó. -Các hoạt động của một hàng đợi làm cho nó trở thành một cấu trúc dữ liệu nhập trước xuất trước (FIFO) . Trong cấu trúc dữ liệu FIFO, phần tử đầu tiên được 1 thêm vào hàng đợi sẽ là phần tử đầu tiên bị xóa. Điều này tương đương với yêu cầu một khi một yếu tố mới được thêm vào, tất cả các yếu tố đã được thêm vào trước đó phải được loại bỏ trước khi yếu tố mới có thể được gỡ bỏ. Hàng đợi là một ví dụ về cấu trúc dữ liệu tuyến tính , hay trừu tượng hơn là một bộ sưu tập tuần tự. Hàng đợi là phổ biến trong các chương trình máy tính, nơi chúng được triển khai như các cấu trúc dữ liệu kết hợp với các thói quen truy cập, như một cấu trúc dữ liệu trừu tượng hoặc trong các ngôn ngữ hướng đối tượng như các lớp. Thực hiện phổ biến là bộ đệm tròn và danh sách liên kết . -Hàng đợi cung cấp các dịch vụ trong nghiên cứu khoa học máy tính , vận chuyển và vận hành trong đó các thực thể khác nhau như dữ liệu, đối tượng, người hoặc sự kiện được lưu trữ và tổ chức để xử lý sau. Trong các bối cảnh này, hàng đợi thực hiện chức năng của bộ đệm . Một cách sử dụng hàng đợi khác là trong việc thực hiện tìm kiếm theo chiều rộng . 1.2 Ví dụ: Hình ảnh về hàng đợi rất hay gặp trong đời sống hàng ngày, hình ảnh việc xếp hàng dưới đây là một mô phỏng dễ hiểu nhất cho cấu trúc dữ liệu hàng đợi(queue): Người vào đầu tiên sẽ được tiến đón đầu tiên;Người mới vào bắt buộc phải xếp hàng ở phía cuối. \ Chương 2.Nội dung và cấu trúc của thuật toán 2.1 Khái niệm về danh sách liên kết đơn: -Một Danh sách liên kết (Linked List) là một dãy các cấu trúc dữ liệu được kết nối với nhau thông qua các liên kết (link). Hiểu một cách đơn giản thì Danh sách liên kết là một cấu trúc dữ liệu bao gồm một nhóm các nút (node) tạo thành một chuỗi. Mỗi nút gồm dữ liệu ở nút đó và tham chiếu đến nút kế tiếp trong chuỗi. 2 -Danh sách liên kết là cấu trúc dữ liệu được sử dụng phổ biến thứ hai sau mảng. Dưới đây là các khái niệm cơ bản liên quan tới Danh sách liên kết: Link (liên kết): mỗi link của một Danh sách liên kết có thể lưu giữ một dữ liệu được gọi là một phần tử. Next: Mỗi liên kết của một Danh sách liên kết chứa một link tới next link được gọi là Next. First: một Danh sách liên kết bao gồm các link kết nối tới first link được gọi là First. 2.2 Định nghĩa về hàng đợi Queue: -Hàng đợi(tiếng anh: Queue) là một cấu trúc dữ liệu dùng để lưu giữ các đối tượng theo cơ chế FIFO (viết tắt từ tiếng Anh: First In First Out), nghĩa là “vào trước ra trước”. 3 -Hàng đợi hỗ trợ các thao tác: Add-Enqueue():Thêm đối tượng vào cuối(rear)Queue. Remove-Dequeue():Lấy đối tượng ở đầu(front)queue ra khỏi queue. Peek:Examine the front element. 2.3 Các kỹ thuật trên hàng đợi Queue: -Có rất nhiều kỹ thuật trên hàng đợi: FIFO(First in first out):Vào trước ra trước. PQ(Priority queue):Hàng đợi ưu tiên. FQ(Fair queue):Hàng đợi cân bằng. -FIFO là kĩ thuật xếp hàng vào trước ra trước cơ bản .Các gói đến trước sẽ là các gói đầu tiên được xử lý.Khi hàng đợi đầy và có tắc nghẽn xảy ra thì các gói đến sẽ bị loại bỏ.Hàng đợi FIFO dựa vào hệ thống đầu cuối để điều khiển tắc nghẽn thông qua cơ chế điều khiển tắc nghẽn.Do loại hàng đợi này rất đơn giản nhiều khi không điều khiển được tắc nghẽn nên ta thường xét các loại hàng đợi hiệu quả hơn:hàng đợi ưu tiên (PQ).hàng đợi có trọng số(WQ),hàng đợi cân bằng(PQ). 2.3.1 Hàng đợi FIFO: -FIFO là hàng đợi mặc định được sử dụng trong hầu hết các router trên thế giới.Hoạt động FIFO.Các gói đến từ các luồng khác nhau được đối xử công bằng 4 bằng cách đưa vào các hàng đợi theo trật tự đến (gói nào đến trước sẽ được đưa vào trước và được phục vụ trước) -Hàng đợi hoạt động như 1 nơi lưu trữ các gói để tránh việc loại bỏ các gói không cần thiết khi có dấu hiệu của tắc nghẽn.Khi có tắc nghẽn xảy ra và hàng đợi tràn thì tất cả các gói đến sẽ bị loại bỏ.Hàng đợi FIFO được sử dụng hầu hết trong cấc router ,nó đơn giản do không phải định cấu hình cho nó mà chỉ việc sử dụng luôn.Trong các router của cisco, khi không có kế hoạch của hàng đợi nào khác được cấu hình, thì tất cả các giao diện (ngoại trừ các giao diện có tốc độ nhỏ bằng hoặc nhỏ hơn luồng E1)đều sử dụng hàng đợi FIFO mặc định. Tốc độ xử lý gói phải nhanh hơn tốc đọ các gói đến hàng đợi IFO thì mới tránh được hiện tượng tắc nghẽn trong mạng (hàng đợi IF1 rỗng),khi tốc độ xử lý quá thấp hơn so với tốc độ các gói vào , có nghĩa là tốc độ ra nhỏ hơn tốc độ gói vào (hàng đợi đầu ra dễ bị tràn )thì sẽ xảy ra tắc nghẽn khi có quá nhiều gói đi vào trong mạng ,và khi vấn đề này xảy ra thì các gói đến sau sẽ bị loại bỏ 2.3.2 Hàng đợi ưu tiên PQ: -Kĩ thuật này được sử dụng trong trường hợp đa hàng đợi, mỗi hàng đợi có 1 mức ưu tiên khác nhau, hàng đợi nào có mức độ ưu tiên cao nhất sẽ được ưu tiên phục vụ trước.Khi có tắc nghẽn xảy ra thì các gói trong hàng đợi có độ ưu tiên thấp sẽ bị loại bỏ.Có 1 vấn đề đối với kĩ thuật này:khi các hàng đợi có độ ưu tiên cao quá nhiều thì các gói trong hàng đợi có độ ưu tiên thấp sẽ không bao giờ được phục 5 vụ.Các gói được phân loại và được sắp xếp vào hàng đợi tùy thuộc vào thông tin bên trong các gói .Tuy nhiên kỹ thuật này dễ bị lạm dụng bởi người sử dụng hay các ứng dụng do ấn định các độ ưu tiên không cho phép. -Vậy PQ cho phép định nghĩa các luồng lưu lượng ưu tiên như thế nào trong mạng ?Ta có thể cấu hình các độ ưu tiên lưu lượng ,có thể định nghĩa 1 loạt các bộ lọc trên cơ sở cấc đặc điểm của gói mạng qua router để sắp xếp các các lưu lượng trong các hàng đợi. Hàng đợi có độ ưu tiên cao nhất sẽ được phục vụ trước cho đến khi hàng đợi rỗng, sau đó các hàng đợi có độ ưu tiên thấp hơn sẽ được phục vụ lần lượt.Câu hỏi đặt ra là PQ làm việc như thế nào? Trong quá trình truyền dẫn các hàng đợi có độ ưu tiên cao được đối xử ưu tiên hơn các hàng đợi có mức ưu tiên thấp hơn,hay nói cách khác lưu lượng quan trọng sẽ được gán các mức ưu tiên cao và lưu lượng có mức ưu tiên cao nhất được truyền trước,còn lại các lưu lượng ít quan trọng hơn .Các gói được phân loại dựa trên các tiêu chuẩn phân loại của người sử dụng và được đặt ở 1 trong số các hàng đợi đầu ra với các độ ưu tiên:độ ưu tiên cao,trung bình,bình thường(không được ưu tiên),ưu tiên thấp.Các gói không được ấn định độ ưu tiên sẽ được đưa tới các hàng đợi bình thường.Khi các gói được gửi tới giao diện đầu ra,các hàng đợi được ưu tiên tại giao diện đó được quét các gói theo thứ tự độ ưu tiên giảm dần.Hàng đợi có độ ưu tiên cao 6 nhất được quét đầu tiên,sau đó đến các hàng đợi trung bình và tiếp tục các hàng đợi có độn ưu tiên khác .Gói đứng đầu hàng đợi có độ ưu tiên cao nhất được truyền đầu tiên .Thủ tục này được lặp lại mỗi khi có 1 gói được truyền .Chiều dài lớn nhất của hàng đợi được định nghĩa theo chiều dài giới hạn.Khi 1 hàng đợi dài hơn chiều dài hàng đợi giới hạn thì các gói đến sau sẽ bị loại bỏ. -Cơ chế hàng đợi đầu ra ưu tiên có thể sử dụng để quản lý lưu lượng từ tất cả các giao thức trong mạng.PQ cung cấp cách đối xử ưu tiên cho các luồng lưu lượng có độ ưu tiên cao. -Các gói được phân biệt như thế nào trong kỹ thuật PQ -Danh sách ưu tiên là 1 tập các luật lệ mô tả các gói sẽ được ấn định các độ ưu tiên như thế nào trong các hàng đợi.Ngoài ra nó cũng có thể mô tả độ ưu tiên mặc định hoặc giới hạn kích thước hàng đợi của cấc hàng đợi ưu tiên . -Các gói được phân loại theo : Loại giao thức hoặc giao thức con. Giao diện đầu vào. Kích thước các gói tin. Các Fragment Danh sách truy nhập. Tất cả các lưu lượng dùng để quản lý và điều khiển mạng đều được ấn định độ ưu tiên cao nhất để trong trường hợp có tắc nghẽn xảy ra thì chúng được ưu tiên truyền trước.Các lưu lượng không được ấn định mức ưu tiên nào thì được đưa vào hàng đợi bình thường. -PQ cung cấp thời gian đáp ứng nhanh hơn so với các kỹ thuật hàng đợi khác .Mặc dù có thể ấn định các độ ưu tiên cho các hàng đợi tại bất kỳ giao diện đầu nào nhưng nó thường được sử dụng cho các lưu lượng có bảng thông tin thấp.Để giải quyết vấn đề các hàng đợi có độ ưu tiên thấp không được xử lý khi có quá nhiều hàng đợi có độ ưu tiên cao thì ta có thể sử dụng các kiểu hàng đợi khác;hàng đợi cân bằng có trọng số (WFQ) hay hàng đợi cân bằng (FQ),đơn giản hơn ta có thể sử dụng cơ chế định dạng lưu lượng hay CAR để giới hạn tốc độ của lưu 7 lượng có độ ưu tiên cao hơn .PQ sử dụng định cấu hình tĩnh do đó nó không thể thích ứng với các mạng thay đổi.Cơ chế xếp hàng ưu tiên là cơ chế đơn giản có thể cung cấp các lớp dịch vụ phân biệt và cần ít nhất 2 hàng đợi FIFO .Lấy 1 ví dụ sau:cho các hàng đợi FIFO và ta sẽ ấn định các mức ưu tiên khác nhau cho chúng:mức ưu tiên cao, trung bình, bình thường,thấp. 2.4 Ví dụ: Cài đặt Queue bằng Linklist Cài đặt Queue bằng using System; using System.Collections.Generic; namespace P02_CustomQueue { class Program { static void Main(string[] args) { Console.Title = "Custom Queue with LinkedList"; var queue = new MyQueue(); queue.Enqueue("Hello"); queue.Enqueue("world"); queue.Enqueue("from"); queue.Enqueue("my"); queue.Enqueue("super"); 8 queue.Enqueue("queue"); queue.Enqueue("class"); while (queue.Count > 0) { Console.Write($"Before: {queue.Count} items, "); Console.Write($"Dequeued item: {queue.Dequeue()}, "); Console.WriteLine($"After: {queue.Count} items"); } Console.ReadKey(); } } class MyQueue { private readonly LinkedList _items; public MyQueue() => _items = new LinkedList(); public void Enqueue(T item) => _items.AddLast(item); public T Dequeue() { var temp = _items.First.Value; _items.RemoveFirst(); 9 return temp; } public T Peek() => _items.First.Value; public void Clear() => _items.Clear(); public int Count => _items.Count; } } Chương 3.Mô tả thuật toán: 3.1 Biểu diễn cấu trúc dữ liệu hàng đợi: Giờ thì có lẽ bạn đã tưởng tượng ra hàng đợi là gì rồi. Chúng ta có thể truy cập cả hai đầu của hàng đợi. Dưới đây là biểu diễn hàng đợi dưới dạng cấu trúc dữ liệu: Tương tự như cấu trúc dữ liệu ngăn xếp, thì cấu trúc dữ liệu hàng đợi cũng có thể được triển khai bởi sử dụng Mảng (Array), Danh sách liên kết (Linked List), Con trỏ (Pointer) và Cấu trúc (Struct). Phần tiếp theo chúng ta sẽ tìm hiểu tiếp về hàng đợi được triển khai bởi danh sách liên kết đơn. 10 3.2 Các thao tác với thuật toán: Khai báo kiểu Item (nếu cần) Struc node{ Item struct struct node queue node infor; *rear; q; *next; }; struct struct queue{ node *front; }; (1) Khởi tạo hàng đợi rỗng: void create(struct queue *q){ q->front = NULL; q->rear= NULL; } (2) Kiểm tra hàng đợi rỗng: int Empty(struct queue q){ return (q.front == NULL) ; } (3) Thêm một phần tử x vào lối sau của hàng đợi: Nếu hàng đợi chưa đầy, chúng ta sẽ thêm phần tử cần thêm vào cuối(rear) của hàng đợi. Ngược lại, thông báo lỗi. Các bạn lưu ý, rear là chỉ số của phần tử sẽ được thêm ở lần tiếp theo. Do đó, thêm xong rồi ta mới tăng rear lên 1 đơn vị. Giá trị rear cần thay đổi nên được truyền theo tham chiếu. void Push(struct queue *q, item x){ struct node *p; p= new node; p->infor= x; 11 p->next= NULL; if (Empty(*q)){ q->front= p; q->rear=p; } else{ q->rear->next = p; q->rear= p; delete p; } } (4) Loại bỏ một phần tử ở lối trước của hàng đợi: Nếu hàng đợi có ít nhất 1 phần tử, chúng ta sẽ tiến hành xóa bỏ phần tử ở đầu của hàng đợi bằng cách tăng front lên 1 giá trị. Ở đây, front đang là chỉ số của phần tử sẽ bị xóa rồi. Cho nên chỉ cần tăng là xong, đó cũng là lý do ta cần truyền tham số front sử dụng tham chiếu. int Pop(struct queue *q, item &x){ struct node *p; if (Empty(*q)) return 0; else{ p= new node; p= q->front; x= q->front->infor; q->front= q->front->next; delete p; return 1; } } 12 3.3 Hoạt động của enqueue trong cấu trúc dữ liệu hàng đợi: Bởi vì cấu trúc dữ liệu hàng đợi duy trì hai con trỏ dữ liệu: front và rear, do đó các hoạt động của loại cấu trúc dữ liệu này là khá phức tạp khi so sánh với cấu trúc dữ liệu ngăn xếp. Dưới đây là các bước để enqueue (chèn) dữ liệu vào trong hàng đợi: Bước 1: kiểm tra xem hàng đợi là có đầy không. Bước 2: nếu hàng đợi là đầy, tiến trình bị lỗi và bị thoát. Bước 3: nếu hàng đợi không đầy, tăng con trỏ rear để trỏ tới vị trí bộ nhớ trống tiếp theo. Bước 4: thêm phần tử dữ liệu vào vị trí con trỏ rear đang trỏ tới trong hàng đợi. Bước 5: trả về success. Đôi khi chúng ta cũng cần kiểm tra xem hàng đợi đã được khởi tạo hay chưa để xử lý các tình huống không mong đợi. 3.4 Hoạt động dequeue trong cấu trúc dữ liệu hàng đợi Việc truy cập dữ liệu từ hàng đợi là một tiến trình gồm hai tác vụ: truy cập dữ liệu tại nơi con trỏ front đang trỏ tới và xóa dữ liệu sau khi đã truy cập đó. Dưới đây là các bước để thực hiện hoạt động dequeue: 13 Bước 1: kiểm tra xem hàng đợi là trống hay không. Bước 2: nếu hàng đợi là trống, tiến trình bị lỗi và bị thoát. Bước 3: nếu hàng đợi không trống, truy cập dữ liệu tại nơi con trỏ front đang trỏ. Bước 4: tăng con trỏ front để trỏ tới vị trí chứa phần tử tiếp theo. Bước 5: trả về success. Chương 4.Ứng dụng : 4.1 Khi lập lịch CPU: -Khi có nhiều tiến trình cùng yêu cầu CPU một số thuật toán lập lịch phức tạp được sử dụng cùng với hàng đợi để phân phối thời gian xử lý của CPU cho các tiến trình.Khi dữ liệu được truyền bất đồng bộ giữa các tiến trình,hàng đợi cũng được dùng để đồng bộ hóa dữ liệu này. 4.2 Khi in ấn: -Khi in ấn,các tài liệu cần in được tải vào 1 bộ nhớ đệm.Sau đó lần lượt đẩy ra bộ đệm riêng của máy in.Cơ chế này được gọi là spooling.Spooling cho phép đặt 14 nhiều lệnh in vào 1 hàng đợi,giúp người dùng không phải chờ kết thúc từng lệnh để bắt đầu lệnh in tiếp theo. 4.3 Ứng dụng của Queue trong Amazon Web Services: 4.3.1 Amazon Web Services là gì? -Amazon Web Services hay AWS là nền tảng dịch vụ công nghệ thông tin điệntoán đám mây toàn diện với các dịch vụ cho thuê máy chủ, lưu trữ cơ sở dữ liệu, hạ tầng mạng, phân phối nội dung và nhiều giải pháp phần mềm khác giúp nhà phát triển phần mềm cũng như doanh nghiệp triển khai và mở rộng hệ thống thông tin dễ dàng và nhanh chóng. -Các dịch vụ AWS đưa đưa ra vào năm 2006 với mục đích ban đầu để quản lý và điều hành hoạt động bán hàng online của website Amazon.com. Sau đó, AWS chính là công ty đầu tiên tiên phong dịch vụ điện toán đám mấy với khái niệm pay-as-you-go trên nền tảng AWS này, tức là doanh nghiệp chỉ trả chi phí thực sự với nhu cầu bạn sử dụng, giúp doanh nghiệp dễ dàng đầu tư cũng như mở rộng hạ tầng công nghệ thông tin với máy tính, dịch vụ lưu trữ dữ liệu với chi phí phù hợp và hiệu quả nhất 4.3.2 Amazon Simple Queue Service: Amazon Simple Queue Service (SQS) là một dịch vụ giúp lưu trữ thông điệp (message), thường là dữ liệu văn bản, dưới dạng hàng đợi (queue). Ưu điểm của Amazon SQS là tính nhanh chóng, đáng tin cậy, có khả năng mở rộng và quản lý một cách đầy đủ. -Cấu trúc cơ bản của Amazon SQS Cấu trúc cơ bản của một Amazon SQS sẽ gồm 3 phần: Các thành phần của hệ thống phân tán. Hàng đợi 15 Các thông điệp trong hàng đợi 16 Cơ chế hoạt động của Amazon SQS Cơ chế hoạt động của Amazon SQS được mô tả như hình dưới đây: Giải thích chi tiết như sau: Thành phần 1 gửi thông điệp A tới một hàng đợi. Hàng đợi này sẽ lưu trữ thông điệp này. 17 Khi thành phần nào đó trong hệ thống (ở đây là thành phần 2) sẵn sàng xử lý thông điệp thì nó sẽ gọi tới hàng đợi, lúc này, một thông điệp sẽ được trả lại (ở đây giải sử là thông điệp A). Sau khi thành phần 2 xử lý xong thông điệp A, nó sẽ xóa A khỏi hàng đợi để tránh các thành phần sau sẽ gọi tới thông điệp này. Ở đây, có thể thấy rõ vai trò của hàng đợi là rất quan trọng. Nó giúp sắp xếp và tổ chức các thông điệp bài bản, có trật tự, làm cho các thông điệp được xử lý theo thứ tự, thông điệp nào được gửi trước thì sẽ được xử lý trước và ngược lại. Từ đó không có thông điệp nào phải chờ quá lâu. Chương 5.Demo mô phỏng thuật toán queue 18 Lời cảm ơn Em xin chân thành cảm ơn Khoa Công Nghệ Thông Tin, trường Đại Học Công nghệ Giao Thông Vận Tải đã tạo điều kiện thuận lợi cho em thực hiện tốt đề tài này . Em xin chân thành bày tỏ lòng biết ơn sâu sắc đến thầy Lương Hoàng Anh .Thầy đã tận tâm hướng dẫn, định hướng và có những nhận xét đúng đắn, kịp thời cho em trong suốt thời gian thực hiện đề tài này. Bên cạnh đó, không thể không nhắc tới sự yêu thương và chăm sóc của gia đình, sự động viên của bạn bè đã giúp em vượt qua những khó khăn khi thực hiện đề tài này. Mặc dù em đã cố gắng hết sức trong quá trình thực hiện đề tài này nhưng chắc chắc sẽ không tránh khỏi những thiếu sót. Kính mong quý thầy cô và các bạn tận tình góp ý, chỉ bảo. Một lần nữa, em xin cảm ơn và mong nhận được tình cảm chân thành từ tất cả mọi người. 19 20 Tài liệu tham khảo [1 https://docs.aws.amazon.com/AWSSimpleQueueService/latest/SQSDevelo ] perGuide/welcome.html [2 https://docs.aws.amazon.com/AWSSimpleQueueService/latest/SQSDevelo ] perGuide/sqs-basic-architecture.html [3 https://tuhocict.com/hang-doi-queue-trong-c-cai-dat-ung-dung-lop-queue/ ] 21 |
