[운영체제및실습] 12주차 1회차 : Address binding

이 시간에는 Address binding에 대해서 알아보겠습니다.

1. Binding of Instructions and Data to Memory

이전 절에서 logical address를 physical address로 주소변환해야 한다고 했습니다.

Address traslation시켜야 하는데 다른 말로 Address binding이라고 합니다.

 

이 struction 안에는 다른 인스트럭션이나 변수의 주소가 등장합니다. 인스트럭션을 실행 하려면, 변수의 경우, variable값을 가져와서 연산을 해야 하서 몇 번 주소에 있는지 조사해야 합니다. 다른 인스트럭션의 주소도 있는데, 어떤 위치로 jump해라 할때, 그 대상 주소를 인스트럭션 안에 집어넣습니다. 이와 같이 인스트럭션 안에 있는 주소는 모두 logical address입니다. 그래서 실제로 실행할 떄는 logical address에 해당하는 실제 main memory의 주소를 알아내야 합니다.

이와 같이 인스트럭션이나 데이터의 physical address를 알아내는 것을 address binding이라고 합니다.

 

Address binding을 언제 하느냐에 따라 세 가지 binding의 종류가 있습니다. 

 

 

1-1. Compile time binding

Compile time binding이라는 것은 즉, 컴파일 시점 바인딩이라는 것은 프로그램 작성 후에 컴파일 단계에서 이 프로그램이 메인 메모리에 몇 번지에 들어가서 실행될 것인가를 미리 알고 컴파일러에게 알려주는 것입니다. 그러면 컴파일러가 logical address를 만들 때, logical address가 들어갈 자리에 physical address와 동일한 주소로 만들어서 변수값이라든가 또는 다른 instruction의 주소를 physical address를 완전히 집어넣는 것입니다.

소스 코드를 바이너리 코드로 변환하는 컴파일 때 바인딩을 해 줄 수 있습니다.

따라서 instruction에 등장하는 logical address가 그 값 자체는 실제로 physical address, 즉, 반도체의 주소와 같다는 특징이 있습니다. 

1-2. Load time binding

Load time Binding은 컴파일 할 때는, 모르지만 나중에 실제로 메인 메모리에 넣을 때, 이 주소를 physical address로 다 바꿔서 넣는 방법입니다. 

 

1-3. Execution time binding

실행 시점 바인딩이라는 것은 컴파일이나 load할 때는 relative address인 logical address를 그대로 넣다가 나중에 인스트럭션을 실행할 때, logical address에 해당하는 physical address가 얼마인지를 계산해내서 physical address를 알아내는 방법입니다.

 

이 3가지 시점이 왜 나왔는지를 보면, 우리가 source program을 짜서 main memory에 넣기까지의 작업을 도식화한 그림을 보면, source program을  compile해서 binary program으로 된 object module을 만들고, 그것을 library들을 쓴다고 하면, library들을 연결해서 이제 실행가능한 형태로 나오면, 그럼 loader를 통해 그것을 memory에 집어넣고 그러고나서 cpu가 실행을 하게 되는 것입니다. 

---

2. Compile Time Binding

예를 들어서 이제 3가지 방법을 설명해보겠습니다. 

source program이 있을 때, 변수 i가 있는데 10을 더해서 옛날 값을 대체하고 label2로 점프를 합니다. 소스 프로그램을 컴파일하면, 컴파일러는 소스 프로그램을 쭉 스캔합니다. 변수가 선언되는 지점이 나오면, 그때마다 컴파일러는 그 변수를 변수 테이블에 기록합니다. 그래서 logical address 0번부터 읽어서 각 인스트럭션의 길이가 나와서 코드가 몇 번지까지 차지할 것인지 알게됩니다. 즉, VAS에서 0번지에서부터 코드가 몇 번지까지 자리를 차지한다라는 것을 알게 됩니다.

 

그러면, code다음의 data영역이 위치하는 것이 나오지 않습니까?그래서 code의 끝주소를 알기 때문에 그 다음 주소부터가 data의 상대적 주소가 됩니다. 이런 식으로 컴파일이 끝나면, 각 변수들의 상대적인 주소값도 다 알게 됩니다. 그러면, 컴파일 시점 바인딩은 컴파일을 한다음, 주소값을 받게 되는데, 컴파일에 대한 인자값으로 컴파일러를 돌리는 사람이 이 프로그램이 앞으로 메인 메모리 몇 번지에 들어갈 것인가를 알아내서 컴파일러에게 인자로 알려주는 것입니다. 

예를 들어, 이 프로그램이 들어갈 시작 주소를 base address라고 하고, 이것을 $BA라고 합니다. 이것이 100이라고 컴파일러에게 파라미터로 주면서 컴파일러를 시킵니다. 그러면, 컴파일러는 내부적으로 소스코드 스캔하면서 변환하는데, 코드 부분의 길이가 얼마인지를 알고, 그 다음 변수가 등장해서 i가 프로그램 시작 주소로부터 406바이트만큼 떨어진 데에 변수 i가 등장한다라는 것을 컴파일러가 아는데, 시작주소를 사람이 100번지로 하라고 했기 때문에 컴파일러는 100번지 + 406번지를 해서 변수 i의 주소가 506번지라는 것을 미리 다 컴파일 할 때 하는 것입니다.그리고 JUMP lable2같은 경우는, 컴파일러가 프로그램을 쭉 스캔을 하면서 label2가 프로그램 코드 내에서 몇 번지 위치라는 것을 알게 되는데, 그것은 상대적인 위치입니다. 프로그램 시작부터 20만큼 떨어진다라는 것을 컴파일러가 아는데, 사람이 시작주소를 100이라고 주었기 때문에 100에서 20만큼 떨어진 120번지가 되는 것입니다.

이런식으로 주소를 결정해서 메모리에 로딩을 합니다. 메모리에 로딩할때, 컴파일러에게 알려준 100번지 그대로 로딩을 해야 ㅎ바니다. 100번지에 시작주소가 들어가면, 시작주소로부터 20만큼 떨어진 곳에 printf라고 하는 label2가 있었습니다.

이런식으로 컴파일을 하는 과정에서 이 프로그램이 메인 메모리 몇 번지에 들어갈 것인가를 미리 알고 컴파일러에게 알려주면, 컴파일러가 그 logical address자리에 실제로는 physical address와 같은 logical address값을 집어넣는 것이 컴파일 타임 바인딩입니다.

 

이 방법에는 문제점이 있습니다. 프로세스 시작 지점이 100번지라고 약속을 했기 때문에 이 주소가 바뀌면 안 됩니다. 만약 7000번지로 relocation됐다고 하면, 시작 지점이 7000번지가 되어야 하는데, 계속 120번지로 점프를 해라고 합니다. 이제 120번지는 가면 안 되는 주소입니다. 이 프로그램이 7000번지로 이사를 갔기 때문에 점프 해서 7020번지로 가야하는 것입니다.

결론적으로 컴파일 타임 바인딩에서는 reloacation이 안되어서 요즘 사용하지 않는 방법입니다. 

 

컴파일 타임 바인딩도 logical address == Physical address인 특징이 있습니다.

 

이 방법을 개선해서 나온 것이 load time binding입니다.

 

3. Load Time Binding

Load Time Binding은 프로그래머가 컴파일을 할때까지는 시작 주소가 얼마인지를 신경쓰지 않고 컴파일합니다. 컴파일을 하면, 컴파일러는 메모리 주소에 대한 정보가 전혀 없으니까 그냥 프로그램 시작에서 406번지에 떨어진 곳에 변수 i가 잡히고 , 프로그램 시작으로부터 20번지 떨어진 곳에 lable2가 있다는 식으로 상대적인 주소를 계산해서 컴파일해냅니다. 그런 다음, 미지수로 주소값이 남아있는 상태에서 메모리에 load할 때, 운영체제가 집어넣어주기 때문에 os가 메인메모리의 상태를 쭉 알아내고 빈 메모리를 찾아서 넣을 것입니다. 빈 메모리가 100번지라고 알아내면, 프로그램 시작 주소가 100번지라는 것을 load할 때, 알기 때문에 주소계산을 해서 506이라고 값을 넣습니다. 그래서 loader가 메모리에 넣고 난 다음에는 506이라고 하는 주소가 실제 메인메모리에 들어가는 주소와 같게 됩니다.

이때에도 컴파일 타임 바인딩 때처럼 똑같은 문제가 있습니다. 이 프로그램은 100번지에서부터 들어갔을 때 제대로 실행이 되지, 7000번지로 이 프로그램이 이사갔다고 하면, 실행이 안 됩니다. 왜냐하면, 이 안에 들어가는 instruction의 주소는 옛날 주소를 가리키기 때문에 그 주소는 가서는 안되는 주소이고 잘못된 주소가 됩니다.

load time binding도 relocation이 안 되서 실행이 안됩니다. 그래서 나온 것이 실행시점 바인딩이라는 execution time binding입니다.

instruction 안에 들어가는 주소를 logical address라고 하는데, cpu가 바라보는 주소가 logical address입니다. 그 값이 실제로 메모리 하드웨어가 바라보는 주소인 physical address와 같습니다. 그래서 logical address == Physical address인 특징이 있습니다.

 

3. Execution Time Binding

실행시점바인딩에서 source code는 아까와 동일한데, 컴파일 하면, 프로그램 시작에서 얼마나 떨어진 위치라는 상대적 주소로 표현됩니다. 아직 모르는 값이 있어 완전히 아는 것이 아닙니다. 그런데 이것을 메모리에 넣습니다. 빈 메모리 상황만 보고 미지수 값이 있는 상태로 프로그램을 집어넣는 것입니다. load 시점 바인딩에서는 반면, load하면서 미지수에 값을 써줬습니다.

cpu가 $BA+406을 실행을 할 때 시작 주소가 어딘지를 그때 알아내는 것입니다. 운영체제는 load해서 빈 메모리에 프로그램을 넣을 떄 그때 시작주소가 100번이라는 것을 register에 기록해놓습니다. 그래서 cpu가 실행을 할 때, 시작주소에서부터 406번지만큼 떨어진 위치를 구할 때, 그제서야 506이라고 계산을 해서 506번지로 점프를 하는 것입니다. 즉, 인스트럭션 실행 과정에서 logical address에 해당하는 physical address를 알아내서 이동합니다. 

그래서 $BA+406에서 시작주소는 register에만 저장을 하기 때문에 그 인스트럭션에서는 406만 저장해서 logical address는 406인데, 나중에는 physical address가 506이 되므로 execution time binding에서는 logical address != Physical address입니다.

 

실행시점 바인딩은 relocation이 지원되는지 한 번 살펴봅시다. 실행시점 바인딩은 인스트럭션 실행 당시의 주소변환까지 수행을 해야 합니다. 그러니까 인스트럭션 실행시간이 약간 길어진다는 단점이 있지만, 장점으로서 relocation이 제공이 됩니다. 프로그램이 100번지에 있다가 7000번지로 relocation됐다고 하면, swapping되어서 보조기억장치로 나갔다가 다시 들어올 때, 처음에는 1000번지에 있다가 그 다음에는 7000번지로 들어올 수도 있는 것입니다. 그리고 이 프로그램을 오늘 실행시킬 때는 100번지에 들어갔는데, 똑같은 프로그램을 내일도 실행시킬 수도 있습니다. 내일도 실행시킬 때는 7000번지에 실행시킬 수도 있습니다. 실행할 떄마다 메모리의 다른 위치에 잡힐 수 있는데, 컴파일 타임 바인딩이나 로드 타임 바인딩 때는 언제든지 꼭 100번지에만 들어가야만 하는 단점이 있습니다. 그러나 실행타임바인딩은 시작주소가 어디든지 상관없습니다. 인스트럭션을 실행할때, 레지스터에 들어간 7000번지를 보고 변수 i의 위치도 7000번지 대로 같이 간 것입니다. 그래서 7406번지로 가면, 변수를 접근 할 수 있는 것입니다.

 

Relocation에 대해서 좀 더 알아봅시다.

이전의 relocation은 process 가 swap out되었다가 swap in되었을 때 발생할 수 있다고 말했었습니다. 이런 relocation이 swapping 외에도 compaction일때도 relocation이 됩니다. 

 

 

relocation이 가능하려면 코드 내에 물리적 주소가 등장하면 안 됩니다. 항상 그 주소에 해당하는 곳에 변수나 또는 인스트럭션이 그대로 남아있어야 하기 때문에 이사를 못간다는 것입니다. 반면에 실행타임바인딩 때에는 시작 주소가 어떻게 되든 간에 인스트럭션 실행할 때 계산을 하기 때문에 시작주소가 바뀌어도 되는 것입니다.

실행시점에 주소를 계산을 하려면 치뤄야 할 대가가 있습니다. 인스트럭션 실행 할 때에 그 주소변환, 주소값을 시작주소에 상대적인 주소값을 더해야 하는 작업을 해야 하는데, 주소변환 계산을 하려면, 시간 지연이 됩니다. 그 시간 지연을 최소화하기 위해서 하드웨어적으로 계산을 합니다. 하드웨어적으로 계산을 하기 위해서 추가로 하드웨어가 cpu에 있어야 하는데, Base register와 BOunds register라는 것입니다. Bounds register는 limit register라고 불리기도 합니다.

 

그림을 보면, cpu가 있습니다. cpu내에 Base register에는 그 프로그램이 어디로 load가 되는지 시작 주소를 저장을 합니다. $BA=100이 되는 것입니다. 다음에 Bounds register는 프로그램의 끝주소를 가리킵니다. 인스트럭션을 실행을 할 때, 인스트럭션 내의 상대적인 주소로 되어있는 logical address가 406만큼 떨어져있다고 주소가 매겨져 있습니다. 그래서 Base Regiser와 Relative address를 더해 506이 되며, 506번지가 합법적인 주소인지, 즉, 프로세스가 접근 가능한 허용 가능한 범위 내에 있는지, 잘못된 주소인지 Bounds Register를 통해 비교를 하여, Bounds Register에 저장된 값보다 작으면 메모리 접근을 하고 값이 크면, 범위를 벗어나서 운영체제에게 인터럽트를 걸어서 프로그램을 중단시켜다라고 요청을 합니다.

 

이것이 전에 trap을 배웠는데, segmentation fault를 배웠습니다. 허용된 주소값을 벗어난 주소를 실행할 때 나타납니다. cpu가 거는 interrupt이므로 이것은 trap입니다. 허용되지 않은 주소로 갔다고 해서 주소 오류를 낸 프로세스를 끝냅니다. 

 

정리:

프로그램 실행을 하기 위해서는 코드 내에 등장하는 변수나 레이블에 해당하는 주소의 physical address를 결정해주어야 하는데, 그 작업을 address binding이라고 하고, 현대 운영체제에서는 binding방법으로 실행시점 바인딩을 사용합니다. 그 이유는 relocation이 가능하기 때문입니다. 실행 시점 바인딩을 하려면 그떄 주소 계산을 해주어야 하기 때문에 시간이 약간 걸리지만, 그 시간을 최소화하기 위해 신속하게 하기 위해서 하드웨어적으로 Base register와 Bounds register를 이용해서 address traslation을 합니다.