Graffiti
Recycle Bin
xroi.cc
Note Graph
Threads #
1pid = fork()
2int kill(pid_t pid, int sig) / Kill [OPTION] pid
3
4// Declaring a new action for a program given a signal
5int sigaction(int sig, struct sigaction *new_act, struct sigaction *old_act)
6
7// Wait unil recieving a signal
8pause()
9
10// add/remove/change current signal mask
11sigprocmask(int how, const sigset_t *set, sigset_t *oldset)
12
13// save and long CPU registers (for implementing user level threads)
14sigsetjmp(sigjmp_buf env, int savesigs)
15siglongjmp(sigjmp_buf env, int val)
16
17###########
18# Threads #
19###########
20
21// Create a new thread
22int pthread_create(pthread_t *thread, const pthread_attr_t *attr=NULL, void *(*start_routine) (void *), void *arg)
23// Terminate current Thread
24pthread_exit(void *status)
25// Cancel other thread
26pthread_cancel(pthread_t thread)
27// Wait for other thread to terminate on it's own
28int pthread_join(pthread_t thread, void **ret_val)
29
30#########
31# Mutex #
32#########
33
34// Initializing a mutex
35pthread_mutex_t mymutex = PTHREAD_MUTEX_INITIALIZER;
36OR pthread_mutex_init(mutex, attr)
37// Detroying mutex
38pthread_mutex_destroy(mutex)
39// Locking mutex
40pthread_mutex_lock(*mutex)
41// Unlocking mutex
42pthread_mutex_unlcok(*mutex)
43
44###########
45# Monitor #
46###########
47//todo recit 4
48
49#############
50# Semaphore #
51#############
52// Initializing a semaphore
53int sem_init(sem_t *sem, int pshared, unsigned int value)
54// Decrementing semphore
55int sem_wait(sem_t *sem)
56// Incrementing semaphore
57int sem_post(sem_t *sem)
58
c
// Peterson Algorithm (1981) (For 2 thread mutual exclusion)
flag[i] = True; // Set intent
turn = 1 - i; // Set turn to other thread
while(flag[1-i] and turn==1-i); // While other thread has intent and turn, wait.
// Critical section
flag[i] = False;
- כל ת'רד לוקח מספר. אם המספר גדול מהמספר של כל הת'רדים האחרים ממשיך לאיזור הקריטי, אחרת מחכה. - אבל זה יוצר בעיה - עם קונטקסט סוויץ' בזמן המתאים שני ת'רדים יכולים לקבל את אותו מספר. - אז מוסיפים גם דגל שאומר אם תהליך נמצא בשלב הבחירה. אם תהליך כלשהו נמצא בשלב הבחירה, אז שום תהליך לא ימשיך לאיזור הקריטי.
- Down(S) - Critical Section - Up(S)
- הפילוסופים יושבים במעגל וכל פילוסוף צריך את הצ'ופסטיק הימני והשמאלי כדי לאכול. איך קובעים אילו צ'ופסטיקס ירימו כדי למנוע דדלוק? - כל אחד מהפילוסופים 1 עד n-1 מנסה להרים את הימני. ולאחר מכן את השמאלי. - הפילוסוף ה-n מנסה קודם את השמאלי ואז את הימני. - אפשרות אחרת היא שהזוגיים ירימו את הימני ואז את השמאלי, והאי זוגיים ירימו את השמאלי ואז את הימני.
- ריק
- ריק
נרצה לתאר אלגוריתמי תזמון שמקטינים את זמן התגובה המתנה הממוצע, זמן התגובה הממוצע, ואת ה-Throughput. (ומגדילים את הניצולת)
- על פי הסדר שהעבודות באו
- על פי האורך של העבודות - הערה: זה האלגוריתם האופטימלי לזמן ההמתנה ולזמן התגובה הממוצע במקרה האופליין כשאנחנו יודעים את אורכי העבודות מראש.
- על פי הסדר שהעבודות באו
- על פי האורך של העבודות
- על פי האורך הנותר של העבודות. - משתמשים פה ב-Preemption, כלומר יכולים לעצור עבודה באמצע. - עדיין מניח שאנחנו יודעים את זמני הריצה של העבודות
- מריצים תהליכים למשך קוונטום קצר וקבוע מראש ואז מזיזים אותם לסוף התור. (ממומש על ידי פסיקות של השעון) - - זה טוב כי כשיש המון שונות באורכי העבודות בדרך כלל. (גם קצרות וגם ארוכות) כלומר $CV > 1$.
- כמו RR אבל יש כמה תורים ולכל תור יש קוואנטום. כשעבודה מסיימת קוואנטום (או כמות קוונטומים) והיא עוד לא הסתיימה היא עוברת לתור עם קוונטום ארוך יותר. - אבל יש עדיפות לעבודות בתורים עם קוונטום נמוך יותר. - יש הרעבה. פתרונות: - להקצות לכל תור זמן אחוז זמן CPU - לתת לכל ג'וב עדיפות, שעולה ככל שהוא לא רץ יותר זמן. - להסתכל על זה בתור פיצ'ר. אם כל הזמן מגיעות עבדוות קצרות המערכת באוברלאוד בכ"מ.
- רלוונטי למחשבי על ומערכות עם הרבה CPUים.
1///////////////////////
2// server and client //
3///////////////////////
4socket() // create a socket
5close() // close a socker
6read() / recv() // read from a socket (like a file)
7write() / send() // write to a socket (like a file)
8
9////////////
10// server //
11////////////
12bind() // bind a socker to a port and address to listen to locally (i.e. listen to wifi, ethernet, etc (usually this can be all))
13listen() // sets a socket to listening mode to allow it to accept connections.
14accept() // a blocking call, returns a file descriptor of a new socket if there was a successful incoming connection
15
16////////////
17// Client //
18////////////
19connect() // connect to server by address and port
- אם x זו הכתובת הלוגית, אז הכתובת הפיזית זה x+base. - כל המרחב הלוגי חייב להיות ממופה בזיכרון הפיזי. - מה שמערכת ההפעלה מחליטה היא מה יהיה ה-Base וה-Bound של כל תכנית, איפה היא תמופה. אלגוריתמי בחירה: - אלגוריתם Best Fit: מוצא את האיזור הרציף הקטן ביותר בזיכרון שיכול להכיל את התכנית. - אלגוריתם First Fit: מוצא את האיזור הרציף הראשון בזיכרון שיכול להכיל את התכנית. - אלגוריתם Next Fit: כמו First Fit, אבל מתחיל מהנקודה שהוא סיים בפעם שעברה במקום מהתחלה כל פעם. - יוצר External Fragmantation. - אפשר לעשות Compaction כדי למנוע את זה אבל זו פעולה יקרה.
- כמו Base+Bound אבל עם הרבה בייסים ובאונדים. - לכל תהליך יש טבלת סגנטים שאומרת איפה הזיכרון שלו.
- מחלקים את מרחב הכתובות הלוגי לפייג'ים של 4KB (2^12B) ומחלקים את המרחב הפיזי ל-Frames באותו גודל. הפייג'ים ממופים לפריימים על ידי מערכת ההפעלה וה-MMU. - לכל תהליך יש Page Table שבו כתוב הפריים של כל פייג'. ה-MMU משתמש בו כדי לתרגם. כשעושים קונטקסט סוויטצ' הפייג' טייבל מוחלף. - תרגום: בהינתן כתובת לוגית כלשהי, $log_2(psize)$ קובע את כמות הבייטים ב-Offset (כלומר הבייטים הקטנים שרק אומרים לנו איפה אנחנו בתוך הפריים). שאר הבייטים הם האינדקס של ה-Page, כלומר נכניס אותם לפייג' טייבל ונחליף אותם בתוצאה. - באפר התרגום/TLB/Translation Lookaside Buffer: רכיב ב-CPU שמשמש בתור Cache לתרגומים האחרונים שנעשו (אותו מבנה כמו הפייג' טייבל: אינדקס פייג' -> אינדקס פריים) - מערכת ההפעלה שומרת רשימה של פריימים פנויים.
- לא לשמור תמיד את כל הפייג'ים בזיכרון. - להוסיף ל-Page Table עמודת Valid Vit (V) עם ביט שמציין האם הדף בזיכרון (1=כן, 0=לא). - מערכת ההפעלה טוענת את הדף לזיכרון רק כשצריך אותו. - אפשר גם לעשות Pre-Paging, כלומר לתת למערכת ההפעלה לנחש אילו דפים התהליך יצטרך ולטעון אותם מראש. יכול להיות טוב אם מנחשים נכון. - מה אם ה-RAM מלא?. כאן נכנסים לתמונה Page Eviction Algorithms.
- בוחרים את העמוד שלא נשתמש בו לזמן הארוך ביותר. - לא פיזבילי במציאות, בפועל אנחנו רק יכולים להעריך את הזמן הנותר.
- לבחור את הקורבן באופן אקראי.
- לשמור רשימה מקושרת ממוינת של הדפים על פי הסדר שהם נטענו לזיכרון, תמיד לבחור את הקורבן להיות הדף הכי זקן. - בעייתי בגלל אנומיליית בלאדי/Belady's Anomaly: - נצפה שככל שיש יותר זיכרון, יהיו פחות Page Faults. בפועל זה לא המצב, ויותר זיכרון גורר יותר Page faults!
באלגוריתמים הבאים, נניח כי יש ב-Page Table שני ביטים נוספים (ואכן יש אותם במעבדים מודרניים בפייג' טייבל עצמו). ה-MMU מנהל אותם: - ביט הרפרנס/Reference bit: נדלק כשניגשים לדף. - הביט המלוכלך/Dirty bit: נדלק כשכותבים לדף.
- באופן מחזורי, מערכת ההפעלה מנקה את ה-Reference bits. - כשיש Page Fault וצריך לעשות Eviction, נבחר פייג' שהרפרנס ביט שלו הוא 0. - משמש כהערכה גסה של LRU.
- נשמור לכל פייג' Timestamp שאומר מתי ניגשו אליו בפעם האחרונה. - כשיש Page Fault וצריך לעשות Eviction, נמצא את הדף הישן ביותר. - זה מוסיף אוברהד משמעותי!
- מארגנים את הפריימים במעגל, עם יד של שעון שמצביעה על אחד מהם. - לכל פייג' יש רפרנס ביט. - ברגע שצריך לעשות Eviction, נבדוק את העמוד שהיד מצביעה עליו ונפעל כך: - אם יש לו 1 ב-reference bit, קבע אותו להיות 0 ותמשיך. - תעשה Evict לראשון שיש לו 0. - אם מפנים לא חוזרים להתחלה אלא ממשיכים מהעמוד הבא.
- מארגנים את הפריימים במעגל, עם יד של שעון שמצביעה על אחד מהם. - לכל פייג' יש רפרנס ביט. וגם שומרים את הזמן האחרון שניגשנו אליו. - ברגע שצריך לעשות Eviction, נבדוק את העמוד שהיד מצביעה עליו ונפעל כך: - אם R=1, קבע R=0, עדכן את זמן השימוש האחרון והמשך. - אם R=0 וההפרש בין זמן השימוש האחרון לזמן הנוכחי קטן מ-k כלשהו, המשך. - אחרת, כלומר אם R=0 וההפרש גדול, תעשה Evict.
- במקום להשתמש בטבלה אחת ענקית, נשתמש במבנה של עץ, כלומר טבלאות שמצביעות לטבלאות אחרות, ואז הטבלאות בעלים הן אלו שיכילו את האינדקס של הפריים. - בדרך כלל נרצה שכל טבלה תמלא בדיוק פריים אחד. כלומר אם גודל של פריים הוא $4KB = 2^12B$, אז הגודל של ה-Offest הוא 12, ואם גודל של פוינטר הוא $4B$ אז כל טבלה תכיל $2^10$ פוינטרים, כלומר אם יש 32 ביט, 10 הביטים השמאליים יהיו לטבלה הראשונה, 10 הביטים האמצעיים לטבלה השנייה ו-12 הביטים שנותרו ל-Offset. - מה שטוב בזה זה שלא חייבים שכל טבלאות הביניים יהיו בזיכרון או אפילו באחסון.
- ממומש כטבלת גיבוב מפייג' לפריים. - יכולות להיות התנגשויות וצריך לטפל בהן עם רשימה מקושרת.
- נועד למקרים בהם הזיכרון ממש קטן. - טבלת דפים אחת לכל התהליכים. - ממפה פריימים לדפים + pid. (האינדקס ברשימה הוא הפריים). - כשרוצים לשלוף דף, מחפשים בכל הרשימה.
מספיק להסתכל על מרחקי הסטאק כדי לחשב ביצועים בשיטת LRU.
ת'ראשינג/Thrashing: תופעה שמתקיימת כאשר יש יותר מדי multiprogramming. ככל שמעלים את כמות התכניות ה-CPU usage עולה ועולה עד שמגיעים לנקודה שהוא יורד בחדות. זה בגלל שעבור כל context switch צריך לעשות המון החלפות פייג'ים וזו פעולה איטית יחסית.
סופרבלוק/Superblock: מבנה נתונים שנמצא בRAM ומכיל רשימה חלקית של הבלוקים שפנויים (באחסון) ושל inodes שפנויים ב-inode table (באחסון).
דרכים לארגן בלוקים:
אפשר גם לעשות inlineing ב-inode ולשמור את התוכן ישר במקום של הפונטרים אם הוא קצר.
טבלת inode table: כל ה-inodes שנמצאים בדיסק.
לסיכום יש שלושה טבלאות שנוגעות לקבצים: 1. בתוך ה-PCB, יש לכל קובץ רשימה של ה-file descriptors של הקבצים הפתוחים שלו. ממפה מ-fd ל-Open File Description Table. (לכל קובץ ה-fd פרטיים כלומר ייתכן ששני קבצים יפתחו קבצים שונים שיקבלו את אותו fd). 2. ה-Open File Description Table: זו טבלה אחת גדולה שמשותפת לכל מערכת ההפעלה, וממפה בין כל קובץ פתוח לפוינטר של ה-inode שלו בטבלת ה-vnode. בנוסף כל entry מכיל reference count של כמות ה-PCB שמצביעים עליו. מכיל גם את המיקום בקובץ. (רלוונטי ל-fork). (יכולים להיות כמה עבור קובץ אחד) 3. טבלת ה-vnode: גם היא משותפת לכל מערכת ההפעלה ומכילה את ה-inodes של הקבצים הפתוחים. (כל קובץ פה יופיע לכל היותר פעם אחת).
Globe
