'Tips'에 해당되는 글 15건

  1. 2012.03.15 PID Namespace
  2. 2012.01.31 Linux Kernel : 커널이란
  3. 2011.07.27 Python-Twitter
  4. 2011.04.18 gprolog-GNU's prolog compiler/interpreter
  5. 2011.04.02 A* Search
Tips/Kernel development2012. 3. 15. 22:50
lwn.net의 PID Namespace 관련 글 하나를 번역해보았다.

Namespace는 커널 2.6.24버전부터 도입된 것으로, 일종의 독립적인 PID 공간이라고 볼 수 있다. Namespace들 간에 부모-자식 관계가 있으며, 각 Namespace별로 PID가 따로 관리되기 때문에 동일한 PID를 Namespace별로 사용할 수 있게 된다.

다음은 글의 원문이다.

A pid namespace is a "view" of a particular set of tasks on the system. They work in a similar way to filesystem namespaces. A file (or a process) can be accessed in multiple namespaces, but it may have a different name in each. In a filesystem, this name might be /etc/passwd in one namespace, but /chroot/etc/passwd in another.

For processes, a process may have pid 1234 in one namespace, but be pid 1 in another. This allows new pid namespaces to have basically arbitrary pids, and not have to worry about what pids exist in other namespaces. This is essential for checkpoint/restart where a restarted process's pid might collide with an existing process on the system's pid.
In this particular implementation, pid namespaces have a parent-child relationship, just like processes. A process in a pid namespace may see all of the processes in the same namespace, as well as all of the processes in all of the namespaces which are children of its namespace. Processes may not, however, see others which are in their parent's namespace, but not in their own. The same goes for sibling namespaces.

The know issue to be solved in the nearest future is signal handling in the namespace boundary. That is, currently the namespace's init is treated like an ordinary task that can be killed from within an namespace. Ideally, the signal handling by the namespace's init should have two sides: when signaling the init from its namespace, the init should look like a real init task, i.e. receive only those signals, that is explicitly wants to; when signaling the init from one of the parent namespaces, init should look like an ordinary task, i.e. receive any signal, only taking the general permissions into account.
The pid namespace was developed by Pavel Emlyanov and Sukadev Bhattiprolu and we eventually came to almost the same implementation, which differed in some details. This set is based on Pavel's patches, but it includes comments and patches that from Sukadev.
Many thanks to Oleg, who reviewed the patches, pointed out many BUGs and made valuable advises on how to make this set cleaner.



pid namespace는 시스템 상의 태스크의 특정 집합의 "View"이다. 
그들은 파일시스템의 namespace와 유사한 방법으로 동작한다. 파일(혹은 프로세스)은 다양한 namespace에서 접근될 수 있다. 그러나 파일(혹은 프로세스)은 각 namespace에서 다른 이름을 가져야 할 것이다. 파일시스템에서, 한 namespace에서 이름이 /etc/passwd가 될 수 있다. 하지만 다른 namespace에서는 /chroot/etc/passwd가 되어야 한다.
 프로세스들을 위해서, 프로세스는 한 namespace에서 pid 1234를 가질 수 있지만 다른 곳에서는 pid 1이 될 수 있다. 이는 다른 namespace에 어떤 pid가 있는지 고려하지 않고 새로운 pid namespace가 기본적으로 임의의 pid들을 가질 수 있도록 해준다. 이는 재 시작된 프로세스의 pid가 시스템의 pid상에서 존재하는 프로세스와 충돌할 때, 
checkpoint/restart를 위해서 필수적이다
.
 특정 구현에서, pid namespace는 마치 프로세스처럼 부모-자식 관계를 갖는다. pid namespace 내의 프로세스는 같은 namespace안의 모든 프로세스 뿐만 아니라 그 namespace의 자녀 관계인 namespace들 안의 모든 프로세스들도 볼 수 있을 것이다. 그러나 프로세스는 그들의 부모 namespace의 프로세스들을 볼 수 없을 것이고, 사촌관계에 있는 namespace의 프로세스들도 볼 수 없을 것이다.
 곧 해결될 이슈는 namespace 경계에서 시그널 처리이다. 이것은 현재 namespace의 init이 namespace에서 kill될 수 있는 일반적인 태스크처럼 다루어지기 때문이다. 이상적으로, namespace의 init에 의한 시그널 처리는 두 가지 측면을 가져야만 한다. : 그것의 namespace로부터 init에 시그널이 도착했을 경우, init은 실제 init 태스크처럼 보인다. 즉 시그널을 받았을 때, 그것은 확실히 받길 원하는 것이어야 한다. 부모 namespace의 하나로부터 init이 시그널을 받았을 때, init은 일반 태스크처럼 보여야 한다. 즉 어떤 시그널을 받던지, 일반적인 권한이 고려되어야 한다.
pid namespace는 Pavel Emlyanov와 Sukadev Bhattiprolu에 의해서 개발되었다. 우리는 거의 같은 사양으로 구현하기로 결정하였고, 몇몇 세부사항만이 다를 뿐이다. 이는 Pavel의 패치에 기초하였으나, 그것은 Sukadev로부터의 패치와 코멘트를 포함하고 있다.
원문주소 : http://lwn.net/Articles/245104/

'Tips > Kernel development' 카테고리의 다른 글

VFS : Virtual File System - Introduction  (0) 2012.09.30
Linux Kernel : 커널이란  (0) 2012.01.31
Posted by 곰푼
Tips/Kernel development2012. 1. 31. 16:10
 컴퓨터는 CPU, 메모리, 디스크 등의 다양한 장치들로 구성되어 있다. 이 장치들을 추상화하여 사용자들이 혹은 응용프로그램이 사용하기 쉽도록 해주는게 바로 운영체제이며, 그 운영체제의 핵심이 바로 커널이다.

 커널은 컴퓨터에 부착된 장치들을 효율적으로 관리하도록 해주는 관리자의 역할을 한다. 각 장치들은 추상화를 통해 사용자들이 접근할 수 있게 된다.

커널은 크게 두 가지 타입으로 나뉠 수 있다. (하이브리드, 엑소 커널은 여기서는 논외로 하자.)

1. 모놀리식 커널 Monolithic Kernel

 이 커널은 시스템을 관리하기 위한 기능들이 하나의 이미지에 내장된 커널을 의미한다. 하드웨어 위에 고수준의 가상 계층을 가지고 있으며, 어플리케이션 영역의 프로그램 구현을 위한 서비스를 제공한다. 이 서비스에는 프로세스 스케줄링, 메모리 관리, 디스크 관리, 장치 관리 등이 있으며, 이를 위하여 시스템 콜(System Call)의 형태로 서비스들을 제공한다. 
 커널이 하나의 프로세스로써 단일 주소 공간에서 실행되도록 구현되어있으며, 커널 이미지는 일반적으로 단일 정적 바이너리로 존재한다. 


2. 마이크로 커널 Micro Kernel
 
 커널의 기능들을 서버(Server)라 불리는 분리된 프로세스로 조각내어서 커널 자체의 크기를 줄인 커널이다. 각 서버들은 다른 주소공간에서 실행되도록 분리되어 있으며, 오직 서버만이 각 기능들을 특권 실행 모드(Privileged execution mode)에서 실행할 수 있다. 그러므로 모놀리식 커널에서와 같은 직접적인 함수 호출이 불가능하고, 대신 IPC와 같은 메시지 패싱 기법으로 호출할 수 있다. 
 IPC 매커니즘이 일반적인 함수 호출에 비해 꽤 큰 오버헤드를 갖고 있고, 또 커널 공간과 사용자 공간의 컨텍스트 전환(Context Switch)이 자주 발생하기 때문에, 모놀리식 커널에서 볼 수 없는 추가적인 처리량을 내재하고 있다.

 

Features of Linux Kernel::

 

리눅스 커널은 모놀리식 커널이지만, 모듈을 동적으로 적재할 수 있도록 지원한다. 모듈은 필요에 따라 그 코드가 적재(Load) 혹은 제거(Unload)될 수 있다.

SMP(Symmetric MultiProcessor)를 지원한다. SMP는 두 개 또는 그 이상의 프로세서가 하나의 메모리 공간을 공유하여 사용하는 다중 프로세서 아키텍쳐이다.

선점형 커널이다. 선점형 커널에서는 시스템 콜 루틴 수행 중간에 인터럽트를 체크해서 인터럽트의 수행을 우선시한다. 비선점형 커널에서는 시스템 콜을 우선시하여, 해당 호출이 끝난 후에 인터럽트를 수행한다.

리눅스에서는 스레드와 프로세스가 서로 다르지 않다. 이는 리눅스에서 스레드의 구현을 light weight process로 구현하기 때문이며, 이에 대해서는 나중에 논하기로 하겠다.

'Tips > Kernel development' 카테고리의 다른 글

VFS : Virtual File System - Introduction  (0) 2012.09.30
PID Namespace  (0) 2012.03.15
Posted by 곰푼
Tips2011. 7. 27. 02:42
아직 잘은 모르지만, Twitter의 API를 사용하게 해주는 파이썬의 래퍼 라이브러리(?-이표현이 맞을까)인 듯 하다.

http://code.google.com/p/python-twitter/


위의 URL로 들어가면 해당 프로젝트의 웹 페이지가 나온다.

먼저
 


각각 json, http, oauth에 관한 라이브러리 패키지들이다. 파이썬-트위터가 위 패키지들에 의존적이므로 미리 설치해두는 편이 무자비한 탈모증상을 막는데 도움이 될 것이다.

각각 패키지의 설치법은 리눅스를 기준으로,

$sudo python setup.py install


이 명령어면 대부분 될 것이다.

다만 내 경우 세번째 패키지를 설치할 때 다소 시행착오가 있었는데, simplejson 패키지에서 ez_setup.py파일을 복사해서 이 코드부터 실행시킨 뒤에 위의 명령어를 날려주면 가뿐할 것이다.

그런 다음, google의 프로젝트 페이지에서 소스코드를 다운받아서

$sudo python setup.py build
$sudo python setup.py install


을 입력해주면 설치가 금방 끝날 것이다. 끝나고 난 뒤, 테스트로

$python twitter_test.py


와 같은 명령으로 제대로 되는지를 테스트해볼 수 있다고 하지만, 내 경우에는 에러메시지만 출력하였다.

자 라이브러리를 설치했으니, 뭔가 테스트해봐야할 것이다.

원래대로라면 basic인증이라 해서 아이디와 패스워드만 있으면 바로 트위터 api를 사용가능했다고 한다. 하지만 지금은 OAUTH나 XAuth와 같은 인증을 통하지 않고는 불가능하다고 한다. 보안문제를 위해 조금 더 번거로워 졌다고 보면 되겠다.

OAuth는 트위터에서 사용하는 인증에 대한 표준이다. 트위터의 리드 프로그래머와 구글의 오픈 웹 담당자와 또 모종의 인물이 담합(?)하여 만든 표준이라는데, 나도 정확하게는 모르겠다. 온라인 결제를 위해 사용하는 공인인증방식을 떠올리면 비슷하겠으나, 이와 같은 방법을 표준화했다고 생각하면 될 것 같다.
더 자세히 설명한 포스팅이 있으니 참고하자.


일단 인증을 하기 위해 다음의 페이지로 가서 등록을 하자.

https://dev.twitter.com/apps/new


여기서 *표시된 것은 반드시 작성해야하는 것이며, URL을 적으라고 하는 부분은 http://localhost/와 같이 적어도 무방하다고 한다. 이후 어플리케이션 배포시 제작자와 사용자간에 소통을 위한 것인 듯 하다. 나같은 경우 이 블로그의 주소를 입력하였다.

입력을 마치면 Access level, Consumer Key, Consumer Secret와 같은 여러 항목들이 보일 것이다. Access Level은 짐작컨데 트위터에 대해 읽을수만 있느냐, 쓰기도 가능하냐에 대한 이야기인 것 같다. Consumer Key와 Consumer Secret의 경우, 어플리케이션에 대한 Public Key - Secret Key의 쌍인 듯 하다. 이 키는 언제든 이 페이지에서 볼 수 있다.

그리고 아래에서 Access를 위한 키를 생성하자. 버튼을 누르면 잠시 뒤 생성된다. 이 키값들을 가지고 API를 실행해 볼 수 있다.

먼저 Idle-2.7을 실행시키자.(3.0 이상은 안되는 것 같았다.)

>>> import twitter
>>> api = twitter.Api(consumer_key="key", consumer_secret="secret", access_token_key="token_key", access_token_secret="token_secret")
>>> list = api.GetPublicTimeline()
>>> for i in range(0, list.__len__()):
    print(i, list[i].GetText())

위와 같이 코드를 입력시키면 sample public time line을 받아볼 수 있을 것이다. 위의 Api 객체 생성을 위한 파라미터는 자신의 등록된 키 값으로 적절히 채워넣자. 위와 같은 코드를 실행시키면


위와 같은 결과를 볼 수 있을 것이다.

역시 환경설정이 가장 어려운 것 같다.
일단 오늘은 여기까지...
Posted by 곰푼
Tips2011. 4. 18. 02:24
현재 우분투에서 SWI-Prolog가 컴파일이 안되는 관계로(XPM 라이브러리 문제라고 한다.) GNU-Prolog를 사용하게 되었다.

헌데 사용하기가 만만치 않다.

일단 gprolog라는 인터프리터를 띄어놓은뒤, 각 함수정의가 되지 않는다. 무조건 에러를 발생시키는 듯....

하지만 내장 함수(?)같은 것들은 잘 동작하는 것 같다.

?- append([a,b], [c,d], X).

X = [a,b,c,d]

yes


이런식으로 나오는 걸 봐서는, 뭔가 다른 방법으로 정의해야하지 않나 싶다.

그래서 메뉴얼을 뒤져 보았다. <메뉴얼 사이트 : http://www.gprolog.org/#manual >

해석해본 결과, 사용자의 코드를 인식하고 인터프리터 내에서 사용하기 위해서는 컴파일이 되어야 하는 듯 하다. 그래서 무작정 인터프리터를 실행시키면, 내장 술어(built-in predicates)를 사용하는 것이다.

사용자 정의 술어를 사용하는 두 가지의 방법을 아래에서 소개하겠다.

1. 컴파일후 실행

뭐 당연하다면 당연할 수 있는데, 컴파일하고 실행하면 잘된다.

FILE NAME : family.pl
parent( mary, jane).
parent( mary, john).
parent(jane, karen).
parent(jane, bill).
parent(john, jim).
sibling(A, B) :- parent(X, A), parent(X, B), A\=B.
grandparent(A, B) :- parent(A, X), parent(X, B).
cousin(A, B) :- sibling(X,Y), parent(X, A), parent(Y, B).
Code : family.pl
위와 같이 코드를 작성하고 다음 명령을 통해 컴파일을 수행하자.

$gplc family.pl

그럼 해당 디렉토리에 family라는 컴파일된 실행파일이 생길 것이다. 그리고 이 파일을

$./family

이 명령어로 실행시키면 gprolog 인터프리터가 뜨게 될 것이다. 이 화면에서 원하는 질의를 수행하면 원하는 결과가 나오는 것을 볼 수 있다.

[foon ~/문서/Private/Prolog]$ ./family
GNU Prolog 1.3.0
By Daniel Diaz
Copyright (C) 1999-2007 Daniel Diaz
| ?- parent(mary, jane).

true ?

yes
| ?-
Figure : 실행화면

2.인터프리터에서 술어 정의

위에서 말했다시피, 사용자 정의 술어는 컴파일되어야 실행할 수 있(는것 같)다. gprolog 쉘에서 다음과 같이 입력하자.

| ?- [user].
compiling user for byte code...

그 뒤 위의 코드작성과 똑같은 원리로 술어를 정의해주면 된다.

근데 해봤더니, 줄 단위로만 작성할 수 있는 듯 했다. 줄넘어가면 수정이 안되는 것 같은데, 뭔가 방법이 있을 듯 하다.

아무튼 이렇게 정의하고 끝날때는 ctrl+d를 입력해서 종료를 알려주면 된다. 그럼 다음과 같이 컴파일 되었음을 알려줄 것이다.

| ?- [user].
compiling user for byte code...
parent(may, jane).
parent(may, john).
parent(jane, karen).
parent(jaen, bill).
parent(john, jim).
sibling(A,B) :- parent(X,A), parent(X,B), A\=B.
grandparent(A,B) :- parent(A,X), parent(X,B).
cousin(A,B):-sibling(X,Y), parent(X,A), parent(Y,B).

user compiled, 9 lines read - 1728 bytes written, 97603 ms

yes
| ?-
Figure2 : 인터프리터 술어 정의

| ?- parent(may, jane).

true ?

yes
| ?- sibling(X,Y).

X = jane
Y = john ?

yes
| ?-
Figure3 : 실행화면

자 일단 이것으로 프롤로그 포스팅은 마친다.

'Tips' 카테고리의 다른 글

안드로이드 부트로더 문제  (0) 2013.10.24
안드로이드 최신버전(>=4.2)에서 USB Debugging 사용하기  (0) 2013.10.24
binutils 크로스 컴파일 방법  (0) 2012.08.10
Python-Twitter  (0) 2011.07.27
A* Search  (0) 2011.04.02
Posted by 곰푼
Tips2011. 4. 2. 11:34
Generic Graph Search 알고리즘은 크게 두 가지로 나눌 수 있습니다.

하나는 LIFO Manner를 이용하는 Depth First Search(DFS), 다음은 FIFO Manner를 이용하는 Best First Search 입니다.

BFS(Best First Search)는 Greedy Algorithm과 연관이 되어 있습니다. 해당 상황에서 가장 그럴싸한 경로를 선택한다는 것이 BFS의 핵심이죠. 이 BFS에 속하는 방법중에 하나가 바로 A* Search입니다. root로부터 현재 노드까지의 거리에, 목표 노드까지 남은 거리를 예측하여 그 값을 더하고 OPEN queue에 삽입합니다. 보통 OPEN queue는 MIN HEAP으로 작성된 Priority queue이기 때문에, 최소 예측 비용을 가진 다음 노드까지의 경로가 queue의 선두에 위치해 있게 됩니다. A* Search는 목적지 노드까지 거리를 예측하는데 어떤 특정한 정보를 사용하기 때문에 Heuristic Search로 분류됩니다.

이 A* search에서 heuristic 값이 항상 0으로 고정된다면 무슨일이 일어날까요? 이를 Uniform Cost Search라고 하는데 보통 queue에 들어간 다음 노드까지의 거리만 가지고 다음 노드를 결정하게 됩니다.

 위의 그림에서 알고리즘은 어떤 경로를 선택하게 될까요? 먼저 루트 노드인 A가 CLOSE list에 삽입되고, 알고리즘은 A의 자식 노드들을 경로 값과 함께 OPEN list에 집어넣게 됩니다. 그 중 최소값을 가진 D가 다음 노드로 선택되고, D의 자식 노드들이 경로값과 합께 OPEN list에 집어 넣어집니다. 그렇게 되면 queue에는 [B:3, C:2, F:4, E:2]의 노드들이 들어있게 됩니다.  이와 같이 동일한 값이 두 개이상 존재할 경우, 알고리즘은 구현자의 구현에 따라 다음 노드를 고르게 됩니다. 가령 C가 먼저 삽입되었기 때문에 C를 선택한다면 queue에는 [B:3, F:5, F:4, E:2]이 들어있게 됩니다. 다음 노드로는 E가 선택되겠죠.
 서로 다른 비용을 가진 노드에 대해서 알고리즘은 최소값을 가진 노드를 선택하게 된다는 것이 이 Uniform Cost Search를 위시한 A* search의 기본 개념입니다. 때문에 Greedy Algorithm과 연관이 되어 있다고 하는 것이기도 합니다.
 A* search에서는 그림에 표기된 경로값 외에도 목표까지의 경로 추정치를 휴리스틱으로 사용하게 됩니다. 경로 추정치가 실제의 거리 값보다 작을 경우 이 A* search는 Admissible하다고 표현합니다.


 만약 Uniform Cost Search에서 다음 노드까지의 경로값까지도 사용하지 않는다면 과연 어떻게 될까요? 이를 Breadth First Search라고 합니다. 많이들 아시는 넓이 우선 탐색이 바로 그것입니다.
Posted by 곰푼