2014年10月23日 星期四
The Difference Between a Curriculum Vitae (CV) and a Resume
Question: Curriculum Vitae vs. Resume? What is the difference between a curriculum vitae (CV) and a resume?
Answer: The primary differences between a resume and a curriculum vitae (CV) are the length, what is included and what each is used for.
A resume is a one or two page summary of your skills, experience and education. While a resume is brief and concise - no more than a page or two, a curriculum vitae is a longer (at least two pages) and more detailed synopsis.
A curriculum vitae includes a summary of your educational and academic backgrounds as well as teaching and research experience, publications, presentations, awards, honors, affiliations and other details. In Europe, the Middle East, Africa, or Asia, employers may expect to receive a curriculum vitae.
In the United States, a curriculum vitae is used primarily when applying for academic, education, scientific or research positions. It is also applicable when applying for fellowships or grants.Create Resume
Writing a Resume Template
Format CV
Cover Letter
Graduate Resume
2014年10月8日 星期三
17 tips for maintaining a long-term relationship
Have a happy relationship
Long-term relationships have become something of an enigma for many as divorce rates soar and the number of single parents keeps climbing. So here are our top tips on how to maintain a long-term relationship to help keep you and your other half happy within your relationship.
- 1. Base your relationship on friendship
There’s a mutual respect that comes with a friendship that is essential for a successful relationship with anyone – partner or not. Building your relationship on the basis of a friendship can help you learn about them without the added intensity of a relationship. For example, talk about everything, literally. If you’re watching the news together and a controversial story comes up, talk about it! You’ll learn a lot about each other’s moral compass and whether you are compatible as a couple or not.
- 2. Don’t cheat
This sounds obvious but is a surprisingly common pitfall. If you have any respect for your partner and the sanctity of your relationship then don’t play away. Even if your partner can bring themselves to forgive you, they will never forget. It will ultimately eat away at your relationship and the trust will have gone.
- 3. Be spontaneous
When you get comfortable in a relationship, it’s natural to fall into a routine which can become mundane over time. To avoid this, surprise your partner every so often, even if it’s something as daft as a fridge magnet you thought they’d like. The little things count and its gifts like these that show you’re thinking about your partner when you aren’t together.
- 4. Make time
Another obvious one, but if you don’t spend any time together alone as a couple then you’re inevitably going to drift apart. Relationships need intimacy in order to succeed so regular contact is essential. If you don’t see much of your partner and don’t feel like you miss them or need to see them more regularly, then maybe it is time to reassess whether you still have feelings for this person. (This of course excludes long-distance).
- 5. Tell them you care
After you’ve been together for a while, the fact that you care for one another becomes a given. But not verbalising your feelings for your partner could lead to them to think you no longer care for them and become disillusioned with the entire relationship. So make sure they know how strongly you feel.
- 6. Don’t hold back
This follows on from the last point, don’t be embarrassed to show intimacy for your partner in public. Whether it’s when you’re out with friends or in a room full of strangers, make sure you aren’t neglecting your partner because ‘people might see’. If anything, showing intimacy for them in front of others solidifies your relationship by showing you don’t care what others think and you aren’t embarrassed to be with them.
- 7. Keep your individuality
Brangelina, Bennifer, and TomKat are just a few of the celebrity power couples to have been given a nickname by the press to define their relationship. Whilst there is nothing wrong with becoming an official ‘couple’ in this way, it is important to maintain your individuality as a person. Make sure you dedicate yourself some ‘me’ time, even if it’s just having a relaxing pampering session or half-an-hour chilling in the bath reading your favourite magazine. Your relationship will do better for it.
- 8. Make time for your friends
Making time for your friends is an extension of the last tip. It’s hard not to spend 24/7 with someone you deeply care about, especially if you live together, but making time for friends outside of your relationship is essential for inner happiness for both you and your partner. One evening every week where you meet up with friends for a girly catch up or a meal out will give your relationship the space it needs as well as giving your other half the opportunity to catch up with their friends or finish that book they’ve been reading for ages.
- 9. Make date nights
Spending time together in a ‘date’ scenario will remind you of the early days of your relationship and keep that spark alive. An occasional shopping trip, night at the cinema, or meal out will bring back all the feelings you had in the beginning and bring you closer as a couple.
- 10. Set goals
Setting mutual goals together will enable you to understand where your relationship is heading. Sitting down together and talking about the future can be a daunting task, especially if you’re worried you might not want the same things. But explaining what you want and where you want to be in 5 or 10 years will help your partner understand what you want from them in the relationship and the longevity of it.
- 11. Experience new things together
Going travelling, trying new things in the bedroom, and even moving away to university are experiences you can share together. This can be an a bonding experience and can make or break relationships but without giving these things a go how will you know if your partner is truly the right person for you?
- 12. Don’t wear rose tinted spectacles
Glazing over issues you have as a couple is not a healthy way to deal with them. These things never stay buried and will eventually come back to bite you later, which could do more damage than if you had tackled the problem head on. No matter how small or large the issue is, it is best to air your feelings straight away so that you can deal with it together and give your relationship the chance to recover and get stronger from it.
- 13. Don’t be afraid to be vulnerable
Bottling up feelings never did anyone any good, so if you have had an emotional experience, sharing it with your partner can be a great way to bond. Showing your vulnerable side will make them want to care and protect you, strengthening the romantic side to your relationship.
- 14. Remember why you got together in the first place
There are moments in every relationship where you come to the point of despair, often during an intense argument. But when the feelings of ‘why do I even bother’ arise, remembering why you initially got with your partner and all the happy moments you’ve had together can lift this feeling and help you realise that all relationships have their ups and downs, it’s how you deal with them that matters.
- 15. Don’t forget to listen
During an argument it’s easy to see red and scream obscenities at each other. But calming down and listening to each other rather than having a screaming match will help you resolve the problem much quicker.
- 16. Appreciate the little things
Whether it’s doing the washing up, cooking your tea or surprising you with flowers, learning to appreciate the small gestures your partner makes to show that they care can only be beneficial. After all, if you don’t give any response at all they might stop bothering!
- 17. Don’t get sloppy
Maintaining your relationship is a two way street. Making sure you keep your hygiene and grooming habits to the same standard they were at the start of your relationship, should be another obvious one but it's surprisingly common for standards to slip. Remember how in the beginning you would take forever to get ready for your dates? While your partner might not expect the same level of dedication every day, they will at least expect you to make a bit of effort or they will lose interest. That person they fell for shouldn’t disappear over time. Making an effort with your appearance shows you want to remain attractive to them and your commitment to the relationship as a whole.
By Sophie Atherton @SophAthers
Read more: http://www.femalefirst.co.uk/relationships/17-tips-for-maintaining-a-long-term-relationship-286076.html#ixzz3FXXrxrc2
2014年10月6日 星期一
[心得] 第一次跨考資工所就上手
1.前言：
因為沒有補習，去年要開始準備的時候完全不知道怎樣下手，那時候觀看版上心得得到很多幫助，希望我的心得也可以給以後想考且不打算補習的同學們，指引一條準備的路。
2.背景：
熱愛數學跟資工的應屆應數系學生，系排約20名左右，沒有嘗試推甄，然後沒有補習。
3.今年成績：
今年我報了七間，最後有去考六間。
台大資工 正取 數學７９ 計系５７.５ 資演７７
總分 ２１６.３
台大電機 缺考
交大資工 正取 數學４５ 計系７１ 資演７７
總分 １９３
清華資工 正取 計科７３ 計系８６
總分 １５９
成功資工 正取 數學５５ 計系５７ 資演７９ 總分 １９１
中央資工 正取 數學５６ 計系８４ 資演６９ 總分 ２０９
中興資工 正取 數學９３ 概論７４ 總分 １６７
4.各科準備方法與參考書目：
一、線性代數：
參考書目有黃子嘉三本，Friedberg 線代原文書以及線代啟示錄(網頁)
因為這科在大二時學的算是不錯，且大三還有修線代三，所以在整個準備過程中沒有花太多時間，這科ＣＰ值是我認為全部科目裡面最高且沒有之一，千萬不要學我都不怎麼念，看我考試成績便知，數學很淒慘，建議花多一點時間，可以拿到跟所花時間相對應的分數，題目雖然靈活但是只要掌握關鍵觀念，非常容易把握，然後今年各校的數學題目都大變，明年考生可能可以參考今年的。 然後，我題目只有做完黃子嘉全部是非，還有１／３的ＥＡＳＹ題目而已，Jordan form 我是全部放棄，個人覺得不會考，要不要讀見仁見智。
二、離散數學：
參考書目有黃子嘉三本，Rosen 離散原文書
很多人都說這科ＣＰ很高，我是覺得還好，因為除了基本的題目，其他都是考感覺的如果當下沒ＦＵ，就很可能無法下筆，然後遞迴跟樹還有圖論超級重要，其他就考反應。這科，我也沒有花很多時間，因為我在大二升大三的暑假，無聊就把原文書看過一遍，之後開始準備研究所的時候衝很快，然後建議題目多作一點，比較有機會觸類旁通。 題目做完黃子嘉第一章到代數，後面全部題目，且很多都做兩三次，其他像有限狀態機，波利雅，個人認為可以不用讀。
三、計算機組織
參考書目有張凡兩本，Patterson 白算盤
個人覺得這科ＣＰ也是相當之高，花在上面的時間絕對可以從分數看出來，這科大主軸就是那些，基本常識、效能分析、處理器、記憶體架構等，全部都沒有很難，然後大部分都不用背，計算機既然是人設計出來的，每一個部分都有其為什麼，只要想通很多都很順理成章，然後這科有時候數字可能有點醜，要耐心的算完。 題目做完白算盤後面題目，以及張凡後面全部題目，然後張凡那本做兩三遍。multicycle 個人認為不會考，可以放棄，不過怕死還是看一下比較好。
四、作業系統：
參考書目有恐龍，跟人家印的洪逸筆記，Google，洪逸題庫94~99
個人最喜歡ＯＳ，不過這科ＣＰ不高，東西很多很雜，雖然跟計組一樣，可以用理解的，不過實在太多，相當容易忘，很多都是忘了讀，讀了再忘這樣，然後可以配合計組一起讀，還有恐龍的英文有點難，很多都要看很多遍才懂再說什麼，然後遇到沒看過的，都可以查恐龍的 index 基本上都會有。這科就是基本拿到，剩下就儘量看恐龍吧。 題目做完恐龍到十二章後面的習題，洪逸題目94~99兩三遍。
五、資料結構：
參考書目有印來的洪逸筆記，Google，洪逸題庫94~99。
強烈建議這科，讀的時候可以把大部分的資料結構都用程式碼打過一遍，會非常有感覺，這科筆記很少，大概三、四天都看就能看一輪，然後重點就是樹、排序，還有時間複雜度，第一遍讀的時候就看完瞭解再說什麼，就跑去打程式，比方說看完 heapsort 確認理解後，就用程式碼打出來，一定會卡住，這時候就會發現，原來之前覺得理所當然的地方，事實上並沒有這麼理所當然，多幾次就會很有感覺，第二第三遍，就可以很快。 題目做完洪逸題庫94~99兩三遍。
六、演算法：
參考書目 Cormen 的 Introduction to Algorithms。
看到原文書很厚可能會覺得這科很難讀，事實上讀這科有一些小技巧，通常原文書再講一個演算法的時候，會先花兩三頁，講解這個問題，以及解決這個問題可以帶來的好處，比方說最小生成樹，他就會說這個問題是要求出最小連通成本，解決完可以讓建構一個網路的成本最低等，之後會再有兩三頁講如何解這個問題，Kruskal、Prim 等，再來會花二十到三十頁證明這些演算法的正確性，同樣以 MST 為例子，他就會證明一個 CUT 中最小的 edge 一定是 safe 的，到此 MST 結束。從中有沒有發現什麼問題？沒錯，碩士班入學考，基本上不會考演算法的正確性證明，所以，讀這本原文書的時候，只要看問題，以及如何解決的方法，非常的快速，累積多了之後，很多題目都可以很快反應，比方說看到 DAG 就馬上連想到拓樸排序，再連想到拓樸排序是用 DFS 等，很快就可以解決一個問題。然後 Cormen 的英文算是非常平易近人，很容易讀懂。 題目只有做完 Cormen 有答案的題目。
最後分享一下我認為各科目的ＣＰ排序：
線代＝計組 ＞ 離散＝資結 ＞ ＯＳ＝演算
5.時間規劃：
我認為實力不只是開始衝刺之後累積的，所以我把我認為對我實力都有影響的都打出來，希望可以參考看看。 前年的７月～８月：
離散原文書第一遍，基本上這段時間並不是再準備研究所，就只是讀爽的，所以題目做不多，就思考一些觀念跟例題而已。
三上：
這段時間，因為我跑去修資工的資料結構，所以只要看到一個新的結構，回來就自己嘗試把他寫出來，算出培養一點資料結構的感覺。
三下：
讀黃子嘉的線性代數，基本上很悠閒，就一天大概翻一小時多一點。三下結束時，剛好看完上跟下。
升四上暑假（７～８月）：
大概從這時候開始衝刺，一天大概讀四小時左右，暑假結束時，讀完黃子嘉離散資料結構筆記，恐龍以及白算盤。
９月：
補上個月剩下一點的離散跟ＯＳ還有看一下線代，然後第一次做考古題被慘電，在九月末便去買張凡的計組來讀，一天也是讀四小時左右。
１０月：
衝張凡的計組，然後資料結構洪逸筆記再看一次，恐龍加減看，參雜一點離散跟 線代，時間開始變多，一天大概五小時左右。
１１月：
這時後去買洪逸的ＯＳ跟資結題庫，這個月就寫完這兩本題庫，然後張凡再衝一遍，然後參雜一點離散。前半月大概也是一天五小時，後半月一天大概７小時左右。
１２月：
再把ＯＳ跟資結題庫再看一次，離散代數再看一次。開始寫考古題，時間開始變 少一天又回到約略５小時。
１月：
一天只寫一份考古題加上把不熟的地方再看熟，所以一天大概只有讀４小時。一月底考古題寫完後，翻出張凡，ＯＳ跟資結的筆記開始再看一遍。
２月：
基本上這時候我已經幾乎沒讀書了，就朋友問問題回一下，版上有問題回一下，然後想到什麼比較沒印象就翻一下，一天大概２小時。最後考試前把清交央的考古在看過一遍就上考場了。
然後我有用ＡＰＰ記錄讀書時間，可以參考：http://ppt.cc/VuIN
6.Ｑ＆Ａ：
一、要不要補習？
Ａ：我認為不用，讀書還是再自己努力，而且不補習有更多的時間可以唸書不過建議還是要弄到補習班的書，畢竟很多都整理過，讀起來相對比較快。
二、要不要看原文書？ Ａ：要，雖然看原文書，可能很累，而且讀完可能還是都不太會，不過那是一個感覺，讀原文書就是培養 sense 可能現在看完會覺得很亂都沒有架構，可是可能之後看了某段，就突然通了，或是原文書會有前呼後應，比較能夠觸類旁通，尤其是ＯＳ跟演算法的原文書特別明顯。
三、一天是不是都要念很久？
Ａ：我覺得看個人，一開始看心得文，每一篇都是一天Ｎ小時，就覺得很恐怖，其實只要依照自己的進度穩紮穩打就可以，像我一天平均大概只有念４小時，不過要確定自己真的有讀進去，而不是有點混過去。
四、考古題重要性？
Ａ：我覺得考古題真的有其重要性，比方說今年清華就出了一題跟１００年一模一樣的題目，然後我考古題只有寫１００～１０２，因為更早的題庫都寫過好幾次了，再寫一遍感覺沒什麼參考價值。
7.結語：
Do something for the future.
有問題歡迎討論。 : )
2014年10月3日 星期五
CS411/511. Operating Systems
CS411/511. Operating Systems
Homework 1 - Solutions
1.1. What are the three main purposes of an operating system?
To provide a convenient environment for users to execute programs on computer hardware.
To allocate, fairly and efficiently, the computer resources needed to execute the program safely (without adversely affecting other users or the OS itself).
To provide a foundation for evolution to future services, while still supporting existing services.Note that "convenience," "efficiency," etc. are not acceptable answers, since they don't explain "convenient/efficient for whom to do what."
1.4. In a multiprogramming and time-sharing environment, several users share the system simultaneously. This siguation can result in various security problems.
(a) What are two such problems?
(b) Can we ensure the same degree of secutiry in a time-shared machine as we have in a dedicated machine? Explain your answer.
Stealing or copying a user's files; writing over another program's (belonging to another user or to the OS) area in memory; using system resources (CPU, disk space) without proper accounting; causing the printer to mix output by sending data while some other user's file is printing.
Probably not, since any protection scheme devised by a human can also be broken -- and the more complex the scheme is, the more difficult it is to be confident of its correct implementation.
1.6. What are the main differences between operating systems for mainframe computers and personal computers?
PC OS's are not concerned with fair use or maximal use of computer resources. Instead, they try to optimize the usefulness of the computer for an individual user, usually at the expense of overall efficiency. Mainframe OS's need more complex scheduling and I/O algortihms to keep the various system components efficiently occupied.1.7. Define the essential properties of the following types of operating systems:BatchInteractiveTime-sharingReal-timeDistributed
Batch: Jobs with similar needs are batched together and run through the computer as a group, by an operator or automatic job sequencer. Performance is increased by attempting to keep CPU and I/O devices busy at all times through buffering, off-line operation, spooling, and multiprogramming.
Interactive: Composed of many short transactions with input and output read/written on the screen; the results and timing of the next transaction may be unpredictable. Note that a purely interactive system (no time-sharing) only has one user; e.g., a PC).
Time-sharing: Uses CPU scheduling and multiprogramming to provide economical interactive use of a system. The CPU switches rapidly from one user to another.
Real-time: The system must respond to inputs/commands within a fixed amount of time to ensure correct performance. Input is typically read from sensors.
Distributed: Divides computation up among several computers. The computers do not share memory or a clock; they communicate with each other over communication lines (e.g., high-speed bus, telephone line).
1.10. Describe the differences between symmetric and asymmetric multiprocessing. What are three advantages and one disadvantage of multiprocessor systems?
Symmetric processing treats all processors as equals; I/O can be processed on any of them. Asymmetric processingdesignates one CPU as the master, which is the only one capable of performing I/O; the master distributes computational work among the other CPUs.
advantages: Multiprocessor systems can save money, by sharing power supplies, housings, and peripherals. Can execute programs more quickly and can have increased reliability.
disadvantages: Multiprocessor systems are more complex in both hardware and software. Additional CPU cycles are required to manage the cooperation, so per-CPU efficiency goes down.
2.3. What are the differences between a trap and an interrupt? What is the use of each function?
An interrupt is a hardware-generated signal that changes the flow within the system. A trap is a software-generated interrupt.
An interrupt can be used to signal the completion of I/O so thatthe CPU doesn't have to spend cycles polling the device. A trap can be used to catch arithmetic errors or to call system routines.
2.5. Which of the following instructions should be privileged?Set value of timerRead the clockClear memoryTurn off interruptsSwitch from user to monitor mode
Should be privileged.
Doesn't need to be.
Should be privileged.
Should be privileged.
Should be privileged.
Answer the following questions about policies and mechanisms:
(a) What is an advantage of separating policy from mechanism in designing any piece of software (including OSs)?
(b) Give three examples of software policies versus mechanisms.
Clean separation makes systems easier to modify and port. Another answer: Clearer thinking allowing you to differentiate the desired properties of a solution from the best solution you've thought of so far. Another answer: Mechanisms can be changed without affecting the policy.
Hint: You should always be able to name at least 2 different mechanisms that could be used to implement a so-called policy.Some examples:
policy: share CPU resource fairly among processes. mechanism: timer interrupts. alternate mechanism: enforce a limit on how long programs can be.
policy: some processes are more important or more critical than others. mechanism: base scheduling upon process priority. alternate mechanism: force processes to use "nice()" values.
policy: data values must be kept in order of priority. mechanism: heap. alternate mechanism: priority-sorted vector.
CS411/511. Operating Systems
Homework 2 - Solutions
Chapter 4: Review Questions 4.2, 4.6, 4.7
4.2. Describe the differences among short-term, medium-term, and long-term scheduling.
Short-term (CPU scheduler): selects a process from those that are in memory and ready to execute, and and allocates the CPU to it.
Medium-term (memory manager): selects processes from the ready or blocked queue and removes them from memory, then reinstates them later to continue running.
Long-term (job scheduler): determines which jobs are brought into the system for processing.
4.6. Describe the actions taken by a kernel to switch context(a) Among threads
(b) Among processes
The thread context (registers, PC, and stack, plus accounting info if appropriate) must be saved and another thread's context must be loaded.
The same as (a), except that the memory and resource info must also be stored and that for the next process must be loaded.
4.7. What are the differences between user-level threads and kernel-supported threads? Under what circumstances is one type "better" than the other?
User-level threads have no kernel support, so they are very inexpensive to create, destroy, and switch among. Kernel-supported threads are more expensive because system calls are needed to create and destroy them and the kernel must schedule them.
In most current systems with threads, when a user-level thread blocks, the whole process blocks. Since kernel-supported threads are scheduled independently, they can block individually; that is, the fact that one blocks does not hold up the others.
Chapter 5
5.4. Suppose that the following processes arrive for execution at the times indicated. Each process will run the listed amount of time. In answering the questions, use nonpreemptive scheduling and base all decisions on the information you have at the time the decision must be made. Process Arrival Time Burst Time ------------------------------------------------------ P1 0.0 8 P2 0.4 4 P3 1.0 1
(a) What is the average turnaround time for these processes with the FCFS scheduling algorithm?
(b) What is the average turnaround time for these processes with the SJF scheduling algorithm?
(c) The SJF algorithm is supposed to improve performance, but notice that we chose to run process P1 at time 0 because we did not know that two shorter processes would arrive soon. Compute what the average turnaround time will be if the CPU is left idle for the first 1 unit and then SJF scheduling is used. Remember that processes P1 and P2 are waiting during this idle time, so their waiting time may increase. This algorithm could be known as future-knowledge scheduling.
(a) 10.53
(b) 9.53
(c) 6.86Remember that turnaround time is completion time minus arrival time, so you have to subtract the arrival times to compute the turnaround. FCFS is 11 if you forget to subtract arrival time.
5.6. What advantage is there in having different time-quantum sizes on different levels of a multilevel queueing system?
Processes which need more frequent servicing, such as interactive processes, can be in a queue with a small q. Processes that are computationally intensive can be in a queue with a larger quantum, requiring fewer context switches to complete the processing, making more efficient use of the CPU.
5.7. Consider the following preemptive priority-scheduling algorithm based on dynamically changing priorities. Larger priority numbers imply higher priority. When a process is waiting for the CPU (in the ready queue, but not running), its priority changes at a rate alpha; when it is running, the priority changes at a rate beta. All processes are given a priority of 0 when they enter the ready queue for the first time. The parameters alpha and beta can be set to give many different scheduling algorithms.(a) What is the algorithm that results from beta > alpha > 0?
(b) What is the algorithm that results from alpha < beta < 0?
(a) Since processes start at 0, any processes that have been in the system (either running or waiting) have higher priority. Therefore, new processes go to the back of the queue. When a process runs, its priority keeps increasing at the rate of beta, which is more of an increase than for the processes in the ready queue. Therefore, every time the process has timerrunout, it goes to the front of the ready queue and gets dispatched again. This is the equivalent of FCFS.
(b) This time, any new processes entering the system have higher priority than any old ones, since priority starts at zero and then becomes negative when the process waits or runs. New processes go in at the front of the queue. When a process runs or waits, its priority decreases, with the waiting processes decreasing faster than the running process. This is a LIFO (last-in-first-out) algorithm. The question didn't promise that this would be an algorithm you would want to use in real life.
Other Question. Take the example that you just used for Question 5.4, and apply it to the following situations.(a) Calculate the average turnaround time for a Round-Robin algorithm with q set at 2. Ignore the effects of context-switching time.
(b) Calculate the average turnaround time for the same algorithm and q, taking into effect the fact that each context switch costs .5 units of time.
(c) Suppose that a fourth process, P4, enters the system at time 7.6 and needs 6 units of CPU time. Also suppose that P2 and P3 are interactive, but P1 and P4 are batch.
A multilevel queue (but not a multilevel feedback queue) is in effect. The first queue is for interactive processes only, and has a qof 1. The second queue is for batch processes, which get up to 4 units each time they are in the CPU. Processes are dispatched as follows: 2 processes are dispatched from the interactive queue, followed by 1 process from the batch queue, etc.
Calculate the average turnaround time.
(a)8.53
(b)10.53 (I didn't count the final context switch after a process leaves the CPU for the last time)
(c)11 (They run in the order P1-P2-P3-P1-P2-P4-P2-P4-P2)
CS411/511. Operating Systems
Homework 3 - Solutions
Chapter 8: Review Questions 8.4, 8.10, 8.11, 8.16511 students only: 8.17
8.4. When a process is rolled out of memory, it loses its ability to use the CPU (at least for a while). Describe another situation where a process loses its ability to use the CPU, but where the process does not get rolled out.
When an interrupt occurs the process loses the CPU, but regains it as soon as the handler completes. The process is never rolled out of memory.
Note that when timerrunout occurs, the process is returned to the ready queue, and it may later be rolled out of memory. When the process blocs, it is moved to a waiting queue, where it may also be rolled out at some point.8.10. Consider a paging system with the page table stored in memory.(a) If a memory reference takes 200 nanoseconds, how long does a paged memory reference take?
(b) If we add associative registers, and 75% of all page-table references are found in the associative registers, what is the effective memory reference time? (Assume that finding a page-table entry in the associative registers takes zero time, if the entry is there.)
400 nanoseconds. 200 ns to access the page table plus 200 ns to access the word in memory.
250 nanoseconds. 75% of the time it's 200 ns, and the other 25% of the time it's 400ns, so the equation is: e.a. = (.75*200)+(.25*400)
Try this, too: What if the time to access the associative registers is actually 2 ns -- how does your answer change? e.a. = 2 + (.75*200)+(.25*400)
Remember that you *always* have to perform the TLB lookup, whether or not the page is found there.8.11. What is the effect of allowing two entires in a page table to point to the same page frame in memory? Explain how this effect could be used to decrease the amount of time needed to copy a large amount of memory from one place to another. What would the effect of updating some byte in the one page be on the other page?
This allows users to shared code or data. If the code is reentrant, much memory space can be saved through the shared use of large programs (e.g., text editors, compilers, database systems). "Copying" large amounts of memory could be effected by having different page tables point to the same memory location.
However, sharing of non-reentrant code or data means that any user having access to the code can modify it and these modifications would be reflected in the other user's "copy."8.16. Consider the following segment table: Segment Base Length 0 219 600 1 2300 14 2 90 100 3 1327 580 4 1952 96
What are the physical addressed for the following logical addresses?(a) 0,430(b) 1,10(c) 2,500(d) 3,400(e) 4,112
(a) 219 + 430 = 649
(b) 2300 + 10 = 2310
(c) illegal reference; traps to operating system
(d) 1327 + 400 = 1727
(e) illegal reference; traps to operating system8.17. Consider the Intel address translation scheme shown in Figure 8.28(a) Describe all the steps that are taken by the Intel 80386 in translating a logical address into a physical address.(b) What are the advantages to the OS of hardware that provides such complicated memory translation?(c) Are there any disadvantages to this address translation system?
(a) The selector is an index into the segment descriptor table. The segment descriptor result plus the original offset is used to produce a linear address with dir/page/offset. The dir is an index into a page directory; the entry from this directory selects the page table, and the page field is an index into that page table. The entry from the page table, plus the offset, is the physical address.
(b) Such a page translation mechanism offers the flexibility to allow most OS's to implement their memory scheme in hardware, instead of having to implement some parts in hardware and some in software. Because it can be done in hardware, it is more efficient -- and the kernel is simpler.
(c) Address translation can take longer due to the multiple table lookups it can involve. Caches help, but there will still be cache misses.
Chapter 9: Review Questions 9.3, 9.11, 9.18511 students only: 9.5, 22.8
9.3. A certain computer provides its users with a virtual memory space of 2**32 bytes. The computer has 2**18 bytes of physical memory. The virtual memory is implemented by paging, and the page size is 4K bytes. A user process generated the virtual address 11123456. Explain how the system establishes the corresponding physical location. Distinguish between software and hardware operations.
The virtual address in binary form is 0001 0001 0001 0010 0011 0100 0101 0110
Since the page size is 2**12, the page table size is 2**20. Therefore, the low-order 12 bits (0100 0101 0110) are used as the displacement into the page, while the remaining 20 bits (0001 0001 0001 0010 0011) are used as the displacement in the page table.
Consider the operations that are needed (a) for DAT, and (b) for page fault servicing. All the DAT operations are carried out in hardware. But of the list of operations for page faults, on pp. 297-298, *at*least* steps 2, 4, 5, 6, 8, 10, and 12 involve software operations.9.11. Consider the following page reference string: 1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3, 7, 6, 3, 2, 1, 2, 3, 6
How many page faults would occur for the following replacement algorithms, assuming one, two, three, four, five, size, or seven frames? Remember that all frames are initially empty, so your first unique pages will all cost one fault each.LRU replacementFIFO replacementOptimal replacement
# Frames LRU FIFO Optimal
1 20 20 20
2 18 18 15
3 15 16 11
4 10 14 8
5 8 10 7
6 7 10 7
7 7 7 7
9.17 (not in the assignement, but I'll leave the solution here).
Consider a demand-paging system with a paging disk that has an average access and transfer time of 20 ms. Addresses are translated through a page table in main memory, with an access time of 1 us per memory access. Thus, each memory reference through the page table takes two accesses. To improve this time, we have added an associative memory that reduces access time to one memory reference, if the page-table entry is in the associative memory.
Assume that 80% of the accesses are in the associative memory, and that, of the remaining, 10% (or 2% of the total) cause page faults. What is the effective memory access time? e.a. = 1 us + (0.20 * 1 us) + (0.02 * 20,000 us) = 401.2 us
Or, if you prefer e.a. = (0.80 * 1 us) + (0.18 * 2 us) + (0.02 * 20,002 us) = .8 us + .36 us + 400.04 us = 401.2 us
9.18. Consider a demand-paged computer system where the degree
of multi-programming is currently fixed at four. The system
was recently measureed to determine utilization of CPU and the
paging disk. The results are one of the following alternatives.
For each case, what is happening? Can the degree of
multiprogramming be increased to increase the CPU utilization?
Is the paging helping?
a. CPU utilization 13 percent; disk utilization 97 percent
System is thrashing. The degree of multiprogramming should be
decreased. Paging is not helping.
b. CPU utilization 87 percent; disk utilization 3 percent
System is well utilized, CPU is being kept busy most of the time.
The degree of multiprogramming probably should stay the same,
increasing it may lead to thrashing. Paging is helping.
c. CPU utilization 13 percent; disk utilization 3 percent
System is under utilized, the CPU is not getting enough work.
The degree of multiprogramming should be increased. Paging is
not really helping or hurting.
9.5. Suppose we have a demand-paged memory. The page table is held in registers. It takes 8 ms to service a page fault if an empty page is available or the replaced page is not modified, and 20 m if the replaced page is modified. Memory access time is 100 ns.
Assume that the page to be replaced is modified 70% of the time. What is the maximum acceptable page-fault rate for an effective access time of no more than 200 ns? [note: everything shown in microseconds] 0.2 us = ((1-P) * 0.1 us) + (0.3P * 8,000 us) + (0.7P * 20,000 us) 0.1 = -01.P + 2,400P + 14,000P 0.1 ~ 16,400 P P ~ 0.000006
22.8. What are three advantages of dynamic (shared) linkage of libraries, compared to static linkage? What are two cases where static linkage is preferable?
The primary advantages are that they reduce the memory and disk space used by a system, and they enhance maintainability. (You should be able to describe in detail why this is so.) Other advantages are the fact that a program that uses shared libraries can often be adapted for other purposes simply by replacing one or more of its libraries (e.g., substituting a debugging library for the normal one in order to trace a problem in an application). Shared libraries also allow program binaries to be linked against commercial, proprietary library code without actually including any of that code in the program's final executable file -- so it's may be possible to distribute code to a third party without having to incur extra licensing charges.
Static linkage is more appropriate for "system administration rescue" situations, such as if a sysadmin makes a mistake while installing a new library that causes it to be corrupted. Therefore, it is common to provide a set of basic "rescue utilities" that are statically linked, so that the fault can be corrected without having to rely on shared libraries. Since dynamic linking adds to the execution time, there may be performance reasons for linking the libraries statically. Also, it's easier to distribute an executable file that is complete (i.e., statically linked) rather than having to count on the recipient having the appropriate shared librares.CS411/511. Operating Systems
Homework 4 - Solutions
Chapter 6: Review Questions 6.1, 6.4, 6.18511 students only: 6.19
6.1.
Busy waiting: A process is waiting for an event to occur and it does so by executing instructions.
Other types of waiting: A process is waiting for an event to occur in some waiting queue (e.g., I/O semaphore) and it does so without having the CPU assigned to it.
Busy waiting cannot be avoided altogether (see p. 170).
6.4.Note that this is the same principle as Dekker's Algorithm, which we studied in class. It was a slightly earlier version, and therefore is more complicated than it really needs to be.
To prove that this algorithm is correct, we need to show that mutual exclusion is preserved, the progress requirement is satisfied, and the bounded-waiting requirement is met.
To prove mutual exclusion, we note that each P enters its critical section only if flag[j]!=in-cs for all other processes. Since each process is the only one that can set its own flag value, and since each process waits to examine the other processes' flags until it has set its own flag to in-cs, it can't be possible for two processes not to know that each other's flag is set. Therefore, it's not possible for two processes to be in their critical sections at the same time.
To prove progress, we note that the turn value can only be modified when a process is just about to enter its critical section, or has just completed its critical section. The turn value remains constant whenever there is no process executing/leaving its critical section. If other processes want to enter their critical sections, one will always be able to (the "first" one in the cyclic ordering [turn, turn+1, ... n-1, 0, ... turn-1]).
To prove bounded waiting, we note that whenever a process leaves its critical section, it checks to see if any other processes want to enter their critical sections. If so, it always designates which one will go next -- the "first" one in the cyclic ordering. This means that any process wanting to enter its critical section will do so within n-1 turns.
6.18. Note that the authors are referring to "cost" very generally (as in cost/benefit analysis), rather than specifically to "price."
Volatile storage fails when there is a power failure. Cache, main memory, and registers require a steady power source; when the system crashes and this source is interrupted, the contents are lost. Access is very fast.
Non-volatile storage retains its content despite power failures. For example, disk and CDROM survive anything other than demagnetization or hardware/head crashes (and less likely things like fire, immersion in water, etc.). Access is much slower.
Stable storage theoretically survives any type of failure. It can only be approximated through techniques such as mirroring. Access is certainly slower than volatile, and possibly slower than non-volatile storage.
6.19. If there is no checkpointing, the entire log must be searched after a crash, and all transactions "redone" from the log. If checkpointing is used, most of the log can be discarded. Since checkpoints are very expensive, how often they should be taken depends upon how reliable the system is. The more reliable the system, the less often a checkpoint should be taken.
When no failure occurs, the cost of checkpointing is "pure overhead" and can degrade performance if checkpointing is done frequently. When a system crash occurs, recovery time is proportional to the number of transactions since the last checkpoint. Assuming that a disk crash means the checkpoint file has been lost, recovery will involve a full rollback and re-doing of all transactions in the log.
Chapter 7: Review Questions 7.4, 7.6, 7.8, 7.13
(hint for 7.4(b): this is what drivers are really supposed to do)511 students only: 7.14
7.4. Note that each section of the street (including each intersection) is considered to be a "resource."
Mutual exclusion: only one vehicle on a section of the street
Hold and wait: each vehicle is occupying a section of the street and is waiting to move to the next section
No preemption: a section of a street that is occupied by a vehicle cannot be taken away from the vehicle unless the car moves into the next section
Circular wait: each vehicle is waiting for the next vehicle in front of it to moveTo keep deadlocks from occurring, allow a vehicle to cross an intersection only if it is assured that the vehicle will not have to stop at the intersection.
7.6.
(a) anytime
(b) only if MAX demand of each process does not exceed total number of available resources, and the system remains in a safe state.
(c) only if MAX demand of each process does not exceed total number of available resources, and the system remains in a safe state.
(d) anytime
(e) anytime
(f) anytime
7.8. Suppose the system is deadlocked. This implies that each process is holding one resource and is waiting for one more. Since there are three processes and four resources, one process must be able to obtain two resources. This process requires no more resources, and therefore it will terminate, releasing its resources. This in turn frees sufficient resources for the other processes to complete, one at a time.
7.13.
(a) Since NEED=MAX-ALLOC, the content of NEED is as follows
A B C D
0 0 0 0
0 7 5 0
1 0 0 2
0 0 2 0
0 6 4 2
(b)Yes, the sequence [P0, P2, P1, P3, P4] satisfies the safety requirement.
(c)Yes. The request does not exceed either Available or Max. Further the new system state, which is
Alloc Max Need
P0 0 0 1 2 0 0 1 2 0 0 0 0
P1 1 4 2 0 1 7 5 0 0 3 3 0
P2 1 3 5 4 2 3 5 6 1 0 0 2
P3 0 6 3 2 0 6 5 2 0 0 2 0
P4 0 0 1 4 0 6 5 6 0 6 4 2
is safe, as demonstrated by the sequence [P0, P2, P1, P3, P4].
7.14.
(a) Deadlock cannot occur because preemption exists. That is, the criterion of "no preemption" has been prevented.
(b) Yes. A process may never acquire all the resources it needs, if they are continuously preempted by a series of requests such as those of process C.
Chapters 22-23: 511 students only: 22.6, 23.11
22.6.
Advantages: The primary impact of disallowing paging of kernel memory is that the non-preemptibility of the kernel is preserved. (Any process taking a page fault, whether in kernel mode or in user mode, risks being preempted while the required data is paged in from disk.) Because the kernel is guaranteed not to be preempted, locking requirements to protect the integrity of its primary data structures are also greatly simplified.
Disadvantages: It imposes constraints on the amount of memory that the kernel can use, since it is unreasonable to keep very large data structures in non-pageable memory (that memory cannot be used for anything else). Two disadvantages that stem from this are:
The kernel must prune back many of its internal data structures manually, since it can't rely on virtual memory mechanisms to keep physical memory usage under control.
It is infeasible to implement features requiring very large amounts of memory in the kernel (such as the /tmp-filesystem, a fast virtual-memory based filesystem found in some UNIX systems).
Note that the complexity of managing page faults while running kernel code is not an issue. The Linux kernel code is already able to deal with page faults (which can occur in a system call whose arguments reference user memory, which may be paged out on disk).
23.11. A process in NT is limited to 2 GB address space for data. The two-stage process allows the access of much larger datasets, by reserving space in the process's address space first, and then committing the storage to a memory-mapped file. An application can thus "window" through a large database (by changing the committed section) without exceeding process quotas or utilizing a huge amount of physical memory.
CS411/511. Operating Systems
Homework 5 - Solutions
12.1.
advantages: Bugs are less likely to cause an operating system crash. Performance can be improved by utilizing dedicated hardware and hard-coded algorithms. The kernel is simplified by moving algorithms out of it.
disadvantages: Bugs are harder to fix - a new firmware version or new hardware is needed; improving algorithms likewise require a hardware update rather than just kernel or device driver update. Embedded algorithms could conflict with OS's priorities or with application's use of the device, causing decreased performance. Testing is harder, since the components are autonomous and each device may behave differently.
12.2.
(a) mouse: Buffering may be needed to record mouse movement during times when higher-priority operations are taking place. Spooling and caching are inappropriate. Interrupt-driven I/O is most appropriate.
(b) tape drive: Buffering may be needed to manage throughput difference between the tape drive and the source or destination of the I/O. Caching can be used to hold copies of data that resides on the tape, for faster access. Spooling could be used to stage data to the device when multiple users desire to read from or write to it. Interrupt-driven I/O is likely to yield the best performance.
(c) disk: Buffering can be used to hold data while in transit from user space to the disk, and vice versa. Caching can be used to hold disk-resident data for improved performance. Spooling is not necessary because disks are shared-access devices. Interrupt-driven I/O is always good for devices -- such as disks -- that transfer data at relatively slow rates.
(d) graphics card: Buffering may be needed to control multiple access and for performance (double-buffering can be used to hold the next screen image while displaying the current one). Caching and spooling are not necessary due to the fast and shared-access nature of the device. Polling and interrupts are only useful for input and for I/O completion detection, neither of which is needed for a memory-mapped device.
12.4.
Generally, blocking I/O is appropriate when the process will only be waiting for one specific event. Examples include a disk, tape, or keyboard read by an application program.
Non-blocking I/O is particularly useful when I/O may come from more than one source and the order of the I/O arrivals is not predetermined. Examples include network daemons listening to more than one network socket, window managers that accept mouse movement as well as keyboard input, and I/O-management programs, such as a copy command that copies data between I/O devices. In the last case, the program could optimize its performance by buffering the input and output and using non-blocking I/O to keep both devices fully occupied.
Non-blocking I/O is also important where real-time or quasi-real-time responses are needed. Examples include the need to track mouse movements in a GUI window and controls over special devices (such as landing gear).
Blocking I/O is what makes multiprogramming possible (and we know that's good). Also, non-blocking I/O is more complicated for programmers, because of the asynchronous rendezvous that is needed when an I/O occurs. Also, busy waiting is less efficient than interrupt-driven I/O, so the overall system performance would decrease without blocking I/O.
13.2
FCFS: Order is (125-143)-86-1470-913-1774-948-1509-1022-1750-130
Total seek distance is 7081 cyls.
SSTF: Order is (125-143)-130-86-913-948-1022-1470-1509-1750-1774 Total seek distance is 1745 cyls.
Note that SSTF optimizes for immediate seek time, not total seek time.
LOOK: Order is (125-143)-913-948-1022-1470-1509-1750-1774-130-86 Total seek distance is 3319 cyls.
C-LOOK: Order is (125-143)-913-948-1022-1470-1509-1750-1774-86-130 Total seek distance is 3363 cyls.
N-Step LOOK: Order is (125-143)-913-1470-1774-86-130-948-1022-1509-1750 Total seek distance is 4983 cyls.13.10.
(a) SSTF would give good access for the high-demand cylinders, but could result in starvation for other requests if the rate of requests is high. FCFS would be fair, but could result in poor performance if references to the high-demand cylinders were interspersed with references to cylinders far away. LOOK and C-LOOK would be good performers, but again could cause starvation if the rate of requests is very high. N-Step LOOK or N-Step C-LOOK would have the performance advantages of LOOK/C-LOOK and also avoid the possibility of starvation.
(b) One suggestion would be to use multiple queues, just as we did in multiple-queue CPU scheduling. One queue would handle the high-demand cylinders only; if a limit is placed on how many of those are serviced before servicing the same number from the other queue, starvation would not be a problem. Each queue could be ordered in LOOK or C-LOOK order to maximize performance while that queue's requests are being processed.
(c) Locate the FAT or inodes in cache to maximize the performance of lookups. Another possibility is to use the FAT/inodes to implement the equivalent of the mapped disk space allocation we discussed as part of file systems. That is, while the entries in the FAT/inodes would reflect the logical ordering of blocks within a file, the actual data could be stored anywhere on disk. Thus, it would be possible to distribute the actual data blocks in order to maximize performance.
13.16.
(a) Using the simplest methods, a drive would fail approximately every month. That is, 1 of the 1000 drives would fail each750,000 hrs/failure * 1/1000 drives = 750 hrs/drive-failure = approx. 31 days.
(b) MTBF for 20-year-olds can be approximated as: MTBF = 24 hrs/day * 365 days/yr ------------------------ 1 / 1000 people
so MTBF=8760000 person-hrs = 1000 person-yrs. Note that this only makes sense because the MTBF drops for each year beyond 20 that an adult continues living. A 20-year-old can't really expect to live that long.
(c)This can be estimated as 1M hours/failure ---------------- 24 hrs/day ---------------------- 365 days/yr
or approximately 114 years.
15.4.
(a) Multiaccess bus LAN. That way, computers could be added or removed from the network (important if we assume that not all students will have them) without requiring network reconfiguration.
(b) Tree-structured or hierarchical LAN. Each building could be a sub-tree (or multiple ones, if there are multiple departments within a building). That way, if one department or building were cut off from the others, the rest of campus could still function.
(c) Double-link ring WAN supporting LANs (which could be a mix of configurations), or multiaccess bus WAN as a trunk-line supporting heterogeneous LANs. The ring would be more costly, but would provide better reliability.
(d) Multiaccess bus WAN supporting heterogeneous LANs. At this scale, a double-link ring would be much too costly. The problem of reliability might be solved by having multiple multiaccess bus trunk-lines, some of lesser capacity that would primarily serve as backups in case of network congestion or failures.
15.6. Faster systems may be able to send out more packets in a shorter amount of time. The network would then have more packets traveling on it, resulting in more collisions, and therefore less throughput relative to the number of packets being sent.
More networks can be used, with fewer systems per network, to reduce the number of collisions.
Homework 1 - Solutions
1.1. What are the three main purposes of an operating system?
To provide a convenient environment for users to execute programs on computer hardware.
To allocate, fairly and efficiently, the computer resources needed to execute the program safely (without adversely affecting other users or the OS itself).
To provide a foundation for evolution to future services, while still supporting existing services.Note that "convenience," "efficiency," etc. are not acceptable answers, since they don't explain "convenient/efficient for whom to do what."
1.4. In a multiprogramming and time-sharing environment, several users share the system simultaneously. This siguation can result in various security problems.
(a) What are two such problems?
(b) Can we ensure the same degree of secutiry in a time-shared machine as we have in a dedicated machine? Explain your answer.
Stealing or copying a user's files; writing over another program's (belonging to another user or to the OS) area in memory; using system resources (CPU, disk space) without proper accounting; causing the printer to mix output by sending data while some other user's file is printing.
Probably not, since any protection scheme devised by a human can also be broken -- and the more complex the scheme is, the more difficult it is to be confident of its correct implementation.
1.6. What are the main differences between operating systems for mainframe computers and personal computers?
PC OS's are not concerned with fair use or maximal use of computer resources. Instead, they try to optimize the usefulness of the computer for an individual user, usually at the expense of overall efficiency. Mainframe OS's need more complex scheduling and I/O algortihms to keep the various system components efficiently occupied.1.7. Define the essential properties of the following types of operating systems:BatchInteractiveTime-sharingReal-timeDistributed
Batch: Jobs with similar needs are batched together and run through the computer as a group, by an operator or automatic job sequencer. Performance is increased by attempting to keep CPU and I/O devices busy at all times through buffering, off-line operation, spooling, and multiprogramming.
Interactive: Composed of many short transactions with input and output read/written on the screen; the results and timing of the next transaction may be unpredictable. Note that a purely interactive system (no time-sharing) only has one user; e.g., a PC).
Time-sharing: Uses CPU scheduling and multiprogramming to provide economical interactive use of a system. The CPU switches rapidly from one user to another.
Real-time: The system must respond to inputs/commands within a fixed amount of time to ensure correct performance. Input is typically read from sensors.
Distributed: Divides computation up among several computers. The computers do not share memory or a clock; they communicate with each other over communication lines (e.g., high-speed bus, telephone line).
1.10. Describe the differences between symmetric and asymmetric multiprocessing. What are three advantages and one disadvantage of multiprocessor systems?
Symmetric processing treats all processors as equals; I/O can be processed on any of them. Asymmetric processingdesignates one CPU as the master, which is the only one capable of performing I/O; the master distributes computational work among the other CPUs.
advantages: Multiprocessor systems can save money, by sharing power supplies, housings, and peripherals. Can execute programs more quickly and can have increased reliability.
disadvantages: Multiprocessor systems are more complex in both hardware and software. Additional CPU cycles are required to manage the cooperation, so per-CPU efficiency goes down.
2.3. What are the differences between a trap and an interrupt? What is the use of each function?
An interrupt is a hardware-generated signal that changes the flow within the system. A trap is a software-generated interrupt.
An interrupt can be used to signal the completion of I/O so thatthe CPU doesn't have to spend cycles polling the device. A trap can be used to catch arithmetic errors or to call system routines.
2.5. Which of the following instructions should be privileged?Set value of timerRead the clockClear memoryTurn off interruptsSwitch from user to monitor mode
Should be privileged.
Doesn't need to be.
Should be privileged.
Should be privileged.
Should be privileged.
Answer the following questions about policies and mechanisms:
(a) What is an advantage of separating policy from mechanism in designing any piece of software (including OSs)?
(b) Give three examples of software policies versus mechanisms.
Clean separation makes systems easier to modify and port. Another answer: Clearer thinking allowing you to differentiate the desired properties of a solution from the best solution you've thought of so far. Another answer: Mechanisms can be changed without affecting the policy.
Hint: You should always be able to name at least 2 different mechanisms that could be used to implement a so-called policy.Some examples:
policy: share CPU resource fairly among processes. mechanism: timer interrupts. alternate mechanism: enforce a limit on how long programs can be.
policy: some processes are more important or more critical than others. mechanism: base scheduling upon process priority. alternate mechanism: force processes to use "nice()" values.
policy: data values must be kept in order of priority. mechanism: heap. alternate mechanism: priority-sorted vector.
CS411/511. Operating Systems
Homework 2 - Solutions
Chapter 4: Review Questions 4.2, 4.6, 4.7
4.2. Describe the differences among short-term, medium-term, and long-term scheduling.
Short-term (CPU scheduler): selects a process from those that are in memory and ready to execute, and and allocates the CPU to it.
Medium-term (memory manager): selects processes from the ready or blocked queue and removes them from memory, then reinstates them later to continue running.
Long-term (job scheduler): determines which jobs are brought into the system for processing.
4.6. Describe the actions taken by a kernel to switch context(a) Among threads
(b) Among processes
The thread context (registers, PC, and stack, plus accounting info if appropriate) must be saved and another thread's context must be loaded.
The same as (a), except that the memory and resource info must also be stored and that for the next process must be loaded.
4.7. What are the differences between user-level threads and kernel-supported threads? Under what circumstances is one type "better" than the other?
User-level threads have no kernel support, so they are very inexpensive to create, destroy, and switch among. Kernel-supported threads are more expensive because system calls are needed to create and destroy them and the kernel must schedule them.
In most current systems with threads, when a user-level thread blocks, the whole process blocks. Since kernel-supported threads are scheduled independently, they can block individually; that is, the fact that one blocks does not hold up the others.
Chapter 5
5.4. Suppose that the following processes arrive for execution at the times indicated. Each process will run the listed amount of time. In answering the questions, use nonpreemptive scheduling and base all decisions on the information you have at the time the decision must be made. Process Arrival Time Burst Time ------------------------------------------------------ P1 0.0 8 P2 0.4 4 P3 1.0 1
(a) What is the average turnaround time for these processes with the FCFS scheduling algorithm?
(b) What is the average turnaround time for these processes with the SJF scheduling algorithm?
(c) The SJF algorithm is supposed to improve performance, but notice that we chose to run process P1 at time 0 because we did not know that two shorter processes would arrive soon. Compute what the average turnaround time will be if the CPU is left idle for the first 1 unit and then SJF scheduling is used. Remember that processes P1 and P2 are waiting during this idle time, so their waiting time may increase. This algorithm could be known as future-knowledge scheduling.
(a) 10.53
(b) 9.53
(c) 6.86Remember that turnaround time is completion time minus arrival time, so you have to subtract the arrival times to compute the turnaround. FCFS is 11 if you forget to subtract arrival time.
5.6. What advantage is there in having different time-quantum sizes on different levels of a multilevel queueing system?
Processes which need more frequent servicing, such as interactive processes, can be in a queue with a small q. Processes that are computationally intensive can be in a queue with a larger quantum, requiring fewer context switches to complete the processing, making more efficient use of the CPU.
5.7. Consider the following preemptive priority-scheduling algorithm based on dynamically changing priorities. Larger priority numbers imply higher priority. When a process is waiting for the CPU (in the ready queue, but not running), its priority changes at a rate alpha; when it is running, the priority changes at a rate beta. All processes are given a priority of 0 when they enter the ready queue for the first time. The parameters alpha and beta can be set to give many different scheduling algorithms.(a) What is the algorithm that results from beta > alpha > 0?
(b) What is the algorithm that results from alpha < beta < 0?
(a) Since processes start at 0, any processes that have been in the system (either running or waiting) have higher priority. Therefore, new processes go to the back of the queue. When a process runs, its priority keeps increasing at the rate of beta, which is more of an increase than for the processes in the ready queue. Therefore, every time the process has timerrunout, it goes to the front of the ready queue and gets dispatched again. This is the equivalent of FCFS.
(b) This time, any new processes entering the system have higher priority than any old ones, since priority starts at zero and then becomes negative when the process waits or runs. New processes go in at the front of the queue. When a process runs or waits, its priority decreases, with the waiting processes decreasing faster than the running process. This is a LIFO (last-in-first-out) algorithm. The question didn't promise that this would be an algorithm you would want to use in real life.
Other Question. Take the example that you just used for Question 5.4, and apply it to the following situations.(a) Calculate the average turnaround time for a Round-Robin algorithm with q set at 2. Ignore the effects of context-switching time.
(b) Calculate the average turnaround time for the same algorithm and q, taking into effect the fact that each context switch costs .5 units of time.
(c) Suppose that a fourth process, P4, enters the system at time 7.6 and needs 6 units of CPU time. Also suppose that P2 and P3 are interactive, but P1 and P4 are batch.
A multilevel queue (but not a multilevel feedback queue) is in effect. The first queue is for interactive processes only, and has a qof 1. The second queue is for batch processes, which get up to 4 units each time they are in the CPU. Processes are dispatched as follows: 2 processes are dispatched from the interactive queue, followed by 1 process from the batch queue, etc.
Calculate the average turnaround time.
(a)8.53
(b)10.53 (I didn't count the final context switch after a process leaves the CPU for the last time)
(c)11 (They run in the order P1-P2-P3-P1-P2-P4-P2-P4-P2)
CS411/511. Operating Systems
Homework 3 - Solutions
Chapter 8: Review Questions 8.4, 8.10, 8.11, 8.16511 students only: 8.17
8.4. When a process is rolled out of memory, it loses its ability to use the CPU (at least for a while). Describe another situation where a process loses its ability to use the CPU, but where the process does not get rolled out.
When an interrupt occurs the process loses the CPU, but regains it as soon as the handler completes. The process is never rolled out of memory.
Note that when timerrunout occurs, the process is returned to the ready queue, and it may later be rolled out of memory. When the process blocs, it is moved to a waiting queue, where it may also be rolled out at some point.8.10. Consider a paging system with the page table stored in memory.(a) If a memory reference takes 200 nanoseconds, how long does a paged memory reference take?
(b) If we add associative registers, and 75% of all page-table references are found in the associative registers, what is the effective memory reference time? (Assume that finding a page-table entry in the associative registers takes zero time, if the entry is there.)
400 nanoseconds. 200 ns to access the page table plus 200 ns to access the word in memory.
250 nanoseconds. 75% of the time it's 200 ns, and the other 25% of the time it's 400ns, so the equation is: e.a. = (.75*200)+(.25*400)
Try this, too: What if the time to access the associative registers is actually 2 ns -- how does your answer change? e.a. = 2 + (.75*200)+(.25*400)
Remember that you *always* have to perform the TLB lookup, whether or not the page is found there.8.11. What is the effect of allowing two entires in a page table to point to the same page frame in memory? Explain how this effect could be used to decrease the amount of time needed to copy a large amount of memory from one place to another. What would the effect of updating some byte in the one page be on the other page?
This allows users to shared code or data. If the code is reentrant, much memory space can be saved through the shared use of large programs (e.g., text editors, compilers, database systems). "Copying" large amounts of memory could be effected by having different page tables point to the same memory location.
However, sharing of non-reentrant code or data means that any user having access to the code can modify it and these modifications would be reflected in the other user's "copy."8.16. Consider the following segment table: Segment Base Length 0 219 600 1 2300 14 2 90 100 3 1327 580 4 1952 96
What are the physical addressed for the following logical addresses?(a) 0,430(b) 1,10(c) 2,500(d) 3,400(e) 4,112
(a) 219 + 430 = 649
(b) 2300 + 10 = 2310
(c) illegal reference; traps to operating system
(d) 1327 + 400 = 1727
(e) illegal reference; traps to operating system8.17. Consider the Intel address translation scheme shown in Figure 8.28(a) Describe all the steps that are taken by the Intel 80386 in translating a logical address into a physical address.(b) What are the advantages to the OS of hardware that provides such complicated memory translation?(c) Are there any disadvantages to this address translation system?
(a) The selector is an index into the segment descriptor table. The segment descriptor result plus the original offset is used to produce a linear address with dir/page/offset. The dir is an index into a page directory; the entry from this directory selects the page table, and the page field is an index into that page table. The entry from the page table, plus the offset, is the physical address.
(b) Such a page translation mechanism offers the flexibility to allow most OS's to implement their memory scheme in hardware, instead of having to implement some parts in hardware and some in software. Because it can be done in hardware, it is more efficient -- and the kernel is simpler.
(c) Address translation can take longer due to the multiple table lookups it can involve. Caches help, but there will still be cache misses.
Chapter 9: Review Questions 9.3, 9.11, 9.18511 students only: 9.5, 22.8
9.3. A certain computer provides its users with a virtual memory space of 2**32 bytes. The computer has 2**18 bytes of physical memory. The virtual memory is implemented by paging, and the page size is 4K bytes. A user process generated the virtual address 11123456. Explain how the system establishes the corresponding physical location. Distinguish between software and hardware operations.
The virtual address in binary form is 0001 0001 0001 0010 0011 0100 0101 0110
Since the page size is 2**12, the page table size is 2**20. Therefore, the low-order 12 bits (0100 0101 0110) are used as the displacement into the page, while the remaining 20 bits (0001 0001 0001 0010 0011) are used as the displacement in the page table.
Consider the operations that are needed (a) for DAT, and (b) for page fault servicing. All the DAT operations are carried out in hardware. But of the list of operations for page faults, on pp. 297-298, *at*least* steps 2, 4, 5, 6, 8, 10, and 12 involve software operations.9.11. Consider the following page reference string: 1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3, 7, 6, 3, 2, 1, 2, 3, 6
How many page faults would occur for the following replacement algorithms, assuming one, two, three, four, five, size, or seven frames? Remember that all frames are initially empty, so your first unique pages will all cost one fault each.LRU replacementFIFO replacementOptimal replacement
# Frames LRU FIFO Optimal
1 20 20 20
2 18 18 15
3 15 16 11
4 10 14 8
5 8 10 7
6 7 10 7
7 7 7 7
9.17 (not in the assignement, but I'll leave the solution here).
Consider a demand-paging system with a paging disk that has an average access and transfer time of 20 ms. Addresses are translated through a page table in main memory, with an access time of 1 us per memory access. Thus, each memory reference through the page table takes two accesses. To improve this time, we have added an associative memory that reduces access time to one memory reference, if the page-table entry is in the associative memory.
Assume that 80% of the accesses are in the associative memory, and that, of the remaining, 10% (or 2% of the total) cause page faults. What is the effective memory access time? e.a. = 1 us + (0.20 * 1 us) + (0.02 * 20,000 us) = 401.2 us
Or, if you prefer e.a. = (0.80 * 1 us) + (0.18 * 2 us) + (0.02 * 20,002 us) = .8 us + .36 us + 400.04 us = 401.2 us
9.18. Consider a demand-paged computer system where the degree
of multi-programming is currently fixed at four. The system
was recently measureed to determine utilization of CPU and the
paging disk. The results are one of the following alternatives.
For each case, what is happening? Can the degree of
multiprogramming be increased to increase the CPU utilization?
Is the paging helping?
a. CPU utilization 13 percent; disk utilization 97 percent
System is thrashing. The degree of multiprogramming should be
decreased. Paging is not helping.
b. CPU utilization 87 percent; disk utilization 3 percent
System is well utilized, CPU is being kept busy most of the time.
The degree of multiprogramming probably should stay the same,
increasing it may lead to thrashing. Paging is helping.
c. CPU utilization 13 percent; disk utilization 3 percent
System is under utilized, the CPU is not getting enough work.
The degree of multiprogramming should be increased. Paging is
not really helping or hurting.
9.5. Suppose we have a demand-paged memory. The page table is held in registers. It takes 8 ms to service a page fault if an empty page is available or the replaced page is not modified, and 20 m if the replaced page is modified. Memory access time is 100 ns.
Assume that the page to be replaced is modified 70% of the time. What is the maximum acceptable page-fault rate for an effective access time of no more than 200 ns? [note: everything shown in microseconds] 0.2 us = ((1-P) * 0.1 us) + (0.3P * 8,000 us) + (0.7P * 20,000 us) 0.1 = -01.P + 2,400P + 14,000P 0.1 ~ 16,400 P P ~ 0.000006
22.8. What are three advantages of dynamic (shared) linkage of libraries, compared to static linkage? What are two cases where static linkage is preferable?
The primary advantages are that they reduce the memory and disk space used by a system, and they enhance maintainability. (You should be able to describe in detail why this is so.) Other advantages are the fact that a program that uses shared libraries can often be adapted for other purposes simply by replacing one or more of its libraries (e.g., substituting a debugging library for the normal one in order to trace a problem in an application). Shared libraries also allow program binaries to be linked against commercial, proprietary library code without actually including any of that code in the program's final executable file -- so it's may be possible to distribute code to a third party without having to incur extra licensing charges.
Static linkage is more appropriate for "system administration rescue" situations, such as if a sysadmin makes a mistake while installing a new library that causes it to be corrupted. Therefore, it is common to provide a set of basic "rescue utilities" that are statically linked, so that the fault can be corrected without having to rely on shared libraries. Since dynamic linking adds to the execution time, there may be performance reasons for linking the libraries statically. Also, it's easier to distribute an executable file that is complete (i.e., statically linked) rather than having to count on the recipient having the appropriate shared librares.CS411/511. Operating Systems
Homework 4 - Solutions
Chapter 6: Review Questions 6.1, 6.4, 6.18511 students only: 6.19
6.1.
Busy waiting: A process is waiting for an event to occur and it does so by executing instructions.
Other types of waiting: A process is waiting for an event to occur in some waiting queue (e.g., I/O semaphore) and it does so without having the CPU assigned to it.
Busy waiting cannot be avoided altogether (see p. 170).
6.4.Note that this is the same principle as Dekker's Algorithm, which we studied in class. It was a slightly earlier version, and therefore is more complicated than it really needs to be.
To prove that this algorithm is correct, we need to show that mutual exclusion is preserved, the progress requirement is satisfied, and the bounded-waiting requirement is met.
To prove mutual exclusion, we note that each P enters its critical section only if flag[j]!=in-cs for all other processes. Since each process is the only one that can set its own flag value, and since each process waits to examine the other processes' flags until it has set its own flag to in-cs, it can't be possible for two processes not to know that each other's flag is set. Therefore, it's not possible for two processes to be in their critical sections at the same time.
To prove progress, we note that the turn value can only be modified when a process is just about to enter its critical section, or has just completed its critical section. The turn value remains constant whenever there is no process executing/leaving its critical section. If other processes want to enter their critical sections, one will always be able to (the "first" one in the cyclic ordering [turn, turn+1, ... n-1, 0, ... turn-1]).
To prove bounded waiting, we note that whenever a process leaves its critical section, it checks to see if any other processes want to enter their critical sections. If so, it always designates which one will go next -- the "first" one in the cyclic ordering. This means that any process wanting to enter its critical section will do so within n-1 turns.
6.18. Note that the authors are referring to "cost" very generally (as in cost/benefit analysis), rather than specifically to "price."
Volatile storage fails when there is a power failure. Cache, main memory, and registers require a steady power source; when the system crashes and this source is interrupted, the contents are lost. Access is very fast.
Non-volatile storage retains its content despite power failures. For example, disk and CDROM survive anything other than demagnetization or hardware/head crashes (and less likely things like fire, immersion in water, etc.). Access is much slower.
Stable storage theoretically survives any type of failure. It can only be approximated through techniques such as mirroring. Access is certainly slower than volatile, and possibly slower than non-volatile storage.
6.19. If there is no checkpointing, the entire log must be searched after a crash, and all transactions "redone" from the log. If checkpointing is used, most of the log can be discarded. Since checkpoints are very expensive, how often they should be taken depends upon how reliable the system is. The more reliable the system, the less often a checkpoint should be taken.
When no failure occurs, the cost of checkpointing is "pure overhead" and can degrade performance if checkpointing is done frequently. When a system crash occurs, recovery time is proportional to the number of transactions since the last checkpoint. Assuming that a disk crash means the checkpoint file has been lost, recovery will involve a full rollback and re-doing of all transactions in the log.
Chapter 7: Review Questions 7.4, 7.6, 7.8, 7.13
(hint for 7.4(b): this is what drivers are really supposed to do)511 students only: 7.14
7.4. Note that each section of the street (including each intersection) is considered to be a "resource."
Mutual exclusion: only one vehicle on a section of the street
Hold and wait: each vehicle is occupying a section of the street and is waiting to move to the next section
No preemption: a section of a street that is occupied by a vehicle cannot be taken away from the vehicle unless the car moves into the next section
Circular wait: each vehicle is waiting for the next vehicle in front of it to moveTo keep deadlocks from occurring, allow a vehicle to cross an intersection only if it is assured that the vehicle will not have to stop at the intersection.
7.6.
(a) anytime
(b) only if MAX demand of each process does not exceed total number of available resources, and the system remains in a safe state.
(c) only if MAX demand of each process does not exceed total number of available resources, and the system remains in a safe state.
(d) anytime
(e) anytime
(f) anytime
7.8. Suppose the system is deadlocked. This implies that each process is holding one resource and is waiting for one more. Since there are three processes and four resources, one process must be able to obtain two resources. This process requires no more resources, and therefore it will terminate, releasing its resources. This in turn frees sufficient resources for the other processes to complete, one at a time.
7.13.
(a) Since NEED=MAX-ALLOC, the content of NEED is as follows
A B C D
0 0 0 0
0 7 5 0
1 0 0 2
0 0 2 0
0 6 4 2
(b)Yes, the sequence [P0, P2, P1, P3, P4] satisfies the safety requirement.
(c)Yes. The request does not exceed either Available or Max. Further the new system state, which is
Alloc Max Need
P0 0 0 1 2 0 0 1 2 0 0 0 0
P1 1 4 2 0 1 7 5 0 0 3 3 0
P2 1 3 5 4 2 3 5 6 1 0 0 2
P3 0 6 3 2 0 6 5 2 0 0 2 0
P4 0 0 1 4 0 6 5 6 0 6 4 2
is safe, as demonstrated by the sequence [P0, P2, P1, P3, P4].
7.14.
(a) Deadlock cannot occur because preemption exists. That is, the criterion of "no preemption" has been prevented.
(b) Yes. A process may never acquire all the resources it needs, if they are continuously preempted by a series of requests such as those of process C.
Chapters 22-23: 511 students only: 22.6, 23.11
22.6.
Advantages: The primary impact of disallowing paging of kernel memory is that the non-preemptibility of the kernel is preserved. (Any process taking a page fault, whether in kernel mode or in user mode, risks being preempted while the required data is paged in from disk.) Because the kernel is guaranteed not to be preempted, locking requirements to protect the integrity of its primary data structures are also greatly simplified.
Disadvantages: It imposes constraints on the amount of memory that the kernel can use, since it is unreasonable to keep very large data structures in non-pageable memory (that memory cannot be used for anything else). Two disadvantages that stem from this are:
The kernel must prune back many of its internal data structures manually, since it can't rely on virtual memory mechanisms to keep physical memory usage under control.
It is infeasible to implement features requiring very large amounts of memory in the kernel (such as the /tmp-filesystem, a fast virtual-memory based filesystem found in some UNIX systems).
Note that the complexity of managing page faults while running kernel code is not an issue. The Linux kernel code is already able to deal with page faults (which can occur in a system call whose arguments reference user memory, which may be paged out on disk).
23.11. A process in NT is limited to 2 GB address space for data. The two-stage process allows the access of much larger datasets, by reserving space in the process's address space first, and then committing the storage to a memory-mapped file. An application can thus "window" through a large database (by changing the committed section) without exceeding process quotas or utilizing a huge amount of physical memory.
CS411/511. Operating Systems
Homework 5 - Solutions
12.1.
advantages: Bugs are less likely to cause an operating system crash. Performance can be improved by utilizing dedicated hardware and hard-coded algorithms. The kernel is simplified by moving algorithms out of it.
disadvantages: Bugs are harder to fix - a new firmware version or new hardware is needed; improving algorithms likewise require a hardware update rather than just kernel or device driver update. Embedded algorithms could conflict with OS's priorities or with application's use of the device, causing decreased performance. Testing is harder, since the components are autonomous and each device may behave differently.
12.2.
(a) mouse: Buffering may be needed to record mouse movement during times when higher-priority operations are taking place. Spooling and caching are inappropriate. Interrupt-driven I/O is most appropriate.
(b) tape drive: Buffering may be needed to manage throughput difference between the tape drive and the source or destination of the I/O. Caching can be used to hold copies of data that resides on the tape, for faster access. Spooling could be used to stage data to the device when multiple users desire to read from or write to it. Interrupt-driven I/O is likely to yield the best performance.
(c) disk: Buffering can be used to hold data while in transit from user space to the disk, and vice versa. Caching can be used to hold disk-resident data for improved performance. Spooling is not necessary because disks are shared-access devices. Interrupt-driven I/O is always good for devices -- such as disks -- that transfer data at relatively slow rates.
(d) graphics card: Buffering may be needed to control multiple access and for performance (double-buffering can be used to hold the next screen image while displaying the current one). Caching and spooling are not necessary due to the fast and shared-access nature of the device. Polling and interrupts are only useful for input and for I/O completion detection, neither of which is needed for a memory-mapped device.
12.4.
Generally, blocking I/O is appropriate when the process will only be waiting for one specific event. Examples include a disk, tape, or keyboard read by an application program.
Non-blocking I/O is particularly useful when I/O may come from more than one source and the order of the I/O arrivals is not predetermined. Examples include network daemons listening to more than one network socket, window managers that accept mouse movement as well as keyboard input, and I/O-management programs, such as a copy command that copies data between I/O devices. In the last case, the program could optimize its performance by buffering the input and output and using non-blocking I/O to keep both devices fully occupied.
Non-blocking I/O is also important where real-time or quasi-real-time responses are needed. Examples include the need to track mouse movements in a GUI window and controls over special devices (such as landing gear).
Blocking I/O is what makes multiprogramming possible (and we know that's good). Also, non-blocking I/O is more complicated for programmers, because of the asynchronous rendezvous that is needed when an I/O occurs. Also, busy waiting is less efficient than interrupt-driven I/O, so the overall system performance would decrease without blocking I/O.
13.2
FCFS: Order is (125-143)-86-1470-913-1774-948-1509-1022-1750-130
Total seek distance is 7081 cyls.
SSTF: Order is (125-143)-130-86-913-948-1022-1470-1509-1750-1774 Total seek distance is 1745 cyls.
Note that SSTF optimizes for immediate seek time, not total seek time.
LOOK: Order is (125-143)-913-948-1022-1470-1509-1750-1774-130-86 Total seek distance is 3319 cyls.
C-LOOK: Order is (125-143)-913-948-1022-1470-1509-1750-1774-86-130 Total seek distance is 3363 cyls.
N-Step LOOK: Order is (125-143)-913-1470-1774-86-130-948-1022-1509-1750 Total seek distance is 4983 cyls.13.10.
(a) SSTF would give good access for the high-demand cylinders, but could result in starvation for other requests if the rate of requests is high. FCFS would be fair, but could result in poor performance if references to the high-demand cylinders were interspersed with references to cylinders far away. LOOK and C-LOOK would be good performers, but again could cause starvation if the rate of requests is very high. N-Step LOOK or N-Step C-LOOK would have the performance advantages of LOOK/C-LOOK and also avoid the possibility of starvation.
(b) One suggestion would be to use multiple queues, just as we did in multiple-queue CPU scheduling. One queue would handle the high-demand cylinders only; if a limit is placed on how many of those are serviced before servicing the same number from the other queue, starvation would not be a problem. Each queue could be ordered in LOOK or C-LOOK order to maximize performance while that queue's requests are being processed.
(c) Locate the FAT or inodes in cache to maximize the performance of lookups. Another possibility is to use the FAT/inodes to implement the equivalent of the mapped disk space allocation we discussed as part of file systems. That is, while the entries in the FAT/inodes would reflect the logical ordering of blocks within a file, the actual data could be stored anywhere on disk. Thus, it would be possible to distribute the actual data blocks in order to maximize performance.
13.16.
(a) Using the simplest methods, a drive would fail approximately every month. That is, 1 of the 1000 drives would fail each750,000 hrs/failure * 1/1000 drives = 750 hrs/drive-failure = approx. 31 days.
(b) MTBF for 20-year-olds can be approximated as: MTBF = 24 hrs/day * 365 days/yr ------------------------ 1 / 1000 people
so MTBF=8760000 person-hrs = 1000 person-yrs. Note that this only makes sense because the MTBF drops for each year beyond 20 that an adult continues living. A 20-year-old can't really expect to live that long.
(c)This can be estimated as 1M hours/failure ---------------- 24 hrs/day ---------------------- 365 days/yr
or approximately 114 years.
15.4.
(a) Multiaccess bus LAN. That way, computers could be added or removed from the network (important if we assume that not all students will have them) without requiring network reconfiguration.
(b) Tree-structured or hierarchical LAN. Each building could be a sub-tree (or multiple ones, if there are multiple departments within a building). That way, if one department or building were cut off from the others, the rest of campus could still function.
(c) Double-link ring WAN supporting LANs (which could be a mix of configurations), or multiaccess bus WAN as a trunk-line supporting heterogeneous LANs. The ring would be more costly, but would provide better reliability.
(d) Multiaccess bus WAN supporting heterogeneous LANs. At this scale, a double-link ring would be much too costly. The problem of reliability might be solved by having multiple multiaccess bus trunk-lines, some of lesser capacity that would primarily serve as backups in case of network congestion or failures.
15.6. Faster systems may be able to send out more packets in a shorter amount of time. The network would then have more packets traveling on it, resulting in more collisions, and therefore less throughput relative to the number of packets being sent.
More networks can be used, with fewer systems per network, to reduce the number of collisions.
2014年10月2日 星期四
Memory
CS372H: Solutions for Homework 3
Problem 1 In a 32-bit machine we subdivide the virtual address into 4 segments as follows:
10-bit 8-bit 6-bit 8 bit
We use a 3-level page table, such that the first 10-bit are for the first level and so on.
What is the page size in such a system?
What is the size of a page table for a process that has 256K of memory starting at address 0?
What is the size of a page table for a process that has a code segment of 48K starting at address 0x1000000, a data segment of 600K starting at address 0x80000000 and a stack segment of 64K starting at address 0xf0000000 and growing upward (like in the PA-RISC of HP)?
Solution:
The page field is 8-bit wide, then the page size is 256 bytes.
Using the subdivision above, the first level page table points to 1024 2nd level page tables, each pointing to 256 3rd page tables, each containing 64 pages. The program's address space consists of 1024 pages, thus we need we need 16 third-level page tables. Therefore we need 16 entries in a 2nd level page table, and one entry in the first level page table. Therefore the size is: 1024 entries for the first table, 256 entries for the 2nd level page table, and 16 3rd level page table containing 64 entries each. Assuming 2 bytes per entry, the space required is 1024 * 2 + 256 * 2 (one second-level paget table) + 16 * 64 * 2 (16 third-level page tables) = 4608 bytes.
First, the stack, data and code segments are at addresses that require having 3 page tables entries active in the first level page table. For 64K, you need 256 pages, or 4 third-level page tables. For 600K, you need 2400 pages, or 38 third-level page tables and for 48K you need 192 pages or 3 third-level page tables. Assuming 2 bytes per entry, the space required is 1024 * 2 + 256 * 3 * 2 (3 second-level page tables) + 64 * (38+4+3)* 2 (38 third-level page tables for data segment, 4 for stack and 3 for code segment) = 9344 bytes.
Problem 2
A computer system has a 36-bit virtual address space with a page size of 8K, and 4 bytes per page table entry.
How many pages are in the virtual address space?
What is the maximum size of addressable physical memory in this system?
If the average process size is 8GB, would you use a one-level, two-level, or three-level page table? Why?
Compute the average size of a page table in question 3 above.
Solution:
A 36 bit address can address 2^36 bytes in a byte addressable machine. Since the size of a page 8K bytes (2^13), the number of addressable pages is 2^36 / >2^13 = 2^23
With 4 byte entries in the page table we can reference 2^32 pages. Since each page is 2^13 B long, the maximum addressable physical memory size is 2^32 * 2^13 = 2^45 B (assuming no protection bits are used).
8 GB = 2^33 B
We need to analyze memory and time requirements of paging schemes in order to make a decision. Average process size is considered in the calculations below.
1 Level Paging
Since we have 2^23 pages in each virtual address space, and we use 4 bytes per page table entry, the size of the page table will be 2^23 * 2^2 = 2^25. This is 1/256 of the process' own memory space, so it is quite costly. (32 MB)
2 Level Paging
The address would be divided up as 12 | 11 | 13 since we want page table pages to fit into one page and we also want to divide the bits roughly equally.
Since the process' size is 8GB = 2^33 B, I assume what this means is that the total size of all the distinct pages that the process accesses is 2^33 B. Hence, this process accesses 2^33 / 2^13 = 2^20 pages. The bottom level of the page table then holds 2^20 references. We know the size of each bottom level chunk of the page table is 2^11 entries. So we need 2^20 / 2^11 = 2^9 of those bottom level chunks.
The total size of the page table is then:
//size of the outer page table //total size of the inner pages
1 * 2^12 * 4 + 2^9 * 2^11 * 4 = 2^20 * ( 2^-6 + 4) ~4MB
3 Level Paging
For 3 level paging we can divide up the address as follows:
8 | 8 | 7 | 13
Again using the same reasoning as above we need 2^20/2^7 = 2^13 level 3 page table chunks. Each level 2 page table chunk references 2^8 level 3 page table chunks. So we need 2^13/2^8 = 2^5 level-2 tables. And, of course, one level-1 table.
The total size of the page table is then:
//size of the outer page table //total size of the level 2 tables //total size of innermost tables
1 * 2^8 * 4 2^5 * 2^8 *4 2^13 * 2^7 * 4 ~4MB
As easily seen, 2-level and 3-level paging require much less space then level 1 paging scheme. And since our address space is not large enough, 3-level paging does not perform any better than 2 level paging. Due to the cost of memory accesses, choosing a 2 level paging scheme for this process is much more logical.
Calculations are done in answer no. 3.
Problem 3
In a 32-bit machine we subdivide the virtual address into 4 pieces as follows:
8-bit 4-bit 8-bit 12-bit
We use a 3-level page table, such that the first 8 bits are for the first level and so on. Physical addresses are 44 bits and there are 4 protection bits per page. Answer the following questions, showing all the steps you take to reach the answer. A simple number will not receive any credit.
What is the page size in such a system? Explain your answer (a number without justification will not get any credit).
How much memory is consumed by the page table and wasted by internal fragmentation for a process that has 64K of memory starting at address 0?
How much memory is consumed by the page table and wasted by internal fragmentation for a process that has a code segment of 48K starting at address 0x1000000, a data segment of 600K starting at address 0x80000000 and a stack segment of 64K starting at address 0xf0000000 and growing upward (towards higher addresses)?
Solution:
4K. The last 12 bits of the virtual address are the offset in a page, varying from 0 to 4095. So the page size is 4096, that is, 4K.
2912 or 4224 bytes for page tables, 0 bytes for internal fragmentation.
Using the subdivision above, the 1st level page table contains 256 entries, each entry pointing to a 2nd level page table. A 2nd level page table contains 16 entries, each entry pointing to a 3rd page table. A 3rd page table contains 256 entries, each entry pointing to a page. The process's address space consists of 16 pages, thus we need 1 third-level page table. Therefore we need 1 entry in a 2nd level page table, and one entry in the first level page table. Therefore the size is: 256 entries for the first table, 16 entries for the 2nd level page table, and 1 3rd level page table containing 256 entries.
Since physical addresses are 44 bits and page size is 4K, the page frame number occupies 32 bits. Taking the 4 protection bits into account, each entry of the level-3 page table takes (32+4) = 36 bits. Rounding up to make entries byte (word) aligned would make each entry consume 40 (64) bits or 5 (8) bytes. For a 256 entry table, we need 1280 (2048) bytes.
The top-level page table should not assume that 2nd level page tables are page-aligned. So, we store full physical addresses there. Fortunately, we do not need control bits. So, each entry is at least 44 bits (6 bytes for byte-aligned, 8 bytes for word-aligned). Each top-level page table is therefore 256*6 = 1536 bytes (256 * 8 = 2048 bytes).
Trying to take advantage of the 256-entry alignment to reduce entry size is probably not worth the trouble. Doing so would be complex; you would need to write a new memory allocator that guarantees such alignment. Further, we cannot quite fit a table into a 1024-byte aligned region (44-10 = 34 bits per address, which would require more than 4 bytes per entry), and rounding the size up to the next power of 2 would not save us any size over just storing pointers and using the regular allocator.
Similarly, each entry in the 2nd level page table is a 44-bit physical pointer, 6 bytes (8 bytes) when aligned to byte (word) alignment. A 16 entry table is therefore 96 (128) bytes. So the space required is 1536 (2048) bytes for the top-level page table + 96 (128) bytes for one second-level page table + 1280 (2048) bytes for one third-level page table = 2912 (4224) bytes. Since the process can fit exactly into 16 pages, there is no memory wasted by internal fragmentation.
5664 or 8576 bytes for page tables, 0 bytes.
First, the stack, data and code segments are at addresses that require having 3 page table entries active in the first level page table, so we have 3 second-level page tables. For 48K, you need 12 pages or 1 third-level page table; for 600K, you need 150 pages, or 1 third-level page table and for 64K you need 16 pages or 1 third-level page table.
So the space required is 1536 (2048) bytes for the top level page table + 3 * 96 (3 * 128) bytes for 3 second-level page tables + 3 * 1280 (3 * 2048) for 3 third-level page table = 5664 (8576) bytes.
As the code, data, stack segment of the process fits exactly into 12, 150, 16 pages respectively, there is no memory wasted by internal fragmentation.
Problem 4
In keping with the RISC processor design philosophy of moving hardware functionality to software, you see a proposal that processor designers remove the MMU (memory management unit) from the hardware. To replace the MMU, the proposal has compilers generate what is known as position independent code (PIC). PIC can be loaded and run at any adress without any relocation being performed. Assuming that PIC code runs just as fast as the non-PIC code, what would be the disadvantaqge of this scheme compared to the page MMU used on modern microprocessors?
Solution:
Need solution.
Problem 5
Describe the advantages of using a MMU that incorporates segmentation and paging over ones that are either pure paging or pure segmentation. Present your answer as separate lists of advantages over each of the pure schemes.
Solution:
Need solution.
Problem 6
Consider the following piece of code which multiplies two matrices:int a[1024][1024], b[1024][1024], c[1024][1024]; multiply() { unsigned i, j, k; for(i = 0; i < 1024; i++) for(j = 0; j < 1024; j++) for(k = 0; k < 1024; k++) c[i][j] += a[i,k] * b[k,j]; }
Assume that the binary for executing this function fits in one page, and the stack also fits in one page. Assume further that an integer requires 4 bytes for storage. Compute the number of TLB misses if the page size is 4096 and the TLB has 8 entries with a replacement policy consisting of LRU.
Solution:
1024*(2+1024*1024) = 1073743872
The binary and the stack each fit in one page, thus each takes one entry in the TLB. While the function is running, it is accessing the binary page and the stack page all the time. So the two TLB entries for these two pages would reside in the TLB all the time and the data can only take the remaining 6 TLB entries.
We assume the two entries are already in TLB when the function begins to run. Then we need only consider those data pages.
Since an integer requires 4 bytes for storage and the page size is 4096 bytes, each array requires 1024 pages. Suppose each row of an array is stored in one page. Then these pages can be represented as a[0..1023], b[0..1023], c[0..1023]: Page a[0] contains the elements a[0][0..1023], page a[1] contains the elements a[1][0..1023], etc.
For a fixed value of i, say 0, the function loops over j and k, we have the following reference string:
a[0], b[0], c[0], a[0], b[1], c[0], ¡ a[0], b[1023], c[0]
¡
a[0], b[0], c[0], a[0], b[1], c[0], ¡ a[0], b[1023], c[0]
For the reference string (1024 rows in total), a[0], c[0] will contribute two TLB misses. Since a[0] and b[0] each will be accessed every four memory references, the two pages will not be replaced by the LRU algorithm. For each page in b[0..1023], it will incur one TLB miss every time it is accessed. So the number of TLB misses for the second inner loop is
2+1024*1024 = 1048578
So the total number of TLB misses is 1024*1048578 = 1073743872
Problem 7
A computer system has a page size of 1,024 bytes and maintains the page table for each process in main memory. The overhead required for doing a lookup in the page table is 500 ns. To recude this overhead, the comnputer has a TLB that caches 32 virtual pages to physical frame mappings. A TLB lookup requires 100ns. What TLB hit-rate is required to ensure an average virtual address translation time of 200ns?
Solution:
Need solution.
Discuss the issues involved in picking a page size for a virtual memory system.
Name one issue that argues for small page sizes? Name two that argue for large page sizes?
How do the characteristics of disks influence the selection of a page size?
Solution:
Need solution
Need solution
Problem 8
Consider a system with a virtual address size of 64MB (2^26), a physical memory of size 2GB (2^31), and a page size of 1K (2^10). Under the target workload, 32 processes (2^5) are running; half of the processes are smaller than 8K (2^13) and half use the full 64MB virtual address space. Each page has 4 control bits.
What is the size of a single top-level page table entry (and why)?
Solution:
What is the size of a single bottom-level page table entry (and why)?
Solution:
If you had to choose between two arrangements of page table: 2-level and 3-level, which would you choose and why? Compute the expected space overhead for each variation: State the space overhead for each small process and each large process. Then compute the total space overhead for the entire system.
Solution:
2014年10月1日 星期三
hard link&soft link
原理：soft link and hard link
目前常見的檔案系統ext3與ext4都是以ext2為基礎改良而來，除了加上journal（日誌）功能外，還有支援存取更大檔案、磁碟分區，以及避免檔案在磁碟內分佈離散等新機制。以下將以較單純的ext2這個檔案系統為例來進行說明。
ext2將檔案系統的屬性與內容分為inode（儲存檔案的屬性）與block（儲存檔案的內容）來儲存，其中，inode內包含了以下的檔案屬性資訊：
該檔案的擁有者與群組（owner/group）；
該檔案允許的存取模式（read/write/execute）；
該檔案的類型（type）；
該檔案建立或狀態改變的時間（ctime）、最近一次的讀取時間（atime）、最近一次的修改時間（mtime）；
該檔案的大小（size）；
該檔案的特殊旗標（flag），如SetUID。
而所有檔案要存放在磁碟內，都必須先取得一個inode，再透過inode來取得該檔案在此磁碟上的位置。對unix-like系統有使用經驗的朋友一定有用過symbolic link（或稱soft link，為方便讀者記憶，以下皆稱soft link）。所謂的soft link，就是一個包含路徑（path）的一個inode，但該inode並沒有指向到實際的block位置，因此，當symbolic link的目標路徑消失時（如：刪除、搬移等），則該link就會變成一個無效的link。
許多人會將soft link當成類似windows作業系統下的“捷徑”來使用，或是當硬碟空間不夠時拿來跨硬碟掛載，是一個很實用的功能。但事實上，在unix-like下的檔案系統還有另一種大家較不熟悉的link，稱作hard link（這也是symbolic link會被稱為soft link的原因之一），兩者之間的差別在於：Hard link會與link的目標使用同一個inode，所以其指向的磁碟的實際位置以及檔案全部的屬性和原來的檔案一模一樣。
一個檔案可以有無數個hard link，但對磁碟來說，存取的都是相同的一個檔案。是故所有的讀、寫甚至是屬性修改都是針對同一個檔案、磁碟位置來操作。
如果想要知道檔案是否為hard link檔案，只要使用指令ls -l的時候便會顯示該檔案的link count數，代表該檔案的hard link有多少。刪除一個hard link，hard link count就會減一，直到刪除至link count為0後，才是真正的將該檔案自磁碟內刪除。
需特別注意的是，因為hard link是使用同一個inode來取得磁碟的實際位置，而inode的分配是以partition為單位，不同的partition內的inode就不會有關聯，因此，hard link功能只限於在同一個partition內使用；如果是使用複製或搬移到另一個partition的情況下，就會在另一個partition建立實體檔案並消耗磁碟空間。此為hard link原理所造成的限制，也會是rsync、rsnapshot使用hard link技術備份時的限制。
Hard Link：在前一節當中，我們提到檔案的讀取方式為：(1)先由一層一層的目錄取得檔案相關的關連資料，(2)再到對應的 inode 取得檔案的屬性，以及檔案內容資料所在的 Block ，(3)最後到 Block area 取得檔案的資料。那麼 hard link 怎麼製作檔案的連結呢？！很簡單， Hard Link 只是在某個目錄下新增一個該檔案的關連資料而已！
舉個例子來說，我的 /home/vbird/crontab 為一個 hard link 的檔案，他連結到 /etc/crontab 這個檔案，也就是說，其實 /home/vbird/crontab 與 /etc/crontab 是同一個檔案，只是有兩個目錄( /etc 與 /home/vbird )記錄了 crontab 這個檔案的關連資料罷了！也就是說，我由 /etc 的 Block 所記錄的關連資料可知道 crontab 的 inode 放置在 A 處，而由 /home/vbird 這個目錄下的關連資料， crontab 同樣也指到 A 處的 inode ！所以囉， crontab 這個檔案的 inode 與 block 都沒有改變，有的只是有兩個目錄記錄了關連資料。
一般來說，使用 hard link 設定連結檔時，磁碟的空間與 inode 的數目都不會改變！由上面的說明來看，我們可以知道， hard link 只是在某個目錄下的 block 多寫入一個關連資料，所以當然不會用掉 inode 與磁碟空間囉！(註：其實可能會改變的，那就是當目錄的 Block 被用完時，就可能會新加一個 block 來記錄，而導致磁碟空間的變化！不過，一般 hard link 所用掉的關連資料量很小，所以通常不會改變 inode 與磁碟空間的大小喔！ )
由於 hard link 是在同一個 partition 上面進行資料關連的建立，所以 hard link 是有限制的：
不能跨 Filesystem；
不能 link 目錄。
Symbolic Link：
相對於 hard link ， Symbolic link 可就好理解多了，基本上，他就是在建立一個獨立的檔案，而這個檔案會讓資料的讀取指向他 link 的那個檔案內容！由於只是利用檔案來做為指向的動作，所以，當來源檔被刪除之後，symbolic link 的檔案會『開不了』，會一直說『無法開啟某檔案！』。這裡還是得特別留意，這個 Symbolic Link 與 Windows 的捷徑可以給他劃上等號，由 Symbolic link 所建立的檔案為一個獨立的新的檔案，所以會佔用掉 inode 與 block 喔！
由上面的說明來看，似乎 hard link 比較安全，因為即使某一個目錄下的關連資料被殺掉了，也沒有關係，只要有任何一個目錄下存在著關連資料，那麼該檔案就不會不見！舉上面的例子來說，我的 /etc/crontab 與 /home/vbird/crontab 指向同一個檔案，如果我刪除了 /etc/crontab 這個檔案，該刪除的動作其實只是將 /etc 目錄下關於 crontab 的關連資料拿掉而已， crontab 所在的 inode 與 block 其實都沒有被變動喔！不過，不幸的是，由於 Hard Link 的限制太多了，包括無法做『目錄』的 link ，所以在用途上面是比較受限的！反而是 Symbolic Link 的使用方面較廣喔！好了，說的天花亂墜，看您也差不多快要昏倒了！沒關係，實作一下就知道怎麼回事了！要製作連結檔就必須要使用 ln 這個指令呢！
http://www.science.unitn.it/~fiorella/guidelinux/tlk/tlk-html.html
訂閱：
文章 (Atom)