VMware를 이용한 Ubuntu 초기화 과정

1. vim 설치 (apt-get 이용)

2. auto-login with root account (아래 글 참조)

3. VM tool 설치

4. 공유 디렉터리 설정하기

5. samba 이용한 공유 디렉터리 생성

6. 우분투 언어 설정

7. 소스코드 분석 환경    

ctags / cscope

"코드로 알아보는 ARM 리눅스 커널" 책 환경 구축

8. Classic Gnome으로 변경 (10버전대 스타일)

9. VMware Unity Mode 활성화 방법

10. ssh 리스트 설정 방법

- vi ~/.ssh./config

Host XX

HostName [IP]

User [account]

PubkeyAuthentication no

11. hardware  정보 얻기

- hardinfo 설치

Building Environment for Android 2.3 on 64-bit Ubuntu

                          2011-10-17  FUNFUN.YOO (funfun.yoo@gmail.com)

 1. Install VMware / VirtualBox

 2. Install Ubuntu 64-bit version (last version : 11.10)

 3. Setting......

 :: root & auto-login ::

 # sudo passwd root

 # vi /etc/lightdm/lightdm.conf 

-----------------------------------------

autologin-user=root

auto login deafult 변경 방법

아래 코드를 추가함. 단 GUI에 따라서 다르다.

user-session=gnome-fallback

 # apt-get install vim

 # apt-get install minicom

 :: Samba ::

 # apt-get install samba smbfs

 # vi /etc/samba/smb.conf

 # smbpasswd -a root

 # service smbd restart

deprecated 되었으므로,

cifs-utils를 사용해야 한다.

https://wiki.ubuntu.com/MountWindowsSharesPermanently

 :: Android Build Configuration ::

 # apt-get install git-core gnupg flex bison gperf build-essential zip curl zlib1g-dev gcc-multilib g++-multilib libc6-dev-i386 lib32ncurses5-dev ia32-libs x11proto-core-dev libx11-dev 

  ※ Ubuntu 11.10 : lib32z-dev => lib32z1-dev

                  lib32readline5-dev => lib32readline-gplv2-dev

 # apt-get install lib32z1-dev lib32readline-gplv2-dev

 # apt-get install flex bison gperf libsdl-dev libesd0-dev libwxgtk2.6-dev zlib1g-dev

 # apt-get install valgrind

 :: JDK 1.6 :: 

 # add-apt-repository "deb http://archive.canonical.com/ lucid partner"

      ---------------------------------------------------------------------------------------------------

  => add-apt-repository "deb-src http://archive.canonical.com/ubuntu lucid partner"  명령어는 자동적으로 실행되므로 할 필요가 없음.

 # apt-get update

 # apt-get install sun-java6-jdk

 :: 32-bit Compatibility ::

 # apt-get install ia32-libs

 :: Swap Configuration ::

 # dd if=/dev/zero of=swapfile bs=1024 count=1655360

 # mkswap swapfile

 # swapon swapfile

 # vi /etc/fstab

      ---------------------

   /root/swapfile swap swap defaults 0 0

 # swapon -s

 # free 명령어로 확인!

 :: arm-2009q3 ::

 # ./arm-2009q3-67-arm-none-linux-gnueabi.bin

 # dpkg-reconfigure -plow dash

   -> "NO"

 # ./arm-2009q3-67-arm-none-linux-gnueabi.bin

   -> "/opt/arm-2009q3"

 # vi ~/.profile

   -> export PATH=$PATH:/opt/arm-2009q3/bin

 # source .profile

 :: Boot-Loader Build ::

 # vi Makefile

   -> "CROSS_COMPILE=...." 수정

 # make clobber

 # make mvtv210_config ARCH=arm CROSS_COMPILE=arm-none-linux-gnueabi-

 # make ARCH=arm CROSS_COMPILE=arm-none-linux-gnueabi-

 # vi ~/.profile

   -> "mkimage"

   -> export PATH=$PATH:.....:/root/V210/u-boot_1.3.4-debug-0419/tools

 :: Kernel Build ::

 # cp mvtv210-20110509.config .config

 # make clean

 # make oldconfig ARCH=arm CROSS_COMPILE=arm-none-linux-gnueabi-

 # make ARCH=arm CROSS_COMPILE=arm-none-linux-gnueabi-

 :: Android File System Build ::

 # apt-get install bison

 -> bison : a general-purpose parser generator

 # make clean

 -> 반드시 실행시킬 것!!!!!!!!!!

 # . ./build/envsetup.sh

 # lunch

   -> V210 관련 "5" 선택

 # vi build_android.sh

 -> "KERNEL_DIR=/root/V210/android-samsung-dev-sdmmc/android-kernel-samsung-dev"

 # ./build_android.sh

Git 간편 사용법: Click

Naver Blog: Click

맨 처음 시작

# set up git on your machine if you have not already.
$ mkdir /path/to/your/project
$ cd /path/to/your/project
$ git init
$ git remote add origin https://leejaymin@bitbucket.org/leejaymin/power-aware-notification-project.git

# Create your first file, commit, and push
$ echo "jemin lee" >> contributors.txt
$ git add contributors.txt
$ git commit -m 'Initial commit with contributors'
$ git push -u origin master

기존 프로젝트가 존재하는 경우

만약 기존에 있던 원격 저장소를 복제한 것이 아니라면, 원격 서버의 주소를 git에게 알려줘야 한다.

로컬의 변경 내용은 현재 HEAD에만 있다. 이것을 원격 서버에 반영 시킨다. 

Note: 특정 branch로 반영을 원할 경우, master 대신에 해당 이름(ex: GUI)를 써야한다.

모든것을 반영하는 방법

git push -u origin --all # pushes up the repo add its refs for the first time

git push -u origin --tags # pushes up any tags

그런데, not fast forwarding 오류가 나면,

원격 저장소 내용을 로컬 저장소에 반영할 때 씀.

강제로 push 하는 방법: Click

Branch

Staging (Index)에 추가된것 초기화 하기: Site

ADB_Over_network을 reboot시 초기화 하지 않는 방법

전체적인 System Properties와 preference와의 일관성 유지 및 사용자와의 상호작용 그리고 초기화 매커니즘은 아래의 그림과 같다.

Android Preference 구조 그림.pptx

□ setprop persist.adb.tcp.port 5555

• 위 명령을 adb를 이용해서 치면, 재부팅 시에도 port가 5555로 설정 되어 짐.
• 플랫폼을 수정할 필요 없는 가장 간단한 방법
• adbd 자체에서, 이 기능을 지원함.
• 원상태 복구를 위해서는, setprop을 다시 직접 쳐야한다는 단점, 발생 왜냐하면, Adb deamon은 persist option에는 반응하지 않음.

□ adbd을 수정

□ Settings App과 System Server 수정

Settings App: 사용자와의 상호작용을 담당. 설정값에 대한 입력 과 출력

System Server: System Properties로부터 값을 읽어와서 System Preference값을 그에 맞추어 변경함. 즉, 서로다른 두 레벨간의 일관성을 유지시켜 줌.

추가로, ContentObserver를 등록 시켜서, System Preference가 변경되어 지면, 그것을 System Properties에 적용 시킴.

System property를 Setting 하는 방법은 3가지가 있습니다.

import android.util.Log 

String TAG = "tag id"

Log.e(TAG,"message");

Criterion C는 coverage domain으로 부터 유도 되어 진다.

이때, 테스팅 기법에 따라서 집중하는 Domain이 달라 지게 된다.

White-box testing의 경우는 Coverage domain을 code로 부터 추출 한다.

Black-box testing의 경우는 Coverage domain을 requirements로 부터 추출 한다.

하지만, 결국 Coverage domain은 P와 R 모두로부터 추출 해야 정확하게 된다.

핵심은, White와 Black은 기법의 이름이지 이것으로부터 Tests를 뽑아 내는것은 아니다.

Tests는 무조건 상세하게 뽑아내는것이 중요하고, 이때는 반드시 requirements를 반영해야한다.

Verification & Validation을 만족하기 위해서, 프로그램 측면과, 요구사항 측면을 모두 반영 해야 한다.

Statement Coverage는 쉬워 보이지만,

if ( x = malloc(10) {

..

}

else {

..

}

와 같은 코드들의 만족시키기란 쉽지 않다.

White-Box testing의 경우, V model 측면에서

Unit test level 수준에서 적용 할 수 있다.

Black-box testing의 경우, V model 측면에서,

System level test 수준에서 적용 할수 있다.

Coverage 공부를 위해 보면 좋은 블로그: http://froginpot.tistory.com/4 

문제점.

wxPython에서 'Start'버튼을 눌렀 때, 정말 긴 작업을 발생 시킬 때가 존재한다.

당연히, 이때 GUI는 락킹 되어진다. 

이때, Thread를 사용하지 않고 이 GUI 락킹 문제를 해결 할 수 있을까?

해결방법.

3가지 방법: Threading, wxYield, Chunking up your processing in a wxEVT_IDLE handler.

1) Threading을 이용하는 방법

Thread와 별 차이가 없으며, 가장 쉽고, 일반적인 방법이다.

import time
from threading import *
import wx

# Button definitions
ID_START = wx.NewId()
ID_STOP = wx.NewId()

# Define notification event for thread completion
EVT_RESULT_ID = wx.NewId()

def EVT_RESULT(win, func):
    """Define Result Event."""
    win.Connect(-1, -1, EVT_RESULT_ID, func)

class ResultEvent(wx.PyEvent):
    """Simple event to carry arbitrary result data."""
    def __init__(self, data):
        """Init Result Event."""
        wx.PyEvent.__init__(self)
        self.SetEventType(EVT_RESULT_ID)
        self.data = data

# Thread class that executes processing
class WorkerThread(Thread):
    """Worker Thread Class."""
    def __init__(self, notify_window):
        """Init Worker Thread Class."""
        Thread.__init__(self)
        self._notify_window = notify_window
        self._want_abort = 0
        # This starts the thread running on creation, but you could
        # also make the GUI thread responsible for calling this
        self.start()

    def run(self):
        """Run Worker Thread."""
        # This is the code executing in the new thread. Simulation of
        # a long process (well, 10s here) as a simple loop - you will
        # need to structure your processing so that you periodically
        # peek at the abort variable
        for i in range(10):
            time.sleep(1)
            if self._want_abort:
                # Use a result of None to acknowledge the abort (of
                # course you can use whatever you'd like or even
                # a separate event type)
                wx.PostEvent(self._notify_window, ResultEvent(None))
                return
        # Here's where the result would be returned (this is an
        # example fixed result of the number 10, but it could be
        # any Python object)
        wx.PostEvent(self._notify_window, ResultEvent(10))

    def abort(self):
        """abort worker thread."""
        # Method for use by main thread to signal an abort
        self._want_abort = 1

# GUI Frame class that spins off the worker thread
class MainFrame(wx.Frame):
    """Class MainFrame."""
    def __init__(self, parent, id):
        """Create the MainFrame."""
        wx.Frame.__init__(self, parent, id, 'Thread Test')

        # Dumb sample frame with two buttons
        wx.Button(self, ID_START, 'Start', pos=(0,0))
        wx.Button(self, ID_STOP, 'Stop', pos=(0,50))
        self.status = wx.StaticText(self, -1, '', pos=(0,100))

        self.Bind(wx.EVT_BUTTON, self.OnStart, id=ID_START)
        self.Bind(wx.EVT_BUTTON, self.OnStop, id=ID_STOP)

        # Set up event handler for any worker thread results
        EVT_RESULT(self,self.OnResult)

        # And indicate we don't have a worker thread yet
        self.worker = None

    def OnStart(self, event):
        """Start Computation."""
        # Trigger the worker thread unless it's already busy
        if not self.worker:
            self.status.SetLabel('Starting computation')
            self.worker = WorkerThread(self)

    def OnStop(self, event):
        """Stop Computation."""
        # Flag the worker thread to stop if running
        if self.worker:
            self.status.SetLabel('Trying to abort computation')
            self.worker.abort()

    def OnResult(self, event):
        """Show Result status."""
        if event.data is None:
            # Thread aborted (using our convention of None return)
            self.status.SetLabel('Computation aborted')
        else:
            # Process results here
            self.status.SetLabel('Computation Result: %s' % event.data)
        # In either event, the worker is done
        self.worker = None

class MainApp(wx.App):
    """Class Main App."""
    def OnInit(self):
        """Init Main App."""
        self.frame = MainFrame(None, -1)
        self.frame.Show(True)
        self.SetTopWindow(self.frame)
        return True

if __name__ == '__main__':
    app = MainApp(0)
    app.MainLoop()

여기서 문제는, 어떤 이유에서 Thread가 종료 되어 지지 않는다면, 그냥 "self.setDaemon(1)"을 에 추가하면 된다. 그러면, Python은 그것의 terminate을 기다리지 않게 된다.

문제점

Thread는 미세한 종료문제를 발생 시킴

Signal 처리와 같은 Process 레벨의 작업

2) wxYield를 이용하는 방법

computation code가 있는 위치에대가 wxYield()의 호출을 추가해 준다.

wxYield 가 호출 되어질 때, 어떤 pending window event들은 dispatched 되어 지게 된다. 즉, window는 refresh되고, 버튼이 눌러지게 되는 등의 작업을 할 수 있다.

그다음, 위에서 Thread로 처리 했을 때와 같게, wxYield 가 리턴된 뒤의 위치의 작업 코드들을 제어하기 위해서 flag들을 설정 해야 한다. 즉, wxYield로 인해서 pending 되어진 'STOP'에 관한 이벤트가 들어 왔다면, 작업은 종료가 되어 져야한다. 따라서 그 후의 처리를 위해서는  flag를 통해서 제어를 해줘야 한다.

Threading의 경우와 마찬가지로, 모든 이벤트들은 wxYield 가 호출되어지는 동안, 처리되어 지므로, 반드시 같은 오퍼레이션이 두번 실행되어지는것에 대해서 보호되어 져야된다.

보여지는 코드는, 위의 Threading 코드와 똑같은 기능을 하지만, Computation Code들이 main window class안으로 들어 갔다. 핵심은, Threading 코드와 다르게 응답성은 절대적으로 wxYield의 호출 빈도에 의존한다는 것이다.

import time
import wx

# Button definitions
ID_START = wx.NewId()
ID_STOP = wx.NewId()

# GUI Frame class that spins off the worker thread
class MainFrame(wx.Frame):
    """Class MainFrame."""
    def __init__(self, parent, id):
        """Create the MainFrame."""
        wx.Frame.__init__(self, parent, id, 'wxYield Test')

        # Dumb sample frame with two buttons
        wx.Button(self, ID_START, 'Start', pos=(0,0))
        wx.Button(self, ID_STOP, 'Stop', pos=(0,50))
        self.status = wx.StaticText(self, -1, '', pos=(0,100))

        self.Bind (wx.EVT_BUTTON, self.OnStart, id=ID_START)
        self.Bind (wx.EVT_BUTTON, self.OnStop, id=ID_STOP)

        # Indicate we aren't working on it yet
        self.working = 0

    def OnStart(self, event):
        """Start Computation."""
        # Start the processing - this simulates a loop - you need to call
        # wx.Yield at some periodic interval.
        if not self.working:
            self.status.SetLabel('Starting Computation')
            self.working = 1
            self.need_abort = 0

            for i in range(10):
                time.sleep(1)
                wx.Yield()
                if self.need_abort:
                    self.status.SetLabel('Computation aborted')
                    break
            else:
                # Here's where you would process the result
                # Note you should only do this if not aborted.
                self.status.SetLabel('Computation Completed')

            # In either event, we aren't running any more
            self.working = 0

    def OnStop(self, event):
        """Stop Computation."""
        if self.working:
            self.status.SetLabel('Trying to abort computation')
            self.need_abort = 1

class MainApp(wx.App):
    """Class Main App."""
    def OnInit(self):
        """Init Main App."""
        self.frame = MainFrame(None,-1)
        self.frame.Show(True)
        self.SetTopWindow(self.frame)
        return True

if __name__ == '__main__':
    app = MainApp(0)
    app.MainLoop()

3) Chunking up your processing in a wxEVT_IDLE handler

마지막으로, 작업을 idle handler에서 처리 할 수 있다. 이것을 사용할 때에는, wxPython이 IDLE event를 언제든지 발생 시킬 수 있도록 허용 해야 한다. 즉, 일반적인 유저 이벤트들의 처리가 완료 되어졌을 때, IDLE 핸들러가 실행 되도록 해야 한다. 단순히 그냥 Flag로 조작 된다.

구현된 알고리즘에 따라서 약간은 어려운 부분이 존재 한다. 이러한 알고리즘들은, 별게의 조각들로 나누어서 실행 할 수 있어야 한다.

IDLE handler안에서, 만약, 작업이 완료 되지 않았다면, 다시 이 핸들러가 호출 되어 질 수 있도록 해야 한다.

결국, IDLE Hander에서 얼마나 자주 return 되는지가 응답성을 보장 하게 된다. 매우 제약적인 방법이며, 복잡하기만 하다. 쓸때없음.

import time
import wx

# Button definitions
ID_START = wx.NewId()
ID_STOP = wx.NewId()

# GUI Frame class that spins off the worker thread
class MainFrame(wx.Frame):
    """Class MainFrame."""
    def __init__(self, parent, id):
        """Create the MainFrame."""
        wx.Frame.__init__(self, parent, id, 'Idle Test')

        # Dumb sample frame with two buttons
        wx.Button(self, ID_START, 'Start',p os=(0,0))
        wx.Button(self, ID_STOP, 'Stop', pos=(0,50))
        self.status = wx.StaticText(self, -1, '', pos=(0,100))

        self.Bind (wx.EVT_BUTTON, self.OnStart, id=ID_START)
        self.Bind (wx.EVT_BUTTON, self.OnStop, id=ID_STOP)
        self.Bind (wx.EVT_IDLE, self.OnIdle)

        # Indicate we aren't working on it yet
        self.working = 0

    def OnStart(self, event):
        """Start Computation."""
        # Set up for processing and trigger idle event
        if not self.working:
            self.status.SetLabel('Starting Computation')
            self.count = 0
            self.working = 1
            self.need_abort = 0

    def OnIdle(self, event):
        """Idle Handler."""
        if self.working:
            # This is where the processing takes place, one bit at a time
            if self.need_abort:
                self.status.SetLabel('Computation aborted')
            else:
                self.count = self.count + 1
                time.sleep(1)
                if self.count < 10:
                    # Still more work to do so request another event
                    event.RequestMore()
                    return
                else:
                    self.status.SetLabel('Computation completed')

            # Reaching here is an abort or completion - end in either case
            self.working = 0

    def OnStop(self, event):
        """Stop Computation."""
        if self.working:
            self.status.SetLabel('Trying to abort computation')
            self.need_abort = 1

class MainApp(wx.App):
    """Class Main App."""
    def OnInit(self):
        """Init Main App."""
        self.frame = MainFrame(None, -1)
        self.frame.Show(True)
        self.SetTopWindow(self.frame)
        return True

if __name__ == '__main__':
    app = MainApp(0)
    app.MainLoop()

Image.open() 이 정상적으로 작동하다가 갑자기 작동 하지 않으면서, no Attribute라는 error 메시지를 나타낼 경우 그것은, namespace 충돌 때문일 것이다.

그 경우 모듈로 다시 masking을 해주면 문제를 해결 할 수도 있다.

PIL.Image

이렇게 하는 경우 어떤 class 이름이 Image일경우 namespace 문제가 발생 하는 것을 맊을 수 있다.

from PIL import Image

위의 것 대신에,

Import PIL.Image 를 사용 한다.

When working with a lot of imports, beware of namespace confilict.

I'm generally very wary of from some_module import * statements.

WordPress에 대한 code-coverage 측정 방법 연구

Commit Hash Code:

Bug list (직접 발견)

Monkey coverage를 측정.

1) Test Project 생성: Eclipse 이용

2) WordPress Project 변환 및 설치: Ant 이용

3) coverage.em 파일 생성 (원본 파일이다.)

4) Test Project 변환 및 설치: Ant 이용

주의: 반드시, ant로 project를 변환하며, 설치 해야함

4) to run testing: adb shell am instrument -e coverage true -w org.wordpress.android.test/android.test.InstrumentationTestRunner

단, ant emma debug install test는 coverage가 0%로 나오니 쓰지 않음.

5) coverage.ec 추출

6) HTML로 변환: 

java -cp ~/Android_Application_tools/android-sdk-linux/tools/lib/emma.jar emma report -r html -in coverage.em,coverage.ec

주의: coverage.em,coverage.ec 사이에 space를 주지 않는다.

Ant builds support a property named adb.device.arg, 를 이용 한다.

For example:

AndroidMonkey is an Android Library. It is, in fact, a copy of the original Android Monkey Toolhttp://developer.android.com/guide/developing/tools/monkey.html and made as a library for testing and analysis (e.g. code coverage) purposes.

Tester/User can easily use the library to create random test cases to test android apps with GUI.

Why this library:

You can use this library to create random test cases for your application, with just few lines of code

You can add your assertions to access the state of the SUT (you can hardly do this with the Android Monkey Tool)

You can do Coverage analysis of random testing on Android Application, this is useful for Research Purpose (like what I'm doing)

실행방법

우선, 위 open project에서 다운받은 example code를 ant로 빌드환경에 맞게 update를 해야한다.

이러한 작업을 완료한 3개의 파일을 본 블로그에 첨부한다.

1) monkey testing할 project를 target smartphone에 설치 한다.

명령어: ant emma debug install 

2) app test project를 설치한다.

해당 project는 AndroidMonkey project와 종속성이 있다. 왜냐하면, 테스팅 수행 과정에서 random event를 생성해서 testing을 수행하기 때문이다.

3) 테스팅을 실행한다.

환경은 notepad 어플리케이션에 2개의 post를 등록한 상태에서 실행을 한다.

명령어: adb shell am instrument -e coverage true -w com.example.android.notepad.test/android.test.InstrumentationTestRunner

특이사항: 위 명령어를 실행하면 app project의 bin 디렉터리에 coverage.em 파일이 생성 되어 진다.

3) report 생성.

주의: coverage.em이 없을 경우, app project 디렉터리에서 ant instrument 명령어를 실행해서 

EMMA for running android application.

▣ 사전지식

본 예제는, test project가 아닌, running application 스스로 EMMA로 instrument해서 coverage를 측정하게 된다.

coverage.em: 이것은 class file들에 대한 meta 정보를 담고 있다.

coverage.em file은 "ant instrument" command를 입력하면, code를 build하며 coverage.em 파일을 생성 하게 된다.

Step 0

GitHub에 있는 Diego의 project를 다운 받는다.

편의를 위해서 본 블로그에 파일을 첨부해 놓았다.

File 1: external library project

ViewServer-master.tar.gz

File 2: Testing App for getting Code Coverage running application with EMMA

TemperatureConverter-master.tar.gz

▣ 기본적으로 Diego의 Project에는 오류가 몇가지 있다.

1) "LocalViewServer" project에 대한 의존성이 있다.

해결 방법: 

GitHub: https://github.com/dtmilano/ViewServer 에서  ViewServer-master를 다운 받는다.

TemperatureConverter-master project의 project.properties를 아래와 같이 수정한다.

2) ViewServer-master에 SDK version이 빠져 있으므로 eclipse에서 추가 해준다.

3) ViewServer-master에 build.xml이 없어서 ant command를 수행 할 수 없다.

해결방법: # android update project -p .

▣ Step 1

root@ubuntu:~/Android_Application_source/TemperatureConverter-master# ant clean

-- clean all class files

▣ Step 2

root@ubuntu:~/Android_Application_source/TemperatureConverter-master# ant instrument install

-- coverage.em 파일이 생성 되어야 한다.

▣ Step 3

This command will start the android application on the device and create coverage.ec file for us

Step 4

/sdcard/coverage.ec 에 위치한것을 꺼내온다.

Step 5

▣ 소스코드를 참고하지 않는 경우. // 소스코드를 보지 못함

root@ubuntu:~/Android_Application_source/TemperatureConverter-master/bin# java -cp ~/Android_Application_tools/android-sdk-linux/tools/lib/emma.jar emma report -r html -in coverage.em,coverage.ec

EMMA: processing input files ...
EMMA: 2 file(s) read and merged in 9 ms
EMMA: writing [html] report to [/root/Android_Application_source/TemperatureConverter-master/bin/coverage/index.html] ...

▣ 소스코드를 참고하는 경우. // 소스코드를 볼 수 있음 (방법 아직 모름, ant emma debug install test시 정상적으로 잘 보임)

this command will give html coverage reports, and we can also see the src code also in the html reports.
the -sp option is given for that reason only.
java -cp emma.jar emma report -r html -in coverage.ec -sp D:\xxxxxx\EMMA_Coverage\TemperatureConverter-master\src -in D:\xxxxxx\EMMA_Coverage\TemperatureConverter-master\bin\coverage.em

// 내용 확인

root@ubuntu:~/Android_Application_source/TemperatureConverter-master/bin/coverage# firefox index.html
failed to create drawable

Step 6

결과를 아래와 같이 볼 수 있다. 단, 아직 소스코드 보는 법은 잘 모르겠음.

reference links for both:
-------------------------

key link: http://dtmilano.blogspot.in/2011/11/obtaining-code-coverage-of-running.html

https://developers.google.com/web-toolkit/doc/latest/DevGuideTestingCoverage#command-line

http://primates.ximian.com/~flucifredi/emma-HOWTO.html

http://stackoverflow.com/questions/2762665/how-to-use-emma-code-coverage-in-android

https://groups.google.com/forum/#!topic/android-developers/Q8-KjKVmL4U

http://mebeingneo.wordpress.com/2011/05/19/emma-code-coverage-of-android-2/

※ 상기 사항

1) ADT 20r 버전 이상을 사용

2) Android Application Testing Guide에 나온 방법 처럼 AOSP로 할 경우 잘 안됨.

3) tools/ant/build.xml을 변경하는 것은 비 추천.

1. android tool을 이용해서 project 생성 및 update

▣ 생성: application과 test 각각 1개씩 project를 생성

▣ 갱신: eclipse로 기존에 작성된 app과 test project가 있을 경우

2. ant와 emma를 이용해서 실행

3. 실행 결과 및 자료.

▣ $ ant emma debug install

 ▣ $ ant emma debug install test

▣ HelloWordTest Coverage Result

▣ TemperatrueConverterTest Coverage Result

관련 파일

HelloWord.zip

HelloWordTest.zip

TemperatureConverter.zip

TemperatureConverterTest.zip

▣ reference site list 

1) ant command[stackoverflow]: http://stackoverflow.com/questions/2762665/how-to-use-emma-code-coverage-in-android 

2) build.xml 수정 한글 블로그: http://codemuri.tistory.com/826 

3) GeekTaco [완벽한 외국 블로그]: http://geektaco.blogspot.kr/2012/07/code-coverage-with-android-and-emma.html

4) google site [android tool 관련]: http://developer.android.com/tools/projects/projects-cmdline.html

5) google site [ am instrumentation과 android test-project 생성 관련]: http://developer.android.com/tools/testing/testing_otheride.html

6) google site [ command line으로 빌드하는 방법]: http://developer.android.com/tools/building/building-cmdline.html

7) unrooted device에 대한 정보: http://stackoverflow.com/questions/8599097/emma-does-not-generate-coverage-ec

3. adb shell am instrument를 이용해서 emma 실행

2) app project에서 ant emma debug install 명령어를 실행해서 emma를 포함해서 디버그 모드로 해당 프로젝트를 Target smartphone에 설치를 한다.

위 작업을, app test project에 대해서도 동일하게 해준다. test 프로젝트도 target 스마트폰에 설치를 한다.

3) 아래의 명령어를 실행 해준다.

adb shell am instrument -e coverage true -w com.eslab.test.test/android.test.InstrumentationTestRunner

여기서 com.eslab.test.test 는 테스팅 코드가 instrumentation 되어있는 테스트 프로제긑의 package 이름이다. 뒤의 android.test.InstrumentationTestRunner는 변경하지 말고 다른 test project를 사용할 때에도 그대로 사용해 준다.

4) html 파일로 coverage 보고서를 생성해 준다. 이때 app project 위치에서 해야한다.

당연히, coverage.em 파일은 app project에 있는 것을 사용 해야한다. app test project가 아니라.

소스 코드를 참조해서 보고서를 생성하는 명령어: java -cp ~/Android_Application_tools/android-sdk-linux/tools/lib/emma.jar emma emma report -r html -in coverage.ec -sp ~/Android_Application_source/HelloWord/src/ -in coverage.em

소스코드를 참조하지 않고 보고서를 생성하는 명령어: java -cp ~/Android_Application_tools/android-sdk-linux/tools/lib/emma.jar emma report -r html -in coverage.em,coverage.ec

결과: ant emma debug install test 보다 좀 더 많은 testing 요소들을 검사한다.

EMMA

1) ant 환경만 지원, build.xml 이 필요.

2) am instrument의 option으로 EMMA를 실행 가능.

3) running android application의 code coverage를 얻기 위해서는 android instrumentation framework를 반드시 이용 해야한다. 얻고자 하는 기등을 안에다가 넣던가, 아니면 code coverage를 수집하는 코드를 저 안에다가 구현 해야 한다.

java -cp ~/Android_Platform/aosp-2.3.3_nexus_one/external/emma/lib/emma.jar emma report -r html -in coverage.ec -sp ~/Android_Application_source/HelloWord/src/ -in coverage.em

Command line으로 Project를 생성 하는 방법.

1) Creating an Android Project

android project를 생성 하기위해서 android tool을 사용하게 된다. 

이것을 사용하면 project directory를 생성하며 몇몇 default application file들과 stub, configuration file, build file을 생성 하게 된다.

1. Android Application Testing Guide 방법

우선 테스트 대상이 되는 프로그램인 2가지를 구성한다.

TemperatureConverter

TemperatureConverterTest

1) AOSP 컴파일

AOSP를 준비해야한다.

명렁어순서

2) AOSP에 Built-In App으로 우리의 테스팅 App을집어 넣는다.

테스팅 App의 심볼릭 링크로 만들어서 Android 아래의 디렉터리에 프로젝트 2개를 추가한다.

각 프로젝트 디렉터리에 Android Build System에 들어가 지도록 Android.mk 파일을 추가한다.

일단 samples에존재하는 아무 App이다. 꺼내온 다음. 

로 변경 한다.

컴파일

development/samples/TemperatureConverter $ EMMA_INSTRUMENT=true mm

TemperatureConverterTest의 프로젝트도 동일한 작업 수행.

심볼릭 링크 or File copy

Android.mk 생성

컴파일

3) 코드 커버리지 분석 보고서 생성

컴파일의 결과가는, out/target/common/obj/APPS 디렉터리에 나와있다.

Coverage 측정을 위한 Emulator는 out/host/linux-86/bin/emulator 

Emulator 실행 명령어

저장을 위해서 mksdcard 명령어를 이용해서 sdcard.img를 생성해 준다.

에뮬레이터 실행에서 막힘 중단. 

-----------------------------

우선 Ant를 설치한다. 아래의 Web 주소를 참고 한다.

Apache Ant home page: http://ant.apache.org/

▣ Ant Command Reference

▣ am instrument option reference

am instrument의 일반적인 사용법

am instrument [flags] <COMPONENT>

-r: 결과를 모두 출력한다. 선능 측정을 위한 자료 수집에 유용하다.

-e <NAME> <VALUE>: Name을 Value로 설정 한다. 일반적으로 인자 <name,value> 쌍이다.

-p <FILE> 측정 데이터를 외부 파일에 저장한다.

-w 종료하기 전에 측정 기능이 끝나기를 기다린다. 보통 이 옵션을 쓰지 않으면 테스트 결과를 볼 수 없으므로 필수는 아니지만 꽤 유용하다.

subprocess

이 모델은 2.4 버전에서 새롭게 생긴것으로 이전의 os, poepn2, commands와 같은 다양한 다른 모듈에 있는 기능을 한곳에 모은 것이다.

args는 'ls -l'과 같은 문자열 또는 ['ls','-l']과 같은 문자열 리스트로 지정 한다.

parms는 하위 프로세스의 다양한 속성을 제어하기 위해 설정한 키워드 인수들을 나타낸다. 다음 키워드 인수들을 인식한다.

bufsize: 버퍼링 방식을 지정한다. 0은 버퍼링하지 않고, 1은 줄 버퍼링을 하며, 음수 값은 시스템 기본 값을 사용한다. 그 밖에 양수 값은 대략적인 버퍼 크기를 나타낸다. 기본 값은 0이다.

excutable: 사용할 실행 프로그램의 이름을 지정한다. 프로그램 이름이 이미 args에 담겨져 있기 때문에 사용할 일이 거의 없다. 다만, shell이 주어지면 이 매개변수는 셀의 이름을 지정한다. 기본 값은 None 이다. 

stdin: 자식프로세스에서 stdin에 사용할 파일을 나타내는 파일 객체. stderr에서 사용할 수 있는 값을 사용할 수 있다. 기본 값은 None 이다.

stdout: 자식프로세스에서 stdout에 사용할 파일을 나타내는 파일 객체. stderr에 사용할 수 있는 값을 사용할 수 있다. 기본 값은 None 이다.

stderr: 자식프로세스에서 stderr에 사용할 파일을 나타내는 파일 객체. open()로 생성한 파일객체, 정수 파일 기술자 또는 새로운 파이프가 생성되었음을 나타내는 특수 값 PIPE가 될 수 있다. 기본 값은 None이다.

preexec_fn: 명령을 실행하기 바로 전에 자식프로세스에서 호출할 함수를 지정한다. 이 함수는 인수를 받지 않는다.

close_fds: True이면 자식 프로세스를 실행하기 전에 0,1,2를 제외한 모든 파일 기술자를 닫는다. 기본 값은 0이다.

shell: True 이면 os.system()함수 처럼 작동하는 유닉스 쉘을 사용하여 명령을 실행 한다. 기본 쉘은 /bin/sh 이지만 executable 설정을 통해서 변경할 수 있다. shell의 기본값은 None 이다.  

cwd: 명령을 실행할 디렉터리, 실행 전에 자식 프로세스의 

1단계: 부트로더 언락과 슈퍼 유저(루팅) 설치 

- ubuntu 환경에서 했다. 하지만 첨부파일을 이용하면 window에서도 할 수 있다. -

▣ 부트로더 언락, Note that 데이터가 모두 날라기니 주의 하세요.

1) 볼륨 2개와 + 전원 버튼을 동시에 4초간 눌러 리커빌 모드로 진입 합니다. 

2) 첨부 파일을 다운 받는다.

r3-galaxynexus-superboot.zip

3) 커멘드 창에서 fastboot devices라고 입력해서 장치가 정상적으로 연결 되었는지를 확인한다.

4) fastboot oem unlock을 적용 한다.

필자는 리눅스 환경에서 설정 하였ㄷ.

8) 겔럭시 넥서스에 경고창이 뜨고 그곳에서 볼륨 상/하 번튼을 이용해서 움직이고 yes를 선택후 전원버튼을 눌러서 실행을 하면 됩니다. 그럼 위와 같은 화면이 나오고 그러면 성공 한것이다.

▣ 슈퍼유저 설치, 루팅하기

1) bootloade로 진입 한다. 

1) 위에 첨부파일 디렉터리로 들어가서, install-superboot-linux.sh를 실행함.

   주의: Mac, Linux, window 별로 스크립트가 다르니 주의해서 실행

2) OKAY라고 메시지가 나오고 재부팅이 되어지면 성공이다.

3) 재부팅이 되어질 때 아래와 같은 자물쇠가 풀린 모양이면 된다.

2단계: CWM Recovery 설치하기. 

1) 우선 첨부파일을 다운로드 받는다.

recovery.img

2) 리커버리 모드로 진입을 해야한다. 진입방법은 아래와같이 여러가지다.

2-1) 볼륨버튼 2개 + 전원버튼을 눌러서 부트로더로 들어간다음 그곳에서 설치 한다.

2-2) adb reboot recovery 명령어를 이용해서 들어간다.

3) fastboot flash recovery recovery.img 를 실행 한다.

4) 위와 같이 OK 뜨게되면, CWM이 정상적으로 설치가 된 것입니다.

5) 절대로 지금 bootloader 화면에서 reboot을 하면 안됨.

reboot 할경우 recovery 이미지가 복구됨.

3단 계: 커스텀 롬 설치하기 

1) reboot 하지 않은 부트로더 화면에서 볼륨키를 이용해서 Recovery mode로 이동.

2) 커스텀롬을 SD 카드에 집어 넣는다.

3) CWM 리커버리에서 아래의 3가지 작업을 한다. 기존의 시스템을 삭제하는 행위이다.

wipe data/factory reset

wipe cache partition

advanced -> wipe dalvik cahce

이 세가지 wipe를 모두 해주셔야 합니다. 이유는 커스텀롬은 시스템적인 부분을 모두 건드리기 때문에 완전히 날리고 새로운 롬을 설치하는게 안전 합니다.

4) 단, 동일한 커스텀 롬을 사용하다가 업그레이드 버전을 설치하는 경우

advanced -> wipe dalvik cache를 해주면 됩니다.

5) 다시 처음으로 돌아가서, install zip from sdacrd를 선택해서 쭉쭉 들어가서 아까 넣은 파일을 선택하면 됩니다. 

multiwin.py: Fatal IO error 0 (Success) on X server :0.0. python: ../../src/xcb_io.c:249: process_responses: Assertion `(((long) (dpy->last_request_read) - (long) (dpy->request)) <= 0)' failed.

Sometimes I get:

multiwin.py: Fatal IO error 11 (Resource temporarily unavailable) on X server :0.0.

위 2개의 에러가 뜬다면, 그것은 multiprocessing 모듈을 썻기 때문일 것이다.

즉 동시에 X server랑 통신하려고하면 에러가 난다.

즉, UI는 무조건 main process에서 변경할 수 있다. fork 시킨 자식 프로세스가 변경하기위해서 X server와 커넥션을 하려고하면 무조건 에러가 난다.

이부분 때문에.. 고생좀 했다. 

아래 사이트 참초:

http://stackoverflow.com/questions/9989475/python-multiprocessing-with-2-gtk-windows

▣ 질문: 멀티 프로세싱을 처리할때 어떻게 해야 신뢰성 있게 자식 프로세스의 stdout 결과를 redirect 할 수 있는가?

답변

이것에 대한 해결방법중 하나는 다음과 같다.

먼저 당신의 프로세스들을 메뉴얼하게 생성 해야 된다. 이러한 것들은 명시적으로 stdout/stderr file 핸들을 접근하게 될 것이다. 그리고 나서 당신은 socket을 이용해서 sub process와 커뮤니케이트를 하게 되고 multiprocessing.connection을 socket 위에서 하게 된다. 즉, multiprocessing.Pipe와 같은 것이다.

이러한 작업은 당신에게 IPC와 같은 기능을 제공해 줄 것이다.

아래에 2개의 에제를 참고하도록 하시오.

master.py

import multiprocessing.connection
import subprocess
import socket
import sys, os

## Listen for connection from remote process (and find free port number)
port = 10000
while True:
    try:
        l = multiprocessing.connection.Listener(('localhost', int(port)), authkey="secret")
        break
    except socket.error as ex:
        if ex.errno != 98:
            raise
        port += 1  ## if errno==98, then port is not available.

proc = subprocess.Popen((sys.executable, "subproc.py", str(port)), stdout=subprocess.PIPE, stderr=subprocess.PIPE)

## open connection for remote process
conn = l.accept()
conn.send([1, "asd", None])
print(proc.stdout.readline())

subproc.py

import multiprocessing.connection
import subprocess
import sys, os, time

port = int(sys.argv[1])
conn = multiprocessing.connection.Client(('localhost', port), authkey="secret")

while True:
    try:
        obj = conn.recv()
        print("received: %s\n" % str(obj))
        sys.stdout.flush()
    except EOFError:  ## connection closed
        break

4.4 분산 공유 메모리와 디렉터리 기반 일관성

스누핑 프로토콜은 공유 데이터에 대한 쓰기나 캐시 미스가 발생할 때마다 모든 캐시들 사이에 통신을 필요로 한다.

장점: 캐시 상태를 추적하는 중앙 데이터 구조가 없는 것이 장점이다.

단점: 하지만 확장성 면에서 문제가 있다.

매번 브로드캐스를 해야한다면, 메모리 대여폭 면에서 문제가 발생하게 된다. 

이것에 대한 해결방법이 디렉터리 기반의 프로토콜이다.

디렉터리는 캐시되는 모든 블록의 상태를 기록한다.

디렉터리에는 다음의 내용들이 저장되어 진다.

즉, 어떤 캐시들이 이 브록의 복사본을 가지고 있고, 이 브록이 변경되었는지 등을 기록한다.

가장 간단한 디렉터리 구현은 각 메모리 블록마다 하나의 디렉터리 엔트리를 갖게 하는 것이다. 

간단한 프로토콜은 다음과 같은 상태들을 관리한다.

1) 공유(shared): 하나 이상의 프로세서가 이 블록을 캐시한다. 모든 캐시와 메모리는 최신 값을 가지고 있다.

2) 캐시 안됨: 어떤 프로세서도 이 캐시 블록의 복사본을 갖고 있지 않다.

3) 변경: 단 하나의 프로세서만 이 캐시 블럭의 복사본을 갖고 있으며 이 프로세서가 블록에 쓰기를 수행하였다. 따라서 메모리에 있는 사본은 오래된 값을 갖고 있다 

고급분산시스템 기말고사 문제 샘플_이제민.hwp

 3. 분산 file system의 성능을 향상시키기 위한 방법으로 caching을 이용할 수 있다.

Client, server측에서 적용할 수 있는 caching 방식을 설명하시오.

(1) Client, server측에서 적용할 수 있는 caching 방식을 설명하시오.

Server Caching: 최근에 읽은 디스크 블럭을 서버에서 유지하고 있는 것을 말한다.

읽는것은 문제가 없다. 하지만 쓰기에서 문제가 발생한다. 따라서 두 개의 선택적인 동작이 가능 하다.

1) Write-through operation

서버가 현재 캐쉬에 데이터를 업데이트하고, 즉시 디스크에도 업데이트 하는 방식

2) Delayed-write

Write-through으로 인한 bottleneck을 해결하기 위한 방법이다.

서버는 단지 현재 캐쉬에 데이터를 업데이트 한다.

디스크에는 commit operation을 받았을 때 디스 에 저장 한다.

Client Caching: client 모듈은 read, write, getattr, lookup, readdir operation 결과를 캐쉬에 저장한다. 이를 통해서 서버에 전송하는 request의 수를 줄일 수 있다.

(2) Caching과 file service reliability와의 관계를 설명하시오.

-> Caching은 서버와 클라이언트의 작업 수행 속도를 줄일 수 있다는 큰 장점을 가지고 있다. 하지만 이러한 Caching은 file service reliability를 감소 시킨다. server의 경우 caching을 사용하는 경우 쓰기 작업을 수행하는 시간과 실제 디스크네 쓰는 시간이 다르기 때문에 디스크의 정보가 최근 정보가 아닐 수 있다. 또한 client의 경우도 각 클라이언트들이 cache에 저장한 값이 최근에 업데이트 된 값과 다를 수 있다.

(3) 둘 이상의 client가 한 file을 update할 때의 문제점 및 해결방안을 서술하시오.

-> 둘 이상의 client가 한 file을 update하면 자신이 update했기에 캐쉬에 저장했던 값이 다른 client의 update로 인하여 실제 file 값과 달라지는 문제점이 발생한다. 따라서 이러한 문제점을 해결하기 위해서는 각 client들 서버의 데이터와 client 캐쉬의 데이터의 같은 지를 계속 폴링하며 확인해야 한다. 하지만 이런 polling 방식은 시간을 낭비한다는 문제점이 있다. 이러한 문제점을 해결한 방식이 callback promise다. callback promise는 client가 파일을 업데이트를 하면 그 파일 캐쉬에 저장하고 있는 다른 client는 callback을 받게 되고 callback을 받았을 때만 자신의 캐쉬 값을 수정하면 된다. 

4. 다음은 Needham-Schroeder의 secret-key authentication protocol이다.

(1) 2번 과정을 설명하시오.

-> S는 A의 비밀 키로 암호화된 메시지를 A에게 보내다. 메시지 안에는 새로 만들어진 key KAB 와 B의 비밀키로 암호화된 티켓이 들어 있다. 또한 nonce NA 를 넣어 이것이 A의 요청에 의해 반환된 메시지 인 것을 입증한다.

1번에서 A는 B와의 커뮤니케이션을 위해서 S에게 Key를 달라고 요청했다.

S는 A가 가지고 있는 비밀키를 이용해서 암호화된 메시지를 리턴 한다. 그 메시지의 내용은 다음과 같다. 이 메시지는 Kb로 암호화 되어있다. 그 암호화된 메시지에는 Kab와 A가 있다. 여기서 Kab는 A와 B의 통신을 위해서 S가 새롭게 생성해준 공유 키이다. 그리고 A는 중요한정보(ticket)이다. 

그리고 추가적으로 Na가 있다. 이것은 A->S를 할때 보낸 nonce 값이다. 따라서 이것을 S->A 메시지 않에 추가해서 넣어주면, A의 요청에 대한 S의 응답이라는것이 증명되는 것이다. 즉, 딴놈이 가짜로 응답한는것을 막을 수가 있다. 또한 S 만이 A의 비밀키를 알고 있기 때문에 이 메시지가 S에게서 보내졌다고 믿을 수 있다. 

(2) 5번 과정에서 {NB }KAB 를 보낼 경우, 이 방식이 안전하지 못하게 되는 이유를 설명하시오.

-> 만약 5번과전에서 {NB }KAB를 보내는 방식이라면 NB 의 값을 몰라도 4번 단계의 날아가는 메시지를 중간에 가로채서 B에게 보내게 되면 B는 메시지가 제대로 들어왔다고 생각하게 되어 보안이 뚫리게 된다. 하지만 {NB – 1}KAB 로 할 경우 NB 값을 알아야만 하므로 더 안전하다고 할 수 있다.

5. Message-oriented middleware 와 remote procedure-call 기반 미들웨어의 특징을 각각 간단히 서술하고 장단점을 비교하시오.

가. Message-oriented middleware

상이한 애플리케이션 간 통신으로 일반적으로 비동기 방식으로 지원하는 메시지 전달을 기반으로 한 것을 가리킨다. message queue를 이용하여 전달된 메시지가 활성화 될 때 까지 수집하고 저장한다.

- 동기식/비동기식 모두를 지원 (그러나 대부분 큐를 사용한 비동기적방식 사용)

- Non-blocking

- 큐를 이용하여 한쪽 에플리케이션으로부터 다른 쪽 에플리케이션으로 메시지 전송

- Message queue API 제공

- 베이스 스테이션 결함 허용

- 환경 설정 간단함

나. remote procedure-call

하나의 프로그램이 네트워크에 연결되어있는 다른 컴퓨터에서 서브루틴이나 프로시저를 실행할 수 있도록 한 IPC(프로세스간의 통신)이라고 할 수 있다. 쉽게 말하면, 내 프로그램이 다른 컴퓨터에서 실행되고 있는 프로그램 내의 함수를 실행할 수 있도록 하는 것이다. 일종의 서버 클라이언트 개념이다.

- 동기식 방식

- sender와 receiver 모두 동시에 on-line상태야 통신이 가능하다.

- 함수 처리결과가 올 때까지 blocking상태이다.

다. 장/단점

RPC는 동기식 방식 통신으로 즉각적이고 빠른 통신이 필요한 경우에 적합하다. 은행 창구에서의 입금이나 출금 등과 같이 즉각적인 응답이 필요한 온라인 업무에서 필요하다. 하지만 분산환경에서 상이한 애플리케이션들은 항상 같은 시간에 동작하고 있지 않으며 네트워크 상황이나 서로다른 애플리케이션들의 변경상항들로 인하여 이기종간의 네트워크 분산화를 어렵게 만드는 요인이 된다.

MOM은 일반적으로 비동기적 방식 으로 사용한다. 즉각적인 응답을 원하는 경우가 아니라 다소 느리고 안정적인 응답을 필요로 하는 경우에 많이 사용된다. 여러 가지 일을 종합적으로 처리한 후에야 결과가 나오는 통계 작성 등에는 메시지 기반 미들웨어가 상당한 장점이 있다.

또한 프로그램들은 각각 다른 시간에 실행이 가능하며, 애플리케이션의 구조상에 별다른 제한이 없으며, many-to-one의 통신 형태로 서로 통신이 가능하다. 이기종간의 네트워크 분산화를 쉽게 구성할 수 있다. 

6. Web Service Description Language 에 대해 설명하시오.

1. 웹 서비스 기술 언어 WSDL(Web Service Description Language)

가. WSDL의 정의

- 웹 서비스의 서식과 프로토콜을 표준 방식으로 기술하고 게시하기 위한 언어이다.

- 추상화/구체화 파트가 존재한다.

나. WSDL의 역할

- 서비스 컴포넌트에서의 인터페이스 기술

- Open된 XML 기반의 명세를 통하여 서비스를 이용하고자 하는 사용자의 참조

2. WSDL의 구조 및 구성요소

가. 웹서비스를 위한 wsdl의 구조

-------------------------------요 위까지만 적으면 답일꺼 같습니다. 밑은 참고 자료----------------------

나. WSDL의 구성요소

7. 프로세스나 객체들간 통신 시 marshalling 이 이용되어야 하는 (1) 필요성 (2) 그 역할을 설명하시오.

1) 필요성 : 분산화 환경을 쉽고 빠르게 구성하고 프로세서 간의 서비스(객체)를 사용하기 위해서 프로세서나 객체의 형태와는 관계없이 사용할 수 있는 방식이 필요하였다.

2) 역할 : 클라이언트에서 원격 객체를 호출하기 위해서 필요한 모든 정보를 묶어서 클라이언트에게 전송하여 클라이언트가 사용하고자 하는 객체의 형태에 관계없이 같은 방식으로 인터페이스 함수를 사용할 수 있게 해준다.

Distributed Transactions

0. Overview

이 장에서는 Distributed transaction들이 필요하다. 이것들은 하나 이상의 server에서 야기되어 지는 것을 말한다. 

Dirtributed transaction들은 flat이거나 nested인 것을 말한다.

2단게로 구성되어진 아토믹한 커밋 프로토콜을 배운다.

분산환경에서 어떻게 컨커런시를 컨트롤하는지를 배운다.

어떻게 분산황경에서의 데드락을 찾아내는지에 대한것을 다룬다. 이것을 찾아내는 알고리즘도 배운다.

서버가 실패 했을때 어떻게 복구하는지에 대해서도 배운다. 

1. Introduction

트렌젝션은 모두 원자성을 띄면서 처리가 되어져야 한다. 

이러한 것을 모두 달성하기 위해서, 서버들 중에 하나가 coordinator 규칙을 따라야 한다. 이 cordinator 룰을 반영하는 서버는 모든 서버들의 결과가 동일할것임을 보장하게 된다.

이러한 방법론은 프로토콜에 의존되어 진다.

현재 많이 알려진 프로토콜이 Two-Phase commit protocol이다.

14.2 Flat and nested distributed transactions

2개의 서로다른 구조가 존재한다. Flat과 nested이다.

Flat transaction이란, 클라이언트가 요청을 하나 이상의 서버로 보내는것을 말한다. 17.1의 예제를 보면, 클라이언트에서 T 트렌젝션이 서버 X,Y,Z로 가는것을 볼 수 있다. 주목할것은, flat transaction은 순차적으로 완료된다는 것이다. 즉, 서버 X로 간 transaction이 완료되어야 서버 Y로 가게된다. 따라서 어떤 서버가 locking을 하고 있다면, 그것에 대한 트렌젝션은 그 오브젝트가 완료될때까지 대기하게된다.

Nested transcation이란, Top-level transaction은 서브 트렌젝션을 오픈 할 수 있다. 그리고 각각의 서브 트렌젝션은 자기보다 더 낮은 서브 트렌젝션을 오픈 할 수 있다. 17.1의 예제를 보면, 트렌젝션 T가 2개의 트렌젝션 t1,t2를 오픈하는것을 볼수 있다. 이 두 트렌젝션은 서버 X와 Y의 오브젝트들을 엑세스 하게 된다. 그 다음, T1,T2의 서브트렌젝션은  T11,T12,T21,T22에 대한 트렌젝션을 오픈하게 된다.그리고 이 새롭게 오픈된 서브 트렌젝션들은 다시 M N P 서버들의 오브젝트들을 접근하게 된다. 

이러한 네스티드 에서는 같은 레벨에서의 서브 트렌젝션들은 컨커런시 할 수 있다. 그리고 서로 다른 서버에서 각기다른 오브젝트를 접근한다.

즉, T1,T2가 동시성 발생, T11,T12,T21,T22가 동시성이 발생한다.

우리는 분산 트렌젝션을 다음과 같이 고려해 본다. 그림 17.2와 같이 10달러를 계좌 A와 C에 대해서 발생 시키고, 20달러를 B와 D에 대해서 발생 시킨다. 그리고 A와 B는 서로다른 서버이고 C,D는 같은 서버이다. 

위와 같은 작업을 하나의 셋으로 구성된 4개의 Nested 트렌젝션으로 구성하면그림 17.2와 같다.

여기서 주목할것은, 네스티드이기 떄문에 4개의 트렌젝션이 모두 컨커런트하게 실행되어 질수 있고 심플 트렌젝션보다 성능이 좋다는것이다. 왜냐하면 심플의 경우 4개의 오퍼레이션들이 모두 순차적으로 발생되어지기 때문이다.

14.2.1 The coordinator of a distributed transaction.

아래의 그림 17.3은 하나의 서버가 조정자가 되는것이다

뭔가 작업이 이뤄지는 서버들은 항상 조정자 서버와의 통신이 필요하다. 즉, 커밋을 할려면 항상 조정자 서버에게 허락을 받아야 하는것이다.

그림 17.3을 보면 우선 클라이언트는 조정자로 openTransaction을 요청 한다. 그다음 조정자는 트렌젝션 구분자를 리턴하게 된다. 이 트렌젝션 구분자는 분산 시스템에서 유일한 값을 가지는 것이다. 이것을 위해서 TID는 2가지 부분으로 구성되어질 수 있다. 1) Server identifier (for example, an IP address)와 2) 서버내에서 생선한 unique한 number를 조합해서 사용할 수 있다.

이렇게 조정자가 해당 트렌젝션을 오픈을 허가 했을경우에, 조정자는 앞으로 분산환경에서 발생하게될 해당 트렌젝션에 대한 커미팅과 어볼팅을 모두 책임지게 된다. 즉 반환받은 T를 이용해서 항상 클라이언트는 작업을 요청하게된다. 

participant: 이제 각각의 서버들은 트렌젝션에 참여를 할 것이다. 그리고 이 트렌젝션에 참여한 오브젝트들은 서버마다 각기 다를것이다. 이렇게 트렌젝션에 참여를한 오브젝트들의 집합을 participant라고 정의한다.

participant는 모든 recoverable object들에 대한 유지를 책임진다.

participant는 조정자가 커밋 프로토콜에서 케리아웃 하는것에 대한 협조를 책임진다.

트렌젝션이 진행되어지는 동안, 조정자는 기록 한다. 참조 리스트를 participant들로 가는 그리고 각각의 participant 기록들을 coordinator들에 대한 참조를.

조정자의 인터페이스는 아래와 같이 4개가 있다.

openTransaction() -> trans;

closeTransaction() -> (commit, abort);

abortTransaction()

join(Trans, reference to participant) // 새로운 participant가 transaction에 합류 했는지를 확인 한다.

그림 17.3에 대해서 설명을 한다.

본 구조는 flat banking 구조를 따른다. Branch X, Branch Y, Branch Z.는 각각의 서버를 나타낸다.

하나의 예로 클라이언트에서 b.withdraw를 하게된다면, 조정자에게 해당 작업을 요청한다. 이때 해당 트렌젝션에 필요로한 participant가 있다면 그냥 그걸 실행 하면 되고, 없다면 join을 발생시켜서 조정자가 해당 reference를 트렌젝션에 인가한다. 이렇게해서 작업을 모두 처리하고 나면, closeTransaction을 해서 모든 reference를 제거한다.

주목할 것은, abortTransaction을 이용해서 조정자는 participant를 transaction에서 제거 할 수 있다.

14.3 Atomic commit protocols.

분산환경에서의 transaction은 atomic 해야한다. 즉 모든 트렌젝션이 실행 되거나, 아니면 실행이 아에 안되야 한다. 그 사이의 상태는 있을수 없다.

이것을 구현하기위한 간단한 방법은, 조정자가 커밋과 어볼트를 모든 참여자에 대해서 처리하는 것이다. 이러한 방법을 on-phase atomic commit protocol. 이라고 한다

단점: 이 방법은 서버 스스로 트렌젝션에 대한 어보트와 커밋을 결정할 수 없기 때문에 문제가 된다. 왜냐하면, 리소스에대한 락킹 매커니즘을 사용했을때, 데드락이 발생할 수 있고, 그경우 서버는 클라이언트가 인지하지 못하는 상태에서도, 스스로가 트렌젝션을 어보트 해야한다. 하지만 이 방법은 서버 스스로가 어보트를 시킬수 없기 때문에 데드락을 해결할 수가 없다. 이것을 조정자가 처리해주기에는 조정자는 가각의 서버들이 언제 크래쉬 되었는지를 알아내기 어렵다.

Two-phase commit protocol.

이 개념이 나온 이유는, participant 스스로가 트렌젝션의 일부분을 abort 시키기 위함이다. 이렇게해야 데드락 문제를 발생 시키지 않는다. 하지만 트렌젝션은 atomic해야 하기 때문에 트렌젝션의 일부분이 어보트 되더라도 트렌젝션 전체가 다시 롤백해야한다. 이 문제를 다시 해결 해야한다.

첫 번째 phase에서는, 각각의 participant가 트렌젝션에 대해서 commit인지 abort인지를 투표하게 된다. 일단 하나의 participant라도 commit을 투표한다면, 절대로 abort 되어질 수 없다. 따라서 참여자의 커밋은 신중해야하며, 궁극적으론 어떠한 문제조 발생 시키지 않는다는것을 보장해야 한다. 

그리고 이것을 위해서 준비단계에서 모든 오브젝트를 트로지에 저장하게 된다.

두 번째 phase에서는, 모든 참여자들은 joint decision을 싱행하게 된다. 만약 어떤 하나의 참여자가 어보트를 투표하게 된다면, 그때 반드시 트렌젝션 전체가 어보트 되어저여햔다. 

모든 참여자가 커밋을 요청 했을 때마 트렌젝션은 커밋 되어 질수 있다. 

문제점: 모든 참여자들의 투표를 검증하는 것이 문제이다. 즉 실패해대한 처리가 어렵다.

14.3.1 The two-phase commit protocol

결국 핵심 알고리즘은 17.5와 같다.

2개의 Phase는 voting과 vote 결과에 따르는 완료로 구성되어진다.

2단계 끝 부분에서, 조정자와 모든 참여자들은 Yes를 투표하면 즉시 영송적인 저장 장치에 해당 트렌젝션을 저장해서 커밋을 위한 준비를 한다. 만약 No라고 하면 즉시 버린다.

3을 보면 조정자는 투표들을 수집하게 된다.

3-a) 모든 투표가 Yes 라면. 조정자는 커밋을 결정한다. 그리고 doCommit 요청을 각각의 참여자들에게 보낸다.

3-b) 달느 한편으로, 조정자는 트렌젝션의 어보트와 doAbort 요청을 투표시 yes를한 모든 참여자들에게 보낸다. No라고 한 참여자들은 스스로 알아서 어보트 했기 때문에 보낼 필요가 없다.

4에서는 yes를 투표한 참여자들은 조정자로부터 doCommit 또는 doAbort 요청 메시지를 받을때 까지 기다리게 된다. 만약 참여자가 이 두 메시지중 1개를 받는다면, 그것에따라서 동작하게 된다. 그리고 만약 commit의 경우 haveCommitted를 호출해서 조정자에게 정상저으로 커밋 했다는것을 최종적으로 알리게 된다.

14.3.2 Two-phase commit protocol for nested transactions

가장 바깥쪽의 transaction T가 서브 트렌젝션은 t1,t2,t11,t12,t21,t22는 서브트렌젝션.

각각의 서브 트렌젝션은 그것의 부모 이후에 시작하게 된다. 그리고 그것 이전에 끝나게 된다.

따라서, t11과 t12가 t1 이후에 시작하게대고, 끝나는것은 t1 이전에 끝나게 된다.

서브트렌젹센이 완료되었을때, 그것은 독립적으로 결정하게 된다. 일시적인 커밋과 abort를 

일시적인 commit은 prepared commit과는 다르다. 그것은 permanent storage에 back-up하는것과는 다르다.

만약 서버가 커밋이후에 crash되어 진다면, 커밋 교체는 가능하지 않다. 왜냐면 영속적인 저장 장치에 백업을 하지 않았기 때문이다. 

따라서 Two-phase commit 프로토콜을 사용해서 nested transaction을 수행하는것이 올바르다.

서브 트렌젝션을 위한 조정자는 서브 트렌젝션을 오픈하는 operation을 제공한다. 그것은 Top-level 트렌젝션을 위한 구분자를 리턴한다. 클라이언트는 서브 트렌젝션을 시작한다. openSubTransaction 오퍼레인션을 실행 시켜서, 이것에 대한 동의는 부모 트렌젝션이 승인하게 된다. 새로운 서브트렌젝션들은 자동으로 parent 트렌젝션들에게로 조인하게 된다 그리고 서브트렌젝션을 위한 트렌젝션 구분자들은 리턴된다.

서브트렌젝션을 위한 구분자는 반드시 부모 트렌젝션의 TID를 확장해서 만들어 져야한다. 즉, 모든 시스템에서 유니크한 정보를 담고 있어야한다. 클라이언트는 최종적으로 트렌젝션을 완료하게 되면, closeTransaction 또는 abortTransaction을 탑 레벨 트렌젝션 조정자에서 실행 시켜서 끝내게 된다.

nested transaction들이 그것의 오퍼레이션들에 의해서 실행되어 지게 된다. 그리고 그것들이 완료 되었을 때, 서버는 서브트렌젝션들이 일시적으로 committed 되었는지 아니면 aborted 되었는지를 기록하게 된다. 

주목할것은, 만약 부모의 트렌젝션이 abort되었다면 반드시 서브트렌젝션들은 강제로 abort 되어야 한다.

탑 레벨 트렌젝션 T와 그곳의 서브트렌젝션은 그림 17.8과 같다. 이 그림은 17.1을 기반으로 새롭게 작성한것이다. 각각의 서브트렌젝션들은 임시적으로 committed 또는 aborted를 실행하게 된다. 예를들면, T12는 임시적으로 커밋을 수행 했다. 그리고 T11은 abort를 실행 했다. 

T12는 부모 트렌젝션인 T1에 의해서 자신의 운명이 결정되어지며, 궁극적으로 top-level 트렌젝션 T에 의해서 모든 서브트렌젝션들이 결정되어 진다. 

즉, T21과 T22가 둘다 잠정적으로 커밋했더라도 T2가 어보트 할경우 이 두개는 반드시 어보트 되어진다. 

(분산 트렌젝션의 원자성의 원리에 근거해서)

T는 비록 T2가 aborted이지만 커밋일 수 있다. 또한 T1은 커밋을 결정할 수 있다 비록 T11이 어보트일지라도.

최상위 레벨 트렌젝션이 완료되었을 때, 그것의 조정자는 Two-phase commit protocol을 실행하게 된다.  

오직한가지 이유가 있다. 참여자의 서브트렌젝션이 완료되어지지 못하는 경우는, 만약 crashed되어지는 시점이 임시 커밋이 이뤄진다음일 경우이다.

조정자는 parent와 서브 트렌젝션들에대한 모든 상태들을 알고 있어야 한다. 모든 서브트렌젝션은 어보트할경우 부모 트렌젝션에게 반드시 이를 보고한다. 따라서 최상위 수준의 트렌젝션은 모두 하위 서브트렌젝션의 상태에 대해서 알 수 있다. 그리고 조정자는 이 최상위 수준의 트렌젝션이 가지고 있는 정보만 참조하면 되는 것이다.

17.8을 기반으로 각각의 조정자가 가지고 있는 정보를 표현한 것이 그림 17.9이다. 

주목할것은, T12,T21은 조정자의 정보를 공유한것이다. 왜냐하면 같은 서버 N에서 동작하기 때문이다.

서브트렌젝션 T2가 어보트 되었을때, 그 사실은 부모인 T 트렌젝션에게로 보고 된다. 하지만 T21, T22 서브트렌젝션들에 대한 정보는 전달하지 않는다. 왜냐하면 T2가 어보트했기때문에 그 자식인 두 서브트렌젝션의 정보는 무엇이 되었는 상관이 없기 때문이다.

서브트렌젝션의 고아현상(orphan)은 다음과 같다.만약 조상중에 하나가 어보트 되었거나, 그것의 조정자가 crash 되었기 때문이다. 

우리의 예제에서는, T21과 T22가 고아이다. 왜냐하면, 그들의 부모가 탑 레벨 트렌젝션에 자신들의 정보를 넘기지않고 어버트 되어졌기 때문이다. 하지만 조정자는 그들의 parent의 상태를 조사하게된다. getStatus operation을 사용해서. T21과 T22는 모두 provisionally committed 이지만 그냥 aborted 되어 진다. 최상위 레벨 트렌젝션이 커밋 되어지더라고 상관없이, 왜냐하면 자신의 부모가 어보트 되어졌기 때문이다.

이제 TPC(Two phase commit)을 수행한다. 투표를 하게될 참여자 들은 T, T1, T12 이다. 다른것들은 모두 어보트 되었거나 고아이기 때문에 투표를 하지 않는다. 

phase 1: 커밋을 투표한다면, 반드시 그들의 트렌젝션 내용은 영속적인 저장장치에 저장이 되어야 한다.

phase 2: 조정자는 투표결과를 수집하고 참여자들의 결과에 대해서 확인 한다.

이때 phase2에서의 동작방식은 non nested case일때와 동일하다.

그렇게 해서 최종적으로 참여자들의 투표 결과에 따라 aborted 인지 커밋인지를 결정한다.

이제 TPC protocol을 2가지 방식으로 수행한다. hierarchic or flat 방법이다.

Hierarchic two-phase commit protocol: 

이 접근법은, two-phase commit protocol은 멀티레벨 네스티드 프로토콜이 된다. 

최상위 레벨 트렌젝션 조정자는 서브 트렌젝션 조정자와 통신을 한다. 이렇게 연결된 각각의 조정자들은 canCommit?이라는 메시지를 보내서 확인을 한다. 이것은 트리구조로써 점점 하위로가면서 처리가 되어지는 형태이다. 각각의 참여자들은 그들의 부모에게 보고하기전에 자손들의 응답을 모두 받은다음에 부모에게 최종적으로 응답하게 된다. 

우리의 예제를 통해서 설명을 하면 다음과 같다.

T는 canCommit? 이라는 메시지를 조정자 T1에게 보낸다. 그리고 T1은 canCommit? 이라는 메시지를 T1의 자식인 T12에게 전송한다. T2는 어보트 했기 때문에 투표에 참여하지 않는다.

canCommit의 아규먼트에 대해서 알아보자.

첫 번 째 아규먼트인 TID는 최상위 레벨 트렌젝션의 것이다. 이것은 데이터를 준비할때 사용한다.

두번째 아규먼트는 참여자에 대한 TID이다. 이 두번쨰 아규먼트를 통해서 호출에 대한 결과값 구분을 하게 된다.

예를들어서 조정자 T12와 T21은 서로 같다. 왜냐하면 이것은 같은 서버에서 동작하는 서브 트렌젝션이기 때문이다. 하지만 canCommit? 콜에대한 리턴을 받을때, 두번째 아규먼트는 T1 이고 그것은 T12로 다뤄 질 것이다.

Flat two-phase commit protocol: 

조종자가 모든 임시적으로 커밋을한 참여자들에 대해서 투표를 요청하게 된다. 그러면 참여자들은 Yes/No를 투표하게 된다.

이것의 핵심은 최상위 레벨 조정자가 canCommit을 보낸다는 것이다. 모든 provisional list에 있는 서브트렌젝션의 조정자들에게 말이다.

3. Concurrency Control in Distributed Transactions

컨커런시한 트렌젝션이 실행 될수 있으므로, 각각의 서버들은 이것을 메니지 해줘야한다.

즉, 트렌젝션 U와 T가 같은 서버에서 실행되고 공통의 자원에 대해서 엑세스를 한다면, 그것의 순서를 반드시 메니지 해줘야 한다는 것이다.

14.4.1 Locking

락은 같은 서버에서 지역적으로만 유지가 된다.

로컬 락의 매니지먼트 방법은 다음과 같다.

락의 승인을 요청허가나 그것이 안되면 문제가 발생한 트렌젝션이 끝날때가지 기다려야한다.

분산에서 데드락이 발생하는 상황은 아래와 같다.

이 문제는 트렌젝션의 어보트를 통해서 해결할 수 있다. 결국 이래서 TPC를 사용해야 하는것이다.

14.4.2 Timestamp Ordering Concurrency Control

싱글 서버 트렌젝션은 유니크한 타임스템프를 가진다.

14.5 Distributed deadlocks

분산에서는 wait-for graph을 그려서 찾을 수가 있다. 분산환경에서의 데드락을

Wait-for graph

1) Node: transactions and data item

2) Edges: a data item that held or waited by a transaction 

위 그림 17.2는 분산 데드락이 있는 트렌젝션들이다.

우선 트렌젝션은 U,V,W가 있다 이 3개는 상호 작용을 하면서 동작을 한다.

오브젝트 A는 서버 X

오브젝트 B는 서버 Y

오브젝트 C와 D는 서버 Z

위 관계를 wait-for graph으로 그린것은 그림 17.3과 같다.

그림 중 (a)는 모든 에지들로 구성된 데드락 사이클을 보여준다. 트렌젝션 때문에 기다리는 오브젝트와 그리고 트렌젝션을 유지하고 있는 오브젝트를 나타내고 있다. 단순히 기다리고 있는 오브젝트들에 대해서만 그림을 그린것이 (b)이다.

결국 이러한 분산 데드락을 발견해 내기 위해서는, local wait for graph을 그려야한다. 이것을 각각의 서버에 대해서 생성을 하면 아래와 같다.

그리고 위와 같은 local deadlock을 합쳐서 global wait for graph을 생성하면 된다.

Centralized deadlock detection 

이러한 deadlock을 찾아내는 간단한 솔루션은  Centralized deadlock detection 기술이다.

각각의 서버들이 자신들의 local-wait-graph을 중앙서버로 전송을 하고, 그것을 합병해서 global wait-for graph을 생성하게 된다. 그 다음, global deadlock detector는 각각의 사이클을 체크해서 분산 데드락을 찾게 된다.

데드락을 찾으면 해당 서버에게 트렌젝션을 어보트 시켜서 해결을 할것인지를 확인하게 된다.

단점: 

하지만 이것은 좋은 생각이 아니다. 이러한 방식은 싱글서버로 전달해야하는 문제점이 있다.

이러한 문제점은 다음과 같은 단점을 야기 시킨다,.

1) 접근성이 떨어진다.

2) 고장 허용이 약해진다.

3) 확장성이 떨어진다.

4) 주기적으로 local wait for graphs를 전송하는것은 비용이 많이 든다. 주기를 떨어 틀이면 데드락 디텍션 시간이 길어지기 때문에 주기를 마냥 길게할 수도 없다.

Phantom deadlocks: 데드락을 찾았지만 실제 데드락이 아닌것을 부르는 말이다. 

즉, 데드락을 찾기위해서 정보를 병합하는 과정에 데드락이 이미 해결되었는데, 그 정보가 제대로 반영이 되지 않았을 경우에 발생하는 문제이다.

잘이해가 안가니 예제를 들어서 설명하도록 하겠다.

X와 Y로 부터 Local wait for graph를 받았다고 치자. 

T->U (at X)

V->T (at Y)

이상태인대 이제 T->U이게 바뀌여서 U->V를 한다고 치자.

그럼 U->V->T가 된다.

그런데 여기서 global detector가 서버 X에 대한 local wait for graph을 갱신받지 않았다면,

T->U는 이미 존재하지도 않은 트렌젝션이지만 이걸 반영해서

T->U->V->T 라는 global wait for graph을 생성하게 되어서, deadlock이 있다고 판단해 버린다. 이러한 경우를 팬텀 데드락이라고 한다. 

Edge chasing (Path Pushing)

이방법은 global wait for graph를 구성하지 않는다. 각각의 서버들은 그것의 edge들에 대해서 알고 있는 지식을들 전송한다. 서버들은 사이클들을 찾으려고 노력한다. 서로 probe을 전송하면서, 

probe는 분산 시스템 전반에 걸친 edge들에 대한 내용이다. 

prob 메시지는  트레젠셕의 관계들로 구성되어 진다.

즉 이것은 서버들의 전체적인 에지를 말하게된다.

첫번째 질문: 서버는 언제 probe를 전송 하는가?

이 알고리즘은 3가지 스탭을 가진다.

initiation, detection and resolution

initiation: 서버 T 트렌젝션이 시작하자마자 다른 트렌젝션 U 때문에 웨이팅 되어지는 것을 인지하게 된다. 이러한 관계를 초기에 발견하고 edge를 생성하게 된다 그것이 T->U 이다. 그리고 U는 블럭 되어져 있는 상태이다. 

detection: 

이 단계는 probes의 receiving과 deadlock 발생의 구분, probe의 포워드로 구성된다.

예를들어서, 서버는 probe <T->U>를 받았다고 치자. <T->U>는 T는 트린젝션 U에 대해서 기다리고 있는 것을 나타낸다. 왜냐하면 U는 local object를 홀드하고 있기 때문이다.

그곳은 U 또한 기다리고 있는 상태인지를 체크하게 된다. 만약 그 U 트렌젝션 또한 V 라는 트렌젝션에 의해서 대기중이라면, probe를 추가한다. ( making it <T->U->V>

이렇게하여서, global wait for graph의 path들을 통과하는 하나의 edge가 생성되게 되어진다. 

resolution: 

사이클을 찾아냈을떄 사이클 내의 트렌젝션을 오버트해서 데드락을 제거한다.

그림 17.5의 예제를 들어서 Edge chasing 방법을 설명하도록 하겠다.

• 서버 X는 초기 발견을 해서 probe< W->U >을 B의 서버(Server Y)로 전송 한다.

• 서버 Y는  probe< W->U >을 받는다. 주목할것은 B는 트렌젝션 V에 의해서 홀드되어지고 있다. 따라서 V는  probe< W->U >에 추가되어지고  probe< W->U->V >가 되어진다. 그리고 V가 기다리고 있는 C의 서버 Z에게 이 probe를 포워드 한다.

• 서버 Z은 probe< W->U->V >을 받는다. 그리고 Z는 자신의 객체 C가 트렌젝션 W에 의해서 홀드되어져 있기 때문에 이것은 현재 전송받은 probe에 추가한다. 최종적으로 probe< W->U->V ->W >가 생성 된다.

11.3.2 Cristian's method for synchronizing clocks

간단하게 계산하면 프로세스 P의 지연 시간은

11.3.4 The Network Time Protocol

Cristian's method나 Berkeley algorithm은 인트라넷을 위한 것이다. 

이장에서 다룰 Network Time protocol은 순전히 인터넷위에서의 타임 서비스와 분산환경에서의 타임 프로토콜을 위한 아키텍쳐이다.

NTP의 중요한 디자인 이념은 다음을 따른다.

인터넷 전반에 걸쳐서 클라이언트 서비스가 정확히 동기화되게 가능하도록 지원한다.

비록 인터넷 환경은 딜레이가 있지만, NTP는 통계적인 기술들을 이용해서 타이밍 데이터를 필터링하고 타이밍 데이터를 서로다른 서버들로부터 그 퀄리티를 식별해 내게 된다.

11.4 Logical time and logical clocks

어떤 이벤트가 발생했고 이러한 이벤트들의 쌍들에 대해서 정확하게 그 인과관계를 알아내는것은 어렵다. 이것을 지원하기 위한 매커니즘이다.

아래의 직관적인 두가지 포인트에 기반해서 이러한 인과관계를 파악하게 된다.

1) 같은 프로세스에서라면 이벤트들의 순서를 정할 수 있다.

2) 언제든지 발생된 이벤트들에대한 정보를 다른 프로세스들에게로 전송 할 수 있다.

이러한 원리들에 대해서 그림을 보며 이해를 하자.

그림 11.5를 보면 3개의 프로세스들이 정의가 되어 있다. 

여기서 핵심은 모든 이벤트들이 관계가 명확히 파악 되어지는것은 아니다. 

즉, a -> e 인지는 알 수 없다. 왜냐하면 서로 다른 프로세스에서 실행 되어졌기 때문이다. 그리고 그것들 사이에 어떠한 메시지 체인도 없기 때문에 더더욱 알 수가 없다.

우리는 이러한 이벤트들을 순서를 정할 수 없다고 하며 이것을 concurrent 하다고 한다.

그리고 그것을 a || e 라고 기술 한다.

Logical clock:

Lamport는 간단한 numerically에 기반한 이벤트 상관 관계를 기록하는 매커니즘을 개발 했다.

결국, Lamport logical clock은 단조 증가하는 소프트웨어 카운터이다. Lamport logical clock는 physical clock에 대한 정보를 가지고 있을 필요가 없다. 각각의 프로세스 pi들은 그것들이 소유하는 logical clock을 유지하고 있다. Li라고 그것을 부르며, 이것은 Lamport timestamp들에 의해서 적용되어 진다. 

우리는 프로세스 pi에서의 이벤트 e의 타임스탬프를 Li(e) 와 L(e)로 표현한다. 우리의 이 표식은 이벤트 e가 어떤 프로세스에서도 발생할수 있음을 뜻한다.

상관 관게를 기록하기 위해서, 프로세스들은 그들의 logical clock들을 갱신하고 메시지에서의 그들의 logical clock들의 값을 전송 한다. 다음과 같이.

비록 클락이 1씩 증가할지라도, 우리는 선택해 왔다 어떤 positive 값을. 그것은 어떤 이벤트들의 순서 관계에 의한 유도가 쉽게 파악될 수 있다. 

즉,  event e와 e'이 e-> e' => L(e) < L(e') 이다.

주목할 것은, 위 명제의 convers는 참이 아니다. 즉, L(e) < L(e')라고 해서, 우리는 e->e'라고 추론 할수는 없다. 

위 그림은 이전의 그림에 대한 logical clock들에 대한 그림으로 전환한 것이다. 

각각의 프로세스들 p1,p2,p3들은 초기 0의 logical clock을 가지게 된다.

The clock values given are those immediately after the event to which they are adjacent.

Totally ordered logical clocks

모든 페어들에 대해서 구별 가능하게 한다. 프로세스 구분자를 사용해서

즉, local Time stamp는 T이다.

(T1,p1) < (T2,p2) if either T1 < T2 or T1 = T2 and p1 < p2

Vector clocks ◇

vector clock은 Lamport timestamp가 가지는 단점을 극복하기 위해서 개발 되어 졌다.

이 단점이란 다음과 같다. 

의 경우 우리는 e와 e'의 관게를 결정 할 수 없다.

왜냐하면, 논리적인 클란은 물리적인 클락과 관계가없고 서로다른 프로세스에서 어떠한 상관 관계도 알 수 없기 때문이다.

N개의 프로세스에서의 벡터 클락은 N integer들의 array 이다. 각각의 프로세스들은 그것들의 vector clock Vi를 유지하게 된다. 이것은 local event들의 타임스탬프를 사용한다. Lamport 타임스탬프와 같이, 프로세스들은 벡터 타임스탬프들을 메시지위에 실어서 다른 프로세스로 보내게 된다. 그리고 다음과 같은 규칙에 의해서 그것을 갱신하게 된다.

아래의 그림14,7을 해석하면 아래와 같다.

V(a) < V(f)를 나타냄을 알 수 있다. 이것은 a->f라는것을 유도해 낼 수 있다. 비슷하게 우리는 2개의 이벤트가 concurrent할때 2개의 타임스탬프를 비교해서 이것을 구분해 낼 수 있다.

For example, that c ||e can be seen from the facts that neither V(c) <=  V(e) nor V(e) <= V(c).

벡터 타임 스탬프의 단점은 , 프로세스의 수 N에 비례해서 storage의 크기와 message payload가 늘어난다는 점이다.

non-recursive server-controlled navigation 아래에서는 어떠한 named server가 클라이언트에 의해서 선택 되어 진다.