 |
Questions from the Cards
Week 5: Process Synchronization
|
Where are we grabbing the lock from in the ARM _lock_acquire? Is the lock passed in from the C function stored in r0? Yes. The argument passed to _lock_acquire() in the C code appears in the assembly routine as the value in r0. In this case, that means r0 contains the address in memory for the lock. Why do we have two midterm exams? If we had one, it would cover too much in one exam and place too much pressure on one 50 minute performance. If we had three, it takes too much class time and makes it VERY hard to schedule projects around exams and holidays. Are we having an exam next week AND another project to complete? No, the next project is due in two weeks. See class calendar How should we prepare for the exam? See hints and years' of previous exams at http://www.mscs.mu.edu/~georgec/OpSys/examMid19A.html I'd read the book more than study class notes. I'd spend quality time with several previous exams. How does the OS handle processes with threads? Does it distribute the threads across multiple cores? Usually, we prefer all threads belonging to one process be running on the same core to take advantage of local memory caching. If multiple processes are running on multiple cores, and each process has multiple threads, how is the operating system able to handle potentially thousands of operations trying to access four cores at the same time? EXCELLENT question. That is THE KEY to good performance from multi-core processors. The problem is compounded by the fact that a single modern deeply-pipelined core may make 6-10 memory accesses PER CLOCK CYCLE. The most important strategy uses multi-level local (to each core) caches. Then, cache consistency and coherency are challenges. -- George What chapters should we read for this exam? See hints and years' of previous exams at http://www.mscs.mu.edu/~georgec/OpSys/examMid19A.html What other evil ways can you make this system break down? How many ways can you find to make errors? You could signal when you should wait and vice versa. You can wait and/or signal on the wrong semaphore. You can leave them out all together. Actually, you've given me an idea for a tricky C question for the exam! How big are typical buffers? Depends VERY MUCH on the application. In some applications, a single location is enough. For this hypothetical real-time arrhythmia detector, the consumer may want to acquire its data in increments of a second or so to get about one heart beat, so the buffer would need 1,000+ available slots. For remote planetary exploration, image transmission may be delayed for days, and the buffer must be many Gb. Is there a downside to using two semaphores in this kind of situation? If the OS has only a few semaphores, you are using twice the resources. In a sense, the programming complexity is worse because there are more ways for the programmer to screw up. Enjoyed the interactive portion of the class Thank you. We'll be doing more as the semester goes along. -- George Project 1. We need to test to create() and get that working before moving on to cxtsw(). How do we test that? Is running the test cases enough? The testcase '0' given in testcases.c calls create() but does not ready() the process for ctxsw(). Instead, it prints out some of the information about the process you have created. I would suggest enhancing this code with a printout of your process's shiny new stack to see if the contents match the design you will send into ctxsw(). No, running the default testcases is not enough. 2. How do we test only the create.c file without testing ctxsw()? As long as you do not ready() a process that has been create()ed, you do not need to test ctxsw(). 3. What test cases beyond the ones provided should we test for? Different numbers of arguments passed to create(). Process termination. Basically, exercising the possible kinds of processed that can be create()ed with different arguments passed into create(). 4. For the project, when displaying the name of the process in create.c, is strncopy() necessary? My partner and I cannot figure out how to display the name. The name of the process should not be displayed in create(). You can see an example of displaying the process name on line 54 of testcases.c. The strncpy() function is recommended for copying string literals, such as when initializing the name field in the process control block. 5. "Initialize process context" means to fill the stack with arguments of the create() function, correct? I consider the process context to include the initial values you expect to find in any of the registers when the process begins running for the first time, as well as its initial stack. 6. Can homework be due at midnight for lecture discussion time? By having projects due at noon, we remove one temptation for skipping the class intended to help you with the NEXT assignment. Synchronization 11. What did programmers do in the 15 year gap before the race condition issue was solved? Peterson's solution is a software solution. While the theoretical computer science community was working toward a software solution, the computer architecture community developed and refined several hardware solutions including TestAndSet, Swap, and semaphores. 12. We said we have to protect critical sections of code from interrupts. Are there other ways the critical regions need to be protected from or affected by? Critical sections need to be protected from simultaneous access. On a single core of ten years ago, disabling interrupts, doing the critical section code, and re-enabiling interrupts solves the mutual exclusion problem, but it causes other problems. On modern high-performance cores that literally execute instructions from two or more threads in the same instruction cycle, mutual exclusion is not achieved by disabling interrupts. Even more so with processes running on separate processors. Synchronization primitives such as semaphores have generalizations that work more generally, but they do not solve all problems in a distributed environment. Consider what must be happening behind the scenes for several people simultaneously editing a GoogleDocs document. 13. Do there exist other critical sections that do not include counters? Yes, other examples include database updates and collaborative updates of shared GoogleDocs documents. 14. How does TestAndSet only take one cycle of execution? By being implemented as a hardware instruction. The TestAndSet instruction
15. Is TestAndSet really indivisible, or is it just treated that way? In many processors, TestAndSet is really indivisible, as the answer to the previous question suggests. On our ARM processor, you could SIMULATE indivisibility by disabling interrupts, coding the TestAndSet logic in C, and re-enabling interrupts. That is exactly what you will do for the primitives you build in Project 6. 16. What should I have gotten from today's lecture? o Design template for a bounded-buffer solution to the Producer-Consumer problem
-— George 1. Should we print out the entire stack or just what we added in create.c? Just what you added in create(). 2. Are we writing the code for aging, or we just checking it "on" in reached()? You are writing the code for aging. 3. Is there a particularly good way to share a folder of your homework with your partner on Morbius so that they have permissions, but it is just them and not everyone? Yes. We can create unix groups for each team to share files. 4. Is there on any update on TA office hours? The UPE tutoring hours are now posted. I don't have office hours from the TAs yet. 5. Is there any chance we can change the schedule of assignments to being assigned introduced on Friday and due on Thursday at noon? Most students are getting the intro on Friday in lab and really getting into it on Sunday night, leaving only Monday to ask questions. The goal is to introduce everybody to the project on Wednesday, so that by Friday you've started and have useful questions and can dig into the details in lab. If we wait to assign it until Friday, then everybody has lab *before* we've introduced the project to the whole class. Which means lab devolves into me just repeating my introduction three times on Friday morning, and still no one gets started right away. If everyone started on Thursday night instead of Sunday night, Friday lab sessions would be a much more productive time to answer detailed questions, help debug, code up bonus test cases together, explain what TA-Bot means by the first runs from Wednesday and Thursday night. My Monday night office hours would be all about putting on final touches, cracking that last elusive bug, rather than trying to dig in five days after we've started talking about it. I know -- it seems like an unrealistic dream of mine. But it actually used to work this way about a decade ago. When most of the class waits until Monday night to start, you've lost the last chance to ask useful questions in class or lab, and my office hours are a traffic jam of discouraged and confused students. Major errors in the project spec or TA-Bot don't come to light until Tuesday, after TA-Bot's second-to-last run, and the day before the week-long assignment is due. The problem is not which day we introduce assignments or make them due. The problem is that all of the support mechanisms are designed to help students who start in the first half of the week after it is assigned. These projects are designed to take two people, working an hour or two each night, several days to understand all of the conceptual roadblocks and code hurdles we've built in deliberately. Time to puzzle over the hard parts, as well as the mental work of going away to do something else, and then coming back to it the next day -- these are assumed as part of the learning model. When you compress it all into the last two nights, you make fewer long-term mental connections, have shallower insights, and do poorer work, not to mention having many fewer opportunities to have TA-Bot evaluate your progress. 6. What is the best way to prepare for the exam? Is there an emphasis on lecture notes, textbook, or homework? See 2018 Exam 1, where there are 12 years of previous exams, solutions, and preparation hints. Read and familiarize yourself with the directions so you do not have to take the time to read them during the exam. If you study previous exams, you might observe
7. How was your day? George: A bit more harried than usual, but I think I helped a couple people today. That's why I get up. Dennis: Stressful. I was working on campus until past 3am on Monday night, caught the baby's cold by Tuesday, and have to get everything done before I leave tonight to run a CS teacher workshop in the Eau Claire area tomorrow. But I enjoyed introducing a new gerrymandering unit in COSC 1020 this morning, so it was still a pretty good day. Thanks for asking! 1. Rank the difficulty of the test 1 - 10, please. 7-8, in the sense that the class mean usually is between 70 & 80. Previous exams include mean, median, standard deviation, and histograms of scores, and mean scores for each question. But you may judge the difficulty for yourself from study of previous exams. 2. Are questions on the exam more about the lecture or the readings? Readings (my opinion; yours may differ), but see previous exams. 3. Is the extra credit worth up to 3% for each time we go? No. Each lecture is worth 1% extra credit. 4. Can we attend more than one of the extra credit talks? Yes. 5. Could you give more context behind the "evil thoughts" behind essentially hijacking the processor by not sending the signal to a semaphore? Maybe an example? Suppose you and I each have a program running. Perhaps you are writing the HTTP server, and I’m writing the database engine, and we agree to share a semaphore to coordinate database access from the web server, e.g., to get user names and passwords. I think MY work is more important than yours. If my program wait()s for our shared semaphore, but never signal()s it, I can force your program to be locked in a wait state from which it will never exit. Essentially, I have eliminated one competitor for CPU time. To an un-informed boss, it may look like my program works, and yours doesn’t, so you get fired, and I get a pay raise. Is that scenario evil enough? 6. In non-programming terms, semaphores are things used to signal various things. Is this why semaphores are named in this way? Yes. Semaphores probably were named after railroad signals that tell a train whether it is safe to proceed. We wait for a semaphore to be raised (> 0). After we have passed our critical section, we signal or raise it so the train/process following us can enter its critical region safely. 7. What exactly is the S value passed to wait() or signal()? A memory location which stores an integer value. 8. How should a semaphore value be initialized? As appropriate for the application. A binary semaphore used to control entry into a critical section usually is initialized to 1 so the first process to approach its critical section is allowed to enter. A counting semaphore, as in our final example today, is initialized according to the logic of the cooperating processes. We initialized countAvailableItems as 0 because at start-up, there are no available items, and we initialized countAvailableSpaces as 5 because at start-up, there are 5 spaces available in the buffer. 9. Why is the infinite while loop bad in mutual exclusion? The infinite loops in my examples have nothing to do with mutual exclusion. They are intended to suggest that many processes in operating and embedded systems are supposed to run forever. 10. So when producer and consumer communicate, it is advised to use blocking receive? Yes, if we use message passing as our buffer, and we want the consumer to delay processing until it has data to process. 11. Are semaphores the best solution to the producer-consumer problem? "Best" depends on further context. For applications as we are suggesting to run on a single processor, properly used semaphores are relatively simple, and they are fast. Message passing usually takes *much* longer, but it may be easier to understand, design, and maintain. Across multiple, especially distributed, processors, message passing may be the only choice. 12. Can more than two processes use one semaphore? Yes. — George Contents:
Project1. Will Dr. Brylow be away for any more conventions for the rest of the semester? Sadly, yes. As research-active faculty at Marquette, 60% of my work week is supposed to go towards research and service; only 40% of my job is actually teaching. As the primary shepherd of three different current National Science Foundation grants, totaling about $2.3 million, plus the director of Marquette's regional partnership with Code.org, I have a heftier number of obligations that interfere with my teaching schedule than a lot of other faculty. I apologize for the disruptions, but I appreciate your patience, and I'm very grateful that George and the teaching assistants can cover for me when necessary. I'll be at the SIGCSE conference in Seattle March 8-10, to present as part of a panel on undergraduate research experiences. I'll be at the NSF Broadening Participation in Computing meeting in Denver March 27-28, as director of two funded projects under that umbrella. I'll be at the Wisconsin Computer Science Educators Summit in Green Lake, WI, May 3rd, which we are the primary sponsor for. In addition, I have to be at the state capital for the CS K-12 Standards Writing Committee meeting next week Wednesday (2/22), so I'll miss your exam, and there are two more Fridays in March where I'll need to miss Lab because of workshops for elementary school computer science teachers. 2. Will we eventually run processes that aren't linked to the kernel at compile time? No. Independent linkage requires a full system-call API and some kind of object code loader mechanism. We will not have time to build either into our lightweight operating system this term. It would be a fantastic project for the graduate level version of this course. Note that it is very common for embedded operating systems to have their processed linked into a monolithic kernel as we are doing. 3. What do you think about the Rust programming language? Rust is another in a long line of C derivatives that offer some stronger safety guarantees while still remaining focused on low-level system development. I think it is great that computer scientists continue to build bigger and better mousetraps like this. It is an interesting philosophical question to ponder what *would* it take to dislodge C as the tyrannical king of systems programming? By the way, porting our Embedded Xinu code base to a new systems language like Rust would make for a phenomenal summer research project... 4. In kill.c, there is a switch statement that intentionally falls through. Is this intentional? If so, can you add a comment for next year explaining why? Yes. No. Falling through is the expected default behavior in both C and Java. That is why the non-mandatory "break" statement was invented, to give programmers the option. The first case doesn't really fall through, because resched() won't ever return to this killed process. So the "break" would be unreachable and redundant. The second one falls through because both cases need to set the state to PRFREE. This switch statement will get more interesting cases added as the semester progresses. 5. Are the load action and the store location at different offsets? Yes. 6. Should the create() function be calling ctxsw.S as a way to switch processes? No. Creation is an independent action from readying or rescheduling. There are many situations in which we might like to create several processes before readying any of them to run. General7. Why did you briefly mention the importance of desk checking in today's lecture? a) What we did today was a form of desk-checking. b) To really understand the code examples in the book showing the operation of various synchronization primitives, careful desk-checking is essential, especially identifying problematic scenarios. c) Exams sometimes include a question requiring careful desk-checking, especially identifying problematic scenarios. d) You will be successful in your project *far* faster if you practice careful desk-checking, especially identifying problematic scenarios. 8. Will there be more demonstrations with food? Come and see. Yes, active participation *always* is more effective than passive listening. 10. Was the first multitasking operating system considered a major breakthrough at the time, or just a simple logical progression? MAJOR breakthrough. When I was in college (College of Wooster, Ohio, in 1965), I would sign up for one hour alone with the college's IBM 1620 computer. I'd turn it off, turn it back on, type in a short sequence of numbers triggering an infinite loop to zero memory, turn it off, turn it back on again, load a (Fortran) compiler stored on 300 punched cards, load in a 10-20 statement Fortran program from cards, compile it, punch a binary desk, load the binary card deck, and watch my program run (or not). If I was lucky, I'd get 3-4 trial runs in my hour, and I could come back again next week. CAREFUL DESK-CHECKING MATTERED. When I got to graduate school (Michigan State University, 1969), we'd submit one deck of punched cards (Fortran source code) in the evening. Over night, student programs were run concurrently with the University's data processing on a CDC 3600. Multi-tasking! In the morning, we'd pick up greenbar 132 character-wide printouts, and spend all day making corrections. One run per 24 hours. CAREFUL DESK-CHECKING MATTERED. When I got my first faculty job (University of Nebraska-Lincoln, 1974), they were phasing out a similar card-based program submission system in favor of an terminal-based remote job submission system. Several hundred terminals were connected to the University's central IBM 360 mainframe. We edited programs on line using an editor that made vi seem like heaven and submitted them to a batch queue. If the machine was lightly loaded, results might be available in a hour or so. The day CS 001 projects were due, 10-15 hours. Hundreds of terminal sessions and tens of programs ran apparently simultaneously! GLORIOUS. One run an hour beat one run per day, but CAREFUL DESK-CHECKING MATTERED. 11. How can you tell from sample code if it uses memory sharing or message passing? Read the code. To use either memory sharing or message passing, the program *must* make calls to operating systems services, either directly or indirectly. 12. What is the robot in Dr. Corliss's outlook profile picture? It is a member of Dr. Williams' HEIR lab 13. How are you? You asked: I am BLESSED to be here. I pray that you find a career that is as satisfying to you as this one is to me. If you think that is BS, ask Dennis. I could complain of the physical ailments of my age (I assume you can do the math from my entering college in 1965), but complaining does not cure them. I look forward to advances in embedded systems for medical technology with greater anticipation and appreciation than I used to. Producer-consumer example14. In modern day processors, can you interrupt an instruction halfway through? Yes. Modern instruction processors are deeply pipelined. The exact meaning of "one clock tick" is ambiguous, but instructions are interrupted in the middle of their execution all the time. The hardware does its best to hide that and make it *appear* that an instruction either never started or else completed. 15. Can one process get interrupted while it is in a weight state doing nothing? I'm assuming it can happily happen, but does it? Busy wait. If you know it will only last a few cycles, busy waiting is more efficient than invoking your context swap to switch to another process and then switch back. Busy wait is fine if there is not much other work for the processor to do. That often is the case for simple embedded systems. A wonderful alternative to busy wait in your current project would be to relinquish the processor by calling resched(). In a system with preemptive scheduling, a timer generates an interrupt, the busy waiting process is swapped out, and another process comes in. That interrupt and swap is timer-driven; it has nothing to do with what work the process is (or is not) doing. The usual implementation of semaphores places the waiting process into an operating system wait state and calls resched() to transfer control to a different process. 16. For the producer consumer example, is there an interrupt that happens during the while loop? Or is it like a flag that says the processes executing nops? Or something different? If it is an interrupt, when does it execute? See previous question. In a system with cooperating processes (your current project), the busy wait would busy wait forever. Nothing good would happen, unless we replace the busy wait with a call to resched() to relinquish the CPU. In a system with preemptive scheduling, yes, an timer interrupt eventually (sub-millisecond, typically) would halt the infinite busy waiting loop. The busy wait is *not* executing nops. It is executing labelA: compare(counter, 0) jump if false to labelA 17. Does a pretzel get removed from the buffer location as soon as it is put in the example? Depends. The point of using the buffer is to provide an asynchronous channel of communication. It *might* be that the producer runs until the buffer is filled. Then the consumer runs and empties it. It *might* be that they alternate, producer inserts, consumer removes. Repeat. In sensor reading applications, the producer is interrupt-driven, and the consumer runs much less frequently. If you are *really* paying attention, you should see that the bounded buffer of this example can be entirely replaced by an operating system message queue, *provided* the queue is unbounded, or else there is a mechanism to stop the producer when the message queue is full. 18. If we use in and out for the local counters, with this example still work? In this example, in and out *ARE* local counters. The critical section involved the *shared* counter. Any solution to the producer-consumer problem requires *some* shared resource. It can be blatant, like the shared counter in our example, or it can be camouflaged, as in the message queue solution suggested in my response to Question 17. The sharing can be masked by a monitor (see Section 5.8). Synchronization19. What is a semaphore? The subject of Friday's discussion. Or read Section 5.6, as you *should* have done before today's class. — Dr. C. Contents: o General o Semaphores o Monitors General1. What does (out <> in) mean, and is it legal C code? No. Should have been (out != in). I have corrected that and the other coding errors we noticed in class today. I forget in which language "<>" is "not equal." 2. Can you give a specific example of desk testing? Most of the in-class examples of walking carefully through code segments has been a type of desk-checking. The idea is to "execute" your code "by hand," paying attention to every detail. One advantage over computer-based testing, especially for testing cooperating processes, is that *you* control when process interrupts occur, and you can force them to occur at the worst possible times. Repeatedly. 3. Can you give the right side of the room a chance to be the consumer so we get candy?
The semester is not over. Can your side put your hands up and volunteer? 5. What is your favorite theater candy? I'm not sure what you mean by "theater candy." My favorite candy is the piece in my hand. If you were a student in this OS course, what would be your dream job / field of work? a) The one I have
Semaphores6. I am not understanding the magical qualities of semaphores. Can't you just have counters to track resources without implementing a semaphore? The point of these discussions is that there is no magic. The real problem is for two processes to cooperate with no possibility of a race condition. The danger is in uncontrolled updates to a shared resource. Counters local to a single process are safe, but then the process with which you are trying to cooperate does not know what you have done. My monitor solution used only counters local to the Buffer process, but it used operating system messages to discipline the communication. A semaphore is a shared memory location that the operating system and hardware protects from undisciplined access, so that it can be used to control less-disciplined access. Semaphores are one tool for allowing programmers to control access to a shared resource (e.g., counter, in most of today's examples). 7. In the second example, is there any danger with the function for the process using the S value (the parameter) of the same function that was called in another process? No. As a parameter, the actual value is passed in. If wait(S) represents an actual hardware instruction, the value to be passed must be copied into a register before the instruction is called. 8. Was the second example using counting semaphores better practice or more efficient? I consider it better practice because it is easier to understand. The challenge with Chapter 5 synchronization primitives is that their success depends on programmers' care. Rigorous testing is *very* difficult because faults come from very unlikely sequences of events. 9. Can you have a boolean/integer/float type semaphore to save memory space? Float semaphores do not make sense. At today's cost of silicon, any savings of a boolean over an int is false economy. 10. I think we have truly beat this to death, but it was still helpful. Hopefully. 11. When is it appropriate to use a mutex over a semaphore, if ever? A semaphore is one means of implementing a mutex. The issue is ease of correct use. 12. Are there priorities in semaphores? No. 13. You said the hardware functions in the semaphores were uninterruptible. If this is the case, how was the weight interrupted? Or is it just the increment decrement that is uninterruptible? Excellent observation. Hope you got a Milky Way. 14. Is there a way to break the producer consumer model of semaphores used in class? What is it? Not that I know of, but I'd bet there is. 15. Is being stuck in the wait for a semaphore different than a busy wait? Depends on the implementation, as we went on to discuss in class. 16. Can you initialize the semaphore to be less than zero just to be used as a flag? I suppose so, unless either the OS or the hardware enforce non-negative (e.g., unsigned). MonitorsJava provides a monitor-like abstraction with the keyword synchronized, which signals the Java Virtual Machine that it should enforce that only one of a set of synchronized functions from a class may be in execution at the same time. 17. Are monitors just a more efficient semaphore?
The important efficiency here is *programmer* efficiency: How much time does it take a team of developers to produce *correct* code? Often, tools are more useful for what they *prevent* us from doing than from what they *allow* us to do. You might prefer Java to C because Java prevents you from doing many "dangerous" things? Semaphores (or TestAndSet or other primitives) require considerable care on the part of programmers to get right. Monitors seem to have some (relative) ease-of-correct-use advantages. Many systems rely on message passing for all inter-process communication. It is slow, but the model is easier to understand. CPU efficiency? Monitors probably are less efficient because: 19. Is the entire monitor code critical? Yes. And a larger critical section means a process (probably) requires longer to execute it, forcing other processes to wait longer than is logically necessary. 20. You say, "Many systems rely on message passing for all inter-process communication. It is slow, but the model is easier to understand." What makes this process so much slower than the semaphore model? Doesn't it eat less of the CPU because as you scale out, there are so many fewer wait loops? This specific problem really interests me. The issue comes down to looking at the cost of each process synchronization. First, suppose the system is lightly loaded, so it is rare to conflict for shared resources. Then there will be very few waits, whether busy or in what queues, so each semaphore call is at most a handful of instructions. To pass a message, you have to allocate space for the message itself, copy content in, call the OS, put the message into a message queue. The receiver calls the OS, retrieves the message, and copies the contents into its local address space. Probably AT LEAST a hundred instructions for a small message payload. Messages are slower. If the system is heavily loaded, there is a lot of waiting anyway, so again the question is the cost of the communication. In the next few projects, you will program both semaphores and messages, and you will see how much more work the CPU must do for each message. Besides having a model we understand, message have the advantage that thinking about them carries over without change to multi-core machines, to multi-machine clusters, or to the world-wide Internet. The mechanics of message delivery is different at different spacial scales, but the logic of the application is the same. Of course, we want speed, but fast wrong answers are dangerous. Correctness is easier to achieve if system architects understand, and messages are easier to understand than disciplined use of synchronization primitives. What is it about this problem that interests you? 21. What does this have to do with embedded systems? Right. I did not say the magic words, "embedded systems" today, but I *did* make a big deal on Monday that cooperating processes are at the heart of many embedded systems, cars, robots, medical devices, etc. Will there be a review session before the exam? No. See previous exams with solution suggestions at Exam 1 What happens when two processes both turn off interrupts at the same time? In a ONE-processor environment: Cannot happen. Only one process is running at a time. In a multi-processor environment: They each turn of interrupts on their own processor, which does not help with mutual exclusion. What are "atomic, indivisible hardware operations"? Single hardware instructions that cannot be interrupted. If the instruction begins its execution, it is guaranteed to complete its execution with no other instructions being executed in between. In the old days, most machine instructions were executed in a single clock cycle, and hence were atomic. In modern deeply pipelined processors, it is a challenge to computer architects to provide both atomic, indivisible instructions AND good performance. How can you wait for the TestAndSet without wasting CPU resources? By placing the process into a Wait queue, as we will discuss with semaphores on Friday. Are there other ways to solve mutual exclusion? Yes. The book mentions swap(), semaphores, and monitors. In practice, one powerful strategy is to make the critical section owned by a single process. Other processes update by sending messages, and the message-passing machinery ensures that the single process receives only one message at a time. That is how your print spooler works. What is "boolean" in C? It isn't. What I showed on the screen was PSEUDO-code. Where did you get the quad-copters? 1) Would it be useful to instead of reschedule(), PRSUSP a current process to wait for something else to put it into the ready list? The create() function does exactly this, leaving a newly created process in PRSUSP state until someone (maybe a different process, maybe the same process) calls ready() to move it to the PRREADY state. 2) Is there a quick way/reference to learn ARM? I only know MIPS. ARM and MIPS, while different architectures, have much more in common than
a lot of other processors. There are quick reference cards for ARM
available, such as
3) You showed untarring at the beginning. Will we have to do this, or was all of this code included in the last assignment? There is new code in the xinu-hw4.tgz tarball (or GitLab repository) that was not included in the previous assignment. 4) Does the new tarball have the code for the last assignment completed? No. You need to provide your own synchronous serial driver in the kprintf.c file. Likewise, you will need working context switch and create() functions in the assignment after this one. As a matter of instructional philosophy, there is always a tension between designing standalone lab assignments that fully scaffold student learning, and designing a coherent sequence of assignments that build on each other and allow students to complete a truly impressive artifact by the end of the sequence. In this course, I lean towards the latter approach, because I want you to be able to (modestly) brag to your future employers that you built most of your own embedded, preemptive multitasking operating system with device drivers, resource management, and synchronization primitives. Sounds a lot more impressive that way, and gives you the opportunity to see the impacts of your own design choices in later stages. But that does mean that each assignment has something essential in it that you need to get working for the subsequent projects. For kprintf(), you need to have basic serial input and output working, but kcheckc() and the kunget() stuff is not on the critical path. For this one, you need to get cooperative multitasking working, but argument passing and some of the finer details of the PCB contents can be fine-tuned later. If you don't have basic input and output working in your kprintf(), come see me ASAP and we'll get you straightened out. 5) Will we ever get access to your completed code, such as for kprintf.c, so we can fix code and learn what we may have done wrong? No. See above. I'd prefer to teach you what you may have done wrong without just handing you the solution. It would be sloppy teaching on my part, and not as helpful for you to develop diagnostic and debugging skills that you'll need in the real world, when there isn't someone standing nearby with the correct answer in their pocket. Still can't get it working? Come see me, and we'll work on it until we get it. 6) Which assignments are in assembly? This is the only Operating Systems assignment that touches on assembly, and you will only use assembly in the ctxsw.S file. 7) What is the different between preemptive and non-preemptive multitasking? From the programmer's perspective, the difference is that you must add periodic calls to resched() or yield() in your code to get non-preemptive multitasking to work, whereas preemptive multitasking works whether you've designed your code to participate or not. (So, for example, your solutions to the first two Linux assignments contained no code for yielding the processor, but the resulting programs automatically participated in preemptive multitasking all the same.) From the Operating System's perspective, non-preemptive multitasking is totally at the mercy of the individual processes, which may cooperate to achieve multitasking or not. Preemptive multitasking is something that the O/S may impose on processes totally unaware of multitasking at all, because, in a word, the O/S "preempts" the process when it thinks it time to be someone else's turn. 8) Do real embedded systems use cooperative multitasking if all of the programs that could run are known? Yes. When the system is small enough to be designed by a single benevolent dictator who can ensure that all processes will cooperate and share the processor effectively, cooperative multitasking is a great, low-overhead solution. 9) Should we implement create() or ctxsw() first? Create(). You can run create() and print out the resulting PCB and stack contents without ever trying to switch contexts to another process. You cannot possibly succeed in a context switch until your create() is more or less working. 10) What lives in a queue that you could muck up? In our O/S, the readylist queue contains the list of processes that will get run next. If you screw up the queue structure, your O/S may attempt to context switch into a non-existent dimension, possibly endangering our space/time continuum, and certainly crashing your O/S. 11) What was the beautiful thing about a return? In resched(), there is a call to ctxsw() before the return statement. The context switch function is a very special function indeed, since it opens the door to perhaps arbitrarily many other processes getting the opportunity to run on the processor before switching back to the original process and returning to the last statement in resched(). When it works, it is a beautiful thing and the circle of multitasking continues. 12) Does killing a process kill all of the process's children? Depends on the operating system. In our embedded operating system, no. Process control blocks do not even contain information about parent and child processes, so it would be hard to implement without adding those additional fields. Linux provides mechanisms both for killing an individual process, and for killing all of its children as well. 13) Can a process be resurrected (i.e. is there an opposite of kill?) In the simplest sense, no. Kill usually frees up the process resources and memory, and this usually is not a revocable operation. On the other hand, when we migrate processes from one processor to another, this is kind of analogous to resurrecting a process that was killed elsewhere. But the O/S has to take very careful notes as it is killing and transferring the process for this to work. 14) What happens if you kill() the Null Process? Do *not* kill the Null Process. The Null Process is eternal. If the Null Process is not eternal, then the O/S can potentially drive right off the cliff when it tries to context switch to the next thing and there is no next thing. There is code in kill() specfically to prevent this case: if (... (0 == pid) ...) { return SYSERR; } 15) Is the tarball on Morbius ARM, or do we need to wait for it to be uploaded? (Last time the MIPS version was still up.) The tarball is ARM. I have archived all of the stale MIPS tarballs from last year, so this should not happen again. 16) What are the odds of one of us bricking one of the Pi's? Exceedingly low. None of the hardware peripherals is particularly brittle, and the code for overwriting the SD-card memory is not included in the student kernel. Under the "million monkeys" theorem, it is still possible, but I would be surprised to see it during the remainder of my career. 17) Are either of you doing any interesting research projects? I'll let George answer in detail, but in summary, yes he is. I've got projects in the fire related to embedded systems curriculum
we're deploying in area high schools, extensions to the existing
Systems Lab infrastructure, an engine for developing serious educational
games, and a new project on embedded solar energy exploration kits.
You can see more about both of our current projects at
18) Comparatively do you feel that computer literacy has increased/decreased over the past 10 years? Do you foresee a time that computer systems will become too complex for students to get even a fundamental education within the four-year cycle? Basic computer literacy is certainly going up, as evidenced by current students' facility with systems that leverage mobile devices, cloud computing resources, and ubiquitous data collection. But at the same time, students don't seem to be coming in the door of Marquette with either more or less of a grasp on the fundamental computing concepts that underlie these systems. That seems to have stayed about the same, although the number of interested students is increasing notably, and that is a great development to see. I do worry about the ever-increasing complexity of systems relative to the average undergraduate's initial starting state. There is far more for me to teach COSC majors now in 4 years than there was when I was an undergraduate, and that necessarily means spending less time on some important things that I got to see in more depth as a student. But the result of that pressure is the predictable splitting of computing majors into more specialized chunks: COSC, COEN, BIOC, COMA, whatever IT majors over in Business are called; the MSCS Department is launching new undergraduate majors in Data Science and Bioinformatics next year. Each of these is an implicit admission that there is already far too much to squeeze into a single 4-year degree, even before we start on specialty areas. The other result is that we raise the level of abstraction we use in the existing degree programs. We no longer have students assemble a program into machine code by hand at least once, or write self-modifying code in COSC courses. In O/S, George and I will spend less time on Virtual Memory hardware and software support than we used to, even though it is still everywhere. Even in the lab assignments, we've axed two of the major O/S components we used to have you build to get to useful networking code by the end. 19) A mechanical student inquired as to why all of our objects/functions are collapsed (GNU, MIPS, PCB, etc.). What do you think is the underlying psychology of this development? In part, I think it is that new, more abstract concepts are coming up in computing a lot faster than our language of concise technical terms can keep up. Mechanical Engineering went through the same process, but over a longer period of time, and starting centuries ago. In the same way that the number of IP addresses on the global Internet is exploding, the number of digital and computing artifacts that we are creating and naming is increasing apace. We are by no means alone, and other rapidly evolving fields like Biology are awash in TLAs. But we cannot *all* have short, pithy, latin-derived words for our most modern concepts. Tell your mechanical friend that I'd call Process Control Blocks "inertia" if Kepler and Newton hadn't already stolen that one hundreds of years ago. At least we're able to co-opt "quanta" for Operating Systems. Otherwise it would be "Time Between Clock-Driven Kernel Context Switchs", or "TBC-DKCSs" for short. You may also note to your mechanical engineering friends that at least we have a clearly articulated standard from the IETF on registering and disambiguating TLAs: tools.ietf.org/html/rfc5513 P.S. The answer for exam question #4 is "42". 1. The example code had "mutex" in it. I've heard this word before, but what does it mean? "Mutual Exclusion". See Chapter 5. 2. How would semaphores function on multiple processors such that a producer wait(S) would not run at the same time as a consumer signal(S)? Yes, if a producer process and a consumer process are running on separate processors, the producer's wait(S) and the consumer's signal(S) COULD run at exactly the same time. Both are accessing the semaphore itself, must be in a hardware-shared memory location. For ANY memory designed to be shared by multiple processors (not by multiple processes), the hardware must be designed to enforce serialization of reads and writes. In principle, multiple reads can occur simultaneously, but the hardware must permit only one write at a time. One consequence is that sharing registers or memory among more than a handful of cores/processors becomes a bottleneck. Hence, while semaphores work well for providing synchronization among many processes running on a single processor, synchronization among processes running on modern multi-processor systems usually rely on message passing. 3. Wait states? A process effectively places itself in a wait state whenever it requests some resource that may take some time. Disk read/write, receive a message, semaphore wait(), and many other resources. Each resource needs its own wait queue. 4. What were the circumstances that Kenny found to exploit the long distance calling? Simply high call volumes. Essentially, they had assumes that when you initiate a call, the computer would be waiting to receive a message you were doing so. If the computer became heavily loaded, it simply missed receiving the message telling it you were making a call. It is very common for errors in cooperating processes to appear only under heavy loads. If you think about the class examples, you have to be REALLY UNLUCKY for the interrupts to occur at just the right (or wrong) times. Hence, moderate testing is unlikely to disclose the errors. 5. Did Kenny use the sequence of events to get free long distance calls? No. 1) Kenny would not do that, and 2) AT&T killed the project before putting it into production. 6. Can an operating system have multiple semaphores? Yes. The producer-consumer example I drew on the board had two: AvailableSpace and AvailableItems. 7. Is sem_t just an int typedef? Yes, in simple implementations with a fixed number of semaphores. If an implementation offers an unspecified number of semaphores (requiring some dynamic allocation), sem_t is some sort of hash value (probably still an int). 9. How relevant is the content of tests from 10 years ago? 5 years ago? Very. I find it amazing how little the contents of this class have changed in 40 years. The look-and-feel of operating systems is completely different, but the underlying principles are the same. The biggest difference from 40 years ago is networking. The only reservation about old exams from this class is that the chapters covered by each exam are slightly difference, because of scheduling and because we have used 3 different editions of the text in 10 years. 10. What can I use a semaphore for? The three classical applications in our book: producer-consumer, dining philosophers, and readers-writer intend to offer prototypical examples of common patterns requiring synchronization. Whenever you have two or more processes (or programs running on two or more computers) attempting to work cooperatively, you MUST think about synchronization, and semaphores MAY be part of the solution. 11. Are Java's "synchronized" and C#'s "lock" semaphores? Java's "synchronized" is a monitor, in the vocabulary of our book. It operates at a higher level than mutual exclusion primitives such as semaphores or TestAndSet. Essentially, if a class has "synchronized" methods called from several processes, the Java Virtual Machine ensures only one method at a time is executing. C#'s "lock" is a language-level mutual exclusion primitive, probably implemented by calling an operating system mutual exclusion primitive such as semaphores. 1. Can there be a 14th Doctor? Yes there can be! Technically Peter Capaldi is the 14th regeneration, but he is dubbed the 12th Doctor. The Doctor was given a brand new generation cycle before Matt Smith's Doctor ended. -- Jeremy Moy 2. Isn't creating N threads dangerous? If the danger is exhausting memory, yes, that is possible. A more robust thread pool would stop creating threads when one attempt failed, probably kill some of those that were created to leave some head-room, and then proceed with the pool it had. If you have other dangers in mind, such as unintended memory access, I do not see how more threads are more dangerous than a few. 3. Why do we use 5 threads instead of 25 in our 5x5 web browser?
4. How can certain threads get priority over others? Generally, threads inherit the priority of their enclosing process. In most OS's, we can override the default user priority. 5. Which prof would win in an arm wrestling match? Brylow! Or running a marathon. Or any other athletic endeavor I can imagine. He's about half my age. -- Dr. C. I might win the arm wrestling, but George has visibly lapped me with his card-question-answering dexterity. -- Dr. D 6. Why did you change to green cards? I like it. I've run low on white cards, and I haven't re-visited Office Depot yet. Besides, perhaps they add a slight bit of interest. 7. Walkthrough was a bit fast. Yes, but I hope the highlights came through:
For ease of finding it, the code is here 14osc9e/ch4/thrd-posix_XINU.c. 8. Are there external resources to read more on this that supplement the book and the lecture? For next week's exam, studying the text should be sufficient. Beyond that, Google is your friend to help add insight. A few promising hits:
Most of those, you should be able to write, although the Wikipedia article might that you 2-3 days to write. -- Dr. C. 1. Do you know any books/websites (besides just Googling) that describe exactly how talking to ports work? I learned how to write serial port drivers out of "C Programmer's Guide to Serial Communication", by Joe Campbell. I have a copy available in the lab, if you'd care to borrow it. 2. Is there a good source to refresh myself on MIPS assembly programming? I learned how to program MIPS out of "MIPS Assembly Language Programming" by Robert Britton. I have a copy available in the lab, if you'd care to borrow it. 3. Where do the names of the routers come from? That is a question you should be able to easily answer through the judicious Googling of several of them. 4. Where do we find the SVN commands to create a repository for the group? svnadmin create repo 5. Is this the same way all operating systems are made? Does Microsoft handle things in its own magical way? At their core, nearly all operating systems have their own versions of the elements we are constructing in this class. 6. Who can we talk to to help us get jobs where we work on code in fewer than two years? George: Me. Dennis might have said "Two years" because quite a few students in the class are sophomores. However, anyone in this class who wants it should be able to find a good part-time or summer programming job. There are a few interviewers in town who will count a passing score on OS Exam 1 as strong evidence of your immediate employability. 7. Are files just a level of abstraction so that other programmers do not need to see how stuff is done? Files are an abstraction. 8. Can hackers hijack the null process? Difficult. In a production operating system, the null process is guarded by both memory protection and privilege features built into the hardware of modern processors. 9. Do you think The Doctor will ever find Gallfrey? Do you think he will be happy? Difficult to see. Always in motion the future is. 10. Will there be a practice test? What can we expect the structure of the midterm exam to be? George: There are 30+ actual exams (with solutions) from previous classes. Follow links at examMid15A.html. Be aware that the material covered on Exam 1 differs slightly from year to year. Questions such as these suggest you are not exploiting the information on the class web site. If you had come across a link to midterm exam 1, 2015 (there is one on every page), you MIGHT have clicked it? 11. Will the information/code from assignment 4 be covered on the exam? George: Yes. Assignment 4 is about process creation and context swapping, which are central to Chapter 3. Also, see previous exams. Further, since you seem to think you can read my mind, you MIGHT guess that I want to encourage you to start work on Assignment 4 right away, rather than waiting until the exam is over. 12. iOS, Android, Windows Phone, or other, which do you prefer? George: I do not care; I want to get work done. I use an iPhone, and I guided my wife to an Android. 13. If the processor returns to the null process, won't it just keep looping forever? George: If there are no other processes in the system so that the null process is the only one that exists, you are correct, except that an interrupt could lead to the creation of additional processes. The usual case is that there are several other processes in the system, but they are each waiting for something, e.g., a timer or disk access. That is what the PSWAIT state is for. When the resource for which it is waiting arrive, the waiting process is moved into the READY state, and resched() chooses that process to run. Notice also that in this assignment, all processes have the same priority, so the null process is selected by resched() every few calls. The more you reflect on even this simple design, the pieces fit together astonishingly well. -Dr. D 1. What is the advantage of having two linked lists next and pre? The process queue structure I talked about in lab is doubly-linked, meaning that the queue can be traversed in either order. Sometimes we need to start from the beginning and walk forward in the data structure, but sometimes we need to start at the end and walk backward. 2. When there are five letter argument words, for example, do we have to assign four words underneath the stack pointer? In MIPS, one never accesses space below one's own activation record. (Interrupt-driven O/S behavior can stomp on memory values below the stack pointer at any time, as we shall see later.) If function A calls another function B with five arguments, then the activation record for A contains not only the obligatory 4 words at the bottom that are always left for the callee's arguments, but also another block of 4 words for fifth, sixth, seventh and eighth potential arguments. Whatever the maximum number of arguments for the callees, the MIPS compiler always rounds up to the next highest multiple of four words. (This has to do with efficient preloading of 16-byte cache blocks in MIPS memory hardware.) -Dr. D 1) When were thread pools first implemented for web servers? I don't know. I would guess 1996-2000-ish, within a few years of the first web servers. I would guess thread pools appeared in database servers a decade earlier. 2) If you passed main to the thread create method as a parameter, what would happen? Thread bomb. Try it and see. 3) Can computers cache service requests to improve efficiency? ABSOLUTELY. Can and DO. 4) If you open task manager in Windows and view running processes, are those processes or threads? See the bottom of p. 188. A Windows application runs as a separate process (what Task Manager displays), and each process may contain one or more threads. 5) Can you draw a flow chart of the thread activity we did in class? Figure 4.2 is close, except that with a thread pool (see Section 4.5.1), rather than creating a new thread, we activate one of several idle threads. 6) What is your favorite restaurant in Milwaukee? Corliss: Golden Mast on Okauchee Lake. Brylow: Habanero's in Wauwatosa is a current, kid-friendly favorite, but I've always had a soft spot for Izumi's, on the East Side. 7) If you could work for any company in the industry (assuming you WANTED to work in industry), which would you choose today? My, these are getting harder ... Corliss: Your criteria might differ, but I'd choose a local start-up. I have no interest in California; I want to stay here. I don't need money; I want something that makes a difference, interests me, and has great people. ANY company? The one we'd form if Dr. Brown ever decides to spin off GasDay. Oh, that's where I AM working! Talk with me if you'd like to join us. Brylow: I've carefully avoided working for industry since I went back to graduate school in the late 90's, but I would probably also choose a local start-up focused on embedded and/or real-time systems. 8) Who comes up with the names for the computers in the lab? Brylow:There are three distinct naming schemes in use for the Systems Lab: Linux workstations; WRT54GL routers and their associated servers (Morbius, Mawdryn and Eldrad); and E2100L routers (see 'xinu-status -c e2100l'). My own workstation (Elsinore) and the two big-iron rack-mount machines that host the server virtual machines (Zen and Bradbury) do not conform to these schemes, and each represent a legacy machine naming regime from one of my earlier institutions. 9) Can you only thread a process, or are there other things that can be threaded? "Thread" is a refinement of the operating systems concept of "process." One can USE threads to manage a variety of resources, but threads are akin to light-weight processes. 10) Why are threads called "threads?" Is there some sewing analogy to processes? Beats me. Perhaps because execution follows a thread of control? See wiki.answers.com/Q/Why_is_thread_called_thread -- Dr. Corliss 1) What are your preferred programming languages? Depends on the task at hand. Generically, across all sorts of applications, I ENJOY working in C, Fortran, or Perl. In actual work, over the past couple months, I probably have programmed most in Matlab, Perl, C, and JavaScript. 2) What is the most important concept to take away from this class? From the semester class: Depends on who you are:
From today's class on threads: What does "thread" mean? What are some of the issues making that question harder to answer than you might wish. 3) If we want to render a web page with 100 images, would we create 100 threads? Depends how the browser author coded it. The author's choices should depend also on the host operating system. If it were up to you, what would YOU do? If it were up to me, I would not exceed 10-40 threads, depending on how busy the host (for the browser) computer is. If the machine is too busy and there are too many threads, it spends all its time context switching, and none doing useful work. 4) Do you know of any campus research presentations in CS or CEngr to attend? I try to list most of the presentations of which I am aware on each week's Discussion Notes page, e.g., for this week, but I do not always hear far enough in advance. Generally, EECE has colloquia many Tuesdays at 2:00 in Olin 202, and MSCS has colloquia many Fridays at 1:00 in Cudahy 414. Both departments are interviewing potential new faculty this spring, so schedules are adjusted to fit the candidates. Biomedical Engineering has colloquia many Fridays at noon in Olin 202. Many of those have storng computer science/engineering components. In addition, many research labs have weekly (or other frequency) research seminars with varying degrees of formality, often with our graduate (or undergraduate) students presenting their work in progress. The GasDay lab where I work has seminars Thursdays 10 - noon in Olin 540. Dennis, what about your lab? You are welcome to ask other Computer Science/Engineering faculty. 5) Is Intel hyper-threading under multi-core programming? Why is hyper-threading considered the same as multiple physical cores? Intel's hyper-threading pre-dated multi-core machines. A modern CPU core executes multiple instructions literally in the same clock cycle, often 4-8 instructions per cycle in real code. One challenge is that most programs do not have 4-6 instructions ready to execute at the same time, due to data or control dependencies. Hyper-threading suggested we could take perhaps 2-4 instructions from one program/process/thread/task and 2-4 from another. Then it might be easier to keep the processor busy. The logical challenge only becomes greater with multiple physical cores, EACH trying to execute several instructions per clock cycle. As yet, we do not try to execute one thread of control simultaneously on multiple cores because of the cost and difficulty of making data available where it needs to go. If that answer makes no sense to you, that's OK. I hope you'll meet those concepts one day in a good Computer Hardware/Architecture class. If that answer makes SOME sense to you, but it makes your head spin, GOOD; you probably get it. Concepts of multiple simultaneous instruction execution IS a mind-expanding concept. That's one reason why we hope our operating system does most of the heavy lifting for us. 6) Can you have a one-to-many thread control idea? Not practically. That would suggest on logical (user) thread was realized by many kernel threads. 7) Today, I was a bit confused about the POINT of the lecture. The point was to develop a deeper understanding of the concept of threads by considering a collection of not-very-related choices that need to be considered by an operating systems designer who wanted to support threads. By implication, that suggests why popular operating systems provide the thread concept in quite different ways. In that sense, the point is that there is no single answer, hence jobs designing sound trade-offs. G. Corliss 1) Why are max, min, average, and variance important scheduling criteria? Max - WORST value for any of the metrics. That is the Service Level Guarantee; the OS is never worse than that. 2) Will there be a review session for the test? No. Read the text, Dr. Barnard's notes, and previous exams with solution hints. 3) Will the exam be all short answer/essay, or will there be other types of questions? Will the test be essay-based? The exam will follow the same format as those posed on the class web site. If I think of a different style of question, I reserve the right to use it. I like graphics, if only I could figure out an effective way to use them on paper. 4) For interactive systems, why is it important to minimize the variance in response time rather than minimize the response time? We like predictability. Consider an analogy: 5) Please explain help desk calls and variability. If you something usually takes 5 seconds, and it takes a minute, what do you do? Especially in a work setting, you are likely to call the Help Desk (at least if your company has a helpful Help Desk) and ask, "What is wrong?" 6) Please explain the difference between waiting time and response time. Response time is the time between your initiation of a task (e.g., mouse click, network submission) and the beginning of a meaningful response (spinning wheels, hour glasses, or progress bars do not count). 7) Round-robin scheme is essentially splitting the work time on a processor evenly in an ordered manner, right? Yes, essentially, but there is a little more to it than that, and implementations may differ in the details. First, RR is pre-emptive, meaning that a timer interrupt (or equivalent) is used to enforce "evenly." Second, "evenly" only applies to processes not waiting for some resource; if your process is waiting for a message, for example, it does not get to run. "Orderly" in the sense that the Ready List is managed as a queue. Also, implementations may differ in how they treat a process asking for a resource that is not available. In most implementations, that process relinquishes the processor, and another process gets to run. In simpler implementations of RR, the requesting process may busy-wait until its time quantum expires. QuestionsDo most current OSs have stable schedulers? Yes, most general-purpose OSs use some variant of approximate shortest job first. What happens to the work the process did when it gets preempted? Is it lost? ABSOLUTELY NOT. When a process P is preempted, the scheduler moves it from the Running state to the Ready state to give the CPU to another process. Somewhat later, the schedule will select P from the Ready list and move it to the Running state, restoring all its registers. Process P resumes exactly where it left off. How would you define a task? Is it different from a process or a thread? Different authorities use each of these words in slightly different ways. Our book does not use the word 'task' in this context. "Task" is used most often in the context of parallel processing as a unit of work which may be executed in parallel. Often, a task is a process.
|
| Marquette University. Be The Difference. | Marquette | Corliss | |