Đề tài Quản lý luồng trong Unix, Win2000

TRƯỜNG ĐẠI HỌC KINH TẾ QUỐC DÂN Bài thảo luận Môn: Hệ điều hành Đề tài Quản lý luồng trong Unix, Win2000 Sinh viên thực hiện: Nguyên Chí Điện Phùng Văn Quyết Đào Mạnh Cường Nguyễn Văn Huy HÀ NỘI, 2009 MỤC LỤC Trang PHẦN I: Tổng quan về luồng 1,Luồng là gì………………………………………………….3 2,Các loại luồng………………………………………………3 3,Các mô hình luồng…………………………………………4 PHẦN II: Cấp phát luồng 1,Lời gọi hệ thống và exec…………………………………..6 2,Hủy luồng…………………………………………………13 3,Truyền thông giữa các luồng…………………………….14 PHẦN III: Mô hình luồng trong win2000 và unix 1,Mô hình luồng trong win2000…………………………...15 2,Mô hình luồng trong unix……………………………….16 Phần l: Tổng quan về luồng 1, Luồng là gì? Luồng (thread), còn gọi là quá trình nhẹ (lightweight process- lwp) hay tiểu trình, là một đơn vị cơ bản của việc sử dụng CPU. Luồng có mô hình tương tự tiến trình, trong việc xử lí tuần tự các chỉ thị máy. Cấu trúc luồng bao gồm một định danh luồng (thread ID), một bộ đếm chương trình, các tập thanh ghi và ngăn xếp (stack). Do được định nghĩa như một tiến trình nhỏ, ta dễ thấy trong phạm vi một tiến trình, có thể có một hoặc nhiều luồng, mỗi luồng gồm: một trạng thái thực thi luồng (running, ready), một lưu trữ về ngữ cảnh của processor khi luồng ở trạng thái not running, các thông tin thống kê về việc sử dụng các biến cục bộ của luồng, một ngăn xếp thực thi. Việc truy xuất đến bộ nhớ và tài nguyên tiến trình được chia sẻ với tất cả các luồng khác trong cùng một tiến trình. Các luồng này có cùng một không gian địa chỉ, nhờ đó mà có thể chia sẻ các biến toàn cục của tiến trình và có thể truy xuất lên các vùng nhớ stack của nhau. Các luồng chia sẻ thời gian sử lý của processor giống như cách của tiến trình, nhờ đó mà các luồng có thể hoạt động song song với nhau. Trong quá trình thực thi của luồng nó có thể tạo ra các luồng con của nó. 2, Các loại luồng Có hai loại luồng: luồng cấp người dùng và luồng cấp nhân. Hỗ trợ luồng được cung cấp ở cấp người dung cho các luồng người dùng hoặc ở cấp nhân cho các luồng nhân. Luồng nhân: được hỗ trợ trực tiếp bởi hệ điều hành, thực hiện việc tạo luồng, lập thời biểu và quản lý không gian nhân. Do việc quản lý được thực hiện bởi hệ điều hành, luồng nhân tạo và quản lý chậm hơn luồng người dùng. Tuy nhiên, do được quản lý thời biểu, nếu một luồng thực hiện một lời gọi hệ thống nghẽn, nhân có thể lập thời biểu cho một luồng khác trong ứng dụng thực thi, giúp hệ thống không bị nghẽn. Hiện nay, các hệ điều hành đều được hỗ trợ luồng nhân. Luồng người dùng: được hỗ trợ dưới nhân và được cài đặt bởi thư viện tại cấp người dùng. Thư viện cung cấp việc tạo luồng, lập thời biểu và quản lý luồng mà không có sự hỗ trợ từ nhân, do đó các luồng ở cấp này thường được tạo và quản lý nhanh. Việc tiến trình bị tắc nghẽn khi thực hiện một lời gọi hệ thống chỉ xảy ra khi nhân là đơn luồng (một dòng điều khiển). 3, Các mô hình luồng Trong quá trình thực thi (running) một tiến trình có thể tạo ra một luồng hoặc nhiều luồng con để phục vụ các yêu cầu của mình. Chính vì thế mà ta có các mô hình đơn luồng và đa luồng. Mô hình đơn luồng là mô hình mà tại một thời điểm khi một tiến trình đưa ra yêu cầu thì nó sinh ra một luồng điều khiển đơn cho phép chỉ thực hiện một yêu cầu của tiến trình tại thời điểm đó. Mô hình đa luồng là mô hình mà tại một thời điểm, khi tiến trình đưa ra các yêu cầu thì nó có thể sinh ra nhiều luồng điều khiển để thực hiện các yêu cầu đó tại cùng thời điểm. Nhiều hệ điều hành cung cấp sự hỗ trợ cả luồng nhân và luồng người dùng, nên từ đó tạo ra nhiều mô hình đa luồng khác nhau. Có ba loại mô hình đa luồng thông thường: + Mô hình nhiều-một: ánh xạ nhiều luồng cấp người dùng tới một luồng cấp nhân.Khi đó, vì chỉ một luồng có thể truy xuất nhân tại một thời điểm nên nhiều luồng không thể chạy song song trên nhiều bộ xử lý: Hình1: Mô hình nhiều-một + Mô hình một-một: ánh xạ một luồng cấp người dùng tới một luồng cấp nhân.cho phép nhiều luồng chạy song song trên các bộ xử lý khác nhau.Nhưng nhược điểm là khi tạo một luồng người dùng thì phải tạo một luồng nhân tương ứng: Hình 2: Mô hình một-một + Mô hình nhiều-nhiều: ánh xạ nhiều luồng cấp người dùng tới nhiều cấp nhân nhưng số lượng luồng người dùng phải nhỏ hơn hoặc bằng số lượng luồng nhân. Hình 3: Mô hình nhiều-nhiều Phần II. Cấp phát luồng: Trên lý thuyết, mỗi tiến trình sẽ có một không gian địa chỉ và một dòng xử lý riêng. Nhưng trong thực tế, có một số ứng dụng cần nhiều dòng xử lý cùng chia sẻ một không gian địa chỉ tiến trình. Các dòng xử lý này có thể hoạt động song song với nhau như các tiến trình độc lập trong hệ thống. Để thực hiện điều này,các hệ điều hành đưa ra một số cơ chế thực thi mà ta gọi là luồng. Khi một tiến trình đang thực thi đưa ra các yêu cầu, trình phục vụ sẽ nhận yêu cầu và tạo ra luồng riêng để phục vụ yêu cầu đó. 1, Lời gọi hệ thống fork và exec Các hệ điều hành dùng lời gọi hệ thống fork và exec để cấp phát luồng. Trong một chương trình đa luồng, ngữ nghĩa của lời gọi hệ thống fork và exec thay đổi. Nếu một luồng trong lời gọi chương trình fork thì quá trình mới sao chép lại qua trình tất cả luồng hoặc một quá trình đơn luồng mới.Một số hệ Unix chọn việc sử dụng hai ấn bản của fork, một sao chép lại tất cả luồng và một sao chép lại chỉ luồng được nạp lên lời gọi hệ thống, phụ thuộc vào ứng dụng của luồng. Còn nếu một luồng nạp lời gọi hệ thống exec thì chương trình được nạp trong tham số exec sẽ thay thế toàn bộ quá trình-chứa tất cả các luồng và các quá trình tải nhẹ. Một số lời gọi hệ thống :fork,wait,signal,exec,brk,shell,init…Trong đó: -Fork(): Tạo ra một tiến trình mới. -Exec(): Cho phép một tiến trình kích hoạt một chương trình “mới”.Bản chất của ‘exec’ là biến tiến trình gọi thành tiến trình mới .Tiến trình mới là một tệp thực thi và mã của nó sẽ “ghi đè ” lên không gian của tiến trình gọi ,vì vậy sẽ không có giá trị trả về kho exec thành công. FORK Sự tạo lập một tiến trình mới được thực hiện bằng lời gọi hệ thống fork.Fork() cho phép một tiến trình lập một bản sao của nó,trừ bộ định dạng tiến trình.Tiến trình gốc tự nhân bản chính nó được gọi là tiến trình cha và bản sao tạo ra gọi là tiến trình con. Cú pháp như sau: Pid = fork() Khi thực hiên xong ,hai tiến trình trên có hai bản sao user lever context như nhau và với các giá trị trả lại pid khác nhau: trong bản thân mã của tiến trình bố, pid là số định danh của tiến trình con; trong bản thân mã của tiến trình con, pid=0 thông báo kết quả tạo tiến trình là tốt; các bước thực hiện fork như sau: 1.cấp cho tt mới một đầu vào (entry) trong process table; 2.gán cho tt con một số định danh duy nhất; 3.tạo ra bản sao logic bối cảnh của tiến trình bố cho tiến trình con.Vì một số phần của tiến trình có thể chia sẻ giữa các tiến trình ,kernel sẽ tăng tốc các số đếm quy chiếu vào các miền đó thay vì sao chép miền trong bộ nhớ vật lý. 4.tăng số đếm quy chiếu trong bảng các tệp mở (file table) kết hợp với tiến trình ,tiến trình con thừa kế sử dụng , tức là cả hai thao tác trên cùng một tệp,bảng inode (inode table) vì tiến trình con tồn tại trong cùng thư mục hiện hành của tiến trình bố ,nên số truy nhập tệp thư mục +1. 5.trả lại số định danh ‘pid’ của tiến trình con cho tiến trình bố. CHƯƠNG TRÌNH C TẠO TIẾN TRÌNH CON #include main(int argc, char* argv[]) { Int pid; /*fork another process*/ pid=fork(); if(pid<0) { /*error occurred */ printf(stderr, “Fork Failed”); exit(-1); } else if (pid==0) { /*child process*/ execlp(“/bin/ls”,”ls”,NULL); } Else { /*parent process*/ /*parent will wait for the child to complete*/ wait(NULL); printf(“Child Complete”); exit(0); } } THUẬT TOÁN FORK Thực tế thuật toán fork() không đơn giản vì TT mới có thể đi vào thực hiện ngay và phụ thuộc vào hệ thống kiểu swaping hay demand paging. Để đơn giản chọn hệ với swaping và giả định rằng hệ có đủ bộ nhớ để chứa TT con, thuật toán sẽ như sau: fork() input: none output: - PID for parent process /* Process ID*/ - 0 to child process; { .check for available kernel resources; .get free process table entry (slot), unique ID number; .check that user not running too many processes; .mark child state is “ being created“; .copy data from parent process table entry to new child entry;/*dup*/ .increment counts on current directory inode and changed root (if applicable); .increment open file counts in file table;/*Ref. count of fds = +1*/ .make copy of parent context (u_area, text, data, stack) in memory; /*create user level context (static part) now in using dupreg(), attachreg(). Except that the content of child’s u_area are initally the same as of parent’s,but can diverge after completion of the fork: the pionter to its process table slot. Note that, if nows parent open new file, the child can’t access to it !!! */ . push dummy system level context layer onto child system level context; /*Now kernel create the dynamic context for child: copy parent context layer 1 containing the user saved register context and the kernel frame stack of the fork system cal. If kernel stack is part of u_area, kernel automaticlly create child kernel stack when create the child u_area. If other method is used, the copying is needed to the private memory associated with chile process. Next kernel creates dummy context layer 2 for child containing the saved register context for lauer 1, set program counter . other regs to restore the child context, even it had never executed before and so that the child process to recognize itself as child when it runs. Now kernel tests the value register reg0 to decide if process is parent (reg0=1) or child (reg0=0).*/; .if (executing process is parent process) { /* After all, kernel set child to “ready to run in memory”, return PID to user*/ .change child state to “ready to run“; .return(child PID); /*from system to user*/ } .else { /* and it start running from here when scheduled executing process is the child process: Child executes part of the code for fork() according to the program counter that kernel restored from the saved regiter context in context layer 2, and return a 0 from the fork()*/ initialize u_area timing field; return(0); /*to user*/ } } EXEC GHT exec sẽ kích hoạt một chương trình khác, phủ lên không gian bộ nhớ của TT gốc bằng bản sao của tệp thực thi. Nội dung của user - level context có trước exec sau đó không truy nhập được nữa, ngoại trừ các thông số của exec mà kernel đã sao chép từ không gian địa chỉ cũ sang không gian địa chỉ mới. PID của TT củ không đổi và TT mới do exec tạo ra sẽ nhận PID đó. execve (filename, argv, envp) filename: tên tệp thực thi sẽ kích hoạt, argv: trường các con trỏ kí tự trỏ vào các xâu kết thúc bằng kí tự NULL. Các xâu này tạo thành danh sách đối đầu vào cho TT mới được tạo. envp: con trỏ trỏ vào các xâu kí tự tạo thành môi trường của tệp thực thi. Trong thư viện C có sáu exec như sau: execl (const char * pathname, const char *arg0, … / * (char *) 0 */ ); execv (const char * pathname, char *const argv[ ]); execle (const char * pathname, const char *arg0, … /*( char *) 0, char *const envp [ ] */ ); execve (const char * pathname, char *const argv[ ], char *const envp [ ] ); execlp (const char * filename, const char *arg0, … / * (char *) 0 */ ); execvp (const char * filename, char *const argv [ ] ); Để dễ nhớ ta dùng bảng sau: Các chử cái có ý nghĩa như sau: p: hàm lấy đối filename và dùng biến mmôI trường PATH để tìm tệp thực thi; l: Hàm lấy một danh sách các đối là sự loại trừ lẫn nhau với v; v: hàm lấy đối ở argv[ ]; e: Hàm lấy đối môI trường từ envp[ ] thay cho môI trường hiện hành. Khi một chương trình dùng dòng lệnh: main(argv, argv) thì trường argv là bản sao của thông số argv cho exec. Các xâu kí tự trong envp có dạng “ name = value” và chứa các thông tin hữu ích cho chương trình (chẳng hạn user’s home directory, đường dẫn tìn tệp thực thi). TT truy nhập các biến môi trường của nó qua biến tổng thể environ được khởi động bằng chu trình thực thi (routine) của C. exec() input: 1. file name 2. parameter list 3. environment variables list output: none { .get file inode(namei()); .verify file is executable, user has permission to execute; .read file header, check that it is a load module; .copy exec parameters from old address space to system space; .for (every region attached to process) detach all old region; .for (very region specified in load module) { allocate new regions; attach the regions; load region into memory if applicable; } .copy exec parameters into new user stack regions; .special processing for setuid programs, tracing; .initialize user register save area for return to user mode; .release inode of file; } Ví dụ của exec: (exec1.c) #include #include #include "ourhdr.h" char *env_init[ ] = { "USER=unknown", "PATH=/tmp", NULL }; int main(void) { pid_t pid; if ( (pid = fork()) < 0) err_sys("fork error"); else if (pid == 0) { /* specify pathname, specify environment */ if (execle("/home/SV1/bin/echoall", "echoall", "myarg1", "MY ARG2", (char *) 0, env_init) < 0) err_sys("execle error"); } if (waitpid(pid, NULL, 0) < 0) err_sys("wait error"); if ( (pid = fork()) < 0) err_sys("fork error"); else if (pid == 0) { /* specify filename, inherit environment */ if (execlp("echoall", "echoall", "only 1 arg", (char *) 0) < 0) err_sys("execlp error"); } exit(0); } Việc sử dụng 2 ấn bản fork phụ thuộc vào ứng dụng. Nếu exec bị hủy ngay sau khi phân nhánh thì việc sao chép lại tất cả luồng là không cần thiết khi chương trình được xác định trong các tham số exec sẽ thay đổi quá trình. Trong trường hợp này, việc sao chép lại sẽ chỉ gọi luồng hợp lý. Tuy nhiên, nếu quá trình riêng biệt này không gọi exec sau khi phân nhánh thì quá trình phân biệt này nên sao chép lại tất cả các luồng 2, Hủy luồng Hủy luồng là một tác vụ kết thúc luồng trước khi nó hoàn thành. Khi đó, một luồng bị hủy được xem như một luồng đích. Sự hủy bỏ một luồng đích thường xảy ra hai viễn cảnh sau: Hủy bất đồng bộ: một luồng lập tức kết thúc luồng đích. Hủy trì hoãn: luồng đích có thể kiểm tra định kì nếu nó sắp kết thúc.Cho phép luồng đích có cơ hội tự kết thúc có thứ tự. Trong việc hủy luồng ta gặp phải một số khó khăn như là: khi tài nguyên được cấp phát tới một luồng bị hủy, hoặc một luồng bị hủy khi việc cập nhật dữ liệu đang xảy ra giữa chừng, nhưng nó đang chia sẻ với các luồng khác, sự hủy bất đồng bộ trở nên khó khăn, hệ điều hành đòi lại tài nguyên nhưng không đòi được, do đó gây ra việc giải phóng hết tài nguyên của hệ điều hành. Đối với hủy trì hoãn thì sự hủy sẽ xảy ra khi luồng đích kiểm tra và xác định nó có hủy được hay không. Hầu hết, hệ điều hành cho phép một quá trình sao cho một luồng bị hủy bất đồng bộ, khi hệ điều hành cài đặt Pthread API (thư viện cài đặt đặc tả tạo và đồng bộ luồng) sẽ cho phép sự hủy có trì hoãn. 3, Truyền thông giữa các luồng Như đã nói ở trên, các luồng trong một tiến trình chia sẻ với nhau không gian địa chỉ chung, nhờ đó mà các luồng có thể chia sẻ các biến toàn cục của tiến trình và có thể truy xuất lên các vùng nhớ stack của nhau. Các luồng chia sẻ thời gian xử lý của processor giống như cách của một tiến trình. Nhờ đó mà các luồng có thể hoạt động song song với nhau.Trong quá trình thực thi của luồng, nó cũng có thể tạo ra các luồng con của nó. Điều đáng chú ý là có nhiều luồng trong phạm vi một tiến trình đơn. Các hệ điều hành khác nhau có cách tiếp cận mô hình khác nhau, trong đó có mô hình luồng từ mô hình tác vụ. Trong hệ thống tồn tại một không gian địa chỉ ảo để lưu trữ tác vụ và một cơ chế bảo vệ truy cập các file, các tài nguyên vào ra và các tiến trình khác. Các thao tác lập lịch và điều phối tiến trình của hệ điều hành thực hiện trên cơ sở luồng. Nhưng nếu có một thao tác nào đó ảnh hưởng đến tất cả các luồng trong tác vụ thì hệ điều hành phải tác động vào tác vụ đó. Vì tất cả các luồng trong một tác vụ chia sẻ cùng một không gian địa chỉ nên tất cả các luồng phải được đưa vào trạng thái hoãn tại cùng một thời điểm. Tương tự, khi một tác vụ kết thúc thi sẽ kết thúc tất cả các luồng trong tác vụ đó. Phần III: Mô hình luồng trong Win2000 và Unix 1, Mô hình luồng trong Win2000 Hệ điều hành Win2000 cài đặt Win32 API. Đây là một API chủ yếu cho họ điều hành Windowns, sử dụng lệnh hủy có trì hoãn. Ứng dụng Windows chạy như một quá trình riêng lẻ, nơi mỗi quá trình có thể chứa một hay nhiều luồng. Win2000 dùng ánh xạ một-một, mỗi luồng cấp người dùng ánh xạ tới luồng nhân được liên kết. Tuy nhiên, Win2000 cũng được cung cấp hỗ trợ cho một thư viện có cấu trúc cung cấp chức năng mô hình nhiều-nhiều. Mỗi luồng thuộc về một tiến trình có thể truy xuất một không gian địa chỉ ảo của tiến trình. Những thành phần thông thường của một luồng trong Win2000 là: * Một định danh luồng duy nhất(thread ID) * Tập thanh ghi biểu diễn trang thái của bộ xử lý * Ngăn xếp người dùng khi luồng đang chạy ở chế độ người dùng. Do đó, mỗi luồng cũng có một ngăn xếp nhân được dùng khi luồng chạy ở chế độ nhân * Một vùng lưu trữ riêng được dùng bởi nhiều thư viện, thời gian thực và thư viện liên kêt động (DLLs). Tập thanh ghi, ngăn xếp và vùng lưu trữ riêng được xem như ngữ cảnh của luồng và được đặc tả kiến trúc tới phần cứng mà hệ điều hành chạy trên đó. Cấu trúc dữ liệu của luồng trong Win2000 gồm: ETHREAD (executive thread block - khối luồng thực thi): gồm một con trỏ chỉ tới quá trình chứa luồng và địa chỉ của thủ tục mà luồng bắt đầu điều khiển trong đó. ETHREAD cũng chứa một con trỏ chỉ tới KTHREAD tương ứng. Tồn tại hoàn toàn ở không gian nhân, chỉ nhân mới có thể truy suất được. KTHREAD (kernel thread - khối luồng nhân): gồm thông tin định thời và đồng bộ hóa cho luồng. Ngoài ra, còn chứa ngăn xếp nhân (được dùng khi luồng đang chạy trong chế độ nhân) và con trỏ chỉ tới TEB. Tồn tại hoàn toàn ở không gian nhân, chỉ nhân mới có thể truy suất được. TEB (thread environment block - khối môi trường luồng): là cấu trúc dữ liệu trong không gian người dùng được truy suất khi luồng đang chạy trong chế độ người dùng. Giữa những trường khác nhau, TEB chứa ngăn xếp người dùng và một mảng cho dữ liệu đặc tả luồng, mà Windows gọi là lưu trữ cục bộ luồng. Mặc dù Windows 2000 không cung cấp rõ sự hỗ trợ tín hiệu quản lý, nhưng chúng có thể được mô phỏng sử dụng lời gọi thủ tục bất đồng bộ (asynchronous produce calls - APC). Tiện ích APC cho phép luồng người dùng xác định hàm được gọi khi luồng người dùng nhận thông báo về một sự kiện xác định. 2, Mô hình luồng trong Unix (trong ấn bản Solaris2) Unix thường dùng mô hình nhiều-nhiều. Ấn bản Solaris2 cài đặt Pthread API hỗ trợ luồng cấp người dùng với thư viện chính chứa APIs cho việc tạo và quản lý luồng. Solaris 2 cũng định nghĩa một cấp độ luồng trung gian. Giữa luồng cấp nhân và cấp người dùng là các quá trình nhẹ (lightweight process- LWPs). Thư viện luồng đa hợp người dùng trên LWPs cho quá trình và chỉ luồng cấp người dùng hiện được nối kết một LWP hoàn thành công việc.Các luồng còn lại bị khóa hoặc chờ cho một LWP mà chúng có thể thực thi trên nó. Luồng cấp nhân thực thi mọi thao tác trên nhân.Luồng người dùng có giới hạn được cấp vĩnh viễn với một LWP, luồng không giới hạn thì được gán với vĩnh viễn với bất kì ột LWP nào vì các luồng không giới hạn là mặc định.Các luồng cấp người dùng không có sự hỗ trợ từ nhân nên hoạt động rất hiệu quả. Hình 4: Luồng Unix (ấn bản Solaris2) Các luồng cấp người dùng có thể giới hạn hay không giới hạn. Một luồng cấp người dùng giới hạn được gán vĩnh viễn tới một LWP. Chỉ luồng đó chạy trên LWP và yêu cầu LWP có thể được tận hiến tới một bộ xử lý đơn (xem luồng trái nhất trong hình trên). Liên kết một luồng có ích trong trường hợp yêu cầu thời gian đáp ứng nhanh, như ứng dụng thời thực. Một luồng không giới hạn gán vĩnh viễn tới bất kỳ LWP nào. Tất cả các luồng không giới hạn được đa hợp trong một nhóm cac LWP sẳn dùng cho ứng dụng. Các luồng không giới hạn là mặc định. Cấu trúc của luồng Unix thông thường: • Luồng cấp người dùng chứa một luồng ID; tập thanh ghi (gồm một bộ đếm chương trình và con trỏ ngăn xếp); ngăn xếp; và độ ưu tiên (được dùng bởi thư viện cho mục đích định thời). Không có cấu trúc dữ liệu nào là tài nguyên nhân; tất cả chúng tồn tại trong không gian người dùng. • Một LWP có một tập thanh ghi cho luồng cấp nhân nó đang chạy cũng như bộ nhớ và thông tin tính toán. Một LWP là một cấu trúc dữ liệu nhân và nó nằm trong không gian nhân • Một luồng nhân chỉ có một cấu trúc dữ liệu nhân và ngăn xếp. Cấu trúc dữ liệu gồm bản sao các thanh ghi nhân, con trỏ tới LWP mà nó được gán, độ ưu tiên và thông tin định thời.