[Android] QAEP (MSM/QSD Android Enablement Project)

QAEP (MSM/QSD Android Enablement Project)
Source: https://www.codeaurora.org/wiki/QAEP#Branch_Releases


-----
Cheers,
June

[CV][IP] DICOM

DICOM (Digital Imaging and Communications in Medicine)

[Link]
* DICOM@OFFIS
http://dicom.offis.de/dcmintro.php.en
* Sample DICOM (.dcm) file
http://filmandpaperdigitizers.com/samples/DICOM/
* Medical Image Samples
http://barre.nom.fr/medical/samples/



-----
Cheers,
June

[Algorithm][AI][Genetic]

AI: Genetic Algorithm

[Link]
* Genetic-Programming by John R. Koza
http://www.genetic-programming.com/johnkoza.html
* Father of the Genetic Programming, John R. Koza (Written in Korean)
http://popsci.hankooki.com/popsci_news/view.php?news1_id=2506&cate=14&page=78&keyword=



-----
Cheers,
June

[Android] Android

Android

* Android Open Source Project
Source: http://android.git.kernel.org/

* Android x86 Project (Porting Android to x86)
Source: http://www.android-x86.org/


* Content Provider
Reference: http://www.devx.com/wireless/Article/41133


{ // CContentProvider Example
http://code.google.com/p/listenmystory/source/browse/

//
// CContentProvider Example
//

#DB: DB_CPtest
#TABLE NAME: info
#TABLE DESCRIPTION:
_id | title | data | data2 (extra)

// Get all of data
Uri allTitles = Uri.parse( "content://com.android.myTest1/db_cptest" );
Cursor c = managedQuery( allTitles, null, null, null, "_id asc" );
if( c.moveToFirst() ) {
do {
//Toast.makeText(this,
// c.getString(c.getColumnIndex(CContentProvider._ID)) + ", " +
// c.getString(c.getColumnIndex(CContentProvider.TITLE)) + ", " +
// c.getString(c.getColumnIndex(CContentProvider.DATA)) + ", " +
// c.getString(c.getColumnIndex(CContentProvider.DATA2)),
//Toast.LENGTH_LONG).show();

String strId = c.getString( c.getColumnIndex(CContentProvider._ID) );
String strTitle = c.getString( c.getColumnIndex(CContentProvider.TITLE) );
String strData = c.getString( c.getColumnIndex(CContentProvider.DATA) );
String strData2 = c.getString( c.getColumnIndex(CContentProvider.DATA2) );
Log.d( TAG, "id = " + strId + ", title = " + strTitle + ", data = " + strData + ", data2 = " + strData2 );
} while( c.moveToNext() );
}

// INSERT
ContentValues values = new ContentValues();
values.put( "title", "title1" );
values.put( "data", "data" );
values.put( "data2", "extra" );
Uri uri = Uri.parse( "content://com.android.myTest1/db_cptest" );
Uri resUri = getContentResolver().insert( uri, values );

// UPDATE #1
ContentValues values = new ContentValues();
values.put( "data", "data" );
Uri uri = Uri.parse( "content://com.android.myTest1/db_cptest/1" );
int resRowCount = getContentResolver().update( uri, values, null, null );
if( resRowCount > 0 )
Log.d( TAG, "Updated [TRUE]" );
else
Log.d( TAG, "Updated [FALSE]" );

// UPDATE #2
ContentValues values = new ContentValues();
values.put( "data", "data" );
Uri uri = Uri.parse( "content://com.android.myTest1/db_cptest" );
String[] strParam = { "title1" };
int resRowCount = getContentResolver().update( uri, values, "title=?", strParam );
if( resRowCount > 0 )
Log.d( TAG, "Updated [TRUE]" );
else
Log.d( TAG, "Updated [FALSE]" );
} // end of CContentProvider Example

// -----------------------------------------------------------



-----
Cheers,
June

[Linux][Memory] User/Kernel Space

--------------------------------------
Q: How does Linux partition logical address space as far as User/Kernel space is concerned, especially when it comes to deciding what gets mapped to virtual versus physical RAM? - Questions
--------------------------------------
Source: http://fixunix.com/questions/14616-how-does-linux-partition-logical-address-space-far-user-kernel-space-concerned-especially-when-comes-deciding-what-gets-mapped-virtual-versus-physical-ram.html

The norm for a memory allocation scheme is to use physical memory before
dumping the overflow to disk. However with Linux it's unique in that
there's a set limit for user and kernel space (aka monolithic kernel).
Which leads me to believe that the logical address space is set aside
ahead of time. Meaning that if a person has 2GBs of physical RAM and
chooses option 3GBs/1GBS of user/kernel space, that either 1GB of kernel
space and 1GB of user space will be allocated to physical RAM; OR, 2 GBs
of user space will go to physical RAM while the remaining 2 GBs (1 user,
the other kernel) will be virtual. This seems rather asinine, so I
hardly believe this is how it works.

It was also proposed to me that the system only considers how much it -
will- give to either user or kernel space. Meaning that at boot up, if a
system only uses 2 MBs of Kernel space, only 2 MBs gets mapped from the
the total available memory for Kernel space (as there's a cap). Also
meaning that those first 2 MBs would be allocated to physical memory.
Then as more would be requested more would be allocated for either user
or kernel space, straight from physical memory, till it ran out. This
sounds like a more solid schema, but at the same time it seems silly to
do things on a first come, first serve basis. It seems more reasonable
that it would partition each application such that each has some
physical memory to work in, and then to use a memory map for anything
additional to disk.

So the question is, how does Linux delegate it's memory with regards to
user/kernel space? Does Linux treat User/Kernel space just as a hard
limit, allocating memory as it's needed until it hits the cap for a
particular "type" of memory? Or does it preordain that kernel space will
be in physical memory while user space will get the remainder, whether
it be physical or not? Is there possibly another partitioning scheme,
similar to the one I suggested above?

I'm beginning to believe it's a simple tallying scheme, checking to see
how much kernel space or user space has been allocated.

ie/
3GB/1GB of User/Kernel space is available.
2 MBs gets allocated at boot-time for the kernel and it's modules -
(1.000GBs-0.002GBs=NewAvailableKernelSpace)
50 MBs gets allocated to X in user space - (3.000GBs-
0.050GBs=NewAvailableUserSpace)
So on and so forth.

I imagine that the logical address space is just a series of pointers
telling the system where everything is. For example, the first logical
address might point to physical memory for kernel space, while the
second logical address unit might point to user space in virtual memory
(similar to the example above). I imagine that's the whole value of
logical address space - it provides the HAL.

Any reference material or solid answers surrounding the mysteries of
Linux's memory allocation would be appreciated.

Thanks,
Dustin
--------------------------------------

--------------------------------------
Q: Virtual memory - user space kernel space
--------------------------------------
Source: http://fixunix.com/linux/7872-virtual-memory-user-space-kernel-space.html

Hi,
I m having some questions in Linux memory management.
I m considering about 32 bit machine only.
If you have a 512 MB of memory, how it is divided between kernel space
and user space?

What is the link between this division and 3GB userspace and 1 GB
kernel space division.
Is the 3G/1G division is for virtual memory?
Is the total Virtual memory can be 4G only? I mean is it the maximum?

Thanks in advance.

regards
SaranJothy

Re: Virtual memory - user space kernel space
SaranJothy wrote:
> Hi,
> I m having some questions in Linux memory management.
> I m considering about 32 bit machine only.
> If you have a 512 MB of memory, how it is divided between kernel space
> and user space?

A (relatively) small part is statically allocated to hold the kernel 
code and static data. The rest is dynamically allocated to whatever is 
required (user, drivers, kernel, ...)

> What is the link between this division and 3GB userspace and 1 GB
> kernel space division.

None.

> Is the 3G/1G division is for virtual memory?

Yes.

> Is the total Virtual memory can be 4G only? I mean is it the maximum?

In 32 bit Linux: yes, you cannot address more than 4GB of virtual 
addresses with 32 bit pointers.

-- 
Josef Möllers (Pinguinpfleger bei FSC)
If failure had no penalty success would not be a prize
-- T. Pratchett


Re: Virtual memory - user space kernel space
On Feb 8, 1:45 pm, "SaranJothy" wrote:
> Hi,
> I m having some questions in Linux memory management.
> I m considering about 32 bit machine only.
> If you have a 512 MB of memory, how it is divided between kernel space
> and user space?

you bumble virtual and physical memory. kernel divides _only_ virtual
memory between kernel space and user space,
physical memory are share to both. so, if for example, I want to
allocate n mb from user space, i can get some virtual address p
associated with physical page g.
and if i after it will try to allocate n mb from kernel space i can
get some virtual address i, associated with the same physical page g.
it's normal.

>
> What is the link between this division and 3GB userspace and 1 GB
> kernel space division.
> Is the 3G/1G division is for virtual memory?

yep

> Is the total Virtual memory can be 4G only? I mean is it the maximum?
>

nope. intel, for example, support PAE feature, that performs 64G
virtual space.

> Thanks in advance.
>
> regards
> SaranJothy


Re: Virtual memory - user space kernel space
Thanks for the reply.
As said,
> A (relatively) small part is statically allocated to hold the kernel
> code and static data. The rest is dynamically allocated to whatever is
> required (user, drivers, kernel, ...)
So, It depends upon the total size of kernel code and static data.
Right?

I read like 1G is allocated for kernel and 3G is allocated for
userspace in Virtual memory.
So part of RAM is mapped to 1G Kernel space address.
If part of RAM where kernel resides is smaller(as in most cases) than
1G, how it is mapped to 1G?

how 3G /1G break is maintained for secondary storage having just
2 G of memory?

I m having some problems in co-relating Physical memory and VM. pls.,
correct me.

Regards,
Saran


Re: Virtual memory - user space kernel space
Hi,
Thanks for the replies.
As said,
> A (relatively) small part is statically allocated to hold the kernel
> code and static data. The rest is dynamically allocated to whatever is
> required (user, drivers, kernel, ...)

So, It depends upon the total size of kernel code and static data.
Right?


1G/3G division in virutal memory is nothing but a set of pointers to
have VM management.
Set of pointers for Kernel. -1G
Set of pointers for User space - 3G
Kernel space pointers are special such that they have direct mapping
to Physical memory.
User space pointers has to go via MMU to get the location in physical
memory. Just correct me with the above understanding?


The process (User space) memory is swapped in and out to Secondary
storage to meet memory requirements of new process required to
execute.
What happens when we dont have enough Secondary storage.
say we have 2G RAM and 1.5G application is currently running.(I hope
this is possible) We have 1G of secondary storage only.
Now a 1.5G application wants to run.
(How the currently executing 1.5G application gets swapped out?

My intention of qn. is what happens when we dont have enough Secondary
memory.

Thanks for your replies,
Saran

Re: Virtual memory - user space kernel space
"just.asgard" wrote in
news:1170938227.135204.298340@p10g2000cwp.googlegr oups.com:

>> Is the total Virtual memory can be 4G only? I mean is it the maximum?
>>
>
> nope. intel, for example, support PAE feature, that performs 64G
> virtual space.

This is incorrect. PAE provides 64G of _physical_ address space. It
doesn't change the 4GB of virtual address space. You still only have 32-
bit registers.

GH

Re: Virtual memory - user space kernel space
SaranJothy wrote:
> Thanks for the reply.
> As said,
> 
>>A (relatively) small part is statically allocated to hold the kernel
>>code and static data. The rest is dynamically allocated to whatever is
>>required (user, drivers, kernel, ...)
>
> So, It depends upon the total size of kernel code and static data.
> Right?

Yes.

In the old days, all physical memory was mapped 1:1 to virtual addresses 
0xc0000000 upwards, so the kernel could access everything directly. If 
you had more than 1GB of physical memory, you could recompile the kernel 
to start at 0x80000000 or even (correct me if I'm wrong) 0x40000000, to 
accomodate up to 2 or 3 GB of physical memory.
Later, Hugemem and friends were introduced and you could have more than 
1GB of physical memory.

> I read like 1G is allocated for kernel and 3G is allocated for
> userspace in Virtual memory.
> So part of RAM is mapped to 1G Kernel space address.

Yes, the part which holds the kernel code and static data is mapped to 
the 1G kernel address space. Dynamically allocated kernel memory is also 
mapped to the space. Other pages (user pages, buffers, ...) can be 
mapped on demand.

> If part of RAM where kernel resides is smaller(as in most cases) than
> 1G, how it is mapped to 1G?

In general, there is no distinction between less than 1GB and more than 
1GB of physical memory.

> how 3G /1G break is maintained for secondary storage having just
> 2 G of memory?

??? "secondary storage" ???
You mean swap space? Linux uses swap space in addition to physical 
memory, so having 1GB of physical memory and 2GB of swap space would 
allow you to use 3GB of virtual memory, distributed amongst the kernel 
(a relatively small portion, locked to physical memory) and user processes.

> I m having some problems in co-relating Physical memory and VM. pls.,
> correct me.

Try to find a decent book on virtual memory.

An attempt of a very short explanation:
virtual memory is subdivided into "page frames", in ia32 these are 4KB.
Likewise, physical memory is subdivided into "pages", again 4KB in size.
There is a piece of hardware, the Memory Management Unit (MMU) which 
takes a virtual address coming out of the CPU and replaces this by a 
physical address, in the simplest case by a table-lookup: The upper 20 
bits (the page frame number) of a 32-bit virtual address selects one of 
the 1048576 slots in the table. This slot contains a bit "valid" and the 
upper 20 bits (the page number) of the physical address. If the "valid" 
bit is 0, then this virtual address is invalid and the access is aborted 
(SIGSEGV). If the "valid" bit is 1, the 20 bits "page frame number" is 
replaced by the 20 bits "page number",keeping the lower 12 bits of the 
(virtual) address. That 32 bit value is then used as the physical address.
When switching between processes, the kernel has to replace the low 
786432 entries in this table by the low 786432 entries of the new 
process' table. Also, you need two tables: one for kernel and one for 
the currently active user process, the kernel's low 786432 entries are 
identical to the user process' low 786432 entries. The upper 262144 of a 
user process' table _always_ have the "valid" bit cleared.

Does this help?

Josef
-- 
Josef Möllers (Pinguinpfleger bei FSC)
If failure had no penalty success would not be a prize
-- T. Pratchett

Re: Virtual memory - user space kernel space
SaranJothy wrote:

> Thanks for the reply.
> As said,
>> A (relatively) small part is statically allocated to hold the kernel
>> code and static data. The rest is dynamically allocated to whatever is
>> required (user, drivers, kernel, ...)
> So, It depends upon the total size of kernel code and static data.
> Right?
>
> I read like 1G is allocated for kernel and 3G is allocated for
> userspace in Virtual memory.
> So part of RAM is mapped to 1G Kernel space address.

If you have less than 1G of physical RAM, *all* physical RAM
is mapped into the top 1G kernel space.

The key is to understand that you can have more than one
virtual mapping for a physical RAM page. So, when userspace
requires a memory page, one of the already mapped (but unused)
pages in kernel space gets mapped into userspace as well.

> If part of RAM where kernel resides is smaller(as in most cases) than
> 1G, how it is mapped to 1G?

The kernel is typically loaded at the beginning of the physical RAM.
This, like all other RAM is then mapped to start at the 3GB boundary.

There is one exception - If you have 1GB or more of physical RAM,
the RAM which cannot be mapped into the top 1GB, gets managed as
high memory and only mapped on request.

>
> how 3G /1G break is maintained for secondary storage having just
> 2 G of memory?

It's unrelated. Of course, if you want to memory map a file, you
have to stay below the free virtual space.

Regards,

Iwo

Re: Virtual memory - user space kernel space
On Thu, 08 Feb 2007 14:06:26 +0000 Iwo Mergler wrote:

| The key is to understand that you can have more than one
| virtual mapping for a physical RAM page. So, when userspace
| requires a memory page, one of the already mapped (but unused)
| pages in kernel space gets mapped into userspace as well.

That's a feature used by VRB to make a ring buffer (provided the size
is an exact multiple of page size) that automatically wraps around
by having a mirror image mapping of the entire buffer immediately
following the first mapping in VM. That allows direct access via
tools that don't understand the ring buffer wraparound (e.g. strXXX
functions in stdlib or others) while avoiding any copy activities
to maintain both the data and empty space as contiguous areas.

See: http://vrb.slashusr.org/
--------------------------------------

-----
Cheers,
June

[Linux][Memory] 리눅스 메모리 모델 (한글)

리눅스 메모리 모델 (한글)
Source: http://www.ibm.com/developerworks/kr/library/l-memmod/

Vikram Shukla, Software Engineer, EMC

요약: 메모리가 어떻게 구현되고 관리되는지를 배워보자. 세그먼트 제어 단위와 페이징 모델 그리고 물리적 메모리 영역을 자세하게 설명한다.

리눅스 디자인과 구현을 이해하는 첫 번째 단계는 리눅스에서 사용되는 메모리 모델을 이해하는 것이다. 리눅스 메모리 모델과 관리는 매우 중요하다.

리눅스는 슈퍼바이저 모드에서 실행되는 여러 모듈에서 프로세스 관리, 동시성, 메모리 관리 같은 운영 체계 서비스를 구현하기 위해 프리머티브 또는 시스템 호출을 정의하는 방식을 사용한다. 리눅스는 호환성을 위해 상징적 표시로서 세그먼트 제어 단위 모델(segment control unit model)을 관리하더라도 작은 레벨에서는 이 모델을 사용한다.

다음은 메모리 관리와 관련된 문제이다.

• 가상 메모리 관리, 애플리케이션 메모리 요청과 물리적 메모리간 논리적 레이어
• 물리적 메모리 관리
• 커널 가상 메모리 관리/커널 메모리 할당자, 메모리에 대한 요청을 만족시키는 컴포넌트. 요청은 커널 내에서 또는 사용자로부터 온다.
• 가상 주소 공간 관리
• 스와핑과 캐싱

이 글에서 운영 체계 내에서의 메모리 관리를 중심으로 설명하겠다.

• 일반적인 세그먼트 제어 단위 모델과 리눅스의 세그먼트 제어 단위 모델
• 일반적인 페이징 모델과 리눅스의 페이징 모델
• 물리적 메모리 영역 상세

리눅스 커널에서 메모리가 어떻게 관리되는지를 상세히 설명하지는 않겠다. 하지만 전체 메모리 모델에 대한 정보와 이것이 어드레싱 되는 방식을 이해하는 것으로도 충분히 도움이 된다. x86 아키텍처에 초점을 맞추지만 다른 하드웨어 구현에도 적용할 수 있다.

x86 메모리 아키텍처

x86 아키텍처에서 메모리는 세 가지 종류의 어드레스로 나뉜다.

• 논리적 어드레스(logical address)는 물리적 위치와 직접적인 관련이 있거나 또는 관련이 없는 스토리지 위치 어드레스이다. 논리적 어드레스는 컨트롤러에서 정보를 요청할 때 사용된다.
• 리니어 어드레스(linear address)(플랫 어드레스 공간(flat address space))은 0으로 시작하여 어드레싱 되는 메모리이다. 각각의 후속 바이트는 다음 순서의 번호(0, 1, 2, 3) 순서대로 배열된다. 이것은 대부분의 비 Intel CPU가 메모리에 어드레스 하는 방식이다. Intel® 아키텍처는 분할된 어드레스 공간을 사용한다. 메모리는 64KB 세그먼트로 나뉘고 세그먼트 레지스터는 언제나 현재 어드레싱 되는 기본 세그먼트를 가리킨다. 이 아키텍처의 32-bit 모드는 플랫 어드레스 공간으로 간주되지만 이 역시 세그먼트들을 사용한다.
• 물리적 어드레스(physical address)는 물리적 어드레스 버스에 비트로 나타나는 어드레스이다. 물리적 어드레스는 논리적 어드레스와는 다르다. 메모리 관리 단위는 논리적 어드레스를 물리적 어드레스로 변환한다.

CPU는 두 개의 단위를 사용하여 논리적 어드레스를 물리적 어드레스로 변형한다. 하나는 분할된 단위(segmented unit)이고 다른 하나는 페이징 단위(paging unit)이다.

그림 1. 두 개의 단위가 어드레스 공간을 변환한다.

세그먼트 제어 단위 모델부터 보자.

위로

일반적인 세그먼트 제어 단위 모델

세그멘테이션 모델의 기본적인 개념은 메모리가 세그먼트 세트를 사용하여 관리된다는 것이다. 기본적으로 각 세그먼트는 자신의 어드레스 공간이다. 세그먼트는 두 개의 컴포넌트들로 구성된다.

• 물리적 메모리 위치의 어드레스를 포함하고 있는 베이스 어드레스(base address)
• 세그먼트의 길이를 지정하는 길이 값(length value)

세그멘티드 어드레스는 또한 두 개의 컴포넌트들로 구성된다. 세그먼트 셀렉터(segment selector)와 오프셋(offset)이다. 세그먼트 셀렉터는 사용할 세그먼트(베이스 어드레스와 길이 값)를 지정하는 반면 오프셋 컴포넌트는 실제 메모리 액세스를 위한 베이스 어드레스에서 오프셋을 지정한다. 실제 메모리 위치의 물리적 어드레스는 이 오프셋과 베이스 어드레스 값의 합이다. 오프셋이 세그먼트의 길이를 초과하면 시스템은 보호 위반을 생성한다.

요약하면,

Segmented Unit is represented as -> Segment: Offset model can also be represented as -> Segment Identifier: Offset

각 세그먼트는 세그먼트 식별자(segment identifier) 또는 세그먼트 셀렉터(segment selector)라고 하는 16-bit 필드이다. x86 하드웨어는 세그먼트 셀렉터들을 보유하고 있는 세그먼트 레지스터(segment registers)라고 하는 프로그래밍 가능한 레지스터들로 구성된다. 이러한 레지스터들은 cs (코드 세그먼트), ds (데이터 세그먼트), ss (스택 세그먼트)이다. 각 세그먼트 식별자는 64-bit (8 바이트) 세그먼트 디스크립터(segment descriptor)에 의해 표현되는 세그먼트를 구분한다. 세그먼트 디스크립터는 GDT(글로벌 디스크립터 테이블)에 저장되고 LDT(로컬 디스크립터 테이블)에 저장될 수도 있다.

그림 2. 세그먼트 디스크립터와 세그먼트 레지스터들의 상호작용

세그먼트 셀렉터가 세그먼트 레지스터에 로딩될 때 마다 이에 상응하는 세그먼트 디스크립터는 매칭하는 비 프로그래밍의 CPU 레지스터로 로딩된다. 각 세그먼트 디스크립터는 8 바이트 길이이며 메모리에 하나의 세그먼트를 나타낸다. 이들은 LDT나 GDT에 저장된다. 세그먼트 디스크립터 엔트리에는 제휴된 세그먼트에 있는 첫 번째 바이트에 대한 포인터가 포함된다. 이들은 메모리에 있는 세그먼트의 크기를 나타내는 베이스 필드와 20-bit 값(제한 필드)로 나타난다.

다른 여러 필드들에는 권한 레벨과 세그먼트 유형 (cs 또는 ds) 같은 특별한 애트리뷰트가 포함된다. 세그먼트 유형은 4-bit Type 필드로 나타난다.

우리는 비 프로그래밍 레지스터를 사용하기 때문에 GDT와 LDT는 참조되지 않지만, 논리적 어드레스에서 리니어 어드레스로의 변환이 수행된다. 메모리 변환의 속도가 빨라진다.

세그먼트 셀렉터에는 다음이 포함되어 있다.

• 13-비트 인덱스: GDT나 LDT에 있는 상응하는 세그먼트 디스크립터 엔트리를 구분한다.
• TI(테이블 인디케이터) 플래그: 값이 0이면 세그먼트 디스크립터가 GDT에 포함되어 있는 것이고, 값이 1 이면 세그먼트 디스크립터는 LDT에 포함된 것이다.
• RPL(요청 권한 레벨): 상응하는 세그먼트 셀렉터가 세그먼트 레지스터에 로딩될 때 현재 CPU 권한 레벨을 정의한다.

세그먼트 디스크립터 길이가 8 바이트이기 때문에 GDT나 LDT 내에 있는 상대적 어드레스는 13 비트의 세그먼트 셀렉터를 8로 곱하면 나온다. 예를 들어, GDT가 0x00020000 어드레스에 저장되어 있고 세그먼트 셀렉터에서 지정된 인덱스가 2이면 상응하는 디스크립터의 어드레스는 (2*8) + 0x00020000이다. GDT에 저장될 수 있는 총 세그먼트 디스크립터는 (2^13 - 1)이다. 즉, 8191 이다.

그림 3은 논리적 어드레스에서 리니어 어드레스를 획득하는 것을 표현한 것이다.

그림 3. 논리적 어드레스에서 리니어 어드레스를 획득하기 

그렇다면 리눅스에서는 어떻게 다른가?

위로

리눅스의 세그먼트 제어 단위

리눅스에서 이 모델은 약간 변화된다. 리눅스는 제한된 방식으로 세그멘테이션 모델을 사용한다고 언급한 바 있다. (대게, 호환성 때문이다.)

리눅스에서, 모든 세그먼트 레지스터들은 같은 범위의 세그먼트 어드레스들을 가리킨다. 다시 말해서, 각각 같은 리니어 어드레스 세트를 사용한다. 리눅스에서는 제한된 세그먼트 디스크립터를 사용하기 때문에 모든 디스크립터들은 GDT에 저장된다. 이 모델은 두 가지 장점이 있다.

• 모든 프로세스가 같은 세그먼트 레지스터 값을 사용할 때(이들이 같은 리니어 어드레스 세트를 공유할 때) 메모리 관리는 더욱 간단해 진다.
• 대부분의 아키텍처로 이식 가능하다. 여러 RISC 프로세서들도 제한된 방식으로 세그멘테이션을 지원한다.

그림 4는 변화된 모습을 그려본 것이다.

그림 4. 리눅스에서는, 세그먼트 레지스터들이 같은 어드레스 세트를 가리킨다. 

세그먼트 디스크립터

리눅스는 다음과 같은 세그먼트 디스크립터를 사용한다.

• 커널 코드 세그먼트
• 커널 데이터 세그먼트
• 사용자 코드 세그먼트
• 사용자 데이터 세그먼트
• TSS 세그먼트
• 디폴트 LDT 세그먼트

자세하게 살펴보자.

GDT의 커널 코드 세그먼트 디스크립터(kernel code segment)는 다음의 값을 갖고 있다.

• Base = 0x00000000
• Limit = 0xffffffff (2^32 -1) = 4GB
• G (세분성 플래그) = 1 : 페이지로 나타나는 세그먼트 크기
• S = 1 : 일반 코드나 데이터 세그먼트
• Type = 0xa : 읽히거나 실행될 수 있는 코드 세그먼트
• DPL value = 0 : 커널 모드

이 세그먼트와 제휴된 리니어 어드레스는 4GB이다. S =1과 type = 0xa는 코드 세그먼트이다. 이 셀렉터는 cs 레지스터에 있다. 리눅스에서 세그먼트 셀렉터가 액세스 되는 매크로는 _KERNEL_CS 매크로이다.

커널 데이터 세그먼트(kernel data segment) 디스크립터는 값이 2로 설정된 Type 파일을 제외하고는 커널 코드 세그먼트와 같은 값을 갖고 있다. 세그먼트는 데이터 세그먼트이고 셀렉터는 ds 레지스터에 저장된다. 리눅스에서 세그먼트 셀렉터가 액세스 되는 매크로는_KERNEL_DS 매크로이다.

사용자 코드 세그먼트(user code segment)는 사용자 모드의 모든 프로세스들에 의해 공유된다. GDT에 저장된 상응하는 세그먼트 디스크립터 값은 다음과 같다.

• Base = 0x00000000
• Limit = 0xffffffff
• G = 1
• S = 1
• Type = 0xa :읽히거나 실행될 수 있는 코드 세그먼트
• DPL = 3 : 사용자 모드

리눅스에서 세그먼트 셀렉터에 액세스 하기 위해 사용되는 매크로는 _USER_CS 매크로이다.

사용자 데이터 세그먼트 디스크립터(user data segment)에서 변화된 유일한 필드는 2로 설정되고 읽히고 작성될 수 있는 데이터 세그먼트를 정의하는 Type이다. 세그먼트 셀렉터에 액세스 하기 위해 리눅스에서 사용되는 매크로는 _USER_CS 매크로이다.

이러한 세그먼트 디스크립터 외에도 GDT에는 생성된 각 프로세스를 위한 세그먼트 디스크립터가 두 개 더 있다. 바로 TSS와 LDT 세그먼트이다.

TSS 세그먼트 디스크립터는 다양한 프로세스를 의미한다. TSS에는 각 CPU에 대한 하드웨어 컨텍스트 정보가 포함되어 있다. 이는 컨텍스트 변환에 쓰인다. 예를 들어, U->K 모드 변환 시, x86 CPU는 TSS에서 커널 모드 스택의 어드레스를 얻는다.

각 프로세스는 GDT에 저장된 상응하는 프로세스에 대한 고유의 TSS 디스크립터를 갖고 있다. 다음은 디스크립터의 값이다.

• Base = &tss (상응하는 프로세스 디스크립터의 TSS 필드의 어드레스; 예를 들어, &tss_struct) 이것은 리눅스 커널의 schedule.h 파일에서 정의된다.
• Limit = 0xeb (TSS 세그먼트는 236 바이트이다.)
• Type = 9 또는 11
• DPL = 0. 사용자 모드는 TSS에 액세스 하지 않는다. G 플래그는 제거된다.

모든 프로세스들은 디폴트 LDT 세그먼트(default LDT segment)를 공유한다. 기본적으로, 무효 세그먼트 디스크립터가 포함되어 있다. 디폴트 LDT 세그먼트 디스크립터는 GDT에 저장된다. 리눅스에 의해 생성된 LDT의 크기는 24 바이트이다. 기본적으로 세 가지 엔트리는 언제나 존재한다.

LDT[0] = null LDT[1] = user code segment LDT[2] = user data/stack segment descriptor

TASKS 계산

GDT에서 허용 가능한 최대 엔트리를 계산하기 위해서는 NR_TASKS (리눅스가 지원하는 동시 프로세스의 수를 결정하는 변수 - 커널 소스에서 디폴트 값은 512이다. 이는 하나의 인스턴스에 최대 256 동시 연결이 가능한 값이다.)를 이해해야 한다.

GDT에서 허용되는 총 엔트리 수는 다음 식으로 결정된다.

Number of entries in GDT = 12 + 2 * NR_TASKS. As mentioned earlier GDT can have entries = 2^13 -1 = 8192.

8192 세그먼트 디스크립터 중에서, 리눅스는 6 개의 세그먼트 디스크립터, 4 개의 추가 디스크립터(APM용-고급 전원 관리 기능), 4 개의 엔트리를 GDT에서 사용하고 나머지는 사용되지 않는다. 따라서 GDT에서 가능한 엔트리의 수는 8192 - 14 또는 8180 이다.

GDT에서는 8180 개의 엔트리 이상을 가질 수 없다. 따라서,

2 * NR_TASKS = 8180
NR_TASKS = 8180/2 = 4090

(왜 2 * NR_TASKS인가? 생성되는 각 프로세스의 경우, TSS 디스크립터(컨텍스트 변환 컨텍스트에 사용됨)가 로딩 될 뿐만 아니라 LDT 디스크립터도 로딩된다.)

x86 아키텍처에서 프로세스 수의 제한은 Linux 2.2의 컴포넌트였지만, 2.4 이후 이 문제가 해결되었다. 하드웨어 컨텍스트 변환(이것이 TSS의 사용을 불가피하게 만들었다.)을 수행하고 이것을 프로세스 변환으로 대체했기 때문이다.

이제 페이징 모델(paging model)에 대해 살펴보자.

위로

일반적인 페이징 모델

페이징 단위는 리니어 어드레스를 물리적 어드레스로 변환한다.(그림 1) 리니어 어드레스들은 한데 묶여 페이지들을 형성한다. 이러한 리니어 어드레스들은 근본적으로 연속적이다. 페이징 단위는 이러한 연속적인 메모리를 페이지 프레임(page frames)이라고 하는 상응하는 연속적인 물리적 어드레스로 매핑한다. 페이징 단위는 램을 시각화 하여 고정된 크기의 페이지 프레임으로 나눈다.

페이징에는 다음과 같은 장점이 있다.

• 페이지에 정의된 액세스 권한은 페이지를 구성하는 리니어 어드레스 그룹에 좋다.
• 페이지의 길이는 페이지 프레임 길이와 같다.

페이지들을 페이지 프레임에 매핑하는 데이터 구조를 page table이라고 한다. Page Table들은 주 메모리에 저장되고 페이징 단위를 실행하기 전에 커널에 의해 초기화 된다.

그림 5. Page Table이 페이지들을 페이지 프레임으로 매핑한다. 

Page1에 포함된 어드레스 세트는 Page Frame1에 포함된 상응하는 어드레스 세트와 매칭된다.

리눅스는 세그멘테이션 단위 보다는 페이징 단위를 사용한다. 이전 섹션에서 보았던 것 처럼, 각 세그먼트 디스크립터는 리니어 어드레싱에 같은 어드레스 세트를 사용하기 때문에 논리적 어드레스를 리니어 어드레스로 변환 할 세그멘테이션 단위를 사용할 필요가 적어진다. 세그멘테이션 단위 대신 페이징 단위를 사용함으로서 리눅스는 메모리 관리와 다른 하드웨어 플랫폼들간 이식성 까지 활용할 수 있다.

페이징에 사용되는 필드

다음은 x86 아키텍처에서 페이징을 지정하는데 사용되는 필드의 디스크립션이다. 페이징 단위는 세그멘테이션 단위의 아웃풋으로서 리니어 어드레스에 들어간다. 이들은 나중에 다음 필드로 나뉜다.

• 디렉토리(Directory)는 10 MSB이다. (Most Significant Bit는 가장 큰 값을 가진 바이너리 숫자에 있는 비트 위치이다- MSB는 맨 왼쪽 비트라고도 한다.)
• 테이블(Table)은 중간 10 비트이다.
• 오프셋(Offset)은 12 LSB이다. (Least Significant Bit는 짝수인지 홀수인지를 결정하는 단위 값을 주는 바이너리 정수에 있는 비트 위치이다. LSB는 맨 우측 비트라고도 한다. 맨 오른쪽에 있다.)

리니어 어드레스를 상응하는 물리적 위치로 변환하기 위해서는 두 단계 프로세스가 필요하다. 첫 번째 단계에서는 Page Directory(Page Directory에서 Page Table 까지)라는 변환 테이블을 사용하고, 두 번째 단계에서는 Page Table이라고 하는 변환 테이블을 사용한다. (이것은 필요한 페이지 프레임에 대한 Page Table과 Offset이다.) (그림 6)

그림 6. 페이징 필드

Page Directory의 물리적 어드레스는 cr3 레지스터로 로딩된다. 리니어 어드레스 내의 디렉토리 필드는 알맞은 Page Table을 가리키는 Page Directory의 엔트리를 결정한다. 테이블 필드의 어드레스는 페이지를 포함하고 있는 페이지 프레임의 물리적 어드레스를 포함하고 있는 Page Table의 엔트리를 결정한다. 오프셋 필드는 페이지 프레임 내의 상대적 위치를 결정한다. 이 오프셋 길이는 12 비트이기 때문에 각 페이지에는 4 KB 데이터가 포함된다.

물리적 어드레스 계산을 요약해 보면,

1. cr3 + Page Directory (10 MSBs) = table_base
2. table_base + Page Table (10 intermediate bits) = page_base
3. page_base + Offset = 물리적 어드레스 (페이지 프레임)

Page Directory와 Page Table의 길이는 10 비트이기 때문에 가능한 어드레스 한계는 1024*1024 KB이고 Offset은 2^12 (4096 bytes)까지 어드레싱 할 수 있다. 따라서 Page Directory의 어드레싱 한계는 1024*1024*4096 (4 GB의 2^32 메모리 셀과 같음)이다. 따라서 x86 아키텍처에서 총 어드레스 한계는 4 GB이다.

확장 페이징

확장 페이징은 Page Table 변환 테이블을 제거할 때 얻을 수 있다. 리니어 어드레스의 분할은 Page Directory(10 MSB)와 Offset(22 LSB) 사이에 수행된다.

22 LSB는 페이지 프레임(2^22)에 4MB의 영역을 형성한다. 확장 페이징은 일반 페이징과 공존하고 큰 연속 리니어 어드레스를 상응하는 물리적 어드레스로 매핑할 때 사용된다. 운영 체계는 Page Table을 제거하고 확장 페이징을 제공한다. 이는 PSE(페이지 크기 확장) 플래그를 설정함으로서 실행된다.

36-bit PSE는 36-bit 물리적 어드레스 지원을 4 MB 페이지로 확장하면서 4 바이트 페이지-디렉토리 엔트리를 관리하고, 운영 체계에 주요한 디자인 변경을 요구하지 않고 4GB 이상의 물리적 메모리에 어드레스 하는 메커니즘을 제공한다. 이러한 방식은 수요 페이징과 관련하여 실질적인 한계를 지니고 있다.

위로

리눅스의 페이징 모델

리눅스의 페이징은 일반 페이징과 비슷하다. 하지만 x86 아키텍처에는 세 가지 레벨의 페이지 테이블 메커니즘이 도입되었다.

• Page Global Directory (pgd): 멀티 레벨 페이지 테이블에서 추상화 된 탑 레벨. 페이지 테이블의 각 레벨은 다른 크기의 메모리를 관리한다. 이 글로벌 디렉토리는 4MB 크기의 영역을 관리한다. 각 엔트리는 보다 작은 디렉토리의 작은 테이블에 대한 포인터가 되기 때문에 pgd는 페이지 테이블의 디렉토리이다. 코드가 이 구조를 트래버스하는 것을 페이지 테이블을 "걷는다(walk)"라고 표현한다.
• Page Middle Directory (pmd): 페이지 테이블의 중간 레벨. x86 아키텍처에서 pmd는 하드웨어에는 없지만 커널 코드에서 pgd에 포함된다.
• Page Table Entry (pte): 페이지에서 직접 다루어 지는 하위 레벨(PAGE_SIZE 찾기) 페이지의 물리적 어드레스와 엔트리가 유효하고 관련 페이지들이 실제 메모리에 존재한다는 것을 나타내는 관련 비트를 포함하고 있는 값이다.

세 레벨의 페이징 스킴은 리눅스에서 큰 메모리 영역을 지원한다. 큰 메모리 영역 지원이 필요하지 않을 경우 pmd를 "1"로 정의하여 2 레벨 페이징으로 좁힐 수 있다.

이 레벨은 컴파일 시 최적화 되어 제 2 레벨과 제 3 레벨을 실행한다. 중간 디렉토리를 실행하거나 실행 불가로 하면 된다. 32-bit 프로세서는 pmd 페이징을 사용하고 64-bit 프로세서는 pgd 페이징을 사용한다.

그림 7. 페이징의 세 레벨 

64-bit 프로세서에서,

• 21 MSB는 사용되지 않는다.
• 13 LSB는 페이지 오프셋에 의해 표현된다.
• 남은 30 bit는,
  
  • Page Table 당 10 bit
  • Page Global Directory 당 10 bit
  • Page Middle Directory 당 10 bit

실제로 43 비트가 어드레싱에 사용된다. 따라서 64-bit 프로세서에서는 사용할 수 있는 가상 메모리는 2이다.

각 프로세스는 고유의 페이지 디렉토리와 페이지 테이블을 갖고 있다. 실제 사용자 데이터를 포함하고 있는 페이지 프레임을 참조하기 위해 운영 체계는 (x86 아키텍처에서) pgd를 cr3 레지스터에 로딩함으로서 시작된다. 리눅스는 TSS 세그먼트에서 cr3 레지스터의 컨텐트를 저장하고, 새로운 프로세스가 CPU에서 실행될 때 마다 TSS 세그먼트에서 또 다른 값을 cr3 레지스터에 로딩한다. 결과적으로 페이징 단위가 정확한 페이지 테이블 세트를 참조하게 된다.

pgd 테이블로 가는 각 엔트리는 pmd 엔트리의 어레이를 포함하고 있는 페이지 프레임을 가리킨다. pmd 엔트리는 pte를 포함하고 있는 페이지 프레임을 가리킨다. pte는 사용자 데이터를 포함하고 있는 페이지 프레임을 가리킨다. 검색된 페이지들이 교체되면 스왑 엔트리가 pte 테이블에 저장된다. 이 테이블은 메모리에 재 로드 되기 위해 페이지 프레임을 찾는데 사용된 것이다.

그림 8은 각 페이지 테이블 레벨에서 오프셋을 상응하는 페이지 프레임 엔트리로 추가하고 있는 모습이다. 세그멘테이션 단위로부터 아웃풋으로 받은 리니어 어드레스들을 나누어서 오프셋들을 얻는다. 각 페이지 테이블 컴포넌트에 상응하는 리니어 어드레스를 나누기 위해 다양한 매크로들이 커널에서 사용된다. 리니어 어드레스가 나뉜 모습을 보자.

그림 8. 어드레스가 다양한 어드레스 길이를 가진다. 

페이지 프레임 보유

리눅스는 커널 코드와 데이터 구조를 위해 페이지 프레임을 보유한다. 이 페이지들은 디스크에 절대 교체되지 않는다. 0x0에서 0xc0000000((PAGE_OFFSET)까지의 리니어 어드레스는 사용자 코드와 커널 코드에 의해 참조된다. (PAGE_OFFSET부터 0xffffffff 까지 커널 코드에 의해 어드레스 된다.)

4GB 중에서, 단 3GB만 사용자 애플리케이션에 사용할 수 있다는 의미이다.

페이징 실행 방법

리눅스 프로세스에 의해 사용되는 페이징 메커니즘은 두 단계로 설정된다.

• 부트스트랩 시, 시스템은 페이지 테이블을 8MB의 물리적 메모리로 설정한다.
• 두 번째 단계에서 나머지 물리적 메모리 매핑을 완료한다.

부트스트랩 단계에서 startup_32() 호출은 페이징을 초기화 한다. 이것은 arch/i386/kernel/head.S 파일 내에서 구현된다. 8MB의 매핑은 PAGE_OFFSET 이상 어드레스에서 발생한다. 초기화는 swapper_pg_dir라고 하는 정적으로 정의된 컴파일 시 어레이로 시작한다. 이는 컴파일 시 특정 어드레스(0x00101000)에 배치된다.

이 액션은 코드에서 정적으로 정의된 두 개의 페이지(pg0과 pg1)용 페이지 테이블 엔트리를 구현한다. 페이지 크기 확장 비트가 설정되어 있지 않는 한, 이 페이지 프레임의 크기는 기본이 4KB 이다. (확장 페이징 섹션 참조) 각각 크기는 4MB이다. 글로벌 어레이가 가리킨 데이터 어드레스는 cr3 레지스터에 저장된다. 이것이 리눅스 프로세스용 페이징 단위를 설정하는 첫 단계이다. 나머지 페이지 엔트리들은 두 번째 단계에서 설정된다.

두 번째 단계는 메소드 호울 paging_init() 때문에 주의해야 한다.

RAM 매핑은 PAGE_OFFSET과 x86 32-bit 아키텍처의 4 번째 GB 제한 (0xFFFFFFFF)으로 표현된 어드레스 사이에 수행된다. 약 1GB의 RAM이 리눅스가 시작할 때 매핑될 수 있다는 의미이다. 하지만 누군가 HIGHMEM_CONFIG를 설정했다면 1GB 이상의 물리적 메모리가 커널에 매핑될 수도 있다. 이것은 임시적인 배열이다. 이는 kmap() 호출로 수행된다.

위로

메모리 존(zone)

(32-bit 아키텍처 상의) 리눅스 커널은 가상 메모리를 3:1 비율로 나누며, 3GB 가상 메모리는 사용자 공간에, 1GB는 커널 공간에 쓴다. 커널 코드와 데이터 구조는 1GB의 어드레스 공간에 상주해야 하지만 이 어드레스 공간의 큰 소비자는 물리적 메모리용 가상 매핑이다.

커널이 어드레스 공간으로 매핑되지 못한다면 메모리를 조작할 수 없기 때문에 이것이 수행된다. 따라서 커널에 의해 핸들 될 수 있는 최대 물리적 메모리는, 커널 코드 자체를 매핑하는데 필요한 공간을 제외한 커널의 가상 메모리 공간으로 매핑될 수 있는 양이었다. 결과적으로 x86 기반 리눅스 시스템은 1GB 미만의 물리적 메모리로 작동될 수 있다.

많은 사용자들에게 공급하기 위해, 더 많은 메모리를 지원하기 위해, 퍼포먼스를 높이기 위해, 아키텍처와 독립된 방식으로 메모리를 기술하기 위해서 리눅스 메모리 모델은 진화해야 했다. 이를 위해 더욱 새로운 모델이 메모리를 각 CPU에 할당된 뱅크로 배열했다. 각 뱅크를 노드(node)라고 한다. 각 노드는 존(zone)으로 나뉜다. 존은 다음과 같은 유형이 있다.

• ZONE_DMA (0-16 MB): 특정 ISA/PCI 장치가 필요로 하는 더 적은 물리적 메모리 영역에 상주하는 메모리 범위.
• ZONE_NORMAL (16-896 MB): 커널에 의해 직접 물리적 메모리의 상위 영역으로 매핑되는 메모리 범위. 모든 커널 작동들은 이 메모리 존을 사용하여 발생할 수 있다. 가장 퍼포먼스 중심적인 존이다.
• ZONE_HIGHMEM (896 MB and higher): 커널에 의해 매핑되지 않은 시스템에 남아있는 가용 메모리.

노드 개념은 struct pglist_data 구조를 사용하여 커널에서 구현된다. 존은 struct zone_struct 구조를 사용하여 기술된다. 물리적 페이지 프레임은 struct Page 구조에 의해 표현되고 모든 struct들은 글로벌 구조 어레이인 struct mem_map에서 유지된다. 이는NORMAL_ZONE 시작 시 저장된다. 그림 9는 노드, 존, 페이지 프레임 간 기본적인 관계를 보여준다.

그림 9. 노드, 존, 페이지 프레임 간 관계 

(32-bit 시스템에서 PAE(Physical Address Extension)에 의해 최대 64GB 까지 액세스 하기 위해) Pentium II의 가상 메모리 확장의 지원이 구현되었을 때와 4GB의 물리적 메모리(32-bit 시스템)용 지원이 구현되었을 때 높은 메모리 존은 커널 메모리 관리에 나타났다. 이것은 x86과 SPARC 플랫폼에 적용된 개념이다. 일반적으로 4GB 메모리는 ZONE_HIGHMEM을 ZONE_NORMAL에 매핑하여 kmap()에 의해 액세스 될 수 있다. 32-bit 아키텍처 상에 16GB 이상의 RAM을 두지 않도록 한다. PAE가 실행될 때도 마찬가지이다.

(PAE는 Intel에서 제공하는 메모리 어드레스 확장으로서 프로세서가 물리적 메모리에 어드레스 하는데 사용될 수 있는 비트의 수를 32 비트에서 36 비트로 확장할 수 있도록 한다. Address Windowing Extensions API를 사용하는 애플리케이션용 호스트 운영 체계의 지원을 통해 가능하다.)

물리적 메모리 영역의 관리는 존 할당자(zone allocator)에 의해 수행된다. 이것은 메모리를 여러 존들로 나눈다. 각 존을 할당용 단위로 취급한다. 특정 할당 요청은 할당이 시도되는 존의 리스트를 활용한다.

예를 들어,

• 사용자 페이지에 대한 요청은 "일반" 존에서 먼저 채워져야 한다. (ZONE_NORMAL);
• 실패하면 ZONE_HIGHMEM부터 채운다.
• 역시 실패하면 ZONE_DMA부터 채운다.

이 같은 할당을 위한 존 리스트는 ZONE_NORMAL, ZONE_HIGHMEM, ZONE_DMA로 구성된다. 한편, DMA 페이지의 요청은 DMA 존에서만 수행된다. 따라서 이 같은 요청의 존 리스트에는 DMA 존만 포함된다.

위로

결론

메모리 관리는 크고, 복잡하고, 시간이 많이 드는 일이다. 실제 멀티 프로그래밍 환경에서 시스템이 어떻게 작동하는지를 모델링 하는 것이기 때문에 매우 까다로운 작업이다. 스케줄링, 페이징 작동, 멀티 프로세서 인터랙션 같은 컴포넌트들은 상당한 도전 과제이다. 이 글이 여러분에게 도움이 되었기를 바란다.

기사의 원문보기

• Explore the Linux memory model

참고자료

교육

• 메모리 관리 (developerWorks, November 2004)
  
• Kernel comparison: Improved memory management in the 2.6 kernel (developerWorks, March 2004)
  
• Linux, outside the (x86) box (developerWorks, May 2005)
  
• Use shared objects on Linux (developerWorks, May 2004)
  
• Outline of the Linux Memory Management System
  
• Linux Device Drivers, Third Edition (O'Reilly, February 2005), chapter on memory management and DMA.
  
• Understanding the Linux Kernel, Third Edition (O'Reilly, November 2005)
  
• Understanding the Linux Virtual Memory Manager (Prentice Hall, April 2004)
  
• developerWorks Linux zone.
  

제품 및 기술 얻기

• Order the no-charge SEK for Linux
  
• IBM trial software
  
  

토론

• developerWorks blogs.
  
  

필자소개

Vikram Shukla, Software Engineer, IBM

-----
Cheers,
June