Thư viện tri thức trực tuyến
Kho tài liệu với 50,000+ tài liệu học thuật
© 2023 Siêu thị PDF - Kho tài liệu học thuật hàng đầu Việt Nam
Lý thuyết lập lịch và ứng dụng giải pháp quyết bài toán lập lịch cho CPU
Nội dung xem thử
Mô tả chi tiết
1
Số hóa bởi Trung tâm Học liệu http://lrc.tnu.edu.vn
ĐẠI HỌC THÁI NGUYÊN
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG
Nguyễn Văn Kiên
LÝ THUYẾT LẬP LỊCH VÀ ỨNG DỤNG GIẢI QUYẾT BÀI
TOÁN LẬP LỊCH CHO CPU
LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH
2
Số hóa bởi Trung tâm Học liệu http://lrc.tnu.edu.vn
Thái Nguyên 2013
LỜI CẢM ƠN
Em xin chân thành cảm ơn Trƣờng Đại Học Công Nghệ Thông Tin và truyền
thông đã tạo điều kiện cho em thực hiện luận văn này.
Em cũng xin chân thành cảm ơn tới toàn thể thầy cô giáo ở Viện công nghệ
thông tin và trƣờng Đại học công nghệ thông tin và truyền thông đã tận tình giảng dạy
và hƣớng dẫn, trang bị cho em những kiến thức cần thiết trong quá trình thực hiện luận
văn đƣợc thành công.
Dựa trên sự chỉ bảo tận tình của T.S Vũ Vinh Quang dựa trên những kiến thức
đã học, và tìm hiểu đƣợc, em đã hoàn thành luận văn theo đúng thời gian quy định. Tuy
nhiên trong quá trình thiết kế và thực hiện luận văn không tránh khỏi sai sót, do thời
gian có hạn và khả năng còn hạn chế. Em mong quý thầy cô và các bạn thông cảm và
có những ý kiến quý báu nhằm hoàn thiện hơn cho sản phẩm.
Em xin chân thành cảm ơn.
Thái nguyên, ngày 18 tháng 7 năm 2013
Học viên
Nguyễn Văn Kiên
3
Số hóa bởi Trung tâm Học liệu http://lrc.tnu.edu.vn
LỜI CAM ĐOAN
Em xin cam đoan luận văn tốt nghiệp: “Lý thuyết lập lịch và ứng dụng giải
quyết bài toán lập lịch cho CPU” do em tự thực hiện dƣới sự hƣớng dẫn của thầy giáo
Vũ Vinh Quang. Các kết quả và số liệu hoàn toàn trung thực.
Ngoài các tài liệu tham khảo đã dẫn ra ở cuối luận văn em đảm bảo rằng không
sao chép các công trình hay luận văn tốt nghiệp của ngƣời khác. Nếu phát hiện có sự
sai phạm với điều cam đoan trên, em xin hoàn toàn chịu trách nhiệm.
4
Số hóa bởi Trung tâm Học liệu http://lrc.tnu.edu.vn
MỤC LỤC
LỜI CẢM ƠN.................................................................................................................. 1
LỜI CAM ĐOAN............................................................................................................ 3
MỤC LỤC....................................................................................................................... 4
LỜI NÓI ĐẦU................................................................................................................. 6
CHƢƠNG 1..................................................................................................................... 8
MỘT SỐ KIẾN THỨC CƠ BẢN VỀ THUẬT TOÁN VÀ ĐỘ PHỨC TẠP THUẬT
TOÁN .............................................................................................................................. 8
1.1. Khái niệm cơ bản...................................................................................................... 8
1.1.1. Thuật toán...................................................................................................... 8
1.1.2. Kh¸i niÖm vÒ ®é phøc t¹p thuËt to¸n. ............................................................ 8
1.1.3. Cách tính độ phức tạp.................................................................................. 12
1.2. Vấn đề phân lớp các bài toán.................................................................................. 13
1.2.1. Tổng quan về sự phân lớp các bài toán ....................................................... 13
1.2.2. Khái niệm dẫn về đƣợc................................................................................ 16
1.3. Lớp các bài toán P và NP ....................................................................................... 16
1.3.1. Một số khái niệm......................................................................................... 16
1.3.2. Một số bài toán đã đƣợc chứng minh là NP – khó, NP - đầy đủ................. 21
1.4. Thuật toán xấp xỉ.................................................................................................... 23
1.4.1. Các khái niệm.............................................................................................. 23
1.4.2. Thuật toán
- xấp xỉ tuyệt đối .................................................................... 24
1.4.3. Thuật toán
- xấp xỉ.................................................................................... 26
CHƢƠNG 2................................................................................................................... 28
LÝ THUYẾT LẬP LỊCH.............................................................................................. 28
2.1. Mô hình bài toán lập lịch........................................................................................ 28
2.2. Các thuật toán lập lịch kinh điển ............................................................................ 32
2.3. Một số thuật toán lập lịch cho CPU ....................................................................... 34
2.3.1. Mô hình bài toán lập lịch cho CPU ............................................................. 34
2.3.2. Một số thuật toán lập lịch cho CPU ............................................................ 35
5
Số hóa bởi Trung tâm Học liệu http://lrc.tnu.edu.vn
2.3.2.1. Lập lịch FCFS........................................................................................... 35
2.3.2.2. Lập lịch SJF.............................................................................................. 37
2.3.2.3. Lập lịch theo độ ƣu tiên............................................................................ 40
2.3.2.4. Lập lịch RR............................................................................................... 43
2.3.2.5. Lập lịch với hàng đợi nhiều cấp ............................................................... 46
2.3.2.6. Lập lịch hàng đợi phản hồi đa cấp............................................................ 48
CHƢƠNG 3................................................................................................................... 51
KẾT QUẢ CÀI ĐẶT MỘT SỐ THUẬT TOÁN LẬP LỊCH CPU.............................. 51
3.1. Giới thiệu sơ lƣợc về ngôn ngữ lập trình C# và công cụ lập trình Visual Studio. ................ 51
3.1.1.Giới thiệu về ngôn ngữ lập trình C#............................................................. 51
3.1.2. Giới thiệu về công cụ lập trình Visual Studio ............................................. 54
3.2. Phân tích thuật toán cài đặt CPU............................................................................ 56
3.2.1. Thuật toán FCFS.......................................................................................... 56
3.2.2 Thuật toán SJF.............................................................................................. 57
3.2.3. Thuật toán RR.............................................................................................. 59
3.2.4. Sơ đồ thuật toán CPU.................................................................................. 60
3.3. Kết quả cài đặt thuật toán CPU .............................................................................. 60
3.3.1. Các thành phần của chƣơng trình................................................................ 60
3.3.2. Cấu trúc chi tiết ........................................................................................... 61
3.3.3. Sử dụng chƣơng trình. ................................................................................. 63
KẾT LUẬN ................................................................................................................... 66
TÀI LIỆU THAM KHẢO............................................................................................. 67
PHỤ LỤC ...................................................................................................................... 68
I. Thuật toán cài đặt....................................................................................................... 68
II. Các hàm và phƣơng thức cơ bản của chƣơng trình. ................................................. 77
6
Số hóa bởi Trung tâm Học liệu http://lrc.tnu.edu.vn
LỜI NÓI ĐẦU
Máy tính điện tử ra đời vào những năm 40 của thế kỷ XX. Ban đầu, phạm vi sử
dụng máy tính còn rất hẹp, đa phần chỉ nhằm phục vụ mục đích nghiên cứu khoa học.
Hơn nữa, để vận hành hệ thống cần phải sử dụng các công cụ phần cứng đặc biệt và
thao tác vận hành rất phức tạp.
Cùng phát triển song song với sự phát triển của kỹ thuật điện tử, các thế hệ máy
tính về sau đƣợc cải tiến ngày một tinh vi hơn, có tốc độ xử lý nhanh hơn, kích thƣớc
nhỏ gọn hơn, tiêu tốn ít năng lƣợng hơn và đã làm nên một cuộc cách mạng trong lĩnh
vực xử lý, tính toán, điều khiển động…Với các hệ máy tính này đòi hỏi phải có sự điều
khiển, vận hành một cách tự động để phát huy hiệu quả của nó một cách tối ƣu nhất.
Nhƣ vậy, cần phải có một chƣơng trình phần mềm đảm bảo việc giải quyết các vấn đề
trên. Đó chính là các hệ điều hành máy tính.
Mỗi hệ điều hành đều cần có thuật toán lập lịch cho riêng chúng. Thuật toán thƣờng
đƣợc thực hiện để cân bằng cho hệ thống máy tính đƣợc hiệu quả. Sự cần thiết của thuật
toán lập lịch xuất phát từ yêu cầu cho hầu hết các hệ thống hiện đại để thực thi nhiều hơn
một công việc tại cùng một thời điểm và có thể truyền tải nhiều luồng dữ liệu một lúc. Trong
môi trƣờng thời gian thực, chẳng hạn nhƣ các hệ thống nhúng điều khiển tự động trong
ngành công nghiệp (Robot) thì lập lịch cũng phải đảm bảo rằng quá trình có thể đáp ứng
đúng thời hạn, điều này là rất quan trọng để giữ hệ thống ổn định.
Việc nghiên cứu các thuật toán lập lịch dành CPU này mở ra nhiều hƣớng mới
cho khoa học và ứng dụng của nó trong thực tiễn cuộc sống. Đƣợc sự đồng ý của Thầy
hƣớng dẫn, Em chọn đề tài “Lý thuyết lập lịch và ứng dụng giải quyết bài toán lập lịch
cho CPU” làm đề tài luận văn cao học. Nội dung chính của đề tài bao gồm:
Chƣơng 1: Trình bày một số khái niệm về thuật toán và các nguyên tắc đánh giá
độ phức tạp của thuật toán, vấn đề phân lớp các bài toán theo độ phức tạp của thuật
toán. Đầy là phần lý thuyết quan trọng làm cơ sở để nghiên cứu trong các chƣơng tiếp
sau của luận văn.
7
Số hóa bởi Trung tâm Học liệu http://lrc.tnu.edu.vn
Chƣơng 2: Trình bày lý thuyết cơ bản về bài toán lập lịch, các thuật toán giải bài
toán lập lịch cơ bản và trọng tâm là trình bày một số thuật toán lập lịch cho CPU. Đây
chính là nội dung trọng tâm của luận văn
Chƣơng 3: Đƣa ra kết quả cài đặt các thuật toán lập lịch cho CPU trên nền ngôn
ngữ Visual Studio 10.
Nội dung đề tài là một lĩnh vực rộng và khó, với khoảng thời gian không nhiều
cùng với kiến thức của bản thân còn hạn chế, trong đề tài này mới chỉ đề cập đến việc
nghiên cứu thuật toán lập lịch chủ yếu là trên một máy và ứng dụng cho lập lịch CPU.
8
Số hóa bởi Trung tâm Học liệu http://lrc.tnu.edu.vn
CHƢƠNG 1
MỘT SỐ KIẾN THỨC CƠ BẢN VỀ THUẬT TOÁN
VÀ ĐỘ PHỨC TẠP THUẬT TOÁN
Trong chƣơng 1, luận văn sẽ trình bày một số kiến thức cơ bản về thuật toán và
độ phức tạp thuật toán, vấn đề phân lớp các bài toán dựa trên độ phức tạp thuật toán.
Các kiến thức này đã đƣợc tham khảo trong các tài liệu [3], [4]. Đây là các kiến thức
quan trọng để trình bày tiếp các nội dung trong chƣơng 2 và chƣơng 3 của luận văn.
1.1. Khái niệm cơ bản
1.1.1. Thuật toán
Thuật toán để giải một bài toán là một dãy hữu hạn các thao tác đƣợc sắp xếp
theo một trình tự xác định sao cho sau khi thực hiện dãy thao tác đó, từ dữ liệu đầu vào
(Input) của bài toán, ta nhận đƣợc kết quả (Output) cần tìm.
Ta đã biết 2 mô hình tính toán là máy Turing và máy xử lý thuật toán viết bằng
ngôn ngữ tựa ALGOL. Ứng với hai mô hình tính toán này có 2 cách biểu diễn thuật
toán:
+ Thuật toán đƣợc biểu diễn bằng ngôn ngữ máy Turing.
+ Thuật toán đƣợc biểu diễn bằng ngôn ngữ tựa ALGOL.
1.1.2. Kh¸i niÖm vÒ ®é phøc t¹p thuËt to¸n.
a. Chi phí phải trả cho một quá trình tính toán
Trong quá trình xử lý thuật toán, ngƣời ta thƣờng quan tâm tới chi phí cho thời
gian tính toán và chi phí cho không gian chứa dữ liệu tính toán (bộ nhớ).
- Chi phí thời gian chính là tổng thời gian cần thiết để thực hiện xong một quá
trình tính toán.
+ Với máy Turing: Chi phí thời gian là số bƣớc chuyển hình trạng từ hình trạng
đầu
0
q
đến hình trạng kết thúc
n
q .
9
Số hóa bởi Trung tâm Học liệu http://lrc.tnu.edu.vn
+ Với thuật toán tựa Algol: Chi phí thời gian là số các phép tính cơ bản cần thực
hiện trong quá trình tính toán.
- Chi phí không gian chính là số ô nhớ cần để thực hiện hoàn chỉnh trong quá
trình tính toán.
Gọi A là một thuật toán tƣơng ứng với một mô hình tính toán, gọi e là bộ dữ liệu
vào đã đƣợc mã hóa theo cách nào đó. Khi đó thuật toán A tính trên bộ dữ liệu e cần
phải trả về giá thời gian và giá không gian trong đó ta kí hiệu
+
( ) A
t e
là giá phải trả về thời gian tính toán
+
( ) A
l e
là giá về không gian của bộ nhớ cần thiết sử dụng
Khi đó tổng giá phải trả của thuật toán A tính trên bộ dữ liệu e chính bằng :
T(A)=
( ) A
t e
+
( ) A
l e
b. Các khái niệm về độ phức tạp của thuật toán
Độ phức tạp trong trƣờng hợp xấu nhất
Cho một thuật toán A với đầu vào n, khi đó:
- Độ phức tạp về bộ nhớ trong trƣờng hợp xấu nhất đƣợc định nghĩa là:
( ) max{ ( ) || | | } A A L n l e e n = £
tức là chi phí lớn nhất về bộ nhớ.
- Độ phức tạp thời gian trong trƣờng hợp xấu nhất đƣợc định nghĩa là :
( ) max{ ( ) || | | } A A
T n t e e n = £
tức là chi phí lớn nhất về thời gian.
Độ phức tạp trung bình
Là tổng số các độ phức tạp khác nhau ứng với các bộ dữ liệu chia cho tổng số.
Độ phức tạp tiệm cận
Thuật toán A với đầu vào n gọi là có độ phức tạp O(f(n)) nếu
$
hằng số C,
0 0 : ( ) . ( ), A
N T n C f n n N £ " ³
tức là
( ) A
T n
có tốc độ tăng là O(f(n))