Software blog

과거에는 모니터와 키보드만 보면 두근 거리는 순간이 있었다. 마치 하얀 캔버스를 보며 자신에 의해서 세상에 처음 모습을 나타낼 한폭의 그림을 상상하는 것 처럼 키보드를 보면 흥분되는 그런 순간이 있었다. 시간이라는 것은 참 많은 것을 우리에게서 빼앗아 간다. 상상해보라. 초등학교 시절, 그 단순한 소풍이라는 단어 하나만으로도 우리는 소풍 전날 쉽사리 잠이 들지 못했다.

작년 한해 나는 3개의 해외 논문을 내고, 11개의 기술 컬럼을 작성했으며, GT와 KU를 졸업하기 위해 열심히 프로젝트에 참여하고 GRE와 같은 영어 시험들을 쳤다. 하지만 그 순간에 내가 했던 것들의 결과가 궁금해서 설레였던 적은 SESC를 통한 캐시 프로젝트 단 한번 이었다. 대부분의 시간은 위경련을 일으킬 만큼 힘겨웠으며 프로그램을 만들면서도 내가 만든 모듈의 결과가 예상과 달라 원인을 생각하기 바빴다. 일본에서는 내 목표가 손에서 벗어나버릴까바 고작 하나 먹은 초코바를 처음 보는 거리에 모두 토해냈으며, 책상에는 항상 아스피린 껍질과 활명수, 박카스 병이 굴러 다녔다. 더욱 중요한 것은 랩실을 들어서면서, 그리고 내 작업실 문을 열면서 오늘 새로 만들어질 그림을 기대하며 흥분을 감추지 못한 적은 한번도 없다. 그곳에는 어떠한 설레임도 없었다. 단순한 나에 대한 신념만이 존재 했다. 지금도 누가 강요한 적은 없지만 박사 과정에 들어가기전에 두개의 논문을 더 작성하고 있지만 그 과정이 그렇게 즐겁지 않다.

회상속에서 내가 단 한번도 내가 평생해야 할 일에 대한 흥분을 느끼지 못한 이유를 분석해본다면 첫 번째 이유는 문제를 해결 하기 위한 내 기반 지식의 부족과 능력의 결여에 있을 것이다. 칙센트 미하이의 플로우(Flow, Optimal Exprience)의 진입 조건을 따져 본다면 목적을 달성하기 위한 기술의 부족에 있을 것이다. 두번 째 이유는 작년 한해를 거치고, 올해 여러 어드미션을 받으면서 내 원래의 목적 -- 내가 잘 할 수 있고 좋아할 수 있는 분야의 교수에게로 간다 --를 벗어나 지명도와 수치적 가치를 먼저 보게 되는 소위 속물이 되어가고 있는 것이다. 오늘도 나는 펀딩은 없지만 이후 나의 위치를 어느정도 대변해줄 위스콘신, UCLA, 브라운 중 하나를 선택할 것인가 아니면 원래의 목적과 일치하고 적절한 펀딩을 지원해주는 펜스테이트를 갈것인가를 고민 하고 있다.

삼성 부사장이 자살을 하고 초 전도계의 이성익 교수의 자살 소식을 들으면서 그들의 자살에 원인은 실적도 삶에 대한 고뇌도 아닐 것이라 생각 했다. 좋아하는 것과 잘하는 것의 차이. 잘하는 것을 자신의 인생의 궁극적인 목적으로 생각한다면 삶이라는 긴 여정에서 우리 자신을 잃어버리지 않을 방법이 있는가? 분명 자신보다 잘하는 사람은 그 긴여정속에 반드시 나타나게 되어 있다. 그러면 우리는 그때 새로운 의미를 찾을 수 있을 만큼 젊은가? 정작 키보드를 보면 이제 설레이는 마음보다는 어떻게 문제를 분석할 것인가에만 초점이 맞춰져 있고 학교의 이름을 살펴보고 지명도를 확인하고 순위를 확인 하는 지금의 내가 그들과 다른 결과를 만들 수 있는 일말에 여지가 있는가? 문제를 풀기 위한 기반 지식에 대한 한계를 겪을때 마다 생기는 그 고통을 넘지 못하고 있다면 잘하는 것에 앞서 내가 좋아하는 일은 할 수 있는 것인가? 내가 잘하는 것도 아니고 좋아하는 것도 아니라면 내가 여기서 얻을 수 있는 것은 무엇인가?


늙은 연인을 안고 어색한 탱고를 추고 싶은 마음은 추어도 없다. 고매한 학자인척 하는 연기하는 것은 나로서는 완전이 불가능한 일이다. 결국 만들어내고 생각하는 것을 즐기지 않는다면 작년 올해 내가 한것과 앞으로 할 것들은 내 인생의 중요한 시간을 창문 밖으로 버리고 있는 것과 같은 부질 없는 짓일 것이다. 언제 쯤이면 나에게 있는 깨진 창문들을 모두 고치고, 예전처럼 키보드와 모니터 앞에서 미칠도록 즐거웠던 그 설레임을 다시 가질 것인가?

Efficient Software-Based Fault Isolation

Myoungsoo Jung

Problems, Solutions and Summaries:

The key idea to isolate fault by software is very simple, and allows us to archive the efficient way to make fault isolation cheap enough. Begin with this paper, Robert Wahbe at al. figure out the problem of the traditional fault isolation method. When we use such scheme (i.e., hardware-based fault isolation), high performance cost is necessary because preventing the code in one address space from corrupting the contents of another induces prohibitive context switch overhead and needs some additional operation such as trapping, copying arguments, saving and loading relative register, and flush look-aside buffer. To overcome this challenge, the authors provide a software approach, which implemented within a single address space. It grants a separated fault domain to load code and data for a distrusted module and modify object code to prevent faults from writing and jumping to address outside such fault domain.

To archive mentioned goal of this paper, the authors propose the software encapsulation transforming distrusted module not to escape its fault domain – fault domain consists of two segments, one for distrusted module's code, and another for its static data, heap and stack. The software encapsulation contains of two kinds of key mechanism to pinpoint the actual location of fault within a module and isolate distrust module. One is called, segment matching preventing the use of illegal addresses. In segment matching, insert checking code before every unsafe instruction that jumps to or store to statically unverified address within the correct segment. If the check fails, such code traps to a system error routine outside the distributed modules' fault domain.

Another key mechanism of software encapsulation is address sandboxing. Sanding boxing indicate inserted code that sets the upper bits of the target address to the correct segment identifier before distrusted instructions. As with segment matching, earlier mentioned, unsafe store or jump instruction can be modified to use dedicate register, and it guarantee that distrusted module code cannot produce an illegal address. There are two instruction for providing sandboxing, one to clear segment-id and store the result in a dedicate register, the other to set segment id for the correct value.

Remaining issues for supporting efficient software encapsulation are optimization, how to prevent corrupting process resources and to access among domains when they need data sharing. In the view of optimization, the authors provide the way to reduce overhead, which is induced from computing target address. Basically, instruction of RISC has register address and offset. However, sandboxing mechanism just use only register addresses or numbers and handles offset by creating guard zone, which indicate unmapped area. In process resources problem, the authors require distrusted modules for accessing resource through cross-fault-domain RPC. For instance, if a distrusted module's object code performs a direct system call, the authors transform this call into the appropriate RPC call. In last, I talk about data sharing. Because segment encapsulation doesn't alter load instruction, fault domains can read any memory mapped in the application's address space. However, each domain cannot share data among them. So the authors provide lazy pointer swizzling that alias the shared regions into multiple locations in the virtual address space by modifying the hardware page table.

Critiques:

Although this paper strives for reducing the cost of fault isolation by using not hardware but software, I afraid some kinds of possibility that its mechanism can break pipeline. Traditionally, many scientists who involved in computer architecture realm take effort to reduce the number of broken pipeline because it induces the terrible performance degradation. As software encapsulation, we should insert code for support segment matching and sandboxing, which incur to break pipeline. So the authors should provide clearer evidence that proposed approach cannot hurt breaking pipeline. Secondly, I don't find realistic solution for adding "correct" value which used for implementing segment matching. If the actual location where occupied with loadable distrusted modules is fixed then we can easily find segment-id during a compile time, but if not, segment-id is unable to be recognized when compile time. For this reason, the authors also should refine the correct value and provide the way to find segment-id without any operating system's load modules mechanism during a compile time.

Unmodified Device Driver Reuse and Improved System Dependability via Virtual Machines

Myoungsoo Jung

 

Problems, Solutions and Summaries:

This paper proposes the way to reuse unmodified device driver. At the same time, Joshua Le Vasseur et al. point out how to improve system dependability by using virtual machine. Actually full reuse for a driver base has been considered unachievable. It's because if we want to introduce device driver into new Operating System, then elusive problems occur such as unavailable code, undocumented feature, and extent of programming errors. The authors suggest pragmatic approach for it and strong isolation of legacy device drivers by guaranteeing that semantics a preserved and incompatibilities are limited using virtual machine multiplexing. Also this scheme allows system suffer from minimal resource overhead by collaborating VMs.

Traditionally, for experience driver reuse, the author divides approaches into two parts. First one is a co-hosting method that indicates binary driver reuse. Another one is transplanting driver that enables to enjoy independence. However the previous approach can interfere between VM and driver OS because they run with all privileges. Also, the last method has problem to successfully reuse device driver because they has to use glue code, and it raise conflicts. When system tries to reuse device driver, the authors propose three considerations such as semantic resource conflicts that represent accidental denial of service, sharing conflicts that are induced since fair address space sharing may be unachievable. Finally, in the view of an engineering effort, donor OS knowledge significantly required writing glue and it is even difficult.

In this paper, drivers are closely knit to kernel, applications are not. In addition to that, orthogonal drivers should be based on following principles: 1. Resource delegation by receiving only bulk resources. 2. Separation of name spaces that indicate each driver has its own address space. 3. Separation of privilege by executing driver in unprivileged mode. In last the author claims secure isolation and common API as basic principle to satisfy orthogonal device driver requirements. In architectural view, to reuse and isolate each device driver, system executes it and its native OS within VM called by DD/OS. This approach is same effect that each deriver can be executed in separate VMs and it allows systems exploit simultaneous use of driver from incompatible OS-s. To communicate each deriver located in separated VMs, translation module support abstractions and control them by adding to DD/OS to interface with client.

The authors also claim that low overhead communication by using message notification and request completion. In addition to it, to bolster their reuse approach, they insist low overhead memory sharing registering memory areas of a VM into another VM's physical memory space. Besides those claims, the authors consider virtualization issues such as DMA operation, additional requirements regarding resources, and special timing. In DMA operation case, there are problem that DD/OS can perform DMA to physical memory not allowed by memory protection system. For this reason, it uses DMA to replace hypervisor code and data. I will discuss regarding these considerations in next critique section to argue for details. This research contributes unmodified reuse, a strong isolation, and fault containment to existing device driver.

 

Critiques:

In DMA and trust section of this paper, I wonder if where actual memory locations that cannot be reclaimed are when this approach uses DMA operation. I think that the author have to solve this ambiguity. In addition to it, the author claims that client must not use pinned memory because of DD/OS until faulted it complete rebooting process. However, I am not confident this mechanism is right. For example if DMA completes before the faulted VM restart then system fall down to ambiguous status, and I wonder if VM fail to reboot their system then what can be incur. If systems need a bunch of drivers to provide one functionality like PCI device then I have question to decide whether the proposed approach still use distributed device drivers to deal with one functionality or not. With this reason, to bolster their claims, the author should provide tradeoff between performance and isolation advantage. More crucial problem is resource consumption. The authors solve this problem by using swapping memory method. To evict it, It considers which one is cold page or not. However, most device drivers are managed as block box. So, the author should suggest the way to recognize cold and hot page even if each device driver is encapsulated, and hide their own information.

Scheduling I/O in Virtual Machine Monitors

Myoungsoo Jung

 

Problems, Solutions and Summaries:

Deigo Ongaro et al. evaluate that the impact of VMM scheduler on performance using multiple guest domains concurrently running different types of applications. To concrete it, the authors add numerous schedulers to Xen. Such evaluation reveals the relationship between domain scheduling and I/O performance in a Virtual Machine Monitor(VMM), and provide the major problems in VMM's I/O scheduling. In other words, this study of Deigo Ongaro et al. is contributed by identifying I/O performance degradation, overcoming unfairness in I/O sensitive domains, and removing side effects from scheduler tickling from the Xen scheduler.

The authors figure out that traditional way to fairly scheduling results in poor and unpredictable I/O performance when applications intending to latency and bandwidth sensitive are performed by VMM schedulers. Basically, the Xen exploit default scheduler as the Credit scheduler which uses a credit/debit system to fairly share process' resources. To bolster the facts those I/O degradations, the authors show experimental results that its scheduler achieve mixed performance depending on the particular configurations with bandwidth-intensive and latency sensitive applications. In addition to it, the author also evaluate impact of Simple Earliest Deadline First(SEDF) scheduler. Its scheduler's performance is similar with Credit scheduler even if it can fairly share process' resources when plays with CPU-sensitive applications.

Turn to problems of Xen's scheduling. First of all, latency is induced by scheduling other domains. It's because event is used to communicate virtual interrupt as well as inter-domain. Especially, in the network interface card(NIC) case, there are at least two chances to run other domains to deliver a network packet, and it results in latency. More serious problem is unfairness in I/O performance. In other words, the scheduler is fairly sharing the process resources only by approximations. Modern trend is exploiting completely fair scheduler. For this reason, if low response latency is desired then such scheduler policy may not be effective. Also Credit scheduler doesn't provide fair latency because it doesn't consider when each domain should receive its allocated fraction of processor resources. Finally, the scheduler's problem occurs if it tickles too frequently. It results in preempting domain in execution is too early.

To minimize above problems, this paper provides scheduling optimizations such as boosting idle domains, re-ordering the run queue according to credits, and adjusting to tickle the scheduler by understanding I/O domain requirements. Such requirements largely divide into three parts. First one is low latency, and lasts are high bandwidth and independent of other domains' workloads respectively. By introducing boosts I/O domain into VM scheduling, latency sensitive applications have chance to try to perform their I/O more. In other view, reordering the run-queue by reinserting I/O domains into near the heard of run-queue can resolve unfairness when Xen has the heavy workload scenario. In addition to that, the authors try to minimize preemption. Actual meaning of it is that tickling is disabled altogether for avoiding to preempt the driver domain, In last, fixing event channel notifications by exploiting 2-level hierarchy of bit vectors can guarantees that no port will be processed a second time before all other pending ports have been processed once.

Critiques:

As all known, Xen has suffered from low I/O performance. I believe that these approaches are very helpful to have different views when designers of the Xen's architecture see the scheduling. However, I think it is better that the authors should provide more classifications to exploiting boost status. Since the boost method also has possible that effective is negated when they have many I/O domains. What we can we expect from when run-queue same number of UNDER domain with number of boost domain. Moreover, I believe that it is insufficient for I/O domain under heavy loads. In reordering the run-queue case, how can we compensate the low utilization of CPU when exploiting combinations of boost with ordered run-queue? If the author provide these considerations, then optimization approach regarding scheduler is more useful to enhance I/O performance of the Xen.

NT Virtual Memory Manger 섹션의 두번째 컬럼인 NT의 가상 주소 변환 (Virtual Address Translation with considering MMU and TLB)의 초안을 제출 하였습니다. 본 칼럼은 아래와 같은 내용을 다루고 있습니다.


컬럼을 읽으시기전에 가상 메모리에 대한 컨셉을 잘 모르시는 분은 아래 자료들을 이해 하시는 것을 권장해 드립니다.

2008/11/16 - [Fundamental Notes/Operating Systems] - Virtual Memory#1, Introduce Memory Managements
2008/11/16 - [Fundamental Notes/Operating Systems] - Virtual Memory #2, Paging
2008/11/16 - [Fundamental Notes/Operating Systems] - Virtual Memory #3, Demand Paging and Page Tables
2008/11/16 - [Fundamental Notes/Operating Systems] - Virtual Memory #4, Cache Replacement Polcies
2008/11/16 - [Fundamental Notes/Operating Systems] - Virtual Memory #5, Working Set Model

L4가 나오기 까지 IPC 오버헤드와 working set size가 문제를 해결 하고자 여러가지 이슈들이 적용 되었다는 것이 재미있다. 어셈블러고 전부 짜 내려갔다는 것은 학술적으로 별로 의미가 있지 않을 것 같고, working set size를 개선하기 위해서 L4 패밀리들이 어떤 것 들을 했는 지 알면 많은 도움이 될텐데..

최근에 느끼는 것이지만, 정말 문제는 아는 것 까지만 보인다. 문제가 아는 것 까지만 보이니, 개선 사항도 딱 아는 것 까지만 보이는 것 같고, 학술적으로 Contribution 할 수 있는 것도 딱 아는 것 까지만 할 수 있는 것 같아서, 입맛에 맞는 것들에만 집중력을 보이는 내 단점을 내년에는 크게 개선 해야 할 것 같다.