|
||||||||||||||||||||
|
||||||||||||||||||||
|
||||||||||||||||||||
|
||||||||||||||||||||
 | ||||||||||||||||||||||||||||||||||||||||||||||||
| ||||||||||||||||||||||||||||||||||||||||||||||||
|
Rating: |
|
||||||||||||||||||||||||||||||||||||||||||||||
| Attendee: | |||||||||||||||||||||||||||||||||||||||||||||||
| Present |
| ||||||||||||||||||||||||||||||||||||||||||||||
| ||||||||||||||||||||||||||||||||||||||||||||||||
| Absent |
| ||||||||||||||||||||||||||||||||||||||||||||||
| ||||||||||||||||||||||||||||||||||||||||||||||||
| Optional Attendee: | |||||||||||||||||||||||||||||||||||||||||||||||
| Present |
| ||||||||||||||||||||||||||||||||||||||||||||||
| ||||||||||||||||||||||||||||||||||||||||||||||||
| Absent |
| ||||||||||||||||||||||||||||||||||||||||||||||
| ||||||||||||||||||||||||||||||||||||||||||||||||
|
Guest Emails | None | ||||||||||||||||||||||||||||||||||||||||||||||
| ||||||||||||||||||||||||||||||||||||||||||||||||
|
Agenda: |
|
||||||||||||||||||||||||||||||||||||||||||||||
| File Attachment: |
|
|||||||||||||||||||||||||||||||||||||||||||||||
| Meeting Minutes: | Hi, all, we will wait a bit for people to come in to the meeting room before we start. I notice that there are some "guests" coming in. That's ok since it is a public meeting. But I will give priority to my students if the interaction is getting busy.
Because of the time slot, there might not be a lot of people attending. Since I have to leave promptly at 12 noon for another meeting, I will start now.
1 Review Ch6 concepts The Dining Philosophers' problem is a classic in CS. Is there any questions anyone has on this?
[Input session 1: input from edwardgem, yanchan1123, Truman Guan, csc41501 and ninjabunny]
[11:06] edwardgem: One clarification to stress on: the critical section of the problem is only about picking up the chopsticks, not on accessing the bowl of rice.
[11:07] edwardgem: The issue at hand is that the 5 philosophers are competing on accessing the chopsticks that are next to them.
[11:07] edwardgem: The lesson is to use semaphores (binary ones) to control accesses to the common resource -- in this case, the chopsticks.
[11:08] edwardgem: If there is no questions, we will move on to the next topic.
[Above are entries from input session 1]
[Input session 2: input from edwardgem, yanchan1123, Truman Guan, csc41501 and ninjabunny]
[11:09] edwardgem: Any questions related to the concept of transactions?
[11:09] edwardgem: Truman, can you tell me why do we need Transactions?
[11:10] truman guan: to facilate the movement of information?
[11:10] edwardgem: I forgot who is cs41501, can you tell me?
[11:11] csc41501: i'm quan
[11:11] edwardgem: ok, quan, can you try that question? Why transactions?
[11:11] csc41501: to
[11:12] csc41501: run programs
[11:12] edwardgem: ok. Let me reiterate the concept.
[11:13] edwardgem: Transaction is used to support concurrency control.
[11:13] edwardgem: When you have a number of people or jobs running at the same time, they might step on each other because they are sharing resources.
[11:14] csc41501: ok
[11:14] edwardgem: People introduce the concept of transactions to protect each and every job to ensure user-expected behavior.
[11:15] edwardgem: The transaction behaviors can be represented by ACID. Anyone knows what they stands for?
[11:15] csc41501: all or nothing
[11:15] csc41501: isolation
[11:15] truman guan: atomaticity, concurrency, isolation,
[11:15] edwardgem: right, plus Durability.
[11:16] edwardgem: Quan says "all-or-nothing", and that is Atomicity.
[11:16] csc41501: ok
[11:17] edwardgem: Atomicity means ensuring that either the whole job get done, or nothing get done. That means make sure that the system won't do part of the job.
[11:17] edwardgem: A good example would be to transfer money from one bank account to another.
[11:17] edwardgem: This job will involve taking $$ out from one account and then putting the same $$ into another account.
[11:18] edwardgem: You don't want to see a system that has done one the first part of these two tasks, right?
[11:18] csc41501: right
[11:18] edwardgem: good. That is why you want Atomicity behavior.
[11:18] truman guan: what about the point of durability?
[11:19] edwardgem: Durability means that if a change is made to the system, then I want to make sure that it will not go away.
[11:20] edwardgem: For example, if you perform a money transfer, and then a disaster hit like the harddisk or the computer system of the bank went down.
[11:20] edwardgem: The question is: would durability be ensured? That is, would my transaction of transferring money be gone?
[11:21] csc41501: no?
[11:21] edwardgem: If a system ensure a good degree of durability, then it will be sure that once your money transfer is completed, even if there is a disaster, the transaction is durable.
[11:22] edwardgem: I saw that a few more people are in the meeting room, let me open up for them for input also.
[Input session 3: input from edwardgem, yanchan1123, Truman Guan, csc41501, dbannister, jsalvador, ninjabunny and raychan]
[11:22] dbannister: thanks
[11:22] dbannister: i was trying everything to type something
[11:22] jsalvador: Thank you.
[11:23] edwardgem: Ok. Let's continue. I remember last night in the quiz I said "C" means concurrency. I lied. It should be consistency.
[11:23] edwardgem: I would review my notes from previous class, but I think I had said consistency before.
[11:23] jsalvador: Everyone should get a bonus point for that.
[11:24] edwardgem: Don't push for it ... perhaps everyone who says either consistency or concurrency.
[11:24] edwardgem: ok, but what is consistency. let me reiterate.
[11:24] edwardgem: Consistency means that the system will ensure the transactions would not create a state that is inconsistent to the expectation of the users.
[11:25] edwardgem: For example, the system might have a rule that says a user's bank account cannot be lower than 0 in balance.
[11:25] edwardgem: Then, when a transaction is executed, if it tries to debit the account for below zero, the system will not allow it.
[11:26] edwardgem: Such a system is maintaining the C property in ACID.
[11:26] edwardgem: Any questions on this?
[11:26] edwardgem: Let's move on.
[11:26] jsalvador: Make sense.
[11:27] edwardgem: Isolation - anyone wants to give a definition?
[11:27] csc41501: one transaction does not affect other transaction
[11:27] edwardgem: Exactly.
[11:27] edwardgem: One transaction would not see the other transaction at work.
[11:28] edwardgem: Just like they are executed in series (not parallel). Even though in reality they are executed at the same time in parallel.
[11:29] edwardgem: And lastly Durability Quan already raised a discussion in the above discussion, so I won't repeat myself.
[11:29] edwardgem: Now we understand the 4 properties of transactions - ACID.
[11:29] edwardgem: Remember that it is a matter of the degree of fulfilling these properties, not necessary in an absolute sense.
[11:30] edwardgem: For example, about Durability. If the bank computer dies, durability may preserved, but what if an atomic bomb hits?
[11:31] edwardgem: Well, yes and no. Nowadays the bank will actually have replication inplace such that even if the whole city is removed, the transaction record will preserve. But what if the atomic bombs so happen to hit a number of cities and there is no more backup preserved?
[11:32] edwardgem: In that case, the transaction's Durability is not there. I hope you get the point.
[11:32] edwardgem: We still have some time left, should we go on to Ch.7? Or is there any questions about transactions?
[Above are entries from input session 3]
[Above are entries from input session 2]
2 Review Ch 7 concepts
[Input session 4: input from edwardgem, MrEricSir, ngoc_lm, yanchan1123, Truman Guan, csc41501, dbannister, jsalvador, ninjabunny and raychan]
[11:35] edwardgem: Why would there be deadlocks?
[11:35] dbannister: when you have a cycle graph
[11:36] MrEricSir: Because there's a loop in the directed process dependency graph
[11:36] raychan: so two processes won't use the same I/O at the same time
[11:36] edwardgem: ok, that's how you can detect there is a deadlock.
[11:36] edwardgem: But my question is why would deadlock exist on a system?
[11:36] ngoc_lm: because the way you design your OS
[11:36] ngoc_lm: no preemtive for ex
[11:37] edwardgem: Hmm... what do you mean, can you tell more?
[11:37] MrEricSir: If process A is waiting for process B, and process B is waiting for process A, you have a deadlock.
[11:37] edwardgem: True.
[11:37] edwardgem: Eric, so now the reason I have deadlock is because I have process waiting for one another.
[11:38] edwardgem: That means: we have deadlock on the system because we have concurrent processing. Right?
[11:38] edwardgem: Is everyone clear about this?
[11:38] MrEricSir: yes
[11:39] edwardgem: If you design an OS that doesn't allow concurrency at all, there is no deadlock.
[11:39] jsalvador: Yes.
[11:39] ngoc_lm: yep
[11:39] csc41501: yes
[11:39] dbannister: ok
[11:39] edwardgem: good... But such a system will be slow and boring.
[11:39] MrEricSir: like DOS
[11:40] edwardgem: you are funny ... but yes, you are right.
[11:40] edwardgem: That said, that means we would wnat the system to have concurrency, but the natural consequence is that there will be potential of deadlocks.
[11:40] raychan: om
[11:40] dbannister: so in dead lock there is no premptive
[11:41] edwardgem: If you have pre-emptive, then you may resolve deadlock by pre-empting a process that is holding up resources.
[11:41] dbannister: right
[11:41] edwardgem: But still the OS needs to identify which process to pre-empt.
[11:42] edwardgem: Ray, do you have a question or a comment?
[11:42] dbannister: by using premptive you can force a process to give up resource
[11:42] raychan: so, we can use hash tables to identify if there is a deadlock?
[11:43] edwardgem: Yes - who is dbannister again? - but you may not.
[11:43] MrEricSir: Couldn't each process keep a simple list of processes it depends on, and processes those depend on, etc. so it could know if there was a cycle?
[11:43] dbannister: Dominic
[11:43] edwardgem: Eric, that is the basic idea.
[11:43] edwardgem: hi, Dominic.
[11:44] edwardgem: Back to Ray first.
[11:44] dbannister: hi
[11:44] edwardgem: Ray, hash table is a general data structure.
[11:44] edwardgem: You do what Eric is suggesting -- build a graph -- to identify the dependency.
[11:44] edwardgem: If the dependency turns out to be a cycle, you know that you have a deadlock.
[11:45] edwardgem: When you do programming to build the graph, you would probably use a link list.
[11:45] raychan: ok
[11:45] edwardgem: But for performance purpose, you would add some sort of hash table so that you can quickly lookup an element on the link list.
[11:46] edwardgem: Eric you statement about building a list to remember who depends on whom is actually the idea of the wait-for graph.
[11:46] edwardgem: And I suggest that you only need to build the graph in one direction.
[11:47] edwardgem: That means only remember who I am waiting for, but don't need to remember who is waiting for me.
[11:47] edwardgem: Why, because if I go in one direction and found a cycle (start from P1 and then reach P1 again), that means I have a deadlock. I don't need to do it again in the opposite direction.
[11:48] edwardgem: Ok, let's move on to the specifics of implementation now.
[Above are entries from input session 4]
[Input session 5: input from edwardgem, MrEricSir, ngoc_lm, yanchan1123, Truman Guan, csc41501, dbannister, jsalvador, ninjabunny and raychan]
[11:49] edwardgem: In the class we go over some implementation data structure. Any question on that discussion?
[11:50] edwardgem: Are people clear or totally confused in that discussion?
[11:52] edwardgem: If I am to ask you to write a code segment in the mid-term about discovering deadlock you think you can handle it?
[11:52] jsalvador: No.
[11:52] csc41501: no
[11:52] raychan: no
[11:52] MrEricSir: I'm not too clear on this either.
[11:52] dbannister: no
[11:52] edwardgem: who is this (jsalvador)?
[11:52] edwardgem: ok. fine.
[11:52] jsalvador: Julian Salvador
[11:53] edwardgem: Hi, Julian.
[11:53] jsalvador: Hello
[11:53] edwardgem: The starting point is to define data structures.
[11:53] csc41501: is the implementation with 2 hash table and linklist?
[11:53] dbannister: i think both
[11:54] edwardgem: basically yes. But in the Mid-term you would not have that much time.
[11:54] edwardgem: So you would only be asked to write code segments.
[11:54] edwardgem: We know that to detect deadlock you need to construct the wait for graph.
[11:54] edwardgem: And the wait for graph is represented by a link list of transaction blocks waiting for others.
[11:55] edwardgem: So we need to find out who is waiting for whom.
[11:55] edwardgem: To find that we need to construct the lock table.
[11:55] edwardgem: Because the lock table will tell us which transaction is holding what resources.
[11:56] edwardgem: If I have a lock table then when a transaction request for a resource (ie. a lock), then I can go to the lock table to see if there is a conflict.
[11:56] dbannister: Dr. Cheng
[11:56] dbannister: i have to go to class
[11:56] edwardgem: ok, see you.
[11:56] dbannister: ok
[11:56] dbannister: bye
[11:56] jsalvador: Same here. Thank you for the review.
[11:56] edwardgem: And if there is a conflict, then I will add a link to the wait for graph link list.
[11:56] edwardgem: After that I will detect if there is a cycle.
[11:57] edwardgem: And that is it.
[11:57] edwardgem: Wooo, I didn't knwo that it is already an hour.
[11:57] edwardgem: Ok, I think we will stop here. I will see you all in class on Thurs. Have a great day.
[11:57] MrEricSir: Time flies when you're having fun!
[11:57] edwardgem: bye.
[11:57] MrEricSir: bye
[11:58] raychan: bye
[Above are entries from input session 5]
3 Others |
|||||||||||||||||||||||||||||||||||||||||||||||
| Action / Decision: |
Show all from linked meetings
|
|||||||||||||||||||||||||||||||||||||||||||||||
| Meeting Blogs: |
New Blog Posting
|
|||||||||||||||||||||||||||||||||||||||||||||||
| ||||||||||||||||||||||||||||||||||||||||||||||||
| ||||||||||||||||||||||||||||||||||||||||||||||||
| ||||||||||||||||||||||||||||||||||||||||||||||||
| Enter your questions, comments or suggestions: | ||||||||||||||||||||||||||||||||||||||||||||||||
 |
|
| Home | FAQ | Feedback forum | Logout | Back to top | |
| Copyright © 2010, MeetWE |
