bộ giáo dục và đào tạo
trờng đại học bách khoa hà nội
-----------------------------------------
luận văn thạc sỹ khoa học
Nghiên cứu, thiết kế hệ điều hành trên
bộ vi điều khiển 8 bítngành: xử lý thông tin và truyền thôngM số: vũ trung kiên
Mục lục
Lời cam đoan.....................................................................................................2
Danh mục các ký hiệu, các chữ viết tắt ..........................................................5
Danh mục các bảng ..........................................................................................6
Danh mục các hình vẽ, đồ thị ..........................................................................7
Lời nói đầu ........................................................................................................9
Chơng 1 -
Tổng quan về hệ điều hành
......................11
1.1. Khái niệm về hệ điều hành (OS-Operating System)................................. 11
1.1.1. Khái niệm................................................................................................. 11
1.1.2. Chức năng của hệ điều hành. ................................................................... 11
1.1.3. Các thành phần của hệ điều hành............................................................. 13
1.2. Quản lý tiến trình......................................................................................... 16
1.2.1. Các trạng thái của một tiến trình.............................................................. 16
1.2.2. Khái niệm về tài nguyên găng và đoạn tới hạn .................................... 17
1.2.3. Hiện tợng bế tắc..................................................................................... 19
1.3. Lập lịch cho CPU ......................................................................................... 20
1.3.1. Khái niệm giờ CPU.................................................................................. 20
1.3.2. Các trạng thái của tiến trình liên quan đến giờ CPU................................ 20
1.3.3. Lập lịch cho CPU..................................................................................... 22
3.2.2. Giao diện ngời sử dụng. ......................................................................... 52
3.2.3. Các thiết bị mô phỏng quá trình hoạt động của tiến trình. ...................... 53
3.3. Thiết kế mạch điện....................................................................................... 58
3.4. Đo thử và kiểm tra lỗi.................................................................................. 59
Chơng 4 -
Thiết kế hệ điều hành
.....................................60
4.1.1. Mục đích và yêu cầu thiết kế. .................................................................. 60
4.1.2. Mục đích. ................................................................................................. 60
4.1.2. Yêu cầu .................................................................................................... 63
4.2. Trình tự thiết kế hệ điều hành.................................................................... 64
4.3. Xây dựng các tiến trình. .............................................................................. 65
4.3.1. Xây dựng các tác vụ tơng ứng các tiến trình.......................................... 65
4.3.2. Giải quyết bài toán tài nguyên găng ........................................................ 69
4.4. Lập lịch cho CPU. ........................................................................................ 71
4.4.1. Sự kiện và chuyển trạng thái giữa các tiến trình. ..................................... 71
4.4.2. Lập lịch cho CPU..................................................................................... 80
4.5. Quản lý bộ nhớ. ............................................................................................ 83
Kết luận và kiến nghị .....................................................................................86
Tài liệu tham khảo .........................................................................................87
B¶ng 2.1. Bé nhí d÷ liÖu trªn chÝp cña AT89S52 .............................................. 33
-7- Danh mục các hình vẽ, đồ thị
Hình 1.1. Các trạng thái của một tiến trình........................................................ 17
Hình 1.2. Các trạng thái của tiến trình liên quan đến giờ CPU.......................... 20
Hình 1.3. Sơ đồ thực hiện tiến trình ................................................................... 21
Hình 1.4. Sơ đồ tổ chức hàng đợi các tiến trình ................................................. 22
Hình 1.5. Sơ đồ Grant......................................................................................... 25
Hình 2.1. Sơ đồ khối của bộ vi điều khiển AT89S52......................................... 29
Hình 2.2. Tổ chức bộ nhớ của vi điều khiển ...................................................... 30
Hình 2.3. Sơ đồ ghép nối AT89S52 với EPROM............................................... 31
Hình 2.4. Sơ đồ ghép nối AT89S52 với RAM .................................................. 34
Hình 2.5. Giải mã địa chỉ cho các vi mạch nhớ ................................................. 34
Hình 2.6. Bộ nhớ dữ liệu đọc nh bộ nhớ chơng trình..................................... 35
Hình 2.7. Hoạt động của Timer0 và Timer1 ở chế độ 1..................................... 36
Hình 4.7. Các tiến trình đợc phân bổ thời gian CPU khác nhau ...................... 74
Hình 4.8. Ngời sử dụng ra lệnh vào các thời điểm khác nhau ......................... 75
Hình 4.9. Chuyển giữa cá tiến trình bằng sự kiện interrupt ............................... 76
Hình 4.9. Mô tả trạng thái của các tài nguyên của tiến trình............................. 77
Hình 4.10. Các tài nguyên cần lu khi dừng một tiến trình............................... 78
Hình 4.11. Phân bổ ngăn xếp cho các tiến trình ................................................ 79
Hình 4.12. Lập lịch cho 8 tiến trình thực hiện quét chữ trên ma trận LED ....... 81
Hình 4.13. Lập lịch cho 4 tiến trình quét các số trên 4 LED 7 đoạn ................. 81
Hình 4.14. Lập lịch cho tiến trình điều khiển LCD........................................... 82
Hình 4.15. Lập lịch cho tiến trình thời gian thực .............................................. 82
Hình 4.16. Tổ chức bộ nhớ ROM của hệ vi điều khiển ..................................... 83
Hình 4.17. Thay đổi vị trí đặt các chơng trình con phục vụ ngắt..................... 84
Hình 4.18. Phân bổ bộ nhớ ROM....................................................................... 85
Hình 4.19. Phân bổ bộ nhớ RAM....................................................................... 85-9-
các trờng Cao đẳng và Đại học. Tuy nhiên để có một hiệu qủa giảng dạy tốt
nhất thì cần có một phơng pháp nghiên cứu và thiết kế đúng chính tắc và cũng
cần phải có một thiết bị phục vụ qua trình thí nghiệm.
Trờng Đại học Công nghiệp Hà nội là một trờng đào tạo các cử nhân và
các kỹ s thực hành. Trong chơng trình đào tạo cũng đã có môn kỹ thuật vi điều
khiển, đây có thể coi là nền tảng để tiếp cận với các hệ thống nhúng sử dụng vi
điều khiển có hệ điều hành. Việc nghiên cứu để đa vào giảng dạy môn thiết kế
hệ điều hành cho các hệ vi điều khiển là phù hợp với yêu cầu hiện tại.
Với sự hớng dẫn của TS Nguyễn Linh Giang, trong khuôn khổ luận văn
này, tôi mạnh dạn nghiên cứu về các nguyên tắc cơ bản khi thiết kế một hệ điều
hành trên hệ vi điều khiển.
Nội dung của luận văn bao gồm 4 chơng, trong đó:
Chơng 1: Giới thiệu tổng quan hệ điều hành.
Chơng 2: Giới thiệu bộ vi điều khiển đợc sử dụng để viết hệ điều hành và
ngôn ngữ lập trình cho vi điều khiển.
Chơng 3. Thiết kế phần cứng hệ vi điều khiển.
Chơng 4. Thiết kế hệ điều hành cho hệ vi điều khiển
Do thời gian và khả năng có hạn nên luận văn này sẽ còn nhiều thiếu sót.
Rất mong đợc sự góp ý và thông cảm của các thầy giáo, cô giáo.
Hà nội, ngày 30 tháng 10 năm 2006
Học viên
Vũ Trung Kiên
-11-
Chơng 1 -
Tổng quan về hệ điều hành
1.1. Khái niệm về hệ điều hành (OS-Operating System)
1.1.1. Khái niệm
hoặc khai thác máy tính ngời sử dụng phải hiểu đợc cơ chế hoạt động của các
bộ phận này và phải tác động trực tiếp vào nó tất nhiên là bằng những con số 0,1
(ngôn ngữ máy). Điều này là quá khó đối với ngời sử dụng hệ điều hành phải
che đậy các chi tiết phần cứng máy tính bởi một máy tính mở rộng, máy tính mở
rộng này có đầy đủ các chức năng của một máy tính thực nhng đơn giản và dễ
sử dụng hơn. Theo đó khi cần tác động vào máy tính thực ngời sử dụng chỉ cần
tác động vào máy tính mở rộng mọi sự chuyển đổi thông tin điều khiển từ máy
tính. Mục đích của chức năng này kà: Giúp ngời sử dụng khai thức các chức
năng của phần cứng máy tính dễ dàng và hiệu quả hơn.
- Quản lý tài nguyên của hệ thống:
Tài nguyên hệ thống có thể là: prrocessor, Memory, I/O Device..., đây là
những tài nguyên mà hệ điều hành dùng để cấp phát cho các tiến trình, chơng
trình trong quá trình điều khiển sự hoạt động của hệ thống. Khi ngời sử dụng
cần thực hiện một chơng trình hay một chơng trình cần nạp thêm một tiến
trình mới vào bộ nhớ thì hệ điều hành phải cấp phát không gian nhớ cho chơng
trình, tiến trình đó để chơng trình, tíên trình đó nạp đợc vào bộ nhớ và hoạt
động đợc. Trong môi trờng hệ điều hành đa nhiệm có thể có nhiều chơng
trình, tiến trình đồng thời cần đợc nạp vào bộ nhớ nhng không gian lu trữ củâ
bộ nhớ có giới hạn do đó hệ điều hành phải tổ chức cấp phát bộ nhớ sao cho hợp
lý để đảm bảo tất cả các chơng trình tiến trình khi cần để đợc nạp vào bộ nhớ
để hoạt động. Ngoài ra hệ điều hành còn phải tổ chức bảo vệ các không gian nhớ
đã cấp cho các chơng trình tiến trình để tránh sự truy cập bất hợp lệ và sự tranh
-13-
chấp bộ nhớ giữa các chơng trình, tiến trình, đặc biệt là các tiến trình đồng thời
hoạt động trên hệ thống. Đây là một trong những nhiệm vụ quan trọng của hệ
điều hành.
Trong quá trình hoạt động của hệ thống đặc bệt là các hệ thống đa ngời
dùng đa chơng trình, đa tiến trình. Còn xuất hiện một hiện tợng khác, đó là
nhiều chơng trình, tiến trình đồng thời sử dụng một không gian nhớ hau một tập
đợc thực hiện và kết thúc đợc.
Tóm lại, bộ phận quản lý tiến trình của hệ điều hành phải thực hiện nhứng
nhiệm vụ sau đây:
Tạo lập, huỷ bỏ tiến trình.
Tạm dừng, tái kích hoạt động tiến trình.
Tạo cơ chế thông tin liên lạc giữa các tiến trình.
Tạo cơ chế đồng bộ hoá giữa các tiến trình.
1.1.3.2. Thành phần quản lý bộ nhớ.
Bộ nhớ chính là một trong những tài nguyên quan trọng của hệ thống, đây là
thiết bị lu trữ duy nhất mà CPU có thể truy xuất trực tiếp đợc.
Các chơng trình của ngời sử dụng muốn thực hiện đợc bởi CPU thì
trwocs hết nó phải đợc hệ điều hành nạp vào bộ nhớ chính, chuyển đổi các địa
chỉ sử dụng trong chơng trình thành những địa chỉ mà CPU có thể truy xuất
đợc.
Khi chơng trình, tiến trình có yêu cầu đợc nạp vào bộ nhớ thì hệ điều
hành phải cấp phát không gian nhớ cho nó. Khi chơng trình, tiến trình kết thúc
thì hệ điều hành phải thi hồi lại không gian nhớ đã cấp phát cho chơng trình,
tiến trình trớc đó.
-15-
Trong các hệ thống đa chơng hay đa tiến trình, trong bộ nhớ tồn tại nhiều
chơng trình/ nhiều tiến trình, hệ điều hành phải thực hiện nhiệm vụ bảo vệ các
vùng nhớ đã cấp phát cho các chơng trình/tiến trình, tránh sự vi phạm trên các
vùng nhớ của nhau.
Tóm lại, bộ phận quản lý bộ nhớ chính của hệ điều hành thực hiện những
nhiệm vụ sau:
Cấp phát, thu hồi vùng nhớ.
Chi nhận trạng thái bộ nhớ.
Bảo vệ bộ nhớ.
Quyết định tiến trình nào đợc nạp vào bộ nhớ.
Chờ đợi sự kiện nào đó xảy ra, đợi một thao tác vào/ra hoàn tất, hết thời gian xử
lý...
Tại mỗi thời điểm, tiến trình có thể nhận một trong các trạng thái sau:
- Khởi tạo (new): Tiến trình đang đợc tạo lập.
- Sẵn sàng (ready): Tiến trình chờ đợc cấp phát CPU để xử lý.
- Thực hiện (runing): Tiến trình đợc xử lý.
- Đợi (waiting): Tiến trình phải dừng vì thiếu tài nguyên hoặc chờ một sự
kiện nào đó.
- Kết thúc (halt): Tiến trình đã hoàn tất công việc xử lý.
Các trạng thái của tiến trình có thể đợc biểu diễn qua sơ đồ (hình 1.1)
-17-
Hình 1.1. Các trạng thái của một tiến trình
Hệ điều hành quản lý hoạt động của các tiến trình trong hệ thống thông
qua khối mô tả tiến trình (process control block - PCB). Khối mô tả tiến trình bao
gồm các thành phần:
- Số thứ tự của tiến trình
- Con trỏ trạng thái của tiến trình (cho biết trạng thái hiện tại của tiến
trình).
- Vùng nhớ lu trữ giá trị các thanh ghi mà tiến trình đang sử dụng.
- Thông tin về tài nguyên tiến trình đang sử dụng hoặc đợc phép sử dụng.
Skip;
Buffer [In]:=NextP;
In:= In + 1
mod
n
;
Until
false;
(Tiến trình C)
Repeat
While
Counter = 0
do
Skip;
NextC:= Buffer [Out];
Out:= Out + 1
mod
n
;
...
Lấy thông tin trong chứa trong NextC
...
Until
false
;
End;
Nhận xét: Vì hai tiến trình P và C song hành nên có thể xảy ra trờng hợp
1
) t
1
Wait (S
2
)
... t
2
...
Wait (S
2
) t
3
...
t
4
Wait (S
1
)
Nhận xét: Tại vị trí trên, sau thời điểm t
3
, tiến trình P
1
rơi vào trạng thái
chờ tài nguyên r
2
đang đợc P
2
sử dụng; Sau thời điểm t
4
1.3.1. Khái niệm giờ CPU
CPU là một loại tài nguyên quan trọng của máy tính. Mọi tiến trình muốn
hoạt động đợc đều phải có sự phục vụ của CPU (để xử lý, tính toán...). Thời gian
mà CPU phục vụ cho tiến trình hoạt động đợc gọi là giờ CPU.
Tại mỗi thời điểm nhất định, chỉ có một tiến trình đợc phân phối giờ CPU
để hoạt động (thực hiện các lệnh của mình).
1.3.2. Các trạng thái của tiến trình liên quan đến giờ CPU
Trong chế độ đa chơng trình, có ba trạng thái của tiến trình liên quan mật
thiết đến giờ CPU bao gồm:
Hình 1.2. Các trạng thái của tiến trình liên quan đến giờ CPU
Ready
Runing
Waiting
-21-
- Sẵn sàng (ready): Là trạng thái mà tiến trình đợc phân phối đầy đủ mọi
tài nguyên cần thiết và đang chờ giờ CPU.
- Thực hiện (running): Là trạng thái mà tiến trình đợc phân phối đầy đủ
mọi tài nguyên cần thiết và giờ CPU.
- Đợi (waiting): Là trạng thái tiến trình không thực hiện đợc vì thiếu một
vài điều kiện nào đó (đợi dữ liệu vào/ra, đợi tài nguyên bổ sung...). Khi sự kiện
mà nó chờ đợi xuất hiện, tiến trình sẽ quay trở lại trạng thái sẵn sàng.
Nh vậy, trong suốt thời gian tồn tại của mình, các tiến trình sẽ tuân thủ
các từ trạng thái (thực chất là các khối điều khiển tiến trình) để ghi nhận tình
trạng sử dụng tài nguyên và trạng thái tiến trình. Các từ trạng thái đợc tổ chức
theo kiểu đợi nh sau: Hình 1.4. Sơ đồ tổ chức hàng đợi các tiến trình
Nh vậy, lập lịch cho CPU có nghĩa là tổ chức một hàng đợi các tiến trình
sẵn sàng để phân phối giờ CPU cho chúng dựa trên độ u tiên của các tiến trình
sao cho hiệu suất sử dụng CPU là tối u nhất.
Mỗi tiến trình ở trạng thái sẵn sàng đợc gắn với một thứ tự u tiên. Thứ tự
u tiên này đợc xác định dựa vào các yếu tố nh: Thời điểm hình thành tiến
trình, thời gian thực hiện tiến trình, thời gian kết thúc tiến trình... Ready queue
CPU
I/O
4. Round Robin (RR)
Trong thuật toán này, hệ thống quy định một lợng tử thời gian (time
quantum) khoảng từ 10-100 mili giây. Mỗi tiến trình trong hàng đợi lần lợt đợc
phân phối một lợng tử thời gian để thực hiện. Sau khoảng thời gian đó, nếu tiến
trình cha kết thúc hoặc không rơi vào trạng thái đợi thì nó đợc chuyển về cuối
hàng đợi.
Hàng đợi các tiến trình đợc tổ chức theo kiểu vòng tròn và các tiến trình
luôn luôn đảm bảo đợc phục vụ. Khi có tiến trình mới phát sinh, nó sẽ đợc đa
-24-
vào hàng đợi vòng tròn và đợc đặt ở vị trí phục vụ ngay. Các tiến trình dù ngắn
hay dài đều có độ u tiên phục vụ nh nhau.
Trên thực tế, để đảm bảo độ u tiên cho các tiến trình dài, hệ thống sẽ
phân chia các tiến trình thành m lớp. Số lần đợc phục vụ và thời gian một lần
phục vụ tiến trình tại mỗi lớp khác nhau (giả sử ở lớp thứ i, tiến trình đợc phục
vụ k lần và mỗi lần với thời gian q
i
).
Nếu sau khoảng thời gian đã đợc phân phối mà tiến trình cha kết thúc
hoặc không bị ngắt thì nó đợc chuyển sang lớp thứ i+1 (với k
i+1
và q
i+1
lớn hơn).
Lợng từ thời gian sẽ tăng dần cho đến khi tiến trình rơi vào lớp ngoài cùng (lớp
m). ở đó nó sẽ đợc phục vụ với lợng tử q
m
không đổi. Nh vậy thứ tự u tiên
của các tiến trình sẽ tăng dần theo thời gian xếp hàng đợi.
Ưu điểm của phơng pháp phục vụ đồng mức theo lớp sẽ cho phép hệ
Processes T thực hiện T đợi
P1 24 6
P3 3 1
P1 3 7
Tổng 30 17
Dẫn đến thời gian chờ đợi trung bình của các tiến trình là 17/3 = 5.66
1.4. Quản lý bộ nhớ
1.4.1. Yêu cầu phải quản lý bộ nhớ
Bộ nhớ là thiết bị lu trữ duy nhất mà thông qua đó CPU có thể trao đổi
thông tin với môi trờng bên ngoài. Do vậy, nhu cầu tổ chức, quản lý bộ nhớ là
một trong những nhiệm vụ cơ bản hàng đầu của hệ điều hành. Bộ nhớ đợc tổ
chức nh mảng một chiều các từ nhớ (word), mỗi từ nhớ có một địa chỉ. Việc
trao đổi thông tin với môi trờng bên ngoài đợc thực hiện thông qua các thao tác
đọc/ghi dữ liệu vào một địa chỉ cụ thể nào đó trong bộ nhớ.
Copyright: Tài liệu đại học ©