I am honored to be with you today at your commencement from one of the finest universities in the world. I never graduated from college. Truth be told, this is the closest I've ever gotten to a college graduation. Today I want to tell you three stories from my life. That's it. No big deal. Just three stories.
The first story is about connecting the dots.
I dropped out of Reed College after the first 6 months, but then stayed around as a drop-in for another 18 months or so before I really quit. So why did I drop out?
It started before I was born. My biological mother was a young, unwed college graduate student, and she decided to put me up for adoption. She felt very strongly that I should be adopted by college graduates, so everything was all set for me to be adopted at birth by a lawyer and his wife. Except that when I popped out they decided at the last minute that they really wanted a girl. So my parents, who were on a waiting list, got a call in the middle of the night asking: "We have an unexpected baby boy; do you want him?" They said: "Of course." My biological mother later found out that my mother had never graduated from college and that my father had never graduated from high school. She refused to sign the final adoption papers. She only relented a few months later when my parents promised that I would someday go to college.
And 17 years later I did go to college. But I naively chose a college that was almost as expensive as Stanford, and all of my working-class parents' savings were being spent on my college tuition. After six months, I couldn't see the value in it. I had no idea what I wanted to do with my life and no idea how college was going to help me figure it out. And here I was spending all of the money my parents had saved their entire life. So I decided to drop out and trust that it would all work out OK. It was pretty scary at the time, but looking back it was one of the best decisions I ever made. The minute I dropped out I could stop taking the required classes that didn't interest me, and begin dropping in on the ones that looked interesting.
It wasn't all romantic. I didn't have a dorm room, so I slept on the floor in friends' rooms, I returned coke bottles for the 5¢ deposits to buy food with, and I would walk the 7 miles across town every Sunday night to get one good meal a week at the Hare Krishna temple. I loved it. And much of what I stumbled into by following my curiosity and intuition turned out to be priceless later on. Let me give you one example:
Reed College at that time offered perhaps the best calligraphy instruction in the country. Throughout the campus every poster, every label on every drawer, was beautifully hand calligraphed. Because I had dropped out and didn't have to take the normal classes, I decided to take a calligraphy class to learn how to do this. I learned about serif and san serif typefaces, about varying the amount of space between different letter combinations, about what makes great typography great. It was beautiful, historical, artistically subtle in a way that science can't capture, and I found it fascinating.
None of this had even a hope of any practical application in my life. But ten years later, when we were designing the first Macintosh computer, it all came back to me. And we designed it all into the Mac. It was the first computer with beautiful typography. If I had never dropped in on that single course in college, the Mac would have never had multiple typefaces or proportionally spaced fonts. And since Windows just copied the Mac, it's likely that no personal computer would have them. If I had never dropped out, I would have never dropped in on this calligraphy class, and personal computers might not have the wonderful typography that they do. Of course it was impossible to connect the dots looking forward when I was in college. But it was very, very clear looking backwards ten years later.
Again, you can't connect the dots looking forward; you can only connect them looking backwards. So you have to trust that the dots will somehow connect in your future. You have to trust in something — your gut, destiny, life, karma, whatever. This approach has never let me down, and it has made all the difference in my life.
My second story is about love and loss.
I was lucky — I found what I loved to do early in life. Woz and I started Apple in my parents garage when I was 20. We worked hard, and in 10 years Apple had grown from just the two of us in a garage into a $2 billion company with over 4000 employees. We had just released our finest creation — the Macintosh — a year earlier, and I had just turned 30. And then I got fired. How can you get fired from a company you started? Well, as Apple grew we hired someone who I thought was very talented to run the company with me, and for the first year or so things went well. But then our visions of the future began to diverge and eventually we had a falling out. When we did, our Board of Directors sided with him. So at 30 I was out. And very publicly out. What had been the focus of my entire adult life was gone, and it was devastating.
I really didn't know what to do for a few months. I felt that I had let the previous generation of entrepreneurs down - that I had dropped the baton as it was being passed to me. I met with David Packard and Bob Noyce and tried to apologize for screwing up so badly. I was a very public failure, and I even thought about running away from the valley. But something slowly began to dawn on me — I still loved what I did. The turn of events at Apple had not changed that one bit. I had been rejected, but I was still in love. And so I decided to start over.
I didn't see it then, but it turned out that getting fired from Apple was the best thing that could have ever happened to me. The heaviness of being successful was replaced by the lightness of being a beginner again, less sure about everything. It freed me to enter one of the most creative periods of my life.
During the next five years, I started a company named NeXT, another company named Pixar, and fell in love with an amazing woman who would become my wife. Pixar went on to create the worlds first computer animated feature film, Toy Story, and is now the most successful animation studio in the world. In a remarkable turn of events, Apple bought NeXT, I returned to Apple, and the technology we developed at NeXT is at the heart of Apple's current renaissance. And Laurene and I have a wonderful family together.
I'm pretty sure none of this would have happened if I hadn't been fired from Apple. It was awful tasting medicine, but I guess the patient needed it. Sometimes life hits you in the head with a brick. Don't lose faith. I'm convinced that the only thing that kept me going was that I loved what I did. You've got to find what you love. And that is as true for your work as it is for your lovers. Your work is going to fill a large part of your life, and the only way to be truly satisfied is to do what you believe is great work. And the only way to do great work is to love what you do. If you haven't found it yet, keep looking. Don't settle. As with all matters of the heart, you'll know when you find it. And, like any great relationship, it just gets better and better as the years roll on. So keep looking until you find it. Don't settle.
My third story is about death.
When I was 17, I read a quote that went something like: "If you live each day as if it was your last, someday you'll most certainly be right." It made an impression on me, and since then, for the past 33 years, I have looked in the mirror every morning and asked myself: "If today were the last day of my life, would I want to do what I am about to do today?" And whenever the answer has been "No" for too many days in a row, I know I need to change something.
Remembering that I'll be dead soon is the most important tool I've ever encountered to help me make the big choices in life. Because almost everything — all external expectations, all pride, all fear of embarrassment or failure - these things just fall away in the face of death, leaving only what is truly important. Remembering that you are going to die is the best way I know to avoid the trap of thinking you have something to lose. You are already naked. There is no reason not to follow your heart.
About a year ago I was diagnosed with cancer. I had a scan at 7:30 in the morning, and it clearly showed a tumor on my pancreas. I didn't even know what a pancreas was. The doctors told me this was almost certainly a type of cancer that is incurable, and that I should expect to live no longer than three to six months. My doctor advised me to go home and get my affairs in order, which is doctor's code for prepare to die. It means to try to tell your kids everything you thought you'd have the next 10 years to tell them in just a few months. It means to make sure everything is buttoned up so that it will be as easy as possible for your family. It means to say your goodbyes.
I lived with that diagnosis all day. Later that evening I had a biopsy, where they stuck an endoscope down my throat, through my stomach and into my intestines, put a needle into my pancreas and got a few cells from the tumor. I was sedated, but my wife, who was there, told me that when they viewed the cells under a microscope the doctors started crying because it turned out to be a very rare form of pancreatic cancer that is curable with surgery. I had the surgery and I'm fine now.
This was the closest I've been to facing death, and I hope it's the closest I get for a few more decades. Having lived through it, I can now say this to you with a bit more certainty than when death was a useful but purely intellectual concept:
No one wants to die. Even people who want to go to heaven don't want to die to get there. And yet death is the destination we all share. No one has ever escaped it. And that is as it should be, because Death is very likely the single best invention of Life. It is Life's change agent. It clears out the old to make way for the new. Right now the new is you, but someday not too long from now, you will gradually become the old and be cleared away. Sorry to be so dramatic, but it is quite true.
Your time is limited, so don't waste it living someone else's life. Don't be trapped by dogma — which is living with the results of other people's thinking. Don't let the noise of others' opinions drown out your own inner voice. And most important, have the courage to follow your heart and intuition. They somehow already know what you truly want to become. Everything else is secondary.
When I was young, there was an amazing publication called The Whole Earth Catalog, which was one of the bibles of my generation. It was created by a fellow named Stewart Brand not far from here in Menlo Park, and he brought it to life with his poetic touch. This was in the late 1960's, before personal computers and desktop publishing, so it was all made with typewriters, scissors, and polaroid cameras. It was sort of like Google in paperback form, 35 years before Google came along: it was idealistic, and overflowing with neat tools and great notions.
Stewart and his team put out several issues of The Whole Earth Catalog, and then when it had run its course, they put out a final issue. It was the mid-1970s, and I was your age. On the back cover of their final issue was a photograph of an early morning country road, the kind you might find yourself hitchhiking on if you were so adventurous. Beneath it were the words: "Stay Hungry. Stay Foolish." It was their farewell message as they signed off. Stay Hungry. Stay Foolish. And I have always wished that for myself. And now, as you graduate to begin anew, I wish that for you.
Stay Hungry. Stay Foolish.
Thank you all very much.
Wednesday, October 5, 2011
Tuesday, June 28, 2011
PARFAIT + I/O Latency study
Title: Supporting Real-time guest OS with Xen-ARM Mobile Virtual Machine
‘Draws attention’
Virtualization in mobile systems presents many advantages regarding reliability, security, and flexible user customizability, etc.
‘Unique characteristics of mobile virtualization’
Mobile virtualization has different requirements such as real-time support, small footprint, performance with limited hardware resources. In this work, we focus on supporting heterogeneous guest OSs support, which is a unique requirement in mobile systems virtualization. Those mobile devices requires real-time performance that only RTOS can guarantee as well as rich functionalities that GPOS is able to provide.
‘Introduce difficulties - Porting is nothing more than executing’
In general, it is difficult to support heterogeneous guest OSs over the same physical machine. It is definitely not sufficient for porting two guest OSs, and running within the single physical machine. That is because heterogeneous guest OSs presents different policies, that might conflict each other, and scheduling is one of most significant issues to be resolved. A real-time guest OS has its unique scheduling policy and task model so that all the tasks can meet their given deadlines. On the other hand, fairness and reasonable response time are two primary concerns for a general-purpose guest OS. Those scheduling policies can conflict. For example, a RT guest OS requires immediate task scheduling in order to meet the deadline of a task, that would break the fairness of task scheduling of the GP guest OS, or vice versa. Namely, the difficulty rises when two guest OSs contend for CPU with different conflicting policies.
‘It is the hypervisor that has to arbitrate scheduling in such an environment’
Hierarchical scheduling is an approach that most hypervisors use. In a hierarchical scheduling system, the hypervisor scheduler strictly partition the CPU utilization, and gives the CPU bandwidth to each guest OS. Since each guest OS runs with explicitly given CPU bandwidth, the scheduling policy of a guest OS doesn’t break the scheduling policy of another guest OS.
‘Difficulties are two-fold; what’s more needed for real-time guest OSs’
On one hand, hierarchical scheduling implements resource partition scheduling that strictly isolates performance among guest OSs. However, it is not sufficient to support a real-time guest OS since the requirements are multi-disciplinary rather than simple CPU bandwidth allocation. To address real-time support in a virtualization system, I/O latency issue has to be addressed as well as performance isolation. Since a real-time guest OS has requirements not only for periodic CPU-bound tasks, but also for unpredictable and aperiodic I/O tasks, static CPU bandwidth allocation is not sufficient to deal with I/O latency issues even though hierarchical scheduling is used.
‘KU-approach for real-time virtualization’
1. ‘PARFAIT is an effort to schedule heterogeneous guest OSs over a single physical machine’
Parfait is a scheduling framework that incorporates both real-time guest OSs and non-real-time guest OSs, at the same time. It allocates static amount of CPU bandwidth to real-time guest OSs, at first hand. Secondly, it fairly distributes the CPU bandwidth among the other GP guest OSs. It enables to isolate performance among RTOS and GPOS so that one of guest OSs doesn’t have negative performance impact to another. To incorporate deterministic scheduling theory into a practical system, we performed quantization analysis, and presents an algorithm that provides a scheduling parameter that guarantees schedulability of a virtual machine.
2. ‘To guarantee I/O latency, scheduling optimization has provided’
To guarantee I/O latency, scheduling algorithm has to be carefully optimized. We particularly focus on the Xen-ARM’s split driver in their paravirtualization architecture. It functionally isolates device drivers from user domains so that the potentially faulty device driver cannot compromise the entire system. Although it enhances the reliability of the entire system, it causes additional latency by frequent switching back and forth to the driver domain. With the original credit scheduling policy in Xen-ARM, it presents serious performance degradation. Increased I/O latency might lead to call drops/misses, which can be regarded a serious system defect in mobile systems. To deal with I/O latency, we prioritize the driver domain so that it cannot be scheduled out by another domain. On top of that, we take advantage of hardware specific architectural state. In addition to the hypervisor scheduler, we optimized the guest OS so that the driver domain’s physical interrupt handling cannot be discontinued by virtualized interrupt disable/enable routine.
‘Draws attention’
Virtualization in mobile systems presents many advantages regarding reliability, security, and flexible user customizability, etc.
‘Unique characteristics of mobile virtualization’
Mobile virtualization has different requirements such as real-time support, small footprint, performance with limited hardware resources. In this work, we focus on supporting heterogeneous guest OSs support, which is a unique requirement in mobile systems virtualization. Those mobile devices requires real-time performance that only RTOS can guarantee as well as rich functionalities that GPOS is able to provide.
‘Introduce difficulties - Porting is nothing more than executing’
In general, it is difficult to support heterogeneous guest OSs over the same physical machine. It is definitely not sufficient for porting two guest OSs, and running within the single physical machine. That is because heterogeneous guest OSs presents different policies, that might conflict each other, and scheduling is one of most significant issues to be resolved. A real-time guest OS has its unique scheduling policy and task model so that all the tasks can meet their given deadlines. On the other hand, fairness and reasonable response time are two primary concerns for a general-purpose guest OS. Those scheduling policies can conflict. For example, a RT guest OS requires immediate task scheduling in order to meet the deadline of a task, that would break the fairness of task scheduling of the GP guest OS, or vice versa. Namely, the difficulty rises when two guest OSs contend for CPU with different conflicting policies.
‘It is the hypervisor that has to arbitrate scheduling in such an environment’
Hierarchical scheduling is an approach that most hypervisors use. In a hierarchical scheduling system, the hypervisor scheduler strictly partition the CPU utilization, and gives the CPU bandwidth to each guest OS. Since each guest OS runs with explicitly given CPU bandwidth, the scheduling policy of a guest OS doesn’t break the scheduling policy of another guest OS.
‘Difficulties are two-fold; what’s more needed for real-time guest OSs’
On one hand, hierarchical scheduling implements resource partition scheduling that strictly isolates performance among guest OSs. However, it is not sufficient to support a real-time guest OS since the requirements are multi-disciplinary rather than simple CPU bandwidth allocation. To address real-time support in a virtualization system, I/O latency issue has to be addressed as well as performance isolation. Since a real-time guest OS has requirements not only for periodic CPU-bound tasks, but also for unpredictable and aperiodic I/O tasks, static CPU bandwidth allocation is not sufficient to deal with I/O latency issues even though hierarchical scheduling is used.
‘KU-approach for real-time virtualization’
1. ‘PARFAIT is an effort to schedule heterogeneous guest OSs over a single physical machine’
Parfait is a scheduling framework that incorporates both real-time guest OSs and non-real-time guest OSs, at the same time. It allocates static amount of CPU bandwidth to real-time guest OSs, at first hand. Secondly, it fairly distributes the CPU bandwidth among the other GP guest OSs. It enables to isolate performance among RTOS and GPOS so that one of guest OSs doesn’t have negative performance impact to another. To incorporate deterministic scheduling theory into a practical system, we performed quantization analysis, and presents an algorithm that provides a scheduling parameter that guarantees schedulability of a virtual machine.
2. ‘To guarantee I/O latency, scheduling optimization has provided’
To guarantee I/O latency, scheduling algorithm has to be carefully optimized. We particularly focus on the Xen-ARM’s split driver in their paravirtualization architecture. It functionally isolates device drivers from user domains so that the potentially faulty device driver cannot compromise the entire system. Although it enhances the reliability of the entire system, it causes additional latency by frequent switching back and forth to the driver domain. With the original credit scheduling policy in Xen-ARM, it presents serious performance degradation. Increased I/O latency might lead to call drops/misses, which can be regarded a serious system defect in mobile systems. To deal with I/O latency, we prioritize the driver domain so that it cannot be scheduled out by another domain. On top of that, we take advantage of hardware specific architectural state. In addition to the hypervisor scheduler, we optimized the guest OS so that the driver domain’s physical interrupt handling cannot be discontinued by virtualized interrupt disable/enable routine.
Monday, June 20, 2011
Minimizing I/O latency in Xen-ARM virtual machine
Title: Minimizing I/O latency in Xen-ARM virtual machine
Recently, virtualization takes attention to mobile systems because it enhances reliability, security, and flexible user customizability. In recent mobile systems, security and user customizability are more important than ever before since it manages all private personal information and more users want to customize the device as their own way. In addition, those mobile systems recently serve as a business assistant, so reliability and security became serious concerns. Mobile systems virtualization can address those issues in an efficient manner. For example, Xen’s split driver presents enhanced reliability by isolating a faulty driver domain or virus-infected malicious domain from trusted user domains.
There are several hypervisors for mobile systems. OKL4 microvisor is one of the most representative hypervisors. OKL4 microvisor serves as trusted computing base, by using formally verified kernel, and it presents efficient virtualization enough to be used in commercial mobile devices. VirtualLogix-VLX is another commercial hypervisor for mobile systems. It supports shared driver model that enables both real-time guest OS and non-real-time guest OS to share a physical device. It also presents comparable performance to native systems. Xen-ARM is yet another approach for incorporating Xen into ARM-based mobile systems. It presents small footprint, secure access control.
Despite the advantages of virtualization in mobile systems, performance issue has to be addressed at the same time. Since mobile systems have limited hardware resources (e.g. power supply, memory size, CPU budgets, etc.,) the implementation has to be efficient enough to overcome the performance overhead from virtualization. Among various performance problems, I/O latency is one of serious concerns because many mobile systems have communication device that needs to handle signaling protocols in a timely manner. In particular, the split driver model in Xen-ARM presents additional latency larger than 1ms, which could disconnect the mobile device from the networks.
In this paper, we analyze the two major sources of I/O latency in Xen-ARM’s split driver model, and propose a new scheduler in order for a real-time guest OS to handle I/O in a timely manner. Our analysis, at first, reveals that interrupt delivery to driver domain can be delayed because interrupt handling is virtualized when running within a guest OS. Although a driver domain disables virtual interrupts, physical interrupt can still be occurred, which might trigger inter-VM scheduling. Thus, physical driver in the driver domain cannot guaranteed to be scheduled in a timely manner. Secondly, additional latency is observed by inter-VM scheduling between the execution of backend and frontend drivers. Even though the existing scheduler supports I/O boost priority, I/O boost can be easily negated by multiple boost or ignored by fair scheduling policy.
To reduce latency while retaining the split driver model, we improve the scheduler so that the driver domain cannot be scheduled out when it disables virtual interrupts and the scheduler provide static priorities to guest OSs in order to provide a time bounded I/O latency. With our scheduler, all I/O interrupt at real-time guest OS is handled within 1ms while retaining split driver model, which is more strict latency bound than native ARM-Linux.
This paper consists of five sections. Section 2 introduces related work on embedded hypervisors and
Related Work
OKL4 microvisor is one of representative hypervisors for mobile systems. It is originated from L4 microkernel that overcomes the performance problems of first generation of microkernels. With extensive architectural optimization, L4Linux achieves good performance as close as native Linux, and OKL4 microvisor presents flexible architecture to incorporate multiple commodity operating systems. On top of that, it supports user-level device driver, which de-privileges driver domain in order to protect trusted user domains from the faulty driver implementation. In addition to performance, it is verified with formal language, so they claim that their hypervisor is bug-free, and thereby it is trustworthy.
Regarding the real-time performance, L4/Fiasco has been developed for real-time and embedded systems. It supports real-time OSs with several optimizations including direct task switching, time slice donation, and user-level reflective scheduling, etc. Although L4’s effort on real-time support presents impressive results in both desktop systems and embedded systems, their performance impact has not been thoroughly analyzed with more complex systems with virtualization such as multiple guest OS environment or multiple driver interactions.
Another hypervisor, VirtualLogix-VLX is a mobile hypervisor for incorporating multiple guest OSs over a single physical hardware platform. VLX supports shared device model that enables to share devices among multiple guest OSs similar to Xen. In their shared driver model, one guest OS has the device driver, and it is shared by communication channel provided by the hypervisor. VLX optimizes performance by locating the bridge driver inside the hypervisor in order to mitigate demultiplexing overhead. However, as shown in our study, using a real-time guest OS along with the driver domain presents degraded performance under some circumtances in terms of both response time and fair CPU utilization.
Xen-ARM is another hypervisor for ARM-based mobile systems. It is an ARM-port for Xen hypervisor, and it presents small footprint and secure access control. Xen-ARM supports the split driver model that has presented in Xen paravirtualization implementation. Xen’s split driver model enhances the reliability by isolating potentially faulty and untrusted device drivers from the trusted user domain. It separately locates IDD (Isolated Driver Domain), that has the physical drivers for virtualized devices, from user domains. IDD performs all physical I/O operations on behalf of the guest OSs, and hypervisor arbitrates only requests and responses among them. Since all drivers are excluded from the hypervisor, the hypervisor itself claims that it is more reliable. To mitigate the performance overhead from synchronous inter-VM communication, Xen-ARM extensively uses asynchronous I/O between IDD and user domain.
Xen-ARM supports the credit scheduler that is also used in Xen. It implements weighted round-robin scheduling algorithm and work-conserving mode. The scheduler periodically distributes the same amount of credit to all VCPUs, and debits as much as it executes. At the beginning, VCPU has UNDER priority, and the priority is changed to OVER when the VCPU consumes all its credits, and has minus credit values. The scheduler selects a VCPU among ones that has UNDER priority. To mitigate the worst-case response time for I/O tasks, it supports BOOST priority that temporarily prioritize interrupt-pending domain. BOOST is the highest priority among UNDER, OVER and BOOST, and the VCPU immediately preempt the running VCPU so that the I/O handling domain can be scheduled in a timely manner. However, it is beneficial only in limited cases because I/O boost in the credit scheduler doesn’t consider the urgency among boosted domains. In addition, boost is not always applied since the scheduler primarily focuses on fairness among CPU-bound domains. Namely, the credit scheduler is not feasible to support time-sensitive virtual machines.
The lack of time-sensitive applications support leads further studies on the credit scheduler. Task-aware scheduler proposed by Hwanjoo et. al. observes task scheduling within the guest OSs, and determines the characteristics of the guest OS whether it is CPU-bound or I/O-bound. Then, based on the estimation, the scheduler adaptively applies boost policy (named partial boost) so that I/O-bound domain can get guaranteed response time. Lee min et. al. proposed a new scheduler improving soft real-time performance. The scheduler estimates average execution time of the VCPU, and calculates the scheduling priority based on the deadline estimation of the VCPU. The scheduler further addresses multicore issues regarding task affinity to maximize cache utilization.
Yanyan et. al. presented I/O scheduling within multicore virtual machine. Proposed scheduler differently allocates CPU cores by workload characteristics: driver core, fast-tick core and slow-tick core. Driver core is dedicated for driver domain, fast tick cores are for I/O-bound domains, and slow-tick cores are for CPU-bound domains. Driver core is dedicated to the driver domain in order not to be preempted by another domain. Driver core minimizes the scheduling latency for physical driver execution and respective backend driver operations. Fast tick core reduces response time because the scheduler is invoked frequently according to the reduced tick interval. On the other hand, CPU-bound domains are running on the slow-tick cores in order to maximize cache utilization and throughput. Their approach is plausible, but in modern servers already have fast ticks with considerably small overhead, such as HRTimers in Linux. In addition, in embedded systems, high frequency timers are not applicable in many cases because the performance overhead for small tick interval is much significant than servers or desktop systems.
Latency presented in Xen-Arm
Recently, virtualization takes attention to mobile systems because it enhances reliability, security, and flexible user customizability. In recent mobile systems, security and user customizability are more important than ever before since it manages all private personal information and more users want to customize the device as their own way. In addition, those mobile systems recently serve as a business assistant, so reliability and security became serious concerns. Mobile systems virtualization can address those issues in an efficient manner. For example, Xen’s split driver presents enhanced reliability by isolating a faulty driver domain or virus-infected malicious domain from trusted user domains.
There are several hypervisors for mobile systems. OKL4 microvisor is one of the most representative hypervisors. OKL4 microvisor serves as trusted computing base, by using formally verified kernel, and it presents efficient virtualization enough to be used in commercial mobile devices. VirtualLogix-VLX is another commercial hypervisor for mobile systems. It supports shared driver model that enables both real-time guest OS and non-real-time guest OS to share a physical device. It also presents comparable performance to native systems. Xen-ARM is yet another approach for incorporating Xen into ARM-based mobile systems. It presents small footprint, secure access control.
Despite the advantages of virtualization in mobile systems, performance issue has to be addressed at the same time. Since mobile systems have limited hardware resources (e.g. power supply, memory size, CPU budgets, etc.,) the implementation has to be efficient enough to overcome the performance overhead from virtualization. Among various performance problems, I/O latency is one of serious concerns because many mobile systems have communication device that needs to handle signaling protocols in a timely manner. In particular, the split driver model in Xen-ARM presents additional latency larger than 1ms, which could disconnect the mobile device from the networks.
In this paper, we analyze the two major sources of I/O latency in Xen-ARM’s split driver model, and propose a new scheduler in order for a real-time guest OS to handle I/O in a timely manner. Our analysis, at first, reveals that interrupt delivery to driver domain can be delayed because interrupt handling is virtualized when running within a guest OS. Although a driver domain disables virtual interrupts, physical interrupt can still be occurred, which might trigger inter-VM scheduling. Thus, physical driver in the driver domain cannot guaranteed to be scheduled in a timely manner. Secondly, additional latency is observed by inter-VM scheduling between the execution of backend and frontend drivers. Even though the existing scheduler supports I/O boost priority, I/O boost can be easily negated by multiple boost or ignored by fair scheduling policy.
To reduce latency while retaining the split driver model, we improve the scheduler so that the driver domain cannot be scheduled out when it disables virtual interrupts and the scheduler provide static priorities to guest OSs in order to provide a time bounded I/O latency. With our scheduler, all I/O interrupt at real-time guest OS is handled within 1ms while retaining split driver model, which is more strict latency bound than native ARM-Linux.
This paper consists of five sections. Section 2 introduces related work on embedded hypervisors and
Related Work
OKL4 microvisor is one of representative hypervisors for mobile systems. It is originated from L4 microkernel that overcomes the performance problems of first generation of microkernels. With extensive architectural optimization, L4Linux achieves good performance as close as native Linux, and OKL4 microvisor presents flexible architecture to incorporate multiple commodity operating systems. On top of that, it supports user-level device driver, which de-privileges driver domain in order to protect trusted user domains from the faulty driver implementation. In addition to performance, it is verified with formal language, so they claim that their hypervisor is bug-free, and thereby it is trustworthy.
Regarding the real-time performance, L4/Fiasco has been developed for real-time and embedded systems. It supports real-time OSs with several optimizations including direct task switching, time slice donation, and user-level reflective scheduling, etc. Although L4’s effort on real-time support presents impressive results in both desktop systems and embedded systems, their performance impact has not been thoroughly analyzed with more complex systems with virtualization such as multiple guest OS environment or multiple driver interactions.
Another hypervisor, VirtualLogix-VLX is a mobile hypervisor for incorporating multiple guest OSs over a single physical hardware platform. VLX supports shared device model that enables to share devices among multiple guest OSs similar to Xen. In their shared driver model, one guest OS has the device driver, and it is shared by communication channel provided by the hypervisor. VLX optimizes performance by locating the bridge driver inside the hypervisor in order to mitigate demultiplexing overhead. However, as shown in our study, using a real-time guest OS along with the driver domain presents degraded performance under some circumtances in terms of both response time and fair CPU utilization.
Xen-ARM is another hypervisor for ARM-based mobile systems. It is an ARM-port for Xen hypervisor, and it presents small footprint and secure access control. Xen-ARM supports the split driver model that has presented in Xen paravirtualization implementation. Xen’s split driver model enhances the reliability by isolating potentially faulty and untrusted device drivers from the trusted user domain. It separately locates IDD (Isolated Driver Domain), that has the physical drivers for virtualized devices, from user domains. IDD performs all physical I/O operations on behalf of the guest OSs, and hypervisor arbitrates only requests and responses among them. Since all drivers are excluded from the hypervisor, the hypervisor itself claims that it is more reliable. To mitigate the performance overhead from synchronous inter-VM communication, Xen-ARM extensively uses asynchronous I/O between IDD and user domain.
Xen-ARM supports the credit scheduler that is also used in Xen. It implements weighted round-robin scheduling algorithm and work-conserving mode. The scheduler periodically distributes the same amount of credit to all VCPUs, and debits as much as it executes. At the beginning, VCPU has UNDER priority, and the priority is changed to OVER when the VCPU consumes all its credits, and has minus credit values. The scheduler selects a VCPU among ones that has UNDER priority. To mitigate the worst-case response time for I/O tasks, it supports BOOST priority that temporarily prioritize interrupt-pending domain. BOOST is the highest priority among UNDER, OVER and BOOST, and the VCPU immediately preempt the running VCPU so that the I/O handling domain can be scheduled in a timely manner. However, it is beneficial only in limited cases because I/O boost in the credit scheduler doesn’t consider the urgency among boosted domains. In addition, boost is not always applied since the scheduler primarily focuses on fairness among CPU-bound domains. Namely, the credit scheduler is not feasible to support time-sensitive virtual machines.
The lack of time-sensitive applications support leads further studies on the credit scheduler. Task-aware scheduler proposed by Hwanjoo et. al. observes task scheduling within the guest OSs, and determines the characteristics of the guest OS whether it is CPU-bound or I/O-bound. Then, based on the estimation, the scheduler adaptively applies boost policy (named partial boost) so that I/O-bound domain can get guaranteed response time. Lee min et. al. proposed a new scheduler improving soft real-time performance. The scheduler estimates average execution time of the VCPU, and calculates the scheduling priority based on the deadline estimation of the VCPU. The scheduler further addresses multicore issues regarding task affinity to maximize cache utilization.
Yanyan et. al. presented I/O scheduling within multicore virtual machine. Proposed scheduler differently allocates CPU cores by workload characteristics: driver core, fast-tick core and slow-tick core. Driver core is dedicated for driver domain, fast tick cores are for I/O-bound domains, and slow-tick cores are for CPU-bound domains. Driver core is dedicated to the driver domain in order not to be preempted by another domain. Driver core minimizes the scheduling latency for physical driver execution and respective backend driver operations. Fast tick core reduces response time because the scheduler is invoked frequently according to the reduced tick interval. On the other hand, CPU-bound domains are running on the slow-tick cores in order to maximize cache utilization and throughput. Their approach is plausible, but in modern servers already have fast ticks with considerably small overhead, such as HRTimers in Linux. In addition, in embedded systems, high frequency timers are not applicable in many cases because the performance overhead for small tick interval is much significant than servers or desktop systems.
Latency presented in Xen-Arm
Monday, May 23, 2011
As CPU executes, information flows.
Title: As CPU executes, information flows.
Temporal information flow control - trusting timely execution
I. Introduction
Reliability and trustworthiness are two of the most important principles in modern computer systems design. It is important not only for financial companies, but also for governments, military, and every individual living in digital era. For trust computing, a system is built from a very reliable trust computing base and each system component has to be constructed with a trust chain so that the behavior of system and sensitive user information can be controlled with high-level of integrity and confidentiality. In many trustworthy computing systems design, information flow control is widely used as a major access control mechanism.
Existing information flow control (IFC) schemes focus on the direction of information flow. Namely, it prevents information from flowing to an unintended or undesired direction. In order to control the direction of information, a reference monitor observes the information flow and performs admission control.
However, existing information flow control cannot capture the notion of temporal properties of information flow. This paper presents a new perspective to information flow control, temporal information flow control. Temporal information flow control (Temporal IFC) identifies the temporal property of information flow so that a system manages information in a temporally sound manner.
Temporal IFC enables to build more reliable and trustworthy computing base. We can more strictly restrain unintended information flow with more fine-grained behaviors control. Although contemporary trust platform module (or TPM) provides validation for a platform, it lacks in dynamic behavior control. Since TPM uses a statically generated key, it cannot capture dynamic behavior of program execution.
This paper focuses on the fact that information leak usually happens with valid directional information flow. Most attackers tackle pathological weak points that cannot be easily traced by defenders. Namely, they steal information via valid path, and store the information for later use. In terms of temporal information flow control, information flow is valid only for temporally sound behaviors. So, information cannot be abused by malicious user even though it is exposed. TPM is one of such efforts, but is never a perfect solution since it uses a static key, and once key is stolen, secrecy and integrity can be broken. Temporal IFC maintains time-varying key that is very unpredictable, so it makes very difficult to abuse information with replay-like attacks.
Besides security perspectives, this paper is trying to find a pin-point where trustworthy computing meets real-time and time-sensitive information. In perspective from temporal IFC, integrity for information is regarded as broken when the information flows at temporally invalid time instant. Similarly, in a real-time system, data processing after deadlines are regarded as invalid, and the temporal integrity of information is broken. In such systems, data handling has to be finished within a specific amount of time since the data is valid temporarily. Temporal IFC tries to explain the scheduling-related information flow with derivative properties so that we can guarantee temporal behavior of program execution.
Paper is organized as following. Section 2 presents several related works. Section 3 defines temporal information flow control and properties. Section 4 explains ...
II. Related work
[Scheduling and Temporal information flow control]
[Stochastic/Probabilistic theoretic approach - Queuing theoretical interpretation for temporal information flow control]
[Real-time scheduling approach - Derivative properties for temporal information flow control]
[Instruction scheduling approach - micro-architectural instruction execution scheduling]
[Information theoretic interpretation of scheduling]
III. Temporal information flow control
[Basic idea for information flow control]
Information flow in a computer system can be defined by the propagation of information from one place to another. As program executes, values of registers, memory values, cached data are changed, which implies the information is propagated.
[Information flow control for trustworthy computer system]
Trustworthiness in existing computer systems depends on the accurate information flow in order to guarantee integrity, confidentiality of private information. The system behavior is strictly controlled by the reference monitor that resides inside an operating system so that it can observe all private information flow within a target system. The reference monitor controls the admissions to access from unreliable and untrusting users, and selectively grants operations by its policies. The information flow control thereby restricts the unintended information flow by leaks in a target system.
[Challenges in Temporal Information Flow control]
Unfortunately, information flow is difficult to control practically since memory access is widely open to every instruction in modern computers. Although modern computer architecture support ‘protected mode’ in order to protect memory from untrusted user applications, operating system, which runs in protected mode, has become too large to be statically analyzed. Moreover, behavior can also be changed dynamically at runtime (by dynamic kernel modules) and it is almost impossible to tracking all the kernel variables by time.
Temporal information flow control is more difficult than traditional information flow control because information flows by every instruction, and it is extremely difficult to control the timing of every instruction execution. Modern computer architectures support pipelining and out-of-order execution, so it is almost impossible to control the execution at instruction level. Instead, this paper focuses on the level of granularity that can be manageable at operating system.
[Limitations of existing information flow control]
Although existing reference monitor-based information flow control schemes capture important trustworthy properties in information flow, but they do not provide any notion of temporal validity of information flow. We observe that information leaks can be temporally incurred, and claim that temporal information flow should also be guaranteed for higher level of trustworthiness.
Most attackers focus on leaking information since the obtained information can be reused in most cases. For example, stack overflow attacks are making use of invalid temporal information flow. Stack frame stores the location of former stack frame, and user can access historic behavior of execution by traversing the stack frames. By carefully observing this historic behavioral pattern, attacker can get much information than expected such as values of local variables, indirect pointer values of newly allocated objects, etc. Although recent IFC approaches use taint-based integrity checks, it is still allow to access and trace private information.
By notion of temporal IFC, private information is secured by temporal key (or timed key). Since the key changes by time, and the entropy of the key is very high, so it is very difficult to get information once key is lost. Our timed key is inspired by one-time password system. In one-time password system, any password is only available at the moment of transaction, and never be utilized at any other time. In the system, information flow is secured by temporal property since the information is only available at the moment of transaction, and invalidated by time. Even though the password is intercepted by a malicious user, intercepted information cannot be used anymore. This paper realizes the notion of time-varying key, and temporal IFC with architectural support.
Furthermore, we apply the notion of temporal IFC to trustworthy computing in real-time systems. Task execution within a real-time system has temporal execution condition. Namely, a real-time task has deadline that the task has to be finished. Deadline miss can significantly degrade performance for soft real-time system applications, or incurs system failure for hard real-time systems. In order to meet deadline, a real-time task should be timely executed. In terms of information flow control, the system guarantee that information flow should be guaranteed temporally; information flow after the temporal deadline is not validated, and the integrity of the information is regarded as broken. So, trustworthiness in a real-time system implies that the program execution is sound in terms of information flow not only by direction, but also by temporal timeliness.
[Real-time scheduling and temporal information flow]
Temporal information flow control resembles the scheduling of tasks, in nature. Since scheduling within an operating system determines task/thread to execute, which implies to select instruction streams to execute. Namely, scheduling within operating system controls the temporal information flow by choosing instruction streams at processor.
In order to have a valid information, processing for the information has to be finished within a deadline. It involves the notion of real-time scheduling so that it guarantees the deadline of OS tasks. Note that important system events have to be explicitly triggered with time information.
IV. The operation of Temporal IFC
In this section, we explain the operation of Temporal IFC. For temporal IFC, we use timed key mechanism. Timed key is established with the following three steps. At first, a timed key has to be installed at the beginning of the operation. Secondly, data has to be securely acquired from device to processor. Thirdly, the raw data is encrypted by the key and opened to memory. Once a temporal key is established, runtime validation is performed so that the information user can preserve the integrity and confidentiality. Key has to be updated in cases when the data is transferred to another task. So, this section presents temporal key establishment, runtime validation of secure information, and key update for temporal IFC. As an example, we explain the temporal IFC by network packet processing in simple real-time operating system.
[Establishment of Timed Key]
A timed key has to be generated at beginning of the operation. Basically, all tainted data (e.g. incoming network packets) are encrypted with this key so that the information is only available with the associated timed key.
When an interrupt occurs, the hardware generates a new timed key. The key is generated with the current timestamp, and stored only inside the processor so that it cannot be easily exposed to other malicious users. Processor maintains the temporal key table which associates object and timed key. At the time of generation, target execution routine (interrupt handler) is stored instead of object since there is no associate object. At the beginning of interrupt handler, the registered key index is handed as a parameter. Note that, the key is not exposed to other software.
At the beginning of interrupt handler, data have to be acquired from device. For data acquisition without CPU operation such as DMA, data is directly moved to processor’s internal memory instead of main RAM so that the user data are not opened to memory without the control of processor. In most cases, packet data is delivered via DMA, and secure DMA function delivers data from NIC to cache or transactional memory inside processor.
Recent direct cache access (DCA) can be used for secure data delivery from device to processor with perfect control of processor. When DCA is applied, data is moved from driver to cache directly with the help of new snoop protocol. Because data are placed in cache, CPU can access data immediately after delivery and can begin encryption even before it is written to main memory. For ARM-based processors, TCM(Tightly-coupled memory) is widely available, and DMA to TCM is possible. So, it similarly works with embedded processors.
Just after getting data from NIC, packet data is security is validated inside the processor. Namely, it is encrypted with timed key. At here, temporal key table is updated so that the secrecy of the object is associated with the given timed key. Note that most operations are run within cache, and cacheline is invalidated after encryption is finished since it can be exported to memory with strong protection.
[Runtime Validation of Secure Information Flow]
Once secure key is established, OS can safely deliver information with strong protection. All data are encrypted with secure timed key, and only available to a user within a given deadline. Since data have been encrypted, it cannot be properly interpreted before decrypted. Decryption logic has to be implemented in hardware and the protected information has to be isolated from untrusted/unsafe code.
Architecturally, we define a Secure Segment, in which all data are safely accessed via platform protection mechanism. All data access to secure segment is required to have proper privilege level. Since all data in secure segment are encrypted, CPU operation which touches the segment involves decryption.
We note that even though secure segment guards the access from untrusted code, register operation can still bypass the protection boundary, and storing register value to untrusted area can leak the information. Even though the code should have a proper privilege level, and should be accessible to secure segment in a sound manner, it may lead to unintended information flow. By Bell-Lapadula’s multi-level security model, higher security level subject cannot write lower security level object since higher security level subject can leak information that only he is responsible to manage.
We architecturally implement multi-level security model, and prevent information leak using memory and register access. In addition to secure segment, we adopt trusted mode, which can access the secure segment. When the processor enters trusted mode, then processor denies all memory write access to insecure segments (not-secure segment) as described above. In addition, trusted mode uses banked registers, so register values in secure segment cannot flow to insecure registers.
For untrusted mode, memory access is permitted for read/write for only insecure segments. Once encrypted, data is securely stored inside secure segment. Since the key is only available temporarily, and stored inside the processor, it cannot bypass protection boundary. In addition, any software routine cannot decrypt and access to the information without temporally valid key.
The key is valid during task to handle the information, and should be invalidated. So, the integrity is preserved within a task execution. However, in many cases, OS tasks co-operate each other and the information flows over task boundaries. In order to handle information flow that cross over task boundary, the timed key has to be hand-over so that another task can manage time-sensitive information.
When hand-over is triggered, then the processor generates a new timed key for the next task execution, and cypher text is re-encrypted with new key. So, a new key is required in order to access the data, and old information is not valid after the hand-over.
Finally, when the information is consumed by the end-user, the information has to be invalidated immediately so that it cannot be re-used, and abused by malicious user. In this case, trust for the information is broken, and can never be revoked. The data is pushed to insecure segment without protection, and the processor destroys the entry in the key table.
[Time-Varying Key : The Key maker function]
In our temporal IFC, timed key plays an important role since all data access is performed with timed key, which is temporally changing key value. It is difficult two folds: firstly, the key has to be changed by time so that the attacker cannot guess or predict the key value, secondly, the key value has to be unchanged until the corresponding task finishes its job; otherwise, all valid information flow generates false-positive alerts.
So, timed key should not be changed for the corresponding task execution, and should be time-varying so that the key value cannot be used for different time instants except for the corresponding task execution.
We achieve both goals by generating time varying key. Time varying key is generated from the internal and invisible clocksource. High bits of the timer clock source specifies the hash key to look up the timed key in the temporal key table. Low bits of the timer clock source generates randomized timed keys. We observe that high bits are changing smoothly than lower bits, so it is easier to specify the time duration for task execution. On the other hands, low bits are very sensitive to time instant that physical events occurs, which is very unpredictable. So, we use the low-bits for random source, and high bits to give time-variants. For multiple data handling at the same time instant, the table maintains Tag bits for exact matching the address for the data.
At the operation time, after passing the secure segment logic, data has to be decrypted and the plain text is given to the banked register of trusted mode. In order to decrypt the cypher text, the processor fetches time value from clock source, and finds the temporal key table with high bits. After that, the address of the data is matched within tag bits in temporal key table so that it ensures the valid timed key is used for the accessing data. Finally, the timed key is obtained from the table, and performs decryption and move the plain text into register.
%[Example]
%We explain the temporal IFC by network packet processing example. For validating the temporal integrity of information, OS routines are invoked with timestamps. For example, NetISR (network interrupt service routine) is called with not only the registers, but also timestamp. Then, the ISR can validate the packetdata by timestamp. Once it is validated, then the designated routine begins to work with packetdata. It can be orthogonally work with other taint-based approaches at here. Each packetdata has its deadline, so OS should be able to schedule the designated task properly.
%Timestamp also have to be properly protected; otherwise the information is easily leaked by hacking the timestamp values. For mandating IFC and securely protecting timestamp, we take advantage of hardware. The H/W platform should include store and record all hardware events with timstamps. The timestamp is not accessed by user-level programs, and only available at specified points. The time-related information is provided via special-purpose register. OS then checks integrity by time-shuffled key which is stored in hardware.
%In order to keep temporal integrity continuously, the system repeatedly invalidate information by task granularity. For example, the information at NetISR is invalidated at IPTask/TCPTask (or ProtocolTasks) and user task.
%For preserving the integrity of the information, inter-task communication also has to be involved with temporally valid key information. Namely, key information has to be stored by OS so that receiving task can properly decrypt (and handle) the original information.
Temporal information flow control - trusting timely execution
I. Introduction
Reliability and trustworthiness are two of the most important principles in modern computer systems design. It is important not only for financial companies, but also for governments, military, and every individual living in digital era. For trust computing, a system is built from a very reliable trust computing base and each system component has to be constructed with a trust chain so that the behavior of system and sensitive user information can be controlled with high-level of integrity and confidentiality. In many trustworthy computing systems design, information flow control is widely used as a major access control mechanism.
Existing information flow control (IFC) schemes focus on the direction of information flow. Namely, it prevents information from flowing to an unintended or undesired direction. In order to control the direction of information, a reference monitor observes the information flow and performs admission control.
However, existing information flow control cannot capture the notion of temporal properties of information flow. This paper presents a new perspective to information flow control, temporal information flow control. Temporal information flow control (Temporal IFC) identifies the temporal property of information flow so that a system manages information in a temporally sound manner.
Temporal IFC enables to build more reliable and trustworthy computing base. We can more strictly restrain unintended information flow with more fine-grained behaviors control. Although contemporary trust platform module (or TPM) provides validation for a platform, it lacks in dynamic behavior control. Since TPM uses a statically generated key, it cannot capture dynamic behavior of program execution.
This paper focuses on the fact that information leak usually happens with valid directional information flow. Most attackers tackle pathological weak points that cannot be easily traced by defenders. Namely, they steal information via valid path, and store the information for later use. In terms of temporal information flow control, information flow is valid only for temporally sound behaviors. So, information cannot be abused by malicious user even though it is exposed. TPM is one of such efforts, but is never a perfect solution since it uses a static key, and once key is stolen, secrecy and integrity can be broken. Temporal IFC maintains time-varying key that is very unpredictable, so it makes very difficult to abuse information with replay-like attacks.
Besides security perspectives, this paper is trying to find a pin-point where trustworthy computing meets real-time and time-sensitive information. In perspective from temporal IFC, integrity for information is regarded as broken when the information flows at temporally invalid time instant. Similarly, in a real-time system, data processing after deadlines are regarded as invalid, and the temporal integrity of information is broken. In such systems, data handling has to be finished within a specific amount of time since the data is valid temporarily. Temporal IFC tries to explain the scheduling-related information flow with derivative properties so that we can guarantee temporal behavior of program execution.
Paper is organized as following. Section 2 presents several related works. Section 3 defines temporal information flow control and properties. Section 4 explains ...
II. Related work
[Scheduling and Temporal information flow control]
[Stochastic/Probabilistic theoretic approach - Queuing theoretical interpretation for temporal information flow control]
[Real-time scheduling approach - Derivative properties for temporal information flow control]
[Instruction scheduling approach - micro-architectural instruction execution scheduling]
[Information theoretic interpretation of scheduling]
III. Temporal information flow control
[Basic idea for information flow control]
Information flow in a computer system can be defined by the propagation of information from one place to another. As program executes, values of registers, memory values, cached data are changed, which implies the information is propagated.
[Information flow control for trustworthy computer system]
Trustworthiness in existing computer systems depends on the accurate information flow in order to guarantee integrity, confidentiality of private information. The system behavior is strictly controlled by the reference monitor that resides inside an operating system so that it can observe all private information flow within a target system. The reference monitor controls the admissions to access from unreliable and untrusting users, and selectively grants operations by its policies. The information flow control thereby restricts the unintended information flow by leaks in a target system.
[Challenges in Temporal Information Flow control]
Unfortunately, information flow is difficult to control practically since memory access is widely open to every instruction in modern computers. Although modern computer architecture support ‘protected mode’ in order to protect memory from untrusted user applications, operating system, which runs in protected mode, has become too large to be statically analyzed. Moreover, behavior can also be changed dynamically at runtime (by dynamic kernel modules) and it is almost impossible to tracking all the kernel variables by time.
Temporal information flow control is more difficult than traditional information flow control because information flows by every instruction, and it is extremely difficult to control the timing of every instruction execution. Modern computer architectures support pipelining and out-of-order execution, so it is almost impossible to control the execution at instruction level. Instead, this paper focuses on the level of granularity that can be manageable at operating system.
[Limitations of existing information flow control]
Although existing reference monitor-based information flow control schemes capture important trustworthy properties in information flow, but they do not provide any notion of temporal validity of information flow. We observe that information leaks can be temporally incurred, and claim that temporal information flow should also be guaranteed for higher level of trustworthiness.
Most attackers focus on leaking information since the obtained information can be reused in most cases. For example, stack overflow attacks are making use of invalid temporal information flow. Stack frame stores the location of former stack frame, and user can access historic behavior of execution by traversing the stack frames. By carefully observing this historic behavioral pattern, attacker can get much information than expected such as values of local variables, indirect pointer values of newly allocated objects, etc. Although recent IFC approaches use taint-based integrity checks, it is still allow to access and trace private information.
By notion of temporal IFC, private information is secured by temporal key (or timed key). Since the key changes by time, and the entropy of the key is very high, so it is very difficult to get information once key is lost. Our timed key is inspired by one-time password system. In one-time password system, any password is only available at the moment of transaction, and never be utilized at any other time. In the system, information flow is secured by temporal property since the information is only available at the moment of transaction, and invalidated by time. Even though the password is intercepted by a malicious user, intercepted information cannot be used anymore. This paper realizes the notion of time-varying key, and temporal IFC with architectural support.
Furthermore, we apply the notion of temporal IFC to trustworthy computing in real-time systems. Task execution within a real-time system has temporal execution condition. Namely, a real-time task has deadline that the task has to be finished. Deadline miss can significantly degrade performance for soft real-time system applications, or incurs system failure for hard real-time systems. In order to meet deadline, a real-time task should be timely executed. In terms of information flow control, the system guarantee that information flow should be guaranteed temporally; information flow after the temporal deadline is not validated, and the integrity of the information is regarded as broken. So, trustworthiness in a real-time system implies that the program execution is sound in terms of information flow not only by direction, but also by temporal timeliness.
[Real-time scheduling and temporal information flow]
Temporal information flow control resembles the scheduling of tasks, in nature. Since scheduling within an operating system determines task/thread to execute, which implies to select instruction streams to execute. Namely, scheduling within operating system controls the temporal information flow by choosing instruction streams at processor.
In order to have a valid information, processing for the information has to be finished within a deadline. It involves the notion of real-time scheduling so that it guarantees the deadline of OS tasks. Note that important system events have to be explicitly triggered with time information.
IV. The operation of Temporal IFC
In this section, we explain the operation of Temporal IFC. For temporal IFC, we use timed key mechanism. Timed key is established with the following three steps. At first, a timed key has to be installed at the beginning of the operation. Secondly, data has to be securely acquired from device to processor. Thirdly, the raw data is encrypted by the key and opened to memory. Once a temporal key is established, runtime validation is performed so that the information user can preserve the integrity and confidentiality. Key has to be updated in cases when the data is transferred to another task. So, this section presents temporal key establishment, runtime validation of secure information, and key update for temporal IFC. As an example, we explain the temporal IFC by network packet processing in simple real-time operating system.
[Establishment of Timed Key]
A timed key has to be generated at beginning of the operation. Basically, all tainted data (e.g. incoming network packets) are encrypted with this key so that the information is only available with the associated timed key.
When an interrupt occurs, the hardware generates a new timed key. The key is generated with the current timestamp, and stored only inside the processor so that it cannot be easily exposed to other malicious users. Processor maintains the temporal key table which associates object and timed key. At the time of generation, target execution routine (interrupt handler) is stored instead of object since there is no associate object. At the beginning of interrupt handler, the registered key index is handed as a parameter. Note that, the key is not exposed to other software.
At the beginning of interrupt handler, data have to be acquired from device. For data acquisition without CPU operation such as DMA, data is directly moved to processor’s internal memory instead of main RAM so that the user data are not opened to memory without the control of processor. In most cases, packet data is delivered via DMA, and secure DMA function delivers data from NIC to cache or transactional memory inside processor.
Recent direct cache access (DCA) can be used for secure data delivery from device to processor with perfect control of processor. When DCA is applied, data is moved from driver to cache directly with the help of new snoop protocol. Because data are placed in cache, CPU can access data immediately after delivery and can begin encryption even before it is written to main memory. For ARM-based processors, TCM(Tightly-coupled memory) is widely available, and DMA to TCM is possible. So, it similarly works with embedded processors.
Just after getting data from NIC, packet data is security is validated inside the processor. Namely, it is encrypted with timed key. At here, temporal key table is updated so that the secrecy of the object is associated with the given timed key. Note that most operations are run within cache, and cacheline is invalidated after encryption is finished since it can be exported to memory with strong protection.
[Runtime Validation of Secure Information Flow]
Once secure key is established, OS can safely deliver information with strong protection. All data are encrypted with secure timed key, and only available to a user within a given deadline. Since data have been encrypted, it cannot be properly interpreted before decrypted. Decryption logic has to be implemented in hardware and the protected information has to be isolated from untrusted/unsafe code.
Architecturally, we define a Secure Segment, in which all data are safely accessed via platform protection mechanism. All data access to secure segment is required to have proper privilege level. Since all data in secure segment are encrypted, CPU operation which touches the segment involves decryption.
We note that even though secure segment guards the access from untrusted code, register operation can still bypass the protection boundary, and storing register value to untrusted area can leak the information. Even though the code should have a proper privilege level, and should be accessible to secure segment in a sound manner, it may lead to unintended information flow. By Bell-Lapadula’s multi-level security model, higher security level subject cannot write lower security level object since higher security level subject can leak information that only he is responsible to manage.
We architecturally implement multi-level security model, and prevent information leak using memory and register access. In addition to secure segment, we adopt trusted mode, which can access the secure segment. When the processor enters trusted mode, then processor denies all memory write access to insecure segments (not-secure segment) as described above. In addition, trusted mode uses banked registers, so register values in secure segment cannot flow to insecure registers.
For untrusted mode, memory access is permitted for read/write for only insecure segments. Once encrypted, data is securely stored inside secure segment. Since the key is only available temporarily, and stored inside the processor, it cannot bypass protection boundary. In addition, any software routine cannot decrypt and access to the information without temporally valid key.
The key is valid during task to handle the information, and should be invalidated. So, the integrity is preserved within a task execution. However, in many cases, OS tasks co-operate each other and the information flows over task boundaries. In order to handle information flow that cross over task boundary, the timed key has to be hand-over so that another task can manage time-sensitive information.
When hand-over is triggered, then the processor generates a new timed key for the next task execution, and cypher text is re-encrypted with new key. So, a new key is required in order to access the data, and old information is not valid after the hand-over.
Finally, when the information is consumed by the end-user, the information has to be invalidated immediately so that it cannot be re-used, and abused by malicious user. In this case, trust for the information is broken, and can never be revoked. The data is pushed to insecure segment without protection, and the processor destroys the entry in the key table.
[Time-Varying Key : The Key maker function]
In our temporal IFC, timed key plays an important role since all data access is performed with timed key, which is temporally changing key value. It is difficult two folds: firstly, the key has to be changed by time so that the attacker cannot guess or predict the key value, secondly, the key value has to be unchanged until the corresponding task finishes its job; otherwise, all valid information flow generates false-positive alerts.
So, timed key should not be changed for the corresponding task execution, and should be time-varying so that the key value cannot be used for different time instants except for the corresponding task execution.
We achieve both goals by generating time varying key. Time varying key is generated from the internal and invisible clocksource. High bits of the timer clock source specifies the hash key to look up the timed key in the temporal key table. Low bits of the timer clock source generates randomized timed keys. We observe that high bits are changing smoothly than lower bits, so it is easier to specify the time duration for task execution. On the other hands, low bits are very sensitive to time instant that physical events occurs, which is very unpredictable. So, we use the low-bits for random source, and high bits to give time-variants. For multiple data handling at the same time instant, the table maintains Tag bits for exact matching the address for the data.
At the operation time, after passing the secure segment logic, data has to be decrypted and the plain text is given to the banked register of trusted mode. In order to decrypt the cypher text, the processor fetches time value from clock source, and finds the temporal key table with high bits. After that, the address of the data is matched within tag bits in temporal key table so that it ensures the valid timed key is used for the accessing data. Finally, the timed key is obtained from the table, and performs decryption and move the plain text into register.
%[Example]
%We explain the temporal IFC by network packet processing example. For validating the temporal integrity of information, OS routines are invoked with timestamps. For example, NetISR (network interrupt service routine) is called with not only the registers, but also timestamp. Then, the ISR can validate the packetdata by timestamp. Once it is validated, then the designated routine begins to work with packetdata. It can be orthogonally work with other taint-based approaches at here. Each packetdata has its deadline, so OS should be able to schedule the designated task properly.
%Timestamp also have to be properly protected; otherwise the information is easily leaked by hacking the timestamp values. For mandating IFC and securely protecting timestamp, we take advantage of hardware. The H/W platform should include store and record all hardware events with timstamps. The timestamp is not accessed by user-level programs, and only available at specified points. The time-related information is provided via special-purpose register. OS then checks integrity by time-shuffled key which is stored in hardware.
%In order to keep temporal integrity continuously, the system repeatedly invalidate information by task granularity. For example, the information at NetISR is invalidated at IPTask/TCPTask (or ProtocolTasks) and user task.
%For preserving the integrity of the information, inter-task communication also has to be involved with temporally valid key information. Namely, key information has to be stored by OS so that receiving task can properly decrypt (and handle) the original information.
Saturday, May 21, 2011
엄마를 부탁해 - 진한 느낌의 뮤지컬
어제 뮤지컬 ‘엄마를 부탁해’를 관람했다. 워낙 잘 알려져 있는 소설인데다 최근에 미국에서도 성공적인 데뷔를 했다고 해서 관심을 갖고 있던 차에, 정말 고맙게도 처제의 뜻밖의 티켓 선물로 아내와 같이 볼 기회가 생긴 것이다. 아내와 같이 공연장을 찾은 것이 얼마만인지.. 연말 공연이라도 예매해야겠다는 다짐을 하고 충무 아트 센터에 도착한 시간은 6시 반. 공연은 7시 반이라, 저녁 식사 시간의 빠듯한 시간도 있었다. 저녁 식사를 마치고, 공연장으로 올라갔다.
뮤지컬은 처음부터 극적으로 계속 고조되는 형태였다. 어머니를 잃어버리다니! 충격으로 시작된 극은, 나머지 가족들을 중심으로 그려져 가고 있었다. 아들과 딸들, 아버지의 후회와 자책으로 이어지고 있지만, 그 안에서 우리 가족을 발견하고는 나도 몇 번이나 목이 메었다.
특히, 아들에 대한 애틋한 어머니를 표현한 아들의 회상 신은 마치 내가 어머니를 그 자리에서 꼭 찾아야만 할 것 같은 느낌을 주었다. 내 자취방 시절이나, 최근 이사온 우리 집 생활이 극 중에서 오버랩되면서, 아들의 입장과 느낌이 고스란히 내게 전해졌다. 데면데면한 아버지의 모습이나, 엄마와의 특별한 감정을 갖고 있는 여동생의 모습도, 많은 극 중의 디테일이 내 기억에서 현실로 바뀌었고, 정말 머릿 속이 복잡다양한 생각으로 꽉찼다..
1막이 정리되고, 불이 들어왔다. 아내는 옆에서 많이 울었다. 워낙 감수성이 풍부한 사람인지라, 안 울 수가 없었을게다. 자리가 살짝 비어있길래 조금 더 편한 자리로 자리를 옮겼다. 옮긴 좌석에선 얼굴과 음향감독도 볼 수 있었다. 막간을 통해 전화를 하지 않을 수 없었다. 어머니에게.. 안받으신다. 현실에는 늘 그자리에 계신 어머니가 길을 잃으신 건 아닌지. 동생에게 대신 안부전화를 넣고 위로할 수 밖에.
2막은 어머니의 일생으로 초점을 맞췄다. 내 어머니의 일생과 목표, 꿈, 시집살이와 자식과 식구들이 모르는 어머니의 삶이 그려졌다. 지난 해 어머니 자서전을 집에서 본 기억이 났다. 내 어머니도 글쓰기를 좋아하시는 문학 소녀적 감성이 풍부한 분이셨는데.. 정작 당신이 자작 일기를 책으로 편집 하실 때는 내가 너무 무심히 지나갔던 건 아닌지.
뮤지컬이란 장르는 특성 상 음악으로 스토리를 끌고 가게 되는데, 너무 무겁게 진행이 되자 사실 마음이 편하진 않았다. 청중들의 감정선을 계속해서 극단으로 몰아붙이는, 그래서 청중에게도 힘든 극이었다. 연기자들도 그만큼 힘들겠지. 이런 극을 매일 하려면, 아주 강인한 사람이어야 할 것 같다.. 극을 하면서 울 수도, 그렇다고 감정을 걷어내고 연기할 수도 없을테니..
극 후반으로 들어서자 특히 어머니의 걸음걸이나 말투가 연기하시는 김성녀씨에게서 너무 똑같이 나타나고 있었다. 눈치채기 어려운 전라도 사투리와 문어체가 살짝 섞인 말투, 그리고 걷는 모양, 얼굴 분장까지 너무 똑같은 느낌이 들었다. 이제 참기 힘든 지경이다.
극에서 어머니는 돌아오지 못한다. .. 그리고 보니, 제목이 마음에 들지 않는다. 어머니를 부탁해 - 누가.. 누구에게 부탁한 건가. 아버지가 자식들에게 어머니를 부탁한 것 까지는 그렇다 치자. 자식들도 누군가에게 어머니를 부탁하고 있다. 갑자기 여기서부터 화가 났다. 대체 자식들이 부모를 누구에게 부탁한단 말인가. 아내는 그냥 받아들이라고 했지만.. 매우 답답해졌다. 청중에게 부탁했던 것인가.. 왜 작가는 극에서 어머니를 무책임하게 버리는 선택을 했을까. 비극적인 장치라고 하기엔, 너무 내게 현실적으로 다가왔다. 마치 가까이의 누군가가 어머니를 잃어버리고, 이제 난 모르겠으니 누군가에게 부탁한다고 도피한 느낌이다. 아... 내가 화가 난 이유는, 그게 내 모습이 아니길 바라기 때문이다.
간만의 뮤지컬 공연 관람이 끝나고 집에 돌아오면서, 아내와 그런 얘기들로 공연을 되씹었다. 전체적으로 무겁게 진행되는 마음 불편한 극이라는 것이라는 것과 스토리가 무책임한 자식을 조명하며 끝나는 점이 아쉽긴 했지만, 간만에 감성을 충전한 느낌이다. 처제~ 고마워요~. 어머니 사랑해요~.
뮤지컬은 처음부터 극적으로 계속 고조되는 형태였다. 어머니를 잃어버리다니! 충격으로 시작된 극은, 나머지 가족들을 중심으로 그려져 가고 있었다. 아들과 딸들, 아버지의 후회와 자책으로 이어지고 있지만, 그 안에서 우리 가족을 발견하고는 나도 몇 번이나 목이 메었다.
특히, 아들에 대한 애틋한 어머니를 표현한 아들의 회상 신은 마치 내가 어머니를 그 자리에서 꼭 찾아야만 할 것 같은 느낌을 주었다. 내 자취방 시절이나, 최근 이사온 우리 집 생활이 극 중에서 오버랩되면서, 아들의 입장과 느낌이 고스란히 내게 전해졌다. 데면데면한 아버지의 모습이나, 엄마와의 특별한 감정을 갖고 있는 여동생의 모습도, 많은 극 중의 디테일이 내 기억에서 현실로 바뀌었고, 정말 머릿 속이 복잡다양한 생각으로 꽉찼다..
1막이 정리되고, 불이 들어왔다. 아내는 옆에서 많이 울었다. 워낙 감수성이 풍부한 사람인지라, 안 울 수가 없었을게다. 자리가 살짝 비어있길래 조금 더 편한 자리로 자리를 옮겼다. 옮긴 좌석에선 얼굴과 음향감독도 볼 수 있었다. 막간을 통해 전화를 하지 않을 수 없었다. 어머니에게.. 안받으신다. 현실에는 늘 그자리에 계신 어머니가 길을 잃으신 건 아닌지. 동생에게 대신 안부전화를 넣고 위로할 수 밖에.
2막은 어머니의 일생으로 초점을 맞췄다. 내 어머니의 일생과 목표, 꿈, 시집살이와 자식과 식구들이 모르는 어머니의 삶이 그려졌다. 지난 해 어머니 자서전을 집에서 본 기억이 났다. 내 어머니도 글쓰기를 좋아하시는 문학 소녀적 감성이 풍부한 분이셨는데.. 정작 당신이 자작 일기를 책으로 편집 하실 때는 내가 너무 무심히 지나갔던 건 아닌지.
뮤지컬이란 장르는 특성 상 음악으로 스토리를 끌고 가게 되는데, 너무 무겁게 진행이 되자 사실 마음이 편하진 않았다. 청중들의 감정선을 계속해서 극단으로 몰아붙이는, 그래서 청중에게도 힘든 극이었다. 연기자들도 그만큼 힘들겠지. 이런 극을 매일 하려면, 아주 강인한 사람이어야 할 것 같다.. 극을 하면서 울 수도, 그렇다고 감정을 걷어내고 연기할 수도 없을테니..
극 후반으로 들어서자 특히 어머니의 걸음걸이나 말투가 연기하시는 김성녀씨에게서 너무 똑같이 나타나고 있었다. 눈치채기 어려운 전라도 사투리와 문어체가 살짝 섞인 말투, 그리고 걷는 모양, 얼굴 분장까지 너무 똑같은 느낌이 들었다. 이제 참기 힘든 지경이다.
극에서 어머니는 돌아오지 못한다. .. 그리고 보니, 제목이 마음에 들지 않는다. 어머니를 부탁해 - 누가.. 누구에게 부탁한 건가. 아버지가 자식들에게 어머니를 부탁한 것 까지는 그렇다 치자. 자식들도 누군가에게 어머니를 부탁하고 있다. 갑자기 여기서부터 화가 났다. 대체 자식들이 부모를 누구에게 부탁한단 말인가. 아내는 그냥 받아들이라고 했지만.. 매우 답답해졌다. 청중에게 부탁했던 것인가.. 왜 작가는 극에서 어머니를 무책임하게 버리는 선택을 했을까. 비극적인 장치라고 하기엔, 너무 내게 현실적으로 다가왔다. 마치 가까이의 누군가가 어머니를 잃어버리고, 이제 난 모르겠으니 누군가에게 부탁한다고 도피한 느낌이다. 아... 내가 화가 난 이유는, 그게 내 모습이 아니길 바라기 때문이다.
간만의 뮤지컬 공연 관람이 끝나고 집에 돌아오면서, 아내와 그런 얘기들로 공연을 되씹었다. 전체적으로 무겁게 진행되는 마음 불편한 극이라는 것이라는 것과 스토리가 무책임한 자식을 조명하며 끝나는 점이 아쉽긴 했지만, 간만에 감성을 충전한 느낌이다. 처제~ 고마워요~. 어머니 사랑해요~.
Thursday, May 19, 2011
Congruence in virtualization
<behavioral congruence within virtualization>
In a virtualization environment, task execution is difficult to be analyzed. Since virtualization layer hides all the physical operations and exposes only a small subset of hardware, the actual physical behavior under the virtualization layer can be largely different from the observed behavior over the virtualization layer. For example, all task execution within a guest OS is based on the virtual time of the guest OS; however, the actual execution with physical time is differently presented, and real-time applications would miss physical deadlines, which makes difficult to incorporate real-time OSs within virtualization.
To present behavioral equivalence within virtualization, event serialization is definitely not enough. Even though events occurs consecutively in the same order, it cannot catch the timeliness of the execution. Timed automata or timed Petri-net tried to address timely execution; however, they also have limitations with respect to the state space. Since they project all the execution behavior to every time instants, the state space increases as much as the execution time. This makes difficult to analyze behavior deterministically since the halting problem is a well-known decidability problem, which is NP-hard. Namely, those timed analysis techniques are too complex, hence they are not directly applicable in scalable virtualization system.
To address timeliness within virtualization, I think, we can use the notion of real-time schedulability. Within a virtualization system, physical execution of a task is determined by the hypervisor instead of a guest OS, so a guest OS cannot impose task execution at a specific physical time instant. Namely, timeliness is difficult to define with a single time instant. Instead, we focus on the execution within a time duration. If a task is executed in a physically timely manner, then it should be executed not too late. Schedulability guarantees that tasks within a system meet deadlines, which means tasks are executed ‘not-too-late’.
In traditional real-time scheduling theory, schedulability tests are defined with a task set and scheduling algorithm. Schedulability tests determine whether all tasks can complete their execution within respective deadlines through the algorithm. For example, if tasks in the set are periodic, and the summation of their utilization is not more than 100%, then all tasks are schedulable with EDF (i.e. EDF schedulable).
In a virtualization system, schedulability of a task is difficult to define since scheduling is performed at two different levels. At first, inter-VM scheduling (or VCPU scheduling) is performed at the virtualization layer (inside a hypervisor). Secondly, intra-VM scheduling (or task scheduling) is separately performed over the virtualization layer (inside the guest OS). Inter-VM scheduling is performed by the hypervisor that doesn’t have any task information inside a guest OS. Instead of scheduling each tasks within guest OSs, the hypervisor simply schedules VCPUs that are given to each virtual machine. To schedule VCPU, each VCPU requires scheduling a parameter that represents all the execution of a guest OS.
Intra-VM schedulability is not easily determined because task execution is determined not only by task set and intra-VM scheduling algorithm, but also by inter-VM scheduling parameter of the guest OS, and inter-VM scheduling algorithm. This
Inter-VM schedulability can be easily determined provided that the scheduling parameters are given.
In a virtualization environment, task execution is difficult to be analyzed. Since virtualization layer hides all the physical operations and exposes only a small subset of hardware, the actual physical behavior under the virtualization layer can be largely different from the observed behavior over the virtualization layer. For example, all task execution within a guest OS is based on the virtual time of the guest OS; however, the actual execution with physical time is differently presented, and real-time applications would miss physical deadlines, which makes difficult to incorporate real-time OSs within virtualization.
To present behavioral equivalence within virtualization, event serialization is definitely not enough. Even though events occurs consecutively in the same order, it cannot catch the timeliness of the execution. Timed automata or timed Petri-net tried to address timely execution; however, they also have limitations with respect to the state space. Since they project all the execution behavior to every time instants, the state space increases as much as the execution time. This makes difficult to analyze behavior deterministically since the halting problem is a well-known decidability problem, which is NP-hard. Namely, those timed analysis techniques are too complex, hence they are not directly applicable in scalable virtualization system.
To address timeliness within virtualization, I think, we can use the notion of real-time schedulability. Within a virtualization system, physical execution of a task is determined by the hypervisor instead of a guest OS, so a guest OS cannot impose task execution at a specific physical time instant. Namely, timeliness is difficult to define with a single time instant. Instead, we focus on the execution within a time duration. If a task is executed in a physically timely manner, then it should be executed not too late. Schedulability guarantees that tasks within a system meet deadlines, which means tasks are executed ‘not-too-late’.
In traditional real-time scheduling theory, schedulability tests are defined with a task set and scheduling algorithm. Schedulability tests determine whether all tasks can complete their execution within respective deadlines through the algorithm. For example, if tasks in the set are periodic, and the summation of their utilization is not more than 100%, then all tasks are schedulable with EDF (i.e. EDF schedulable).
In a virtualization system, schedulability of a task is difficult to define since scheduling is performed at two different levels. At first, inter-VM scheduling (or VCPU scheduling) is performed at the virtualization layer (inside a hypervisor). Secondly, intra-VM scheduling (or task scheduling) is separately performed over the virtualization layer (inside the guest OS). Inter-VM scheduling is performed by the hypervisor that doesn’t have any task information inside a guest OS. Instead of scheduling each tasks within guest OSs, the hypervisor simply schedules VCPUs that are given to each virtual machine. To schedule VCPU, each VCPU requires scheduling a parameter that represents all the execution of a guest OS.
Intra-VM schedulability is not easily determined because task execution is determined not only by task set and intra-VM scheduling algorithm, but also by inter-VM scheduling parameter of the guest OS, and inter-VM scheduling algorithm. This
Inter-VM schedulability can be easily determined provided that the scheduling parameters are given.
Tuesday, May 10, 2011
Does mobile phones give more freedom to people?
Small essay for writing practice
Recently mobile phones are widely used by a lot of people. Although there is a controversy, I think mobile phones have provided more freedom to people. There are two specific reasons why I think mobile phones give more freedom.
First, mobile phones free people’s communication from a fixed physical location. Even though a telephone enables a person to communicate with another at distance, the person has to be at a specific location that the telephone is installed. On the contrary, with mobile phone, one can make or receive phone call while moving places. Thus, people can work more efficiently overcoming the limitation of physical location. For example, important business decision can be made in a car, or urgent meeting can be arranged in an airplane.
Second, using a mobile phone, one can put/get useful information to/from Internet with respect to a location in a timely manner because recent mobile phones provide location-free Internet connection. For example, navigation service in your mobile phone helps you to find the shortest or the least congested path to the destination when you are traveling a new place. Besides, you can post a movie clip during a travel to Internet through a mobile phone. The media is immediately shared among people who are connected to Internet, and it provides more realistic information. So, people don’t need to rely upon the mass media such as newspaper or news broadcast. This implies that mobile phone serves as a new media service platform, and enables people to freely distribute useful information without the help of mass media.
In conclusion, mobile phones have been developed for free communication in terms of location, and helps people to work more efficiently. Furthermore, it frees people from the limitations of current mass media. Personal news or useful local information can be easily shared with the help of recent mobile phones.
Thursday, May 5, 2011
Game-theoretic approach vol. 3
To testify the assumption, we measure fairness and latency satisfaction. With the current credit scheduler, we run two domains: dom1 and dom2. dom1 has both I/O and CPU load, and dom2 has only CPU workload. By changing the CPU workload (0, 20, 40, 60, 80 and 100%), we observe the characteristics of the scheduler. Fairness is measured by the throughput (amount of work done during unit time), and latency is measured by the percentage of missed deadlines.
Sunday, May 1, 2011
Air way plan
Itinerary:
From Incheon to Paris,
From Paris to Wien,
From Wien to Incheon
Vienna
to meet opera or classical music
I had not been to concerts for a long time
This year, anna-sophie has come to Korea, but I couldn’t go
Sorry for my un-attendance
Wish to meet magic flute at vienna
From Incheon to Paris,
From Paris to Wien,
From Wien to Incheon
Vienna
to meet opera or classical music
I had not been to concerts for a long time
This year, anna-sophie has come to Korea, but I couldn’t go
Sorry for my un-attendance
Wish to meet magic flute at vienna
Thursday, April 28, 2011
Game-theoretic approach vol. 2
Cont. from prev. Game-theoretic. article
A real-time virtual machine(VM) requires a strictly time-bounded I/O latency, and a non-real-time VM demands a guarantee for fair utilization for physical resources. I/O latency can be reduced by prioritization and preemption; fair utilization requires accurate accounting and compensation for lost execution time.
We define inter-VM scheduling game to determine how both VMs can be scheduled with satisfied. To define a pay-off function, we measure how much the domain is unsatisfied with scheduling.
To measure the unsatisfaction for the I/O latency, we can use statistical information. An example can be the probability of deadline miss. i.e. A domain is more unsatisfactory if the domain misses the more deadlines. Another example measure is the expectation for the latency over the deadlines. i.e. E[Min{(Latency - deadline),0}] can measure how the real-time domain is unsatisfactory. On the other hand, Jain’s fairness can be used for measuring how the non-real-time is unsatisfactory.
So, now we can provide a parametric unsatisfaction for scheduling with respect to I/O latency and CPU fairness. The key control parameter in the credit scheduler is the BOOST mechanism since it controls the temporal priority of a domain. If a domain is boosted, it can quickly run a task, so that the task meets the deadline. If I/O domains are not boosted, the credit scheduler will achieve fairness by giving the equivalent CPU time for all the domains.
We want to control the scheduler so that it can flexibly adjust latency or fairness levels. To control the CPU fairness or I/O latency level, BOOST can be flexibly controlled. If a domain wants to have a I/O latency with strict time bound, then it has to be boosted always, and it can handle events within a deadline. If a domain demands a strict fairness, (i.e. don’t want to get penalty by another domain) the boost has to be applied only when it doesn’t break the fairness.
We can find an optimal scheduler that boosts a domain with a probability in order to meet the required fairness as well as latency. Boost probability p_i decides how often the domain i is boosted. For current credit scheduler, CPU fairness is preserved, and applies boost for domains that have enough remaining credit. So, a latency sensitive domain have penalty; particularly when it has I/O and CPU mixed workload. Unfortunately, a real-world domain usually has CPU-I/O mixed workload; thus, it takes penalty with regard to latency. If a domain has CPU-intensive task, the domain is not boosted when the CPU-intensive task is running.
A real-time virtual machine(VM) requires a strictly time-bounded I/O latency, and a non-real-time VM demands a guarantee for fair utilization for physical resources. I/O latency can be reduced by prioritization and preemption; fair utilization requires accurate accounting and compensation for lost execution time.
We define inter-VM scheduling game to determine how both VMs can be scheduled with satisfied. To define a pay-off function, we measure how much the domain is unsatisfied with scheduling.
To measure the unsatisfaction for the I/O latency, we can use statistical information. An example can be the probability of deadline miss. i.e. A domain is more unsatisfactory if the domain misses the more deadlines. Another example measure is the expectation for the latency over the deadlines. i.e. E[Min{(Latency - deadline),0}] can measure how the real-time domain is unsatisfactory. On the other hand, Jain’s fairness can be used for measuring how the non-real-time is unsatisfactory.
So, now we can provide a parametric unsatisfaction for scheduling with respect to I/O latency and CPU fairness. The key control parameter in the credit scheduler is the BOOST mechanism since it controls the temporal priority of a domain. If a domain is boosted, it can quickly run a task, so that the task meets the deadline. If I/O domains are not boosted, the credit scheduler will achieve fairness by giving the equivalent CPU time for all the domains.
We want to control the scheduler so that it can flexibly adjust latency or fairness levels. To control the CPU fairness or I/O latency level, BOOST can be flexibly controlled. If a domain wants to have a I/O latency with strict time bound, then it has to be boosted always, and it can handle events within a deadline. If a domain demands a strict fairness, (i.e. don’t want to get penalty by another domain) the boost has to be applied only when it doesn’t break the fairness.
We can find an optimal scheduler that boosts a domain with a probability in order to meet the required fairness as well as latency. Boost probability p_i decides how often the domain i is boosted. For current credit scheduler, CPU fairness is preserved, and applies boost for domains that have enough remaining credit. So, a latency sensitive domain have penalty; particularly when it has I/O and CPU mixed workload. Unfortunately, a real-world domain usually has CPU-I/O mixed workload; thus, it takes penalty with regard to latency. If a domain has CPU-intensive task, the domain is not boosted when the CPU-intensive task is running.
Wednesday, April 27, 2011
Game-theoretic approach on latency-bandwidth trade-off
This is a tech. article, so you can skip this if you are not interested in computer systems or systems virtualization.
Recently, I had an interesting observation on Xen-scheduler. Xen uses the credit scheduler, by default. You can refer the credit scheduler at other papers, articles, etc. (So, I will skip to explain this) Xen’s credit scheduler has been designed to preserve fairness among CPU-bound guest domains. This results in bad latency for time-sensitive applications (or domains). For mobile virtual machines that require real-time facilities, it is a critical problem. To support real-time, I/O latency has to be time-bounded, which is difficult with the current credit scheduler and split driver.
Recently, I had an interesting observation on Xen-scheduler. Xen uses the credit scheduler, by default. You can refer the credit scheduler at other papers, articles, etc. (So, I will skip to explain this) Xen’s credit scheduler has been designed to preserve fairness among CPU-bound guest domains. This results in bad latency for time-sensitive applications (or domains). For mobile virtual machines that require real-time facilities, it is a critical problem. To support real-time, I/O latency has to be time-bounded, which is difficult with the current credit scheduler and split driver.
Keep it simple.
The first article on this blog.
This blog will include personal misc things and tech spots that I am focusing
Making a footprint on this site requires me a lot continuous effort and care
So, I try to focus on a few things enough to keep this work simple
Let us watch this out, the evolution of the site and me
...
This blog will include personal misc things and tech spots that I am focusing
Making a footprint on this site requires me a lot continuous effort and care
So, I try to focus on a few things enough to keep this work simple
Let us watch this out, the evolution of the site and me
...
Subscribe to:
Posts (Atom)