Tìm kiếm tài liệu miễn phí

Bài giảng môn Hệ điều hành: Chương 3 - TS. Nguyễn Văn Hiệp

Bài giảng môn Hệ điều hành - Chương 3: Tương tranh giữa các process" cung cấp cho người học các kiến thức: Giới thiệu về tương tranh, loại trừ tương hỗ giữa các đoạn code CS, các phương pháp dừng chờ chủ động (busy waiting), đồng bộ các process - Bài toán Sản xuất-Tiêu dùng,... Mời các bạn cùng tham khảo nội dung chi tiết.



Đánh giá tài liệu

0 Bạn chưa đánh giá, hãy đánh giá cho tài liệu này


  • 5 - Rất hữu ích 0

  • 4 - Tốt 0

  • 3 - Trung bình 0

  • 2 - Tạm chấp nhận 0

  • 1 - Không hữu ích 0

Mô tả

MÔN HỆ ĐIỀU HÀNH
Chương 3

TƯƠNG TRANH GIỮA CÁC PROCESS
3.1 Giới thiệu về tương tranh
3.2 Loại trừ tương hỗ giữa các đoạn code CS
3.3 Các phương pháp dừng chờ chủ động (busy waiting)
3.4 Đồng bộ các process : Bài toán Sản xuất-Tiêu dùng
3.5 Các phương pháp dừng chờ thụ động (sleep-wakeup)
3.6 Các bài toán IPC kinh điển và giải quyết
Tài liệu tham khảo : chương 2, sách "Modern Operating Systems",
Andrew S. Tanenbaum: , 2nd ed, Prentice Hall
Khoa Công nghệ Thông tin
Trường ĐH Bách Khoa Tp.HCM

Môn : Hệ điều hành
Chương 3 : Tương tranh giữa các process
Slide 1

3.1 Giới thiệu về tương tranh
‰

‰

‰

Trong hệ đa chương, thường có nhiều process chạy song hành,
nhưng mỗi process c kh ng gian l m việc độc lập, không ai có
thể truy xuất trực tiếp không gian làm việc của process khác => rất
tốt cho việc bảo vệ ch ng lẫn nhau nhất l khi các process này là
những chương trình độc lập.
Nếu 2 hay nhiều process cần giao tiếp nhau để đồng bộ hay để
trao đổi dữ liệu, ta cần cung cấp cơ chế cho ch ng. C 2 cơ chế
giao tiếp ch nh giữa c c process : truy xuất bộ nhớ d ng chung v
gởi/nhận th ng b o.
Truy xuất bộ nhớ chung là 1 trong nhiều hoạt động tương tranh
giữa các process. Vấn đề tương tranh trên 1 tài nguyên dùng
chung là vấn đề lớn cần phải giải quyết triệt để vì nếu nhiều
process truy xuất đồng thời v o 1 t i nguy n d ng chung mà
không có sự kiểm soát thì dễ xảy ra lỗi làm hư hỏng tài nguyên
(điều kiện Race).
Khoa Công nghệ Thông tin
Trường ĐH Bách Khoa Tp.HCM

Môn : Hệ điều hành
Chương 3 : Tương tranh giữa các process
Slide 2

1

Giới thiệu về tương tranh
‰

‰

‰

Phân tích kỹ code của chương trình, ta nhận thấy chúng là
danh sách liên tiếp của 2 loại đoạn code :
đoạn code truy xuất các biến cục bộ của chương trình. Đoạn
code này thường dài và xuất hiện nhiều. May mắn là chúng ta
không cần quan tâm và kiểm soát đoạn code này.
Đoạn code truy xuất tài nguyên dùng chung và có thể tranh
chấp với process khác. Đây là đoạn code, mặc dù ít xuất hiện
và thường rất ngắn, nhưng dễ gây lỗi trên tài nguyên nên ta
gọi nó là 'critical session‘ (viết tắt là CS), chúng ta cần kiểm
soát cẩn thận đoạn code CS này.

Môn : Hệ điều hành
Chương 3 : Tương tranh giữa các process
Slide 3

Khoa Công nghệ Thông tin
Trường ĐH Bách Khoa Tp.HCM

Giới thiệu về tương tranh
đoạn lệnh truy
xuất cục bộ

đoạn lệnh truy
xuất cục bộ
critical session 1

resource 1

đoạn lệnh truy
xuất cục bộ

đoạn lệnh truy
xuất cục bộ
critical session 2
đoạn lệnh truy
xuất cục bộ

Khoa Công nghệ Thông tin
Trường ĐH Bách Khoa Tp.HCM

critical session 2

critical session 1
resource 2
đoạn lệnh truy
xuất cục bộ

Môn : Hệ điều hành
Chương 3 : Tương tranh giữa các process
Slide 4

2

Giới thiệu về tương tranh
Thí dụ 2 ứng dụng truy xuất tài khoản A đồng thời :
1. hiển thị giao diện & chờ
người dùng ra lệnh
2. Người dùng ra lệnh nạp
vào tài khoản A số tiền
700USD → xử lý :
21a Đọc tài khoản A vào
bộ nhớ,
22a Tăng giá trị tài
khoản trong bộ nhớ
lên 700USD.
23a Ghi lại giá trị mới.
3. Quay về bước 1

Tài khoản
A

Vùng CS

1. hiển thị giao diện & chờ
người dùng ra lệnh
2. Người dùng ra lệnh rút tiền
từ tài khoản A 500USD →
xử lý :
21b Đọc tài khoản A vào
bộ nhớ,
22b Giảm giá trị tài
khoản trong bộ nhớ
đi 500USD.
23b Ghi lại giá trị mới.
3. Quay về bước 1

Nếu tài khoản A là 1000USD và HĐH điều khiển chạy 2 process P1 và P2
theo thứ tự 21a→22a→21b→22b→23b→23a thì kết quả tài khoản A sẽ là
1700USD (giá trị đúng là 1200USD).
Khoa Công nghệ Thông tin
Trường ĐH Bách Khoa Tp.HCM

Môn : Hệ điều hành
Chương 3 : Tương tranh giữa các process
Slide 5

3.2 Loại trừ tương hỗ giữa các đoạn CS
ƒ

ƒ

ƒ

ƒ

Để kiểm soát việc truy xuất tài nguyên đồng thời giữa nhiều process, ta
không cho phép hơn 1 vùng CS của các process đó cùng truy xuất tài
nguyên xác định tại từng thời điểm. Phương pháp này được gọi là loại
trừ tương hỗ giữa các đoạn CS (Mutual Exclusion).
Có nhiều phương pháp loại trừ tương hỗ cụ thể khác nhau và được chia
làm 2 nhóm chính : nhóm các phương pháp dừng chờ chủ động (busy
waiting) và nhóm các phương pháp dừng chờ thụ động (sleep/wakeup).
Tinh thần của nhóm phương pháp dừng chờ chủ động là khi 1 process
cần thực hiện đoạn code CS tương tranh với process khác thì nó phải
dừng chờ đến khi process khác chạy xong đoạn code CS này, trong
quá trình dừng chờ, nó vẫn chiếm CPU liên tục để dò điều kiện chạy
tiếp liên tục (nhưng không thành công).
Tinh thần của nhóm phương pháp sleep/wakeup là khi phải dừng chờ
process khác, nó xin ngủ (trả CPU) và nằm bất động. Khi process khác
thực hiện xong vùng CS, hệ thống sẽ đánh thức process ngủ để bắt đầu
thực hiện đoạn lệnh CS…
Khoa Công nghệ Thông tin
Trường ĐH Bách Khoa Tp.HCM

Môn : Hệ điều hành
Chương 3 : Tương tranh giữa các process
Slide 6

3

Loại trừ tương hỗ giữa các đoạn CS
Mỗi lần muốn vào vùng
CS, ta phải gọi hàm
In_Control() để kiếm soát
việc thi hành vùng CS, khi
hoàn thành vùng CS, ta
phải
gọi
hàm
Out_Control() để thông
báo cho các process khác
đang chờ để chúng kiểm
tra lại việc đi vào.

Khoa Công nghệ Thông tin
Trường ĐH Bách Khoa Tp.HCM

In_Control();
Vùng CS truy xuất tài
nguyên dùng chung
Out_Control();

Môn : Hệ điều hành
Chương 3 : Tương tranh giữa các process
Slide 7

3.3 Các phương pháp chờ chủ động
1. Phương pháp dựa trên Interrupt
ƒ Tính chất cơ bản của CPU là sau khi thi hành 1 lệnh máy, nó sẽ
tự động thi hành lệnh máy kế tiếp,… mà không để ý bất kỳ thứ gì
bên ngoài.
ƒ Tuy nhiên, nếu chỉ vậy, CPU sẽ không bao giờ đáp ứng kịp thời
1 sự kiện nào đó xảy ra trong quá trình thi hành chương trình của
CPU. Do đó, người ta phải tạo thêm 1 chân nhập có tên là IRQ.
Một thiết bị nào đó nếu muốn yêu cầu CPU xử lý dùm công việc
nào thì hãy tạo tín hiệu (ngắt) gởi về CPU trên chân IRQ. Bình
thường, mỗi khi CPU thấy có tín hiệu trên chân IRQ, nó sẽ dừng
tạm thời chương trình đang chạy hiện hành, chạy đoạn lệnh qui
định trước (trình phục vụ ngắt) để xử lý công việc dùm cho thiết
bị yêu cầu. Sau khi hoàn thành trình phục vụ ngắt, CPU sẽ quay
về tiếp tục thi hành chương trình từ vị trí ngừng trước đây.
Khoa Công nghệ Thông tin
Trường ĐH Bách Khoa Tp.HCM

Môn : Hệ điều hành
Chương 3 : Tương tranh giữa các process
Slide 8

4

3.3 Các phương pháp chờ chủ động
1. Phương pháp dựa trên Interrupt
Tuy nhiên, nếu CPU đang thi hành chương trình real-time hay nhạy
cảm với thời gian, nó cần có khả năng phớt lờ yêu cầu ngắt. Để giúp
chương trình quyết định lúc nào cho phép CPU đáp ứng ngắt, lúc
nào phớt lờ, người ta cung cấp 2 lệnh máy sau :
Cli : clear Interrupt : cấm CPU được phục vụ ngắt
Sti : set interrupt : cho phép CPU được đáp ứng ngắt.
Như vậy, nếu ta viết :
In_Control() ≡ cli
Out_Control() ≡ sti
thì tại từng thời điểm chỉ có tối đa 1 process chạy được vùng CS, vì
không có process nào khác (kể cả trình lập lịch) có thể ngắt nó tạm
thời.
Khoa Công nghệ Thông tin
Trường ĐH Bách Khoa Tp.HCM

Môn : Hệ điều hành
Chương 3 : Tương tranh giữa các process
Slide 9

3.3 Các phương pháp chờ chủ động
Phương pháp dựa trên ngắt quảng rất đơn giản, hiệu quả nhưng nếu
lập trình sai thì nguy hiểm khôn lường. Thí dụ nếu ta quên viết lệnh
sti sau khi hoàn thành vùng CS thì process tương ứng sẽ tiếp tục
chạy đến hết chương trình rồi treo máy vì không process nào khác,
kể cả trình lập lịch, có thể chiếm được CPU để chạy.
Hiện nay, chỉ có HĐH mới được phép dùng phương pháp này,
chương trình ứng dụng không được phép dùng.
Hơn nữa, phương pháp dựa trên ngắt chỉ tác động trên 1 CPU, nếu
máy có nhiều CPU thì các CPU khác không bị ảnh hưởng bởi lệnh
cấm ngắt trên 1 CPU nào đó.

Khoa Công nghệ Thông tin
Trường ĐH Bách Khoa Tp.HCM

Môn : Hệ điều hành
Chương 3 : Tương tranh giữa các process
Slide 10

5

Tài liệu cùng danh mục Hệ điều hành

Creating concrete5 Themes

Get to grips with the concrete5 architecture. Learn how to create a concrete5 theme. Discover how to make a theme responsive to improve it for small devices.


Sử dụng CGI Script với Nginx trên Fedora 15

Common Gateway Interface (CGI) là chuẩn để kết nối chương trình ứng dụng với Web server. Dữ liệu từ bảng biểu do người dùng điền vào trên trang Web được chuyển cho ứng dụng CGI, ứng dụng này sau đó sẽ gửi trả nội dung Web được tạo ra theo yêu cầu ngược về cho trình duyệt của người dùng. Trong khi bản thân nginx không đáp ứng CGI, chúng ta có hai giải pháp để giải quyết vấn đề này: đầu tiên là yêu cầu proxy cho các script CGI tới Thttpd (một máy chủ nhỏ hỗ trợ CGI),...


Sao lưu và phục hồi các ứng dụng đã cài từ Windows 8 Store

Phần mềm không thể thiếu cho người dùng Windows 8. Trong quá trình sử dụng Windows 8, chắc hẳn bạn đã cài đặt rất nhiều các ứng dụng từ Windows 8 Store và hiện tại bạn đang muốn cài đặt lại hệ điều hành và không muốn tốn thời gian để tải về và cài đặt lại các ứng dụng từ Windows 8 Store cho máy tính hay bạn muốn đồng bộ các ứng dụng Windows 8 này sang một máy tính Windows 8 khác mà không muốn mất thời gian cài đặt lại,... tất cả sẽ đơn giản với...


Quản trị hệ thống Linux part 10

Tham khảo tài liệu 'quản trị hệ thống linux part 10', công nghệ thông tin, hệ điều hành phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả


A Foundation in Digital Communication

This intuitive yet rigourous introduction derives the core results of digital communication from first principles. Theory, rather than industry standards, motivates the engineering approaches, and key results are stated with all the required assumptions. The book emphasizes the geometric view, opening with the inner product, the matched filter for its computation, Parseval's theorem, the sampling theorem as an orthonormal expansion, the isometry between passband signals and their baseband representation, and the spectral-efficiency optimality of quadrature amplitude modulation (QAM). Subsequent chapters address noise, hypothesis testing, Gaussian stochastic processes, and the sufficiency of the matched filter outputs....


Khám phá tính năng tìm kiếm mới của Windows 7 T

Trong bài này chúng tôi sẽ giới thiệu cho các bạn về cỗ máy tìm kiếm mới được thiết kế lại của Windows 7. Trong đó đề cập chi tiết về một số tính năng mới và một số sự tối ưu mà Microsoft đã thực hiện để cải thiện sự hiệu quả. Giới thiệu Một vài năm gần đây, tính năng tìm kiếm (Windows Search) của Windows đã nhận được một số lời khiển trách. Mặc dù không thích sự suy đoán nhưng sẽ có rất nhiều người cảm thấy có ít các tính năng tìm kiếm nổi trội...


HP tiên phong sử dụng Google Android trong netbook?

HP tiên phong sử dụng Google Android trong netbook? HP và nhiều hãng sản xuất máy tính khác đang cân nhắc việc cài phần mềm miễn phí của Google cho các netbook đời mới. Động thái này chắc chắn sẽ tạo ra một cuộc cạnh tranh mới giữa gã khổng lồ Google với Microsoft. Sẽ có netbook chạy hệ điều hành Android? Hệ điều hành mã mở miễn phí Android đã được sử dụng trong một số dòng điện thoại smartphone. Theo các nhà phân tích, Android sẽ là nền tảng hữu ích cho netbook - phân đoạn thị trường khá sôi...


Cấu hình máy tính dành cho Windows Vista

Cấu hình máy tính dành cho Windows Vista Thứ tư, 15/03/2006, 05:12 GMT+7 Cho em hỏi cấu hình máy như thế nào mới có thể chạy được Windows Vista? Em đang làm tiệm game online vậy Windows Vista có hỗ trợ cho nhiều phòng game không vậy? (quoctien2003…@yahoo.com) Vào cuối tháng 2-2006, Microsoft công bố rằng họ đã lên kế hoạch tung ra đến 6 phiên bản khác nhau của Windows Vista để phục vụ cho những nhu cầu sử dụng máy tính đa dạng của người dùng, thay vì “chỉ định” một phần cứng tối thiểu nào đó mới “được quyền” chạy...


MCITP Microsoft Exchange Server 2007 Messaging Design and Deployment Study Guide phần 4

Cuối cùng, chúng tôi đã giới thiệu một số điều chỉnh bổ sung mà bạn nên làm gì để làm cho tổ chức Exchange của bạn như là an toàn nhất có thể. Chúng tôi đã điều tra làm thế nào bạn có thể an toàn môi trường của bạn bằng cách ủy quyền vai trò quản trị viên Exchange và bằng cách đảm bảo email SMTP. Để kết thúc, chúng ta đã thông tin quản lý quyền.


The ThoughtWorks Anthology, Volume 2: More Essays on Software Technology and Innovation

When you hit a rough spot in software development, it's nice to know that someone has been there before. The domain experts at ThoughtWorks share what they've learned in this anthology, bringing together the best field-tested insights in IT and software development. You'll benefit from their experience in areas from testing to information visualization, from object oriented to functional programming, from incremental development to driving innovation in delivery. You'll find yourself referring to this collection of solved problems whenever you need an expert's insight....


Tài liệu mới download

Từ khóa được quan tâm

Có thể bạn quan tâm

Windows Automated Installation Kit
  • 28/07/2010
  • 63.919
  • 348
What Is XQueryX?
  • 08/08/2009
  • 26.957
  • 747
Lectures Note on Game Theory
  • 11/10/2012
  • 60.803
  • 520

Bộ sưu tập

Danh mục tài liệu