Study & Project repository

Dining-Philosophers Problem

• 내용

• 5명의 철학자들은 평생 정해진 원탁의 자리에서 살아야 함
• 철학자들이 하는 일은 철학하는 것과 음식을 먹는 것 두 가지뿐이라고 모델링
• 접시는 각자 하나씩 총 5개가 있고 젓가락은 접시 양 옆에 한 짝씩 존재하여 이 또한 5개
• 식사를 하는 철학자는 접시 양 옆의 젓가락을 들고 식사를 할 수 있음
• 한 사람씩 식사를 하고 싶다면 순서대로 젓가락을 사용할 수 있지만 동시에 모든 사람이 배가 고파진다면 젓가락이 부족
• 만약 모든 철학자들이 젓가락을 한 짝씩 들고 있다면 모두 식사를 하지 못하게 될 것

• 각자의 철학자에 맞춰서 구성을 해본다면(해결 방안)

• 실제 구현

• 잘 생각해볼 것

임계 영역 프로그래밍

• 기본 코드

• 두 개의 스레드로 동작
• 메인 프로그램

• 두 스레드를 생성
• 앞의 코드 for(;;)에 sleep(1) 함수를 추가해 보자 - 그 순간에 스케줄링을 시켜줌

• 임계 영역(Critical Section) 접근 동기화

• g_var라는 int형 변수를 선언한 후 사용
• 첫 번째 스레드는 g_var를 1로 만들고 Sleep(1)을 한 후 g_var 값을 출력

• 두 번째 스레드는 g_var를 2로 만들고 Sleep(1)을 한 후 g_var 값을 출력
• 원하는 결과

• 실제 결과

•  Sleep을 하는 동안 공유 변수 g_var의 값이 다른 스레드에서 바뀌기때문
• Sleep을 빼고 확인해볼 것

유저 모드의 동기화

• 임계 구역 기반의 동기화

• 화장실에 걸어 놓은 열쇠(비유)

• CRITICAL SECTION의 변수를 설정(화장실 열쇠) - CRITICAL_SECTION gCriticalSection;
• 변수 초기화(열쇠 걸어 놓음)

• Critical Section의 변수를 사용하여 임계 영역으로 들어감.(화장실 열쇠를 획득)

• 키를 반환하고 임계 구역을 빠져나옴.(화장실 열쇠를 반환, 다시 걸어놓음)

• 형식

1. 임계 영역에 하나라도 들어가 있다면 나머지 프로세스들은 대기

• 실제 프로그램 코드

1. 각 스레드의 for문 안의 내용을 critical section으로 묶음
2. 임계 영역에 sleep이 있으므로 스케줄링은 할 수 있으나 다른 스레드에 의해 값은 바뀌지 않음
3. LeaveCriticalSection 이후에 여러 코드를 추가하여 어떻게 실행되는지를 확인해보자

커널 모드의 동기화

• 뮤텍스(Mutex) 기반의 동기화

• 구조는 동일
• 사용하는 함수의 이름이 달라짐
• 운영체제가 개입 - wait 할 때, CPU를 사용하게 할 수도 있고 안 할 수도 있음 -> 유저 레벨에서 할 수 없었던 일을 할 수 있음

• 세마포어(Semaphore) 기반의 동기화

• 세마포어(세마포어 오브젝트)를 생성하는 함수

• 시뮬레이션

1. 한 테이블에는 1명씩 총 10명이 동시에 식사를 할 수 있음
2. 각 사람마다 초기값을 가지고 있음(식사시간)
3. 치우는 시간은 없다고 가정
4. 이러한 프로그램을 이용하여 여러 가지 요소들을 예측하여 최적의 환경을 만들어낼 수 있음(아르바이트생의 수, 일을 해야 하는 시간 등)

Deadlocks

• The Deadlock Problem

• 한 프로세스가 자원을 요청했을 때, 그 자원을 사용할 수 없게 된다면 대기상태가 됨
• 대기 중인 프로세스가 요청한 자원들이 다른 대기 중인 프로세스에서 점유되어 있을 때, 이 프로세스 상태를 변경시킬 수 없는 경우를 교착상태라고 함
• 두 개의 프로세스가 한 개의 구동기를 점유한다고 가정
• 만약 프로세스가 다른 구동기를 요청한다면 두 개의 프로세스는 교착상태가 됨

1. 어떤 한 자원을 가지고 있고 다른 자원을 또 가지려고 대기
2. 두 자원을 다 가지면 어떤 일을 하겠다는 것
3. 두 프로세스가 각각 자원 하나씩을 가지게 된다면 계속 대기해야 하는 상황

• Bridge Crossing Example(외나무다리)

• 마주오는 두 개의 자동차를 생각해보자
• 하나의 차량이 돌아가기 전까지는 누구도 빠져나갈 수 없게 됨
• 교착상태 -> 기아상태가 발생

• System Model

• 시스템은 경쟁할 프로세스들 사이에서 유한한 수의 자원들로 구성
• 자원은 R1~Rm까지 존재(CPU cycle, memory space, I/O devices 등)
• 이들 각각 자원들은 동일한 다수의 인스턴스를 가지고 있음(Ri has Wi instances)
• 프로세스는 자원을 사용하기 전에 요청을 해야 함
• 사용한 후에는 해제해야 함

• Deadlock Characterization

• 아래 네 가지 특징을 모두 가지고 있을 경우 교착상태 - 교착상태일 때 이러한 특징을 가지고 있음(필요조건 o, 충분조건 x)
• Mutual exclusion(상호 배제) : 하나의 프로세스는 한 번에 하나의 자원만 사용할 수 있도록 되어있음
• Hold and wait(점유 및 대기) : 최소한 하나의 자원을 점유하고 있는 프로세스가 있는데, 이 프로세스는 다른 프로세스에 의해 점유된 다른 자원을 추가로 얻기 위해서 기다리고 있는 상태
• No preemption(비선점) : 점유된 자원은 강제적으로 해제될 수 없고 점유하고 있는 프로세스가 그 테스크를 종료한 후에 자원이 저절로 해제됨
• Circular wait(순환 대기) : 대기하고 있는 프로세스의 집합에서 P0 -> P1, P1 -> P2 ... Pn-1 -> Pn, Pn -> P0로 점유한 자원을 대기하는 것이 고리를 형성하여 순환하는 상태

• Resorce-Allocation Graph(자원 할당 그래프)

• 교착상태는 시스템 자원 할당 그래프라는 방향 그래프로 표명할 수 있음
• Vertices(정점)와 Edges(간선)로 이루어져 있음
• V(정점)는 2가지 형태로 구성되어 있음 - P(시스템 내 모든 프로세스들의 집합), R(시스템 내 모든 자원들로 이루어진 집합)
• Request edge - Pi가 Rj를 요청하는 요청선(Pi -> Rj)
• Assignment edge - Rj가 Pi에 할당된 것을 의미하는 할당선(Rj -> Pi)
• 그림으로 나타내면

1. 프로세스는 원
2. Resource는 사각형인데 안에 작은 사각형이 있는 것은 여러 디스크(D, C, E 등)가 할당된 것을 의미
3. 프로세스 Pi가 자원 Rj를 요청하고 있는 것
4. Rj이 가지고 있는 것들 중 하나가 Pi에 할당(Rj안의 인스턴스 하나가 할당)

• 3개의 프로세스의 예

1. P1은 R1을 요청
2. R1의 인스턴스는 P2에 할당
3. P2는 R3를 요청
4. R3의 인스턴스는 P3에 할당
5. R2의 인스턴스는 P1과 P2에 할당
6. 순환 그래프가 그려지지 않는다면 교착상태가 아님

• 또 다른 예

1. P3가 R2에 자원을 요청하지만 R2의 자원을 P1과 P2가 사용 중
2. P3는 R2에 자원이 돌아올 때까지 대기
3. P1과 P2도 마찬가지로 R1과 R3에 각각 자원을 요청하였으나 이미 사용 중이기 때문에 대기하는 중
4. 따라서 3개의 프로세스가 전부 기다리게 됨 -> 교착상태

• 또 다른 예 2

1. P1 -> R1 -> P3 -> R2 -> P1으로 순환이 형성 -> 교착상태인가?
2. P4나 P2가 끝나고 자원을 돌려주면 돌려받은 자원을 P1과 P3에 할당할 수 있으므로 교착상태는 생기지 않음
3. 순환이 형성된다고 해서 무조건 교착상태는 아님

• Basic Facts

• 그래프가 주기를 가지지 않으면 교착상태는 존재하지 않음
• 그래프가 주기를 가지면
  1. 자원이 인스턴스를 하나만 가지고 있다면 반드시 교착상태
  2. 자원이 인스턴스를 여러 개 가지고 있다면 다른 프로세스가 해제할 경우 돌려받은 자원을 할당해 줄 수 있으므로 교착상태에서 벗어날 수 있음 -> 가능성은 있으나 항상 교착상태는 아님

• 교착상태를 처리하는 방법

• 시스템이 교착상태가 되지 않도록 보장하는 프로토콜을 만드는 방법
• 시스템이 교착상태가 되도록 허용한 후에 이를 회복하는 방법을 만듦
• 이러한 문제를 무시하고 교착상태가 생기지 않는다고 생각, 운영체제에 교착상태가 절대 발생하지 않는 척 -> 교착상태가 발생하지 않도록 운영 프로그램 개발자가 알아서 사용

• 교착상태의 예방(Prevention)

• 아래 네 가지 중 하나를 안생기게 하면 교착상태에 빠지지 않음
• Mutual Exclusion : 공유 자원을 요청하지 않음, 비공유 자원을 전제로 함
• Hold and Wait : 점유 대기 조건이 시스템에서 발생하지 않으려면, 프로세스가 자원을 요청할 때마다 다른 자원들을 점유하지 않도록 보장해야 함 -> 자원 이용률이 낮아짐

• No Preemption(비선점)

• Circular Wait(순환 대기) : 모든 자원 형태들에게 전체 순서를 부여하고, 각 프로세스가 열거된 상태에서 순서(오름차순)를 정해 자원을 요청하는 프로토콜을 사용하는 것

• Deadlock Avoidance(교착상태 회피)

• 자원을 요청하는데 필요한 추가의 앞선 정보(additional a priori information)를 요청하는 알고리즘 작성으로 교착 상태를 회피

• Safe State(안전 상태)

• 특정한 순서대로 각 프로세스의 자원을 할당할 수 있게 되었을 때, 교착상태를 방지할 수 있으면 이것을 안전 상태라고 함
• 하나의 프로세스가 이용 가능한 자원을 요청할 때, 시스템은 즉각적인 자원 할당이 안전상태를 벗어나는 것을 매번 결정하게 됨
• 모든 프로세스의 안전 순서(안전상태를 유지하는 순서)가 존재하면 이 시스템은 안전 상태에 있다고 말할 수 있음

1. 시스템이 안전 상태에 있다면 교착상태는 아님
2. unsafe 하다면 교착 상태가 생길 수 있음
3. 시스템이 불안정 상태로 들어가지 못하도록 하는 것이 교착 상태 회피 알고리즘 -> 시스템이 항상 안전 상태에 머무르도록 하는 것

• 안전한 상태가 있는가를 살펴보자

1. 자원은 총 12개
2. P0는 최대 10개를 요청할 수 있고 5개 할당
3. P1은 최대 4개를 요청할 수 있고 2개 할당
4. P2는 최대 9개를 요청할 수 있고 2개 할당
5. 3개가 남아있음
6. 만약 P0~2가 동시에 최대 수요량만큼을 요청했다면 자원이 부족해짐 -> 교착상태
7. 이 상황에서 P0가 나머지 수요량인 5개의 자원을 요청한다면 2개가 부족하므로 교착상태가 발생
8. 최대는 넘지 않게 각각의 요구를 만족할 수 있는 순서가 있느냐를 봐야 함
9. P0는 5개가 필요하고 P1은 2개, P2는 7개가 필요하므로 나머지 자원(3개)을 할당했을 때 최대 수요를 만족하는 P1에 우선적으로 자원을 할당
10. P1이 끝났다면 남은 자원은 5개가 되어 P0에 모두 할당 -> 최대 수요를 만족
11. 마지막으로 남은 자원 10개를 P2에 7개 할당 -> P2 만족
12. 이 순서로 할당하지 않는다면 교착 상태가 발생할 수 있음

• Resource-Allocation Graph Algorithm

• 앞서 한 것들을 요청 가능선, 요청선, 할당선 등으로 구체화시켜 나타냄

1. 점선 : 요청 가능선 -> 요청이 되어 자원 할당을 받는다면 할당선으로 바뀜
2. 실선(R1 -> P1) : 할당선
3. 실선(P2 -> R1) : 요청선

• Banker's Algorithm

• 앞의 리소스로 설명한 것을 Multiple instances에 대해 어떻게 이 알고리즘을 바꿔야 하는지를 정리한 것
• 자원 할당 그래프의 알고리즘은 다수개의 자원 유형을 갖는 시스템에서 적용할 수 없음
• 다수개의 자원 유형을 갖는 시스템에서 적용하기 위한 알고리즘
• 새로운 프로세스가 시스템에 들어가면 필요로 하는 각 자원 형태들의 최대수를 미리 선언하고 알고 있어야 함
• 프로세스가 자원을 요구할 때, 시스템은 자원을 할당한 다음에 안전상태로 남아있는지를 결정해야 함
• 안전상태로 남아있으면 할당하고 그렇지 않으면 다른 프로세스들이 자원을 충분히 해제할 때까지 대기
• 은행가 알고리즘은 은행이 모든 고객의 수요를 충족시킬 수 있도록, 현금을 할당하는 데 기인한 알고리즘
• Data Structures for the Banker's Algorithm

1. 여러 개의 프로세스가 여러 개의 자원들을 필요로 함
2. 필요로 하는 자원들을 어떻게 관리를 할 수 있는지 -> 안전한 상태를 유지할 수 있는지

• Safety Algorithm(꼭 해볼 것! 시험에 매번 나옴)

1. 어떻게 유지가 되는지를 잘 보면 됨

• 예시

1. 프로세스는 5개
2. 자원은 세 가지
3. 현재 각 프로세스가 할당받은 자원들과 최대로 할당받아야 하는 양, 남은 자원의 양
4. 꼭 해볼 것

• Resource-Request Algorithm for Process Pi - 추가 요청

• 예시) P1이 (1,0,2)를 추가로 요청했을 경우 -> 어떻게 업데이트를 할 것인가

1. 남아있는 자원(3,3,2)이 (2,3,0)으로 줄어듦

• Deadlock Detection

• 시스템이 교착상태로 들어가도록 하는 것 까지는 허용
• 교착상태가 발생했는지 파악하기 위해서 시스템 상태를 탐지
• 탐지를 했다면 회복(Recovery)

• Single Instance of Each Resource Type

• Resource-Allocation Graph를 Wait-for Graph로 단순화 -> 교착상태가 생겼는지를 한눈에 볼 수 있음(순환 고리 형성)

• Several Instances of a Resource Type

• 교착상태가 발생하고 여러 개의 인스턴스가 있을 경우의 설명

• Detection Algorithm

• 표현법이 Need가 아닌 Request가 됨

• Detection-Algorithm Usage - 언제 탐지 알고리즘을 호출할 것인가?

• 교착 상태 발생 빈도수
• 교착 상태가 발생했을 때, 영향을 받는 프로세스의 수
• 교착 상태가 자주 발생하면 탐지 알고리즘도 더 자주 호출해야 함 -> 운영체제가 하는 일이 많아져서 효율이 떨어짐

• Recovery from Deadlock : Process Termination

• 순환 대기를 탈피하기 위해서 단순히 프로세스 하나를 중지시키는 것
• 교착상태 프로세스들로부터 자원을 선점하는 것

• Recovery from Deadlock : Resource Preemption

• 자원 선점에 의한 방법 - 잘 읽어볼 것

• Combined Approach to Deadlock Handling(복합적인 방법)

두 개 이상의 프로세스가 동작하고 있을 경우의 알고리즘

가장 낮은 번호를 받은 프로세스가 가장 먼저 임계 영역에 들어갈 수 있음

번호 부여는 증가하는 방식으로 하지만 우연히 같은 번호를 받을 수 있음 -> 은행에서는 번호표 지급기가 1개뿐인 이유

Bakery Algorithm

• Notaion <= lexicographical order (ticket #, process id #)

• (a, b) < (c, d)는 a와 b를 비교하고 b와 c를 비교한다는 의미
• max는 이중 가장 큰 값을 의미

• 공유 데이터(shared data)

• boolean choosing[n]; 
• int number[n];
• 이 두 값의 초기값은 각각 모두 false와 0

• 알고리즘 코드

1. 각각의 프로세스들이 이 형태의 구조로 되어있어서 각자가 알아서 판단
2. 하나의 프로세스만 임계 영역에 들어감 - 프로세스들은 각자의 임계 영역이 있음
3. choosing을 true로 만듦 -> 이제 번호표를 받을 것이라는 의미
4. 현재 대기 중인 가장 큰 번호보다 1이 큰 number를 받음
5. 번호를 받은 후에는 choosing이 flase가 됨
6. for문에서 0~n까지의 번호를 확인하게 됨
7. 첫 번째 while문은 어떤 프로세스가 번호표를 받고 있는 중에는 잠시 대기한다는 의미
8. 두 번째 while문은 서로를 존중해주는 알고리즘
9. number가 0이라는 것은 아직 번호표를 받지 못했거나 이미 끝난 프로세스라는 의미(임계 영역에 들어가지 않겠다는 의미)
10. 어떤 번호가 0이 아니면 현재 자신의 번호와 비교하여 작은 지를 비교 -> 작다면 우선순위에서 밀리므로 대기
11. 만약 내 번호가 n개의 프로세스들의 번호 중에 가장 작다면 임계 영역에 들어간 후 번호를 0으로 바꿈
12. 우연하게 같은 번호의 번호표를 받을 경우에는 프로세스 고유번호를 비교하여 더 작은 프로세스가 먼저 임계 영역에 들어갈 수 있음
13. choosing과 number 또한 critical section문제를 가지기 때문에 이러한 조건을 준 것(동시에 같은 번호를 받을 수 있음)
14. 앞 시간에 배운 3가지 조건을 만족하는지 확인해볼 것

• Synchronization Hardware

• 베이커리 알고리즘은 훌륭하고 좋은 알고리즘(n개의 프로세스가 동시에 작동 가능) -> 모두 SW적으로 구현이 되어 있으므로 복잡함
• 이런 것들을 제공하는 하드웨어적인 명령어가 있고 제공받는 명령어가 CPU에 있다면? - Synchronization Hardware
• 조건을 판별해본 뒤에 한 word의 값을 바꾸거나 word사이의 내용을 바꿔치기하는 작업들을 Atomic 하게 처리
• Synchronization Hardware는 자신이 어떤 일을 하는 동안에 쪼개지지 않고 한 번에 실행되어야 함
• ex) test and set이라는 명령어

1. CPU의 하나의 명령어 - 쪼개지지 않고 atomic 하게 실행
2. 어떤 CPU가 혹은 어떤 hardware 시스템이 test and set 명령어를 지원한다면 쉽게 critical section을 구현 가능
3. lock이라는 boolean변수를 선언하고 TestAndSet(&lock - 주소)로 사용
4. 두 프로세스의 처리 속도가 다른 경우(Pi가 빠름(먼저 처리), Pj가 그 후)
5. TestAndSet에 들어간 Pi의 rv(리턴 값)가 flase가 되고 lock값은 ture가 됨 -> 그 후 임계 영역에 들어감
6. Pj는 그 후에 실행되는데, 아직 Pi가 임계 영역을 끝내지 않았으므로 lock은 아직 true이고 따라서 rv값 또한 true -> while문에서 대기
7. Pi가 나오면 lock이 false가 되고 Pj가 while문을 탈출하게 됨 -> 임계 영역 접근 가능
8. Pi는 Pj가 실행되는 동안 while문에서 대기

• 두 프로세스의 속도가 같은 경우를 생각해보자
• Swap이라는 명령도 존재하므로 232 page 환인하고 예제 해결해 볼 것

Semaphores(정수 변수)

• 영역을 나눠서 각각 하나씩 처리하는 것은 같지만(atomic) 실제로 돌아가는 것은 조금 다름
• 임계 영역 중 하나를 제외한 모든 프로세스들이 while문에서 대기 - Busy waiting(바쁜대기)

• 대기만 하는 것이 아니라 대기하는 동안 계속 무언가를 검사해야 함 - CPU 사용
• 동작을 하지는 않지만 동작하는 순간을 기다리기 위해 CPU를 사용 - CPU는 바쁘지만 일은 못함
• 불필요한 CPU의 동작이 문제

• 단지 두 개의 개별적인 atomic 한 연산(wait와 signal)을 가지고 접근 가능

• wait(S)

1. 만약 S값이 0보다 작거나 같으면 동작을 하지 않음(no-operation)
2. while문에 대기시키지 말고 no-op부분에서 할 수 있는 일을 시키라는 의미
3. S가 0보다 작거나 같은 동안에는 no-op를 실행하고 벗어나면 S값을 줄임

• Signal(S) : 단순하게 S를 증가시키는 연산

• Critical Section of n Processes

• 공동 semaphore인 mutex라는 변수를 공유 initially mutex = 1(1로 초기화)
• 사용 방식

1. P0가 접근 - 데이터 구조에 mutex를 1로 주고 wait에 넣음
2. mutex가 0보다 작거나 같지 않으므로 mutex 값을 1 감소시키고 critical section에 들어감
3. 그 후 P1이 들어왔을 때 mutexr값이 0이므로 no-op 실행(waiting 시킴 - CPU를 사용하지 않고 대기)
4. P0가 critical section을 벗어나면 mutex를 1 증가시킨 후(signal) remainder section실행
5. 그 순간 대기 중이던 P1은 waiting상태에서 ready queue로 넘어감
6. 어느 순간에 P1이 다시 CPU를 차지하게 되면 공유 변수인 mutex가 1이므로 wait에서 1 감소시킨 후 critical section에 들어갈 수 있음

• Semaphore Implementation

• semaphore의 정의

1. value값을 줌 - S
2. 프로세스 리스트를 만듦 -> block 시켜서 suspend시킴(waiting영역에 넣음) - 동작을 안 함
3. busy waiting 문제 해결

• 자세하게 살펴보자

1. wait(S)에서 Semaphore의 value값을 1 감소시키고 0보다 작을 경우 이 프로세스를 wait list에 집어넣고 block시킴(waiting)
2. signal(S)에서 value값을 1 증가시키고 만약 0보다 작거나 같을 경우 wait list에서 제외시키고 wakeup시킴
3. 운영 프로세스가 동작하는 것이 아니라 운영체제가 이 동작들을 맡아서 처리
4. 효율적으로 동기화 문제를 해결할 수 있음

• Semaphore as a General Synchronization Tool

1. 하나의 프로세스는 우선적으로 자신의 일을 하고 나머지 프로세스는 wait를 시킴
2. Pi가 critical section을 수행하는 동안 Pj는 wait
3. Pi가 다 끝난 후 signal -> Pj는 대기상태에서 나와 자신의 일을 수행
4. 운영체제 기능을 이용하여 Busy waiting을 안 하게 하는 것

• Deadlock and Starvation

• semaphore가 2개인 경우

1. P0는 S를 먼저 wait 하고 Q를 그 후에 wait 함, P1은 반대로 수행
2. 수행을 마친 후 순서대로 signal을 해줌
3. 프로세스 하나가 먼저 수행된 후 다음 프로세스가 수행되면 상관이 없지만 한 줄씩 번갈아가며 수행된다면 문제가 생김
4. critical section에 들어가기 전, S와 Q가 0보다 작아지게 되므로 두 프로세스 모두 blocking 됨
5. 두 프로세스 모두 blocking 되어 누군가 꺼내주기를 기다리지만 나갈 수 없는 상태가 됨 - deadlock(교착) 상태
6. 프로세스가 실행되면서 정해놓은대로 잘 진행되지만 한 프로세스가 계속 blocking 당하는 상황 - starvation상태

• Two Types of Semaphores

• Counting semaphore(계수) - 정수값에 제한을 가지지 않음
• Binary semaphore(이진) - 0 또는 1로 한정 -> 구현하기 쉬움(계수 세마포어도 구현 가능)

Classical Problems of Synchronization

• Bounded-Buffer Problem

• 공유 데이터 : full, empty, mutex;
• 초기값 : full = 0, empty = n, mutex = 1
• Producer Process

1. 첫 번째 wait는 비어있는지를 확인하는 것 - 채울 것이 있는 상태인지
2. 두 번째 wait는 사용할 수 있는지를 확인하는 것
3. 첫 번째 signal은 critical section 사용을 끝냈음을 의미
4. 두 번째 signal은 다 채웠음을 의미

• Consumer Process

1. 첫 번째 wait는 채워져 있는지 확인
2. 두 번째 wait는 사용할 수 있는지 확인
3. 첫 번째 signal은 다 사용했음을 의미
4. 두 번째 signal은 하나를 다 비웠음을 의미
5. 잘 보고 이해해볼 것

• Readers-Writers Problem

• text 파일을 편집하는 중에 이 파일을 다른 사용자가 열려고 할 때

1. 접근을 아예 하지 못하게 하는 방법
2. 파일을 편집 중임에도 불구하고 읽게 해 줄 수는 있음
3. 어떤 방식이든 하나의 방법(알고리즘)을 정해놓고 세마포어로 어떻게 해결할 것인지 살펴보는 것은 우리가 해야 할 일

• 공유 데이터 : mutex, wrt;
• 초기값 : mutex = 1, wrt = 1, readcount = 0
• 흐름

1. writer가 공유데이터에 배타적으로 접근(두 개 이상이 동시에 쓸 수 없음)
2. 데이터를 두 개 이상이 읽고 있다면 쓰기는 안됨
3. 어떤 기준을 가지고 동작하는지를 잘 봐야 함
4. 이 기준은 언제든 바뀔 수 있으며 바뀔 때 이미 짜여 있던 코드를 수정할 수 있어야 함

• Writer Process

1. 세마포어의 값을 확인하고 쓸 수 있는 상태면 write 해줌
2. 그 후 signal - 끝났음을 알림
3. 쓸 수 있느냐 없느냐를 확인하는 것

• Reader Process

1. 쓰는 사람은 하나밖에 없지만 읽는 사람은 여러 명이 될 수 있음
2. 첫 번째는 readcounter를 변경하기 위함
3. if문은 readcounter가 1일 경우(첫 번째 read process인지를 물어보는 것)
4. 첫 번째 read process일 때, 쓰는 중인 프로세스가 있는지 확인하는 것 -> 있으면 기다림
5. read counter가 2 이상이면 signal을 거쳐 아래 내용을 수행 -> 2개 이상이면 안 기다리고 바로 넘어간다는 의미
6. 첫 번째 read process가 기다리는 중에 다음 read process가 들어오더라도 첫 번째 wait에서 대기
7. write process가 끝나면 내려감
8. signal로 인해 mutex가 증가하고 대기하고 있던 나머지 read process들은 모두 readcounter를 증가시키면서 reading is performed부분으로 한꺼번에 들어감 -> 두 개 이상의 read process들은 동시에 읽을 수 있음을 의미
9. read가 끝나면 readcount가 1 감소
10. write는 그냥 할 수 있으면 write 하는 것이지만 read는 위와 같이 동작
11. 한 줄 한 줄 의미를 확인하며 잘 생각해볼 것
12. 읽는 동안에 다른 readers와 writers는 어떻게 동작해야 하는지를 잘 생각해볼 것

Background

• 야구 : 20명 정도의 선수들이 시합 -> 각자의 역할이 있음(투수가 공을 던져야 시작, 타자가 공을 치거나 포수가 공을 받음, 공이 어느 방향으로 가느냐에 따라 달라짐)

• 각 선수들을 스레드로 보면 각 스레드들은 독립적으로 하는 일이 정해져 있음
• 스레드들 간의 일부 순서가 있고 상호 순서가 지켜져야만 한다.
• 시스템 내의 상호 협조 프로세스 -> 다른 프로세스 실행에 영향을 받음, 주소 공간을 공유하거나 파일에 의해서 데이터의 공유가 허용됨
• 공유 데이터에 대한 동시 접근은 데이터의 불일치로 이어짐 -> 반드시 해결해야 됨

Bounded-Buffer

• Producer process

• in과 out이 같은지를 비교했을 때와 달리 정해진 크기의 BUFFER_SIZE와 같은지를 비교하도록 바꿨음
• count변수로 loop를 반복시킴

• Consumer process

• 값을 꺼낼 때 counter를 줄임 -> 포인터 대신 개수로 비교

• 수정된 알고리즘에는 counter라는 공유 변수가 있음
• 두 프로세스는 counter값을 변화시키면서 사용, 비교
• 어느 한순간의 counter가 5라고 가정
  • 두 프로세스가 한 번씩 counter에 접근한다면 5->6->5로 값이 변하는 것이 맞음
  • 그러나 count++와 count--는 CPU입장에서 하나의 명령인가?
• assembly에서 본 count++

1. register1 = counter -> CPU가 값을 레지스터에 읽어옴
2. register1 = register1 + 1 -> 그 레지스터 값을 1 증가시킴(아직 counter값은 5)
3. counter = register1 -> counter에 6을 저장

• count--

1. register2 = counter -> CPU가 값을 레지스터에 읽어옴
2. register2 = register2 - 1 -> 그 레지스터 값을 1 감소시킴
3. counter = register2 -> counter에 레지스터값을 저장

• 두 프로세스를 동시에 실행시켰다면 어셈블리에서 총 6개의 명령이 실행됨 -> 이것들이 무조건 순서대로 실행이 되는가? (x)
• 엄청나게 많은 프로세스의 사용이 반복된다면 정말 우연히도 6개의 명령이 섞일 수도 있음

• counter를 증가시키는 producer의 프로세스가 진행되는 중에 counter의 값을 바꾸기 전에 consumer의 프로세스가 실행되어 버림
• counter의 값이 6? 4? 나중에 바뀌는 값으로 들어가 버림 -> 오류 발생(counter를 다루는 명령어가 atomic하지 못했다.)

Race Condition

• 위의 문제점을 레이스 컨디션이라고 함 -> 한 프로세스에서만 접근하도록 만들어야 한다.
• 분리할 수 없는 명령이라고 생각하는 것이 섞이지 않도록 나누는 것(동기화)

Critical Section Problem(임계 영역)

• 두 개의 프로세스로 이루어진 시스템
• 각 프로세스는 임계 영역이라는 code segment내에 가짐
• 이 임계 구역은 공유 데이터를 처리하는 각각의 프로세스가 가지는 것
• 한 프로세스가 공유데이터를 처리하는 동안 다른 프로세스가 접근할 수 없는 구역
• 프로세스가 협조할 수 있도록 프로토콜을 설계
• 각 프로세스는 임계 구역에 진입하기 위한 허가권을 운영체제에 요청
• 진입 구역, 임계 구역, 출구 구역, 자유구역으로 나누고 그 구역에 맞게 처리해줌

1. 위와 같이 구역을 나눠서 생각
2. 임계 구역에 해당하는 부분은 분리되지 않음
3. 임계 구역 앞에 있는 것을 entry section, 뒤에 있는 것을 exit section이라고 함
4. entry section : 필요한 세팅, 설정, 관계없는 일들을 모아둠
5. exit section : 일부분, 임계 구역에 관련된 나머지 일들을 처리
6. remainder section : 위와 관련 없는 나머지 일들을 하는 부분

Solution to Critical-Section Problem

• 상호 배제(Mutual Exclusion) - p1가 임계 구역에서 실행된다면 다른 프로세스들은 임계 구역에서 실행될 수 없다.(단 하나만)
• 진행(Progress) - 임계구역에서 실행되는 프로세스가 없는 상태에서 임계 구역으로 진입하려는 프로세스가 있으면 잔류 구역에서 실행되지 않고 있는 프로세스들만 다음에 임계 구역으로 진입할 수 있는 대상이 되고 이 구역은 무한하게 연기할 수 없다.
• Bounded Waiting(한계 대기) : 프로세스가 임계 구역으로의 진입을 요청한 후에 그 요청이 허용될 때까지 다른 프로세스들도 임계 구역에 진입하도록 허용하는 시간 간격에도 한계를 두어야 한다.(무한하게 대기하면 안 됨)
• 각 프로세스들은 무조건 대기하는 것이 아니라 진행되고 있어야 한다.

• P0, P1은 turn이라는 공유 변수를 가짐
• 만약 turn이 i다 라는 조건을 만족하면 임계 구역으로 들어갈 수 있음
• i = 0, j = 1
• Pi : turn값이 i와 다르면 무한루프 -> 처음에는 같기 때문에 critical section으로 들어감
• 끝난 후 turn을 j로 바꿈 -> 나머지를 수행 -> 반복
• Pj : i가 실행되는 동안 while문에서 대기 -> turn이 j가 되는 순간 탈출 -> 임계 영역에 들어감
• 두 프로세스가 동시에 진행된다면? -> i와 j값이 다르므로 어쨌든 하나는 대기, 하나는 실행됨
• 상호 대기 만족
• turn은 0으로 초기화되었는데, P1이 먼저 들어왔다면 P0이 들어오기 전까지 기다려야 하므로 진행(Progress)과 한계 대기(Bounded Waiting)를 만족하지 못함
• 반드시 번갈아서 진행되는 알고리즘이므로 하나의 프로세스 실행 후 다음 프로세스가 응답하지 않을 시 대기해야 한다.

• 플레그 2개를 선언함 -> flag[i]를 true, j를 flase로 정함
• Pj는 플레그가 flase이므로 while문을 통과하여 Pi가 실행됨 -> Pj가 응답하지 않더라도 계속 Pi가 실행될 수 있음
• Pj는 flag[i]는 ture일 때 임계 구역에 들어가지 못하고 대기 -> Pi가 실행된 후 flase가 되는 순간 Pj가 실행됨
• Pj가 실행되는 동안, Pi 역시 임계 영역에 들어가지 못함
• 번갈아서 실행할 필요가 없어짐
• 상호 배제 만족, 그러나
• 두 프로세스가 타이트하게 문맥 교환을 하는 경우
  1. 한 줄씩 번갈아가며 실행된다고 가정해보자
  2. flag를 각각 true로 바뀌면 두 플래그가 전부 true로 바뀐 후 while문에 접근하므로 두 프로세스 모두 대기
  3. 두 플레그 중 하나가 바뀌어야 프로세스 하나가 실행될 수 있음

• 마지막 알고리즘 - Peterson's Solution

• 앞의 두 가지의 문제를 잘 종합하여 둘 다 쓰면서 아무 문제없이 진행될 수 있음

• 프로세스가 하나씩 실행되는지
• 대기하는 경우가 발생하는지
• 타이트하게 문맥 교환이 이루어질 경우

• Code Segment만 존재하는 예

• CODE SEGMENT로 시작 ASSUME으로 이름을 지정
• MOV로 AH, AL레지스터에 값을 대입 -> AX = 1234H
• ADD로 AH + AL 후 결과 값을 AH에 저장
• 프로그램을 종료할 때 빨간 네모 안의 명령을 실행 -> 인터럽트 호출(시스템 콜) - 트랩

• 데이터 정의 의사 명령어

• 데이터를 정의하기 위해 지시자가 필요
• Byte단위, word단위 등 단위가 정해져 있음
• 8086은 16bit이므로 DW를 사용
• 하나를 써도 되고 여러 개를 써도 됨 -> 콤마로 구분
• 초기값이 없는 경우 0자리에?를 넣으면 자리만 가지고 있고 값은 없음
• ex) 문자 출력 프로그램

1. 코드 세그먼트, 데이터 세그먼트가 각각 1개씩 존재
2. 실행은 별개의 문제이므로 데이터 세그먼트의 주소를 넘겨주기 위해 MOV AX, DATA와 MOV DS, AX를 써준다.
3. AX를 거치는 이유는 MOV명령에 데이터 이름을 레지스터에 바로 쓰는 경우가 존재하지 않기 때문 -> 범용 레지스터를 거쳐서 저장
4. INT 21H를 기점으로 나뉜다. -> 4CH는 프로그램을 종료, 2는 문자 하나를 콘솔에 출력하는 시스템 콜
5. DL에 A를 넣고 출력 -> CX에 4243H를 넣고 CH를 출력(42 - B) -> DL에 CL값(43 - C)을 넣고 출력

• 주소 지정 방식(Addressing mode)

• 즉치 주소 지정 방식(Immediate addressing)

ex) MOV AX, 1234H

ex) DAT EQU(define) 1234H

• 직접 방식(Register addressing; Direct addressing) - 레지스터의 내용을 직접 전송

ex) MOV AH, DH

     MOV DS, AX

ex) MOV AX, DH (X) -> 두 레지스터의 사이즈가 같아야 함

ex) MOV DX, [BX] -> 주소 값을 가져옴

• 간접 방식(Memory reference addressing; Indirect addressing) - 전송하는 값이 저장되어 있는 번지를 지정(값이 메모리 내에)

ex) MOV AX, DAT -> 변수 이름 = 데이터가 들어가 있는 번지

     MOV AX, [BX+DI+4] -> 번지의 내용(계산) pointer 개념

1. 없는 경우도 있음 -> 셋 중 하나 이상은 있어야 함
2. 숫자만 사용할 때 8bit만 가능
3. [BP + 0]으로만 사용 가능

1. Data segment는 없지만 Code segment에 데이터가 선언되어있음
2. 데이터가 있는 경우에는 반드시 MOV AX, CODE와 MOV DS, AX를 사용
3. MOV BX, OFFSET BUFFER는 BUFFER의 주소 값을 BX에 넣는다는 의미 -> e를 가리킴
4. BX+SI는 e에서 2칸 옆, 즉 a를 가리킴 -> a를 출력 -> +1 -> m을 출력
5. CR후 LF는 줄 바꿈
6. +2를 해서 p가 출력 -> 프로그램 종료

1. 주소를 나타내는 값을 쓰고자 할 때, 크기를 지정해줌(BYTE, WORD 등)

• 역 워드 형식 - 순서를 바꿔서 저장

1. 4243H의 경우 43 42로 저장

• 덧셈 명령

• OP1에 OP2를 더해서 OP1에 저장
• ADC의 경우 Carry Flag도 더해줌

1. 32비트끼리 연산의 경우 16비트 자리를 각각 정해서 따로 더한 후 합침
2. 올림이 발생하는 경우에 Carry Flag도 더해줌 -> ADC사용

1. ADD를 사용하는 BX와 DX는 하위 16비트, ADC를 사용하는 AX, CX는 상위 16비트
2. 응용

CODE SEGMENT
ASSUME CS:CODE, DS:DATA
	MOV AX, DATA
	MOV DS, AX

	MOV AX, VAR1
	MOV BX, VAR2
	MOV CX, VAR3
	MOV DX, VAR4

	ADD BX, DX
	ADC AX, CX
	MOV VAR1, AX
	MOV VAR2, BX

	MOV AH, 4CH
	INT 21H
CODE ENDS

DATA SEGMENT
	VAR1	DW	1223H
	VAR2	DW	8000H
	VAR3	DW	2000H
	VAR4	DW	8123H
DATA ENDS

END

CODE SEGMENT
	ASSUME CS:CODE, DS:DATA
	
	MOV AX, DATA
	MOV DS, AX

	MOV AX, VAR1
	ADD AH, AL

	MOV VAR2, AH

	MOV AH, 4CH
	INT 21H

CODE ENDS

DATA SEGMENT
	VAR1	DW	1234H
	VAR2	DB	?
DATA ENDS

END

CODE SEGMENT
	ASSUME CS:CODE, DS:DATA

	MOV AX, DATA
	MOV DS, AX

	MOV BX, OFFSET VAR1

	MOV AH, [BX]
	MOV AL, [BX+1]

	ADD AH, AL
	MOV VAR2, AH

	MOV AH, 4CH
	INT 21H

CODE ENDS

DATA SEGMENT
	VAR1	DW	1234H
	VAR2	DB	?
DATA ENDS

END

• 응용 프로그램 - 분기와 반복

• 증가, 감소 명령

1. INC에 OP(레지스터나 메모리)를 넣으면 1 증가
2. DEC에 OP를 넣으면 1 감소
3. 16비트, 8비트 둘 다 가능

• 키 입력 방법

1. 키보드에서 입력받을 수 있음
2. 에코가 있는 입력은 AH 1번, 없는 입력은 AH 8번 -> 화면에 출력되는지 안되는지의 차이
3. 키보드로부터 입력을 받을 때까지 기다림 AH로 시스템 콜을 호출하고 입력받은 값을 AL에 저장
4. 입력받은 값들을 차례대로 출력

• 비교 명령어

1. 비교하여 같으면 플레그를 1로 만들고 다르면 0으로 만듦
2. 플레그 값에 따라 명령을 달리 수행

1. 두 값의 AND연산 결과에 따라서 플레그를 달리해줌
2. CL이나 ZF의 값이 변하면서 플레그가 달라짐

• 분기 명령어의 비교

1. AX와 0을 비교
2. 같으면 JE를 0으로
3. 플레그의 값에 따라 점프하는 라인이 달라짐

1. 값을 입력 받음
2. DL에 저장
3. DL값을 1 증가시킨 후 출력
4. JMP로 다시 처음으로 돌아감 -> 무조건 분기(무한루프)

1. AX = 0, CX = 1
2. AX + CX = 1
3. CX += 1
4. CX와 10 비교
5. JBE -> 작거나 같으면
6. SUM10으로 돌아감
7. 11이 되는 순간 JBE를 안 거치고 다음으로 넘어감 -> 10번 반복
8. 1~10까지 AX에 더한 것을 TOTAL에 저장

1. A : 크다
2. B : 작다
3. E : 같다
4. N : 아니다
5. A> B이면 JA -> CMP A, B 후에 JA를 쓰면 A가 큰 경우의 조건문 => JNBE는 작거나 같지 않다(크다)
6. A>=B이면 JNB(작지 않다), JAE(크거나 같다)

1. 플레그 레지스터를 이용한 분기
2. 한 번 읽어볼 것

1. 에코 있는 입력을 받음, AL에 저장
2. 20H(스페이스)와 비교
3. 같으면 EXIT로 점프 -> 프로그램 종료
4. 아니면 'A'와 비교
5. 'A'보다 작으면 PRINT로 점프 -> 입력받은 값을 출력 -> NEXT로 돌아가서 다시 입력 받음
6. 아니면 'Z'와 비교
7. 'Z'보다 크면 PRINT
8. 위의 조건들을 살펴보았을 때, 스페이스를 입력받으면 프로그램 종료, A보다 작으면 출력, Z보다 크면 출력이므로 대문자 A~Z까지의 문자만 조건문에 걸리지 않고 넘어갈 수 있음
9. 대문자인 경우 AL에 'a' - 'A'(대소문자 차이)를 더해줌 -> 대문자를 소문자로 바꿔줌
10. 소문자를 출력
11. 대문자를 소문자로 바꾸는 경우도 생각해보자

• 예제

CODE SEGMENT
	ASSUME CS:CODE
	MOV CX, 10

LOOP1:	MOV AH, 8
	INT 21H

	CMP AL, 20H
	JE EXIT

	CMP AL, 'a'
	JB PRINTZ

	CMP AL, 'z'
	JA PRINTZ

	MOV DL, AL
	MOV AH, 2
	INT 21H

	LOOP LOOP1

EXIT:	MOV AH, 4CH
	INT 21H

PRINTZ:	MOV DL, '0'
	MOV AH, 2
	INT 21H
	DEC CX
	CMP CX, 0
	JE EXIT
	JMP LOOP1

CODE ENDS
END

• 반복 명령어

1. LOOP는 CX의 값을 필수로 사용 -> 카운터의 기능
2. CX의 값만큼 반복 -> 1씩 줄여가며 반복
3. 중간에 CX값을 바꿔버리면 횟수가 바뀌어 무한루프가 발생할 수 있음

1. 참고만 할 것 -> 너무 깊다!

• 응용 코드 작성

1. 모델 스몰 부분은 그대로 써줌
2. 스택 - 시작 부분
3. 데이터 - 데이터 세그먼트 대신에 써줌 - 더 간편하게 사용 가능
4. @data : get data segment -> 반드시 써야 하는 부분, 세그먼트 이름 대신에 써야하는 것
5. 나머지 부분은 포맷, 똑같이 써도 되고 이전에 배운 것들처럼 써도 됨
6. int 21h의 9번 기능 -> 2번은 문자 하나, 9번은 문자열을 출력
7. 문자가 끝나는 부분은 $로 끝을 냄 -> 처음부터 $전까지 출력
8. dx에 prompt의 시작 주소를 넣어줌 -> 시작 주소의 문자열을 출력($까지)
9. 21번 -> 에코 있는 입력
10. 입력받은 값에서 20h를 빼고 char에 저장
11. msg의 시작 주소를 dx에 넣고 출력 -> 0Dh.0Ah. 는 줄 바꿈
12. 9번은 시작 주소로부터 $까지 출력하는 함수
13. 실행 예

• 도스 command line에서의 실행 예

• 스택의 동작

• 16bit 컴퓨터이므로 push와 pop은 2byte씩 이루어짐
• push로 OP의 값을 stack에 저장, pop으로 stack의 데이터를 OP에 저장

1. AX, BX PUSH
2. PUSHF는 플레그를 PUSH 한다는 의미
3. POP은 OP를 꺼낸다는 뜻이 아니고 정해진 순서대로 꺼내서 OP에 저장한다는 의미

• 서브루틴 사용법

• 서브루틴은 C언어에서 위치를 호출하는 것
• CALL은 되돌아올 주소를 자동으로 stack에 저장한 후 lable로 점프 -> 진행하다가 return을 만나면 저장해 두었던 주소를 pop 하여 되돌아감

1. 레이블을 콜 하여 점프 후 RET를 만나면 다시 돌아감

• 잘 읽어보고 만들어볼 것
• 정답

• 코드를 이해하여 앞과 비교해보고 직접 작성도 해볼 것
• AND와 SHIFT를 사용한 코드

CODE SEGMENT
	ASSUME CS:CODE, DS:DATA

	MOV AX, DATA
	MOV DS, AX
	MOV CX, 12

LOOP1:	MOV DX, VAR1
	SHR DX, CL
	AND DX, 000FH

	CMP DL, 0AH
	JAE LEVEL1
	
	ADD DL, '0'
	MOV AH,2
	INT 21H
	
	CMP CL, 0
	JE EXIT

	SUB CL, 4

	JMP LOOP1

LEVEL1:	ADD DL, 'A'-0AH
	MOV AH,2
	INT 21H

	CMP CL, 0
	JE EXIT

	SUB CL, 4

	JMP LOOP1

EXIT:	MOV AH, 4CH
	INT 21H

CODE ENDS

DATA SEGMENT
	VAR1	DW	2B3FH

DATA ENDS

END

• 10진수 출력

CODE SEGMENT
	ASSUME CS:CODE, DS:DATA

	MOV AX, DATA
	MOV DS, AX

	MOV CX, 0
	MOV AX, 0

	MOV AX, VAR1
	MOV SI, 10

LOOP1:
	MOV DX, 0
	DIV SI
	PUSH DX
	INC CX
	CMP AX, 0
	JNE LOOP1

PRINT:	
	POP DX
	ADD DL, '0'
	MOV AH, 2
	INT 21H
	
	DEC CX
	CMP CX,0
	JNE PRINT

	MOV AH, 4CH
	INT 21H

CODE ENDS

DATA SEGMENT

	VAR1	DW	1234H

DATA ENDS

END

• PROC에 의한 서브루틴 작성 - 참고

• System Call의 예

• 비디오 스테이터스를 돌려줌
• 설명
• 입력값을 주면 하는 일, 출력 값

• 스크롤을 up, down 해주는 시스템 콜

• prompt를 어디로 옮길 것인지
• 커서 포지션
• 예제들 -> 동작시켜볼 것

• 예제의 내용

1. 출력한 것을 박스 안에서 스크롤할 수 있음
2. 출력해놓고 스크롤시키는 프로그램
3. 응용으로 스크롤 속도를 늦추거나 반대방향으로 스크롤 되게 수정해볼 수 있음 -> 이것도 해볼 것

• PC Assembly

• 데이터를 만들어주고 결과를 확인하기 위해 시스템 콜들을 이용

• 컴파일&실행 파일 만드는 법

• DOS Box 설치 / MASM 폴더 복사 / 폴더 Mount

• 윈도우 환경의 Editor로 편집

CODE	SEGMENT
	ASSUME		CS:CODE ,DS : DATA

	MOV	AX, DATA
	MOV	DS, AX

	MOV DL, SCR_1
	MOV AH, 2
	INT 21H

	MOV CX, SCR_2
	MOV DL, CH
	MOV AH, 2
	INT 21H

	MOV DL, CL
	MOV AH, 2
	INT 21H

	MOV AH, 4CH
	INT 21H

CODE ENDS

DATA SEGMENT
SCR_1 DB		'A'		; 1 Byte
SCR_2 DW	4243H		; 2 Byte
DATA ENDS
	END

• Dos Box에서 Masm sample.asm

• Link ascii.obj
• 혹은 ml sample.asm
• 실행

1. 위의 사진처럼 dir dtype이라는 명령어를 입력하면 exe파일이 생긴 것을 확인할 수 있다.
2. cv /s dtype -> dtype만 호출해도 실행이 가능하지만 디버그를 하고 싶다면 cv /s를 앞에 붙여주어야 한다.

• 어셈블리에서 데이터들이 바뀌는 방식 등을 자세히 볼 수 있음

• Data type의 저장 방법

• 시스템 콜들의 비중이 매우 높은 것을 알 수 있음

• MASM에 의한 프로그램 개발 과정

• 여러 개의 파일을 묶어서 실행파일을 만들 수 있다.(동시 실행 가능)
• Object 파일들을 묶어놓은 것을 정적 라이브러리라고 한다.
• 소스는 달라도 오브젝트 파일로 만들어 묶으면 하나의 실행파일로 만들 수 있다.(exe, com)

• CPU의 명령어 실행 과정

• 명령어 인출(Instruction Fetch Cycle) : 실행할 명령어를 기억 장치로부터 읽어오는 과정
• 명령어 해독(Instruction Decode Cycle) : 읽어온 명령어를 해독하는 과정
• 데이터 인출(Data Fetch Cycle) : 데이터가 필요한 경우 데이터를 읽어오는 과정
• 실행 사이클(Execution Cycle) : 프로세서가 명령어를 실행하는 과정

• 8086 계열(16bit)

• Register : Data 저장, 연산 등을 위한 임시 기억 장치
• 각 레지스터는 자체의 특수한 용도와 제한점이 있다.
• 장점 : Memory(변수) 보다 access 속도가 빠르다.
• 단점 : 개수가 한정되어 있고, 용도가 제한적이다.
• 종류

1. 범용 register : 8개(8086)
2. 세그먼트 register : 4개(메모리 공간을 나타냄)
3. 프로세서 컨트롤 register : 2개
4. 총 14개의 register

• AX, BX, CX, DX : 범용 레지스터(General Purpose Register) - Accumulator Register, Base Register, Counter Register, Data Register
• SP, BP, SI, DI : 위치, 주소를 나타내는데 사용(포인터를 사용하기 위한 용도) - Stack Pointer, Base Pointer, Source Index, Destination Index
• 각각 16bit를 가지지만 8bit씩 가지고 사용하는 경우도 있음(AL + AH = AX) -> 공용체 구조
• Segment Register : {CS(Code Segment Register), DS(Data Segment Register)}, SS(Stack Segment Register), ES(Extra Segment Register)
• Processor Control Register : IP(Instruction Pointer - 어떤 위치의 명령어를 수행할 것인지), FL(Flag Register - 어떤 상태가 어떤 이유로 변했는지 알려주기 위한 flag)

• Register의 기능

• 어떤 메모리 공간을 나타낼때 사용하는 segment(덩어리)
• 그 세그먼트로부터 얼마나 떨어져 있는지 알려주는 offset
• CS(CODE Segment - 시작 주소)에서 IP가 가지고 있는 명령어의 위치를 실제 주소로 계산
• Data는 DS에 있는 offset값과 변위 값을 계산해서 사용
• SS:SP를 가지고 Stack동작
• 세그먼트 : offset이 정해진 형태

• Flag Register

• ex)Over flow가 발생했을 때 O라는 플래그가 1이 됨

• 8086의 주소 지정

• 8086 프로세서는 1MB까지의 memory를 취급(00000H~FFFFFH)
• 1MB = 2^20b => address data로 20 bit 필요
• 8086의 register는 16bit 크기이기 때문에 2개의 register를 조합

1. 1개는 segment 1개는 offset으로 정함
2. 세그먼트의 비트를 왼쪽으로 한 칸 옮긴 후(가상으로 0 하나를 붙임) 더함

• CS는 코드 세그먼트, DS는 데이터 세그먼트
• 0이 하나 붙어있기 때문에 1이 늘어났어도 실제로는 16이 늘어난 것

• 10000(segment) + 1000(offset) = 11000
• segment와 offset의 값에 따라 각자 값이 다르더라도 같은 주소 위치를 나타낼 수 있음

• 명령의 구성

• 뒤에서 앞으로 실행
• 의사 명령 : 예제 프로그램이 돌아가도록하는 MOV AX, BX을 제외한 L1과 같은 코드를 의미, 코드에 필요
• OP code(연산자)와 Operand(피연산자)는 반드시 필요
• Label은 특별한 경우에 붙이고 대부분 필요 없음
• Comment는 명령에 대한 간단한 설명을 붙이는 것 -> 어셈블하면 기계어 code로 변환되지 않고 단지 설명일 뿐

• 의사 명령어(Pseudo Code) : label이나 ASSUME, SEGMENT, ENDS, DB 등
• 프로그램의 초기 작성

• 세그먼트 선언

1. Code Segment, Data Segment, Stack Segment 중 필요한 Segment를 선언
2. Code Segment는 반드시 선언

1. segment의 이름은 시작과 마지막이 같아야 한다.
2. Code segment는 프로그램 code, data segment는 필요한 데이터, Stack segment는 필요한 크기의 메모리 영역을 확보한다.
3. 실제 프로그램이 아니라 전체적인 프로그램 형태이기 때문에 의사명령어라 함 -> 프로그램을 만들어가는 과정에 사용하는 것, 적용될 때는 추가적인 것들을 더 사용해야 함

• ASSUME 의사 명령어

• ASSUM에 CS는 CODE에 있고 DS는 DATA에 있다고 가정해줌
• 프로그램 전체가 끝나면 END를 써줌 -> ENDS는 Segment가 끝났다는 의미
• 예제

1. Code 세그먼트 하나만 있음
2. Data, stack, 엑스트라 세그먼트 모두 없음
3. ASSUME이 시작점으로 잡힘, DS는 자동으로 잡히지 않음
4. 명령어 수행

• 명령어의 구성과 기계어 생성

• 인텔 사이트에서 명령어 세트 찾을 수 있음

• 구글에서 24319102.pdf를 검색하는 것이 빠를 수 있음
• MOV의 경우

1. 9개의 형태를 가짐
2. Operand는 2개
3. imm은 실제 숫자, reg16은 16비트 레지스터, segreg는 세그먼트 레지스터
4. MOV는 뒤의 값을 앞의 값에 복사하라는 명령어
5. imm을 imm으로 넣지 못함, mem에서 바로 mem으로 옮기지 못함, segreg에서 segreg로 바로 옮기지 못함

• 여러 CPU에 따른 명령어들

• MOV reg,reg는 보통 2 클럭이면 처리가 됨, immed to reg는 4 클럭으로 처리 -> 어디에서 어디로 가져오느냐에 따라 클럭 수가 바뀜

• 곱셈(MUL)은 MOV보다 매우 많은 시간이 소요됨 -> 따라서 보통 shift연산을 함

• 해독(Decoding)

• 9가지에 따라 세부적으로 다시 나뉘어짐
• 해석하는 과정이 필요

1. 처음 6비트는 opcode(명령어)로 사용, d는 direction, w는 word
2. mod는 mode(뒤에 있는 것들을 어떻게 할 것인지), reg는 레지스터, rm은 레지스터 혹은 메모리
3. 예시

• MOD 자리에 00을 쓰면 R/M Table 1에서 사용, 01 10 11 모두 테이블이 정해져 있음

• ex) MOV AL, BL

1. reg에서 reg는 100010이라는 OP코드를 가지고 있음
2. BL -> AL의 연산에서 d가 0이면 REG에서 R/M으로 가는 것이므로 BL은 REG에 AL은 R/M에 넣는다.
3. d가 1이면 R/M에서 REG로의 연산이 되어 BL을 R/M에 넣고 AL을 REG에 넣는다.
4. 이 예시는 d가 1일 경우이다.
5. 위의 REG filde에서 BL은 011, AL은 000이므로 각 자리에 값을 넣어준다.
6. reg -> reg이므로 mod는 11
7. d는 1, w는 byte단위로 사용 중이므로 0
8. 이를 모두 이어서 4개씩 끊어 읽으면 8AC3이 됨

• ex) MOV AL, BL 반대(d가 0일 경우)

• 다른 것들도 해보자