< 미션 제출 방식 흐름 설명 >

여기에는 크게 두 가지 역할이 존재한다.

1. ** 드라이버(Driver)**
   • 키보드와 마우스를 직접 다루며 코드를 작성하는 사람
   • 실시간 피드백을 받아 바로 코드에 반영

2. ** 내비게이터(Navigator)**

   • 코드의 방향성과 아이디어를 제시하는 사람
   • 전체적인 흐름을 살펴보고 오류나 개선점을 찾아 제안

   하지만, 현실에서는 “내비게이터의 조언을 받아 드라이버가 따라간다”는 단순한 역할 구분보다는 둘이 함께 머리를 맞대고 더 효율적인 코드를 작성하기 위해 고민하는 과정에 조금 더 가깝다.

< 예제 풀어보기 (13주차-1번) >

< 초기 전제 >

node* ar[9] = { NULL };  
// ar는 노드 포인터를 저장하는 배열
// 1~8번 노드 사용(노드 아이디가 1~8)로 주어지기 때문

---
## < 노드 구조 >
>
<img src="https://velog.velcdn.com/images/hyebin_s/post/e6c73a95-a109-4e93-b3d4-7e3c2b271172/image.png" width="300"/>
>
``` c
typedef struct node {
    int id, data;
    struct node* left, * right;
} node;
//id는 노드의 번호, data는 노드 안의 값
//left는 노드의 왼쪽 노드의 주소, right는 노드의 오른쪽 노드의 주소

< 노드 생성하기 >

node* newnode(int id, int data) {
    node* n = (node*)malloc(sizeof(node));
    n->id = id;
    n->data = data;
    n->left = NULL;
    n->right = NULL;
    return n;
}

< 노드 초기값 넣기 >

void init_nodes(node* ar[]) {
    ar[1] = newnode(1, 20);
    ar[2] = newnode(2, 30);
    ar[3] = newnode(3, 50);
    ar[4] = newnode(4, 70);
    ar[5] = newnode(5, 90);
    ar[6] = newnode(6, 120);
    ar[7] = newnode(7, 130);
    ar[8] = newnode(8, 80);
}

< 노드 연결하기>

void connect_nodes(node* ar[]) {
    ar[1]->left = ar[2];
    ar[1]->right = ar[3];
    ar[2]->left = ar[4];
    ar[2]->right = ar[5];
    ar[3]->right = ar[6];
    ar[6]->left = ar[7];
    ar[6]->right = ar[8];
}

⭐️ 의사코드 -> c언어 코드가 되는 과정에 집중

< 선위순회(전위순회) >

선위순회란?

[루트 - 왼쪽 자식 - 오른쪽 자식] 순으로 순회하는 것

< 중위순회 >

중위순회란?

[왼쪽 자식 - 루트 - 오른쪽 자식] 순으로 순회하는 것

< 후위순회 >

후위순회란?

[왼쪽 자식 - 오른쪽 자식 - 루트] 순으로 순회하는 것

참고 ) isInternal함수

//내부 노드인지 확인
int isInternal(node* root) {
    return root->left != NULL || root->right != NULL;
}

질문사항 있으면 언제든 질문해주세용....👍

스택이란?

가장 마지막에 추가된 데이터를 가장 먼저 내어주는 자료구조 즉, 후입선출(Last-In First-Out, LIFO) 원칙을 따름

⭐️ 스택의 주요 특징

삽입과 삭제는 항상 top(맨 위) 에서 이루어짐 ex: 워드의 '되돌리기' 기능 → 가장 마지막에 한 작업부터 거꾸로 하나씩 취소

< 예제 풀어보기 (9주차-1번) >

⭐️ 의사코드 -> c언어 코드가 되는 과정에 집중

초기 전제

int t, N; //전역변수
// t는 top의 위치를 의미
// N은 스택의 size를 의미

< 스택 초기화 >

//1. 스택 초기화
t = -1;

<img src="https://velog.velcdn.com/images/hyebin_s/post/e4faa062-e3a7-42df-8947-06c01c3d3c4e/image.png" width="400"/>


---

## < 스택 PUSH(삽입) >
> <img src="https://velog.velcdn.com/images/hyebin_s/post/d726151b-009b-4d51-ad62-f8bced8d8ec7/image.png" width="600"/>

>``` c
void push(char *stack, char c){
    // 1. 스택이 가득 찼는지 확인
    if(t == N-1){
        printf("Stack FULL\n");
        return;
    }
    // 2. top 한 칸 올리기
    t = t+1;
    // 3. top 위치에 원소 추가
    stack[t] = c;
    // 4. 함수 종료
    return;
}

< 스택 POP(삭제) >

char pop(char *stack){
    //1. 스택이 비었는 지 확인
    if(t <= -1){
        return printf("Stack Empty\n");
    }
    //2. top 한 칸 내리기
    t = t-1;
    //3. 기존의 top 원소 반환
    return stack[t+1];
}

<img src="https://velog.velcdn.com/images/hyebin_s/post/28a12e7a-8ce5-4063-87fb-4f59f759e234/image.png" width="400"/>

---

## < 스택 Peek(top 원소 반환) >
> ``` c
char peek(char *stack){
    //1. 스택이 비었는 지 확인
    if(t <= -1){
        return printf("Stack Empty\n");
    }
    //2. top 원소 반환
    return stack[t];
}

< 스택 DUPLICATE >

//top 원소를 꺼내서 두 번 다시 넣기

void duplicate(char *stack){
    //1. 스택 크기 확인
    if(t >= N-2){
        printf("Stack FULL\n");
        return;
    }
    //2. top에 있는 원소 삭제
    char c = pop(stack);
    //3. 삭제한 원소 2번 삽입
    push(stack,c);
    push(stack,c);
    // 4. 함수 종료
    return;
}

![](https://velog.velcdn.com/images/hyebin_s/post/d04de27f-80d3-40a5-8ea1-5895a702d028/image.png)

---
## < 스택 upRotate >
#### //stack의 맨 위 n개의 원소를 위쪽으로 회전
>``` c
void upRotate(char *stack, int n) {
    //1. 스택 사이즈 구하기
    int stackSize = t+1;
    //2. 회전할 원소의 개수가 스택의 크기보다 큰 지 확인
    if (stackSize < n) return;
    //3. top의 원소 임시 저장 
    char tmp = stack[t];
    //4. 맨 위 n개의 원소를 한 칸씩 위로 이동
    for (int i=0; i<n-1; i++) {
        stack[t-i] = stack[t-i-1];
    }
    //5. 원래 top이였던 값을 top의 n번째 아래에 넣기
    stack[t-(n-1)] = tmp;
    //6. 함수 종료
    return;
}

< 스택 downRotate >

//stack의 맨 위 n개의 원소를 아래쪽으로 회전

void downRotate(char *stack, int n) {
    //1. 스택 사이즈 구하기
    int stackSize = t+1;
    //2. 회전할 원소의 개수가 스택의 크기보다 큰 지 확인
    if (stackSize < n) return;
    //3. top의 n번째 아래에 있는 값 임시 저장
    char tmp = stack[t-(n-1)];
    //4. 맨 위 n개의 원소를 한 칸씩 아래로 이동
    for (int i = n-1; i >0; i--) {
        stack[t-i] = stack[t-i+1];
    }
    //5. 원래 top의 n번째 아래에 있던 값을 맨 위에 넣기
    stack[t] = tmp;
    //6. 함수 종료
    return;
}

```

스택이 생소해서 그렇지, 전혀 어렵지 않으니까 이거 참고하셔서 문제 풀어보시고 모르는 거 있으시면 언제든 질문해주세요 🐢

리스트는 데이터를 일렬로 저장하는 자료구조 ex)

< 초기 가정 >

전역변수 int n; node *H, *T;

< 노드 구조체 >

//노드 구조체
typedef struct node {
    char elem;
    struct node *prev, *next;
} node;

< 리스트 초기화 >

// 리스트 초기화
void initialize() {
    // 동적할당
    H = (node *)malloc(sizeof(node));
    T = (node *)malloc(sizeof(node));
    // 헤더와 트레일러를 연결
    H->next = T;
    T->prev = H;
    H->prev = NULL;
    T->next = NULL;
    // 리스트 크기 0으로 초기화
    n = 0;
}

node **H는 포인터를 가리키는 포인터 (즉, 포인터 자체를 변경할 수 있음)

< 노드 삽입 >

// 삽입
void add(node *list, int r, char e) {
    // 범위 확인
    if (r < 1 || r > n + 1) {
        printf("invalid position\n");
        return;
    }
    //삽입할 위치까지 이동
    node *p = list;
    for (int i = 0; i < r; i++) p = p->next;
    //노드 삽입
    addNodeBefore(p, e);
    //리스트 크기 1증가
    n++;
}
// p 노드 앞에 삽입
void addNodeBefore(node *p, char e) {
    // 새로운 노드 q 만들기
    node *q = (node *)malloc(sizeof(node));
    // 새로운 노드 q 연결
    q->elem = e;
    q->prev = p->prev;
    q->next = p;
    // 기존 노드 p 재연결
    p->prev->next = q;
    p->prev = q;
}

< 노드 삭제 >

// 삭제
void delete(node *H, int r) {
    //범위 확인
    if (r < 1 || r > n) {
        printf("invalid position\n");
        return;
    }
    //삭제할 위치까지 이동
    node *p = H;
    for (int i = 0; i < r; i++) p = p->next;
    // 노드 삭제
    removeNode(p);
    //리스트 크기 1 감소
    n--;
}
// 노드 삭제
void removeNode(node *p) {
    // 삭제할 노드의 양옆 노드를 서로 연결
    if (p->prev != NULL) p->prev->next = p->next;
    if (p->next != NULL) p->next->prev = p->prev;
    // 삭제할 노드 동적할당 해제
    free(p);
}

< 특정 노드 값 get >

// r번째 노드 값 출력
void get(node *H, int r) {
    //범위 확인
    if (r < 1 || r > n) {
        printf("invalid position\n");
        return;
    }
    //출력할 노드 위치까지 이동
    node *p = H;
    for (int i = 0; i < r; i++) p = p->next;
    // 출력
    printf("%c\n", p->elem);
}

< 전체 리스트 출력 (순회)>

// 전체 리스트 출력
void print(node *H) {
    // 트레일러 전까지 리스트를 순회하며 출력
    node *p = H->next;
    while (p != T) {
        printf("%c", p->elem);
        p = p->next;
    }
    printf("\n");
}

< 리스트 동적할당 해제 (재귀 ver)>

void putNode(node *p) {
    if (p != NULL) {
        putNode(p->next);
        free(p);
    }
}

---
## < 리스트 동적할당 해제 (비재귀 ver)>
>```c
void freeList(node *H) {
    node *cur = H;
    while (cur != NULL) {
        node *tmp = cur;
        cur = cur->next;
        free(tmp);
    }
}

• main에 scanf(" %c",&mode);라고 써야함

• 공백 문자(' ')를 넣는 이유는 버퍼에 남아 있는 공백 문자(특히 개행 문자 \n)를 무시하기 위해서...

< 배열이란? >

같은 종류의 데이터를 줄 세워서 저장하는 자료구조

< 2차원 배열이란? >

배열 안에 배열이 들어 있는 구조 즉, 행(row)과 열(column)로 이루어진 표 형태의 배열

< 동적할당이란? >

필요할 때 메모리를 그때그때 요청해서 사용하는 것 (빌린 메모리를 반환하는 과정도 필요함)

< 2차원 배열 동적할당 >

//동적할당 
arr = (int **)malloc(n * sizeof(int *)); // 행 크기만큼
for (i = 0; i < n; i++) { // 열 행 크기만큼
    arr[i] = (int *)malloc(m * sizeof(int));
}
.
.
//메모리 사용
.
.
//동적할당 해제
for (i = 0; i < n; i++) { // 열의 해제
    free(arr[i]);
}
free(arr); //행의 해제

조건을 만족할 때까지 함수가 자기 자신을 다시 호출하는 방법

< 재귀의 기본 규칙 >

1. 베이스 케이스를 항상 가져야함
2. 재귀호출은 항상 베이스케이스를 향하는 방향으로 진행

• 만약 베이스 케이스가 없다면?

• 만약 베이스 케이스를 향하지 않는다면?

< 재귀의 핵심 >

깊이 파고들었다가 베이스 케이스에 도달한 뒤, 쌓인 호출들을 거꾸로 돌아오면서 하나씩 처리하는 구조

< 이 개념들을 실습에 적용하기 >

코드 ex)-> 베이스 케이스가 존재하는가? 0 -> 재귀 케이스가 베이스케이스를 향하는 가? 0

흐름 ex)

• 추가) 실습 5번 하노이 탑 문제 : 저는 개인적으로 이 문제가 가장 어려웠는 데요. 이런 문제가 익숙치 않아서 그렇지, 어려운 개념은 아니니까 편하게 앞으로 오시면 쉽게 설명드릴게요!!

  어려울 땐 이 그림을 잘 떠올려 보세요 :)from: 시작 aux : 임시 버퍼 to: 도착

1. Delegate-based Creator 생성자의 매개변수가 JSON 전체(객체 전체)라고 판단하고 처리

ex) 이 객체 전체가 매개변수구나

{
    "name":"sejong"
}

2. Property-based Creator 매개변수가 JSON의 특정 필드라고 판단하고 처리

ex) 이 객체안의 name이라는 값이 매개변수구나... "name":"sejong"

<오류사항> 생성자의 매개변수가 2개 이상일 경우 Property 방식으로 처리가 되지만 매개변수가 1개일 경우 Delegate 방식으로 처리할 지, Property방식으로 처리할 지 모호성이 생기므로 오류가 발생

<해결방법> 생성자 위에 @JsonCreator(mode = JsonCreator.Mode.PROPERTIES)을 붙여 Property방식으로 매개변수 처리방식을 명시적으로 나타내주면 됨

라우터와 스위치는 모두 네트워킹 연결장치입니다.

다른 점:

(1) 네트워크의 연결 범위:

• 스위치는 동일한 네트워크(ex: 로컬 네트워크) 내에서 장치들 간의 연결을 관리합니다.
• 라우터는 서로 다른 네트워크(ex: LAN과 인터넷) 간의 연결을 관리합니다.
• LAN? Local Area Network의 약자

  (2) 주소 체계:

• 스위치는 MAC 주소를 기반으로 장치 간의 데이터를 전송합니다.
• 라우터는 IP 주소를 기반으로 네트워크 간의 데이터의 전송합니다.

• MAC이란? Media Access Control Address의 약자로 네트워크 내에서 장치를 식별하는 고유한 하드웨어 식별자입니다. 주로 이더넷(Ethernet) 또는 Wi-Fi 네트워크에서 장치들이 서로 통신할 때 사용됩니다.

  • 이더넷? 주로 유선 네트워크를 의미

• IP란? Internet Protocol Address의 약자로IP 주소는 네트워크 상에서 장치들이 서로 통신하기 위해 사용하는 논리적 주소입니다.

(3) 데이터 전송의 역할

• 스위치는 네트워크 내에서 패킷을 전달하여 충돌을 최소화합니다.
• 라우터는 네트워크 외부로 데이터를 전달하여 다른 네트워크와의 통신을 가능하게 합니다.

  (4) 사용 위치

• 스위치는 주로 내부 네트워크에서 장치 간의 통신을 관리하는 데 사용됩니다.
• 라우터는 내부 네트어크와 외부 네트워크를 연결하는 데 사용됩니다.

control + shift + R : 코드 실행하기(바로 전 코드)

opt + tab: 오류가 생겼을 때 해결 실마리 제공 opt + cmd + L: 코드 자동정렬 opt + cmd + m: 메소드 추출하기 opt + cmd + v: 변수 추출하기

f2: 오류난 곳으로 바로 이동 sout + v : 변수명 포함한 출력문 생성 psvm + tab: public static void main~ 자동입력 iter + tab: 향상된 for문 출력

@BeforeEach: 현재 클래스의 각 @메소드보다 먼저 메소드가 실행되어야 함

lsof -i:8080 -t | xargs kill -9

#include <time.h>

int main(){
    // 걸리는 시간 잴 때 필요한 함수
    clock_t start, end; // 시작시간, 끝나는 시간
    double cpuTimeUsed; // 총 걸린 시간

    //시간재기 시작
    start = clock();

    /*
    시간 잴 코드 넣기
    */

    // 시간재기 끝
    end = clock();
    // 걸린 시간 계산
    cpuTimeUsed = ((double)(end - start) / CLOCKS_PER_SEC);
    // 걸린 시간 출력
    printf("cputime = %.10lfs\n", cpuTimeUsed); //단위 : 초
}

start=clock();과 end=clock(); 사이에 시간 잴 코드를 넣어주면 된다 ㅎㅎ

** clock() 함수**란? CPU가 사용한 시간을 측정할 수 있는 함수이다.

• <time.h> 헤더 파일에 정의됨
• 프로그램이 시작된 이후부터 clock()을 호출한 시점까지의 CPU 시간을 clock_t 타입으로 반환

• 즉, clock()을 두 번 호출하고 그 차이를 구하면, 특정 코드 블록이 CPU를 얼마나 사용했는지 측정 가능

CLOCKS_PER_SEC란? 1초 동안 몇 번의 clock tick이 일어나는지를 나타내는 상수

• 대부분의 시스템에서는 1초 = 1,000,000 tick으로 정의
• 이 값으로 clock()의 반환값을 나누면 초(second) 단위로 변환 가능 ex)cpuTimeUsed = ((double)(end - start)) / CLOCKS_PER_SEC; 이렇게 계산하면 우리가 이해하기 쉬운 초 단위로 결과를 얻을 수 있음

주의) clock()이 반환하는 값은 CPU 시간이기 때문에, 아주 짧은 코드에서는 정확도가 떨어질 수도 있다.

좋은 객체 지향 어플리케이션을 개발할 수 있게 도와주는 프레임워크

<객체 지향 프로그래밍이란?>

프로그램을 명령어의 목록이 아닌 "객체"들의 모임으로 파악하고자 하는 것

<객체 지향 핵심 - 다형성>

<다형성이란?>

어떤 객체의 속성이나 기능이 상황에 따라 여러 가지 형태를 가질 수 있는 성질 ex) 남자의 역할이 아내에게는 남편, 자식에게는 아버지, 부모님에게는 자식, 회사에서는 회사원, 동아리에서 총무 등 상황과 환경에 따라서 달라지는 것과 비슷

<다형성의 본질>

<역할과 구현을 분리> 역할과 구현으로 구분하면 세상이 단순해지고, 유연해지며 변경도 편리해진다. 장점)

1) 클라이언트는 대상의 역할(인터페이스)만 알면된다. 2) 클라이언트는 구현 대상의 내부 구조를 몰라도 된다. 3) 클라이언트는 구현 대상의 내부 구조가 변경되어도 영향을 받지 않는다. 4) 클라이언트는 구현 대상 자체를 변경해도 영향을 받지 않는다.

<객체의 협력 관계> 클라이언트: 요청, 서버:응답 수 많은 객체 클라이언트와 객체 서버는 협력관계를 가진다.

<다형성 장단점> 장점: 클라이언트에 영향을 주지 않고, 서버의 구현 기능을 유연하게 변경 가능 확장 가능한 설계 단점: 인터페이스(역할) 자체가 변하면, 클라이언트, 서버 모두에 큰 변경이 발생한다.

-->그래서, 인터페이스를 안정적으로 잘 설계하는 것이 중요 변화가 있어도 인터페이스 자체가 최대한 안 흔들리게 개발하는 것이 중요

<좋은 객체 지향 설계의 5가지 원칙(SOLID)>

1) SRP: 단일 책임 원칙(Single responsibility principle) 2) OCP: 개방-폐쇄 원칙(Open/closed principle) 3) LSP: 리스코프 치환 원칙(Liskov substitution principle) 4) ISP: 인터페이스 분리 원칙(Interface segregation principle) 5) DIP: 의존관계 역전 원칙(Dependency inversion principle)

1) SRP: 단일 책임 원칙

Single responsibility principle의 약자 한 클래스는 하나의 책임만 가져야한다는 원칙 ex) UI변경, 객체의 생성과 사용 분리

하지만 책임이라는 것은 모호하고 중요한 것은 변경이다. --> 즉, 변경이 있을 때 파급효과가 적으면 단일 책임 원칙을 잘 따른 것

2) OCP 개방-폐쇄 원칙⭐️

Open/closed principle의 약자 확장에는 열려있으나 변경에는 닫혀 있어야 한다는 원칙 -> 확장을 해도 코드변경이 작아야 함

• 다형성 활용해야함 인터페이스를 구현한 새로운 클래스를 하나 만들어 새로운 기능 구현

• OCP가 깨지는 경우(=기존 코드를 변경해야하는 경우)
• -> 객체를 생성하고, 연관관계를 맺어주는 별도의 조립, 설정자(스프링 컨테이너)가 필요

3) LSP 리스코프 치환 원칙

Liskov substitution principle의 약자 인터페이스를 구현한 구현체를 믿고 클래스는 인터페이스 규약을 지켜야 한다는 원칙

"컴파일 성공->끝" 이 아니라 약속을 지켜야함 ex) 자동차의 엑셀은 앞으로 가야함, 뒤로 가게 만들 수는 있지만 규약에 위반됨. 엑셀은 느리더라도 앞으로 가게 구현해야함.

4) ISP 인터페이스 분리 원칙

Interface segregation principle의 약자 특정 클라이언트를 위한 인터페이스 여러 개가 범용 인터페이스 하나보다 낫다는 원칙

효과: 인터페이스가 명확해지고, 대체 가능성이 높아진다.

ex) 분리하면 정비 인터페이스 자체가 변해도 운전자 클라이언트에 영향을 주지 않음 ( 자동차 인터페이스-> 운전 인터페이스, 정비 인터페이스로 분리 ) ( 사용자 인터페이스-> 운전자 클라이언트, 정비사 클라이언트로 분리 )

5) DIP 의존관계 역전 원칙⭐️

Dependency inversion principle의 약자 구현 클래스(구현체)에 의존하지 말고, 추상화된 인터페이스(역할)에 의존해야 한다는 원칙

ex) DIP 위반 예시

class Keyboard {
    public void type() {
        System.out.println("Typing on keyboard");
    }
}
class Computer {
    private Keyboard keyboard;
    public Computer() {
        this.keyboard = new Keyboard();
    }
    public void use() {
        keyboard.type();
    }
}

여기서 Computer 클래스는 Keyboard라는 구체적인 클래스에 의존하고 있습니다. 만약 Keyboard가 아니라 WirelessKeyboard 같은 새로운 키보드를 사용하고 싶다면, Computer 클래스를 수정해야 합니다. 이렇게 되면 코드 변경이 자주 발생하고, 유지보수가 어려워집니다.

ex) DIP을 적용한 예시

interface InputDevice {
    void type();
}
class Keyboard implements InputDevice {
    public void type() {
        System.out.println("Typing on keyboard");
    }
}
class WirelessKeyboard implements InputDevice {
    public void type() {
        System.out.println("Typing on wireless keyboard");
    }
}
class Computer {
    private InputDevice inputDevice;
    public Computer(InputDevice inputDevice) {
        this.inputDevice = inputDevice;
    }
    public void use() {
        inputDevice.type();
    }
}

여기서Computer 클래스는 InputDevice라는 인터페이스에 의존합니다. 구체적인 구현체(Keyboard, WirelessKeyboard)가 아닌 추상화된 InputDevice에 의존하기 때문에, 새로운 키보드를 추가해도 Computer 클래스를 수정할 필요가 없습니다. 코드의 유연성이 높아지고, 유지보수가 쉬워집니다.

<정리>

1) 객체 지향의 핵심은 다형성 2) 다형성 만으로는 쉽게 부품을 갈아 끼우듯이 개발할 수 없다. 3) 다형성 만으로는 구현 객체를 변경할 때 클라이언트 코드도 함께 변경된다. 4) 다형성만으로는 OCP, DIP를 지킬 수 없다. (OCP, DIP이 제일 중요한 개념)

• 스프링은 DI 컨테이너 기술로 다형성 +OCP, DIP를 가능하게 지원 효과: 클라이언트 코드의 변경 없이 기능 확장 쉽게 부품을 교체하듯이 개발

  DI란? 객체 간의 의존성을 스프링 컨테이너가 자동으로 주입하여 관리해주는 방식

<핵심>

모든 설계에 역할과 구현을 분리하자! 이상적으로는 모든 설계에 인터페이스를 부여하자!

ex) 배우가 바뀌어도 공연이 진행이 되는 것처럼, 애플리케이션 설계도 공연을 설계하듯이 배역만 만들어두는 것

--> 기능을 확장할 가능성이 없다면 구체 클래스를 직접 사용하고, 향후 리팩터링해서 인터페이스를 도입하는 것도 방법

• 리팩토링(Refactoring)이란? 기능은 그대로 유지한 채로 코드의 구조를 개선하는 작업

• 물론 추상화의 단점도 있음
• -> 개발자 코드를 한 번 더 열어봐야함 (귀찮)

// 노드 구조체
typedef struct _Node
{
    struct _Node *prev;
    struct _Node *next;
    char elem;
} Node;

// 리스트 구조체 typedef struct { Node *header; Node *trailer; int length; } List;

위의 코드를 전재했을 때

> ```
//1번째 경우 - 오류 발생
List *L;
init(L);

1번째 경우는 List L;은 포인터 변수를 선언하지만, 메모리를 할당하지 않아서 L은 유효한 메모리 주소를 가리키지 않고 코드는 *정상 작동을 하지 않는다.**

//2번째 경우 - 정상 작동
List *L = (List *)malloc(sizeof(List));
init(L);

2번째 경우는 List 구조체의 크기만큼 동적 메모리를 할당하여, L은 유효한 메모리 공간을 가리키고 있으므로 코드가 **정상적으로 작동한다.**

> ```
//3번째 경우 - 정상 작동
List L;
init(&L);

이 경우는 정적 메모리에서 할당된 구조체의 주소를 전달하는 방식입니다. 그래서 동적 메모리를 할당할 필요 없이, L이 가리키는 메모리가 이미 할당된 상태이므로 정상적으로 동작한다.

나는 첫 번째 경우로 코드를 짜서 오류가 발생했다. 교수님께 1번째 경우의 오류 이유를 여쭤보았다. 교수님께서는 그 이유와 대안 2가지(2번째 경우, 3번째 경우)를 알려주셨다. 오늘은 그 내용을 정리해보았다.

1) new 연산자를 사용할 때마다 메모리에 인스턴스가 생성합니다. 2) 인스턴스는 더 이상 참조되는 것이 없을 때, 가비지 컬렉션(Garbage Collection)이 됩니다. 3) static한 필드는 클래스가 로딩될 때 딱 한번 메모리에 올라가고 초기화됩니다. 4) 인스턴스 메소드(non-static)는 인스턴스를 생성하고 나서 레퍼런스 변수를 이용해 사용합니다. 5) 클래스 메소드(static)는 클래스명.메소드명()으로 사용가능합니다. 6) 메소드 안에 선언된 변수들은 메소드가 실행될 때 메모리에 생성되었다가, 메소드가 종료될 때 사라집니다.

*참고) 소스코드, 클래스 파일 자체는 정적

1) 동적인 것들은 실행되면서 생성되는 것이다. 2) 클래스 정보 자체는 정적이다.

<객체지향 프로그래밍의 4가지 특성>

<1.추상화>

중요한 것은 남기고, 불필요한 것은 제거한다. ex) 신발 고객인 경우 : 신발 사이즈 찜질방 손님인 경우: 성별, 옷 사이즈

<2.캡슐화(encapsulation)>

관련된 것들을 잘 모아서 가지고 있는 것

<좋은 객체>

좋은 객체는 응집도는 높고 결합도는 낮다. ex) 세탁기는 세탁과 관련된 기능을 잘 가지고 있어야 함(높은 응집도) 컴퓨터를 샀는 데 부가적인 장비가 있어야만 컴퓨터가 동작한다.(높은 결합도)

<3.다형성>

어떤 객체의 속성이나 기능이 상황에 따라 여러 가지 형태를 가질 수 있는 성질 ex) 남자의 역할이 아내에게는 남편, 자식에게는 아버지, 부모님에게는 자식, 회사에서는 회사원, 동아리에서 총무 등 상황과 환경에 따라서 달라지는 것과 비슷

<다형성 - 오버로딩(Overloading)>

1) 메소드의 이름은 같고 매개변수의 개수나 타입이 다른 함수를 정의하는 것을 의미한다. 2) 리턴값만을 다르게 갖는 오버로딩은 작성할 수 없다.

<4. 상속>

기존 클래스를 재사용하여 새로운 클래스를 작성하는 것

• 상속은 반드시 써야할 때만 쓰고 되도록 안 쓰는 것이 좋음

<상속 선언 관례>

[접근제한자] [abstract | final] class 클래스명 extends 부모클래스명{ ..... } *여기서 []안의 내용은 없어도 됨 *아무것도 상속받지 않으면 자동으로 java.lang.Object를 상속받는다.

<상속 관련 정보>

1) 메소드가 오버라이딩(overriding) 되면 무조건 자식의 메소드가 실행된다.

• 오버라이딩? 상위 클래스의 메소드를 자식 클래스에서 재정의하는 것

2) 부모 타입으로 자손 타입을 참조할 수 있다. ex) Car car = new Bus(); 3) 정보은닉은 객체지향의 중요한 기법이다. ex) 중요한 필드는 은닉하고, 필드는 메소드를 통해서만 접근하도록 한다.

<기본 개념>

1) 클래스(Class) 객체를 생성하기 위한 설계도 및 도안 2) 오브젝트(Object) or 인스턴스(Instance) 클래스에서 정의된 구조를 실제로 구현한 것 3) 참조(reference) 변수 객체의 메모리 주소를 가리키는 변수 -> 참조되지 않은 값: 가비지(Garbage)(직역:쓰레기)

ex) 책상을 갖고 싶다라고 했을 때 클래스 : 컴퓨터 설계도면 오브젝트 or 인스턴스: 실제로 만들어진 책상

< Class >

<Class 선언>

<Class의 구성요소>

1) 필드(Field) 객체의 정보(상태) 2) 메소드(Method) 객체의 동작(기능) ex)

<접근 제한자>

Class 앞에는 접근 제한자가 붙습니다.

1) Private 2) Protected 3) Default

• class 앞에 접근 제한자가 없을 시 접근제한자를 Default로 지정

4) Public

• 모든 접근 가능

<class 선언 관례>

1) 클래스 명은 대문자로 시작 2) 카멜표기법 사용 카멜표기법이란? 단어와 단어가 만날 경우 단어의 시작은 대문자로 시작 ex) HelloWorld

<Field 선언>

<필드(Field)>

1) 소위말해 변수, 클래스가 가지는 속성 2) static 필드는 클래스 필드, non-static 필드는 인스턴스 필드

<필드 선언 방법>

[접근제한자] [static] [final] 타입 필드명 [=초기값]; *여기서 []안의 내용은 없어도 됨

<필드 선언 관례>

1) 첫 번째 글자는 소문자로 시작 2) 타입(type)은 기본형 (boolean, byte, char, short, int, long, float, double)과 참조타입(class, 인터페이스, 배열) 3) 초기값이 없을 경우: 참조형일 경우 null, boolean형일 경우는 false, 나머지 기본형은 모두 0으로 초기화

<메소드 선언>

<메소드 선언 방법>

[접근제한자][static] 리턴type 메소드이름(매개변수){ ... }

• 여기서 []안의 내용은 없어도 됨
• 매개변수와 전달인자는 다름

-> 매개변수(prameter): 메소드 메소드의 정의부분에 나열되어 있는 변수들 -> 전달인자(argument): 메소드를 호출할 때 전달되는 실제 값

<메소드 선언 관례>

1) 메소드 명은 소문자로 시작 2) 카멜표기법 사용

<static 메소드(클래스 메소드)>

1) 인스턴스를 생성하지 않아도 사용할 수 있다. (클래스가 로딩될 때 함께 메모리에 로드됨) 2) 오버라이드(Override)될 수 없다. *오버라이드란? 상위 클래스의 메소드를 자식 클래스에서 재정의하는 것

<non-static 메소드(인스턴스 메소드)>

1) 인스턴스 별로 다르게 동작해야하는 경우 주로 사용 2) 되도록 non-static 메소드를 사용해야한다.

<패키지>

<패키지(package)>

관련된 클래스들을 관리하는 폴더

<패키지 명명 관례>

1) 웹사이트 주소를 반대로 기재한 모양으로 패키지 이름 부여 2) 명칭은 소문자를 사용 3) 그룹으로 구분하기 위해 점(.) 사용 ex) com.nexon.maplestory.member.object

1) 프로그램이 실행되기 위해서 디스크에서 메모리로 불러와서 프로세스 내에 배치되어야 함 2) 메인 메모리와 레지스터는 CPU가 직접 접근할 수 있는 유일한 저장 장치임 3) 메모리 유닛은 오직 주소와 읽기 요청, 또는 주소와 데이터 및 쓰기 요청의 흐름만을 본다. 4) 레지스터 접근은 하나의 CPU 클럭(또는 그 이하) 내에 이루어진다. 5) 메인 메모리는 여러 사이클이 걸릴 수 있으며, 이는 정체를 유발할 수 있다. 6) 캐시는 메인 메모리와 CPU 레지스터 사이에 위치한다. 7) 올바른 운영을 보장하기 위해 메모리 보호가 필요하다.

base and limit 레지스터

한쌍의 base 레지스터와 limit 레지스터는 논리(logical, virtual) 주소 공간을 정의한다. CPU는 사용자 모드에서 생성된 모든 메모리 접근이 해당 사용자의 base와 limit 사이에 있는지 확인해야 한다.

<Address binding(주소 바인딩)>

• 논리 주소를 물리적 메모리로 연결시키는 작업

ex) 예를 들어, "이 모듈의 시작에서 14바이트"라는 코드 주소는 재배치 가능한 주소입니다. 그러나 이를 메모리에 로드하고 실행하기 위해서는 이 주소를 절대 주소(예: 74014)로 바인딩해야 합니다. 이것이 바로 주소 바인딩이 수행하는 작업입니다.

<주소 바인딩 3가지 방법>

1) Compile time(컴파일 타임 바인딩): 컴파일할 때 물리적 메모리 주소가 결정되는 주소 바인딩 시작 위치가 변경되면 코드를 다시 컴파일해야 합니다.

2)Load time(로드 타임 바인딩): 프로세스가 메인메모리에 저장이 될 때 물리적 주소가 결정되는 주소 바인딩 컴파일 시간에 메모리 위치를 알 수 없는 경우 재배치 가능한 코드(Relocatable code)를 생성해야함 프로그램이 종료될 때까지 물리적 주소 위치 고정

3)Execution time(실행 시간 바인딩): 프로세스가 실행되는 동안 물리적 주소가 결정되는 주소 바인딩 주소 맵을 지원하는 하드웨어(Memory Management Unit(MMU))가 필요

<Logical(논리) vs Pysical(물리) 주소 공간>

a) 논리(Logical) 주소 공간: 프로그램이 생성하는 주소의 집합 CPU에 의해 생성되며 가상(Virtual) 주소로도 불립니다. b) 물리(Pysical) 주소 공간: 메모리 장치에서 볼 수 있는 주소의 집합

• (컴파일 타임 & 로드 타임 바인딩)은 논리주소와 물리주소가 동일

• 프로그램이 컴파일되거나 로드될 때 주소가 결정되기 때문

• 실행 시간 바인딩은 논리주소와 물리주소 다를 수 있음

• 프로그램이 실행되는 동안에만 주소가 매핑되기 때문입니다.

논리 주소 공간은 프로그램이 생성하는 모든 논리 주소의 집합입니다. 물리 주소 공간은 프로그램이 생성하는 모든 물리 주소의 집합입니다.

<Memory-Management Unit(MMU)>

가상 주소를 실제 물리 주소로 매핑하는 하드웨어 장치

먼저, 메모리로 전송될 때 사용자 프로세스에 의해 생성된 모든 주소에 재배치 레지스터의 값이 추가되는 간단한 방식 고려

1) 재배치(relocation) 레지스터는 베이스 레지스터로 불립니다. 2) Intel 80x86 아키텍처에서 MS-DOS는 4개의 재배치 레지스터를 사용했습니다.

사용자 프로그램은 논리 주소만 처리하며, 실제 물리 주소를 볼 수 없습니다. 1)실행 시간 바인딩은 메모리 위치에 대한 참조가 발생할 때 발생합니다. 2)논리 주소가 물리 주소에 바인딩됩니다.

<재배치(Relocation) 레지스터를 이용한 동적(Dynamic) 재배치>

• 주소가 디스크에 재배치 가능한 형식으로 있다가 프로그램이 실행될 때 주소가 물리주소로 바인딩된다.

1) 사용되지 않는 루틴은 절대 로드되지 않습니다.(메모리 공간 활용도 향상) 2) 모든 루틴이 디스크에 재배치 가능한 로드 형식으로 디스크에 저장됩니다. 3) 드물게 발생하는 경우를 처리하기 위해 많은 양의 코드가 필요할 때 유용합니다 4) 운영 체제의 특별한 지원이 필요하지 않습니다

• 프로그램 설계를 통해 구현됩니다.
• OS는 동적 로딩을 구현하기 위해 라이브러리를 제공함으로써 도움을 줄 수 있습니다

  <Dynamic Linking(동적연결)>

  1) 정적 연결(Static linking) –

  프로세스가 메인메모리에 로드될 때 라이브러리와 프로그램을 컴바인시키는 것 단점: 같은 코드가 여러개 존재(메모리 많이 잡아먹음), 라이브러리가 변경될 경우 프로세스마다 새로운 버전의 라이브러리와 다시 컴바인 시켜야함

2) 동적 연결(Dynamic Linking) –

• 프로그램이 실행될 때 필요한 라이브러리와 결합됩니다.
• 동적 연결 시스템은 공유 라이브러리(shared libraries - dynamic linking labaries(dll))라고도 알려져 있습니다.

stub의 역할 작은 코드 조각인 스텁이 메모리에 상주하는 라이브러리 루틴을 찾습니다. 스텁은 자신을 찾은 루틴의 주소로 대체하고, 해당 루틴을 실행합니다.

운영체제 도움필요

1) 프로세스의 외부공간에 라이브러리가 존재하는 지 체크해주기 위해 운영체제 필요 2) 여러개의 프로세스가 같은 라이브러리를 공유하도록 운영체제 필요 3) 필요한 루틴이 현재 메모리 주소 공간에 없다면, 운영체제가 이를 메모리에 추가

장점: 하나의 메인메모리에 로드된 라이브러리를 여러개의 프로세스들이 공유할 수 있다. 라이브러리가 새로운 버전으로 바뀌면 바뀐 버전을 프로세스들이 쉽게 업데이트 할 수 있다. (각각의 프로세스가 필요한 버전 넘버를 명시해야함)

라이브러리 루틴이란? 특정 기능을 수행하는 코드 단위 ex)printf

• 동적 적재(Dynamic loading)에서는 적재를 실행 시까지 미룬 것이고 동적 연결은 연결을 실행 시기까지 미루는 것이다.

Swapping

프로세스가 메인메모리의 크기보다 클 때 디스크에 저장된 프로세스의 일부를 조금씩 메인메모리로 들고와 실행하는 것

Backing store(백업 저장소): 모든 사용자에 대한 메모리 이미지의 복사본을 저장할 수 있을 만큼 큰 빠른 디스크입니다. 이 디스크는 메모리 이미지에 직접 접근할 수 있어야 합니다.

Roll out, roll in 우선순위 기반 스케줄링 알고리즘에서 사용되는 스와핑 방식입니다. 우선순위가 낮은 프로세스를 스와핑 아웃하여 우선순위가 높은 프로세스를 메모리에 로드하고 실행합니다.

전송 시간: 스와핑 시간의 주요 부분은 전송 시간입니다. 총 전송 시간은 스와핑되는 메모리 양에 비례합니다.

준비 큐: 시스템은 디스크에 메모리 이미지를 가진 실행 준비가 된 프로세스들의 준비 큐(ready queue)를 유지합니다.

<스왑된 프로세스가 동일한 물리적 주소로 스왑 인될 필요가 있는가?> -주소 바인딩 방식에 따라 다릅니다. 많은 시스템(예: UNIX, Linux, Windows)에서 수정된 스왑 방식이 사용됩니다.

-스왑은 일반적으로 비활성화되어 있습니다. -할당된 메모리가 임계값을 초과하면 스왑이 시작됩니다. -메모리 수요가 임계값 이하로 줄어들면 다시 비활성화됩니다.

<Swapping의 문맥교환(context switch)시간>

다음 프로세스가 메모리에 없는 경우: 현재 프로세스를 swap out 하고 목표 프로세스를 swap out해야 합니다. 이로 인해 문맥 전환 시간(단점)이 매우 길어질 수 있습니다.

• request_memory()와 release_memory() 함수를 사용하여 메모리 사용을 관리

ex) 100MB 크기의 프로세스를 하드 디스크로 스왑하는 경우, 전송 속도가 50MB/초라면: 스왑 아웃 시간: 2000ms (2초) 동일한 크기의 프로세스를 스왑 인하는 시간: 2000ms (2초) 총 문맥 전환 시간: 4000ms (4초)

문맥 전환 시간 줄이기: swap하는 메모리 크기를 줄이면 문맥교환 시간을 줄일 수 있습니다. 일정 조건에만 swap한다?

<swapping의 제약조건>

대기 중인 입출력(I/O) 작업이 있는 경우(Pending I/O): swap out할 수 없습니다. 그렇지 않으면 I/O 작업이 잘못된 프로세스에 발생할 수 있습니다. 그래서 속도가 느려짐

대안으로 I/O를 항상 커널 버퍼으로 전송한 후 swap 후에 I/O 장치로 전달하는 경우: 이를 더블 버퍼링(double buffering)이라고 하며, 추가적인 오버헤드가 발생합니다. 즉, 2개의 버퍼를 사용해 i/o데이터를 보호하는 것

<Contiguous Allocation(연속할당)>

프로세스에게 연속적인 메모리 공간을 주는 방법 2가지

1) fixed partition(고정 분할)

메인메모리를 똑같은 크기로 나누고 한 파티션에 한 프로세스만 들어가게 메모리를 할당하는 방법 한 파티션에서 남는 공간은 못 쓰는 공간이 됨 프로세스가 차지하고 남는 공간을 내부 단편화(internal fragmentation)라고 함 paging에서도 발생

2) 가변 분할(variable partition)

각각의 프로세스가 필요한 크기만큼 메모리를 할당하는 방법 프로세스가 사용 후 빠진 공간에 다른 프로세스가 못 들어가 남는 공간을 외부 단편화(external fragmentation)이라고 함

둘 다 프로세스와 피티션의 개수는 똑같음, 즉 멀티프로그래밍의 개수는 파티션의 개수에 따라 결정됨

주 메모리는 보통 두 개의 파티션으로 나뉩니다: 운영 체제는 보통 낮은 메모리에 위치합니다. 사용자 프로세스는 높은 메모리에 위치합니다.

베이스 레지스터에는 가장 작은 물리적 주소 값이 들어 있습니다. 리미트 레지스터에는 논리 주소의 범위가 들어 있으며, 각 논리 주소는 리미트 레지스터보다 작아야 합니다.
MMU(메모리 관리 장치)는 논리 주소를 동적으로 매핑합니다.

이렇게 하면 커널 코드가 일시적(transient )이거나 커널 크기가 변경되는 등의 작업을 허용할 수 있습니다.

< Relocation and Limit Registers의 하드웨어 지원>

<Multiple-partition allocation(다중 파티션 할당)>

가변 분할: 프로세스가 필요한 만큼한 할당되기 때문에 프로세스가 종료되면 빈 공간이 생김 홀(hole) – 프로세스와 프로세스 사이에 빈 공간 이때 홀이 어떤 프로세스도 들어가지 못 할 정도로 작으면 external fragment(외부 단편화) 발생

프로세스가 도착하면, 해당 프로세스를 수용할 수 있을 만큼 큰 홀에서 메모리를 할당받습니다. 프로세스가 종료되면, 해당 파티션이 해제되고 인접한 자유 파티션들이 결합됩니다.

운영 체제는 다음 정보를 유지 관리합니다: a) 할당된 파티션(allocated partitions) b) 자유 파티션(홀)(free partitions)

<동적 저장 할당(Dynamic Storage-Allocation )>

1)First-fit(최초 적합): 이 프로세스가 들어갈 수 있는 첫 번째 큰 공간에 할당 2)Best-fit(최적 적합): 이 프로세스가 들어갔을 때 남는 공간이 가장 적은 곳에 할당 3)Worst-fit: 이 프로세스가 들어갔을 때 남는 공간이 가장 큰 공간에 할당

속도는 First-fit이 가장 빠름 , but 프로세스의 메모리 할당이 한 쪽으로 쏠리는 경향이 있음

<Fragmentation(단편화)>

내부 단편화(Internal Fragmentation) 파티션 안의 못 쓰는 공간, 주로 고정 분할에서 발생

외부 단편화(External Fragmentation) 프로세스 사이의 못 쓰는 공간, 주로 가변 분할에서 발생

최초 적합(First fit) 분석에 따르면, N 블록이 할당된 경우 0.5 N 블록이 단편화로 손실됨 전체 메모리 공간의 1/3이 사용되지 못한다. -> 50% 규칙

외부 단편화를 줄이는 법: 압축(compaction) 또는 수집(collection) 못 쓰는 공간이 남아있으면 쓰는 부분을 한 쪽으로 밀고 안 쓰는 부분을 다른 한 쪽으로 밀어 모아두는 것 (즉, 못 쓰는 공간을 한 곳으로 모아두는 것)

주의 해야할 점

1) 프로세스의 주소가 바뀌기 때문에 주소 바인딩이 실행시간에 일어나지 않으면 압축할 수 없음 2) Pending I/O: 프로세스가 입출력 작업을 수행 중에는os 버퍼에 데이터를 넣고 주소가 결정되면 그 곳에 copy

segmentation

프로세스의 각 요소를 나눠서 메인메모리의 비연속적인 공간에 저장하는 것

세그먼트는 다음과 같은 단위: main program / procedure / function/ method /object /local variables, global variables /common block /stack/ symbol table /arrays

<Segmentation 구조>

논리 주소는 <세그먼트 번호, offset> 즉, 2개의 튜플(tuple)로 구성

세그먼트 테이블 – 이차원 물리 주소를 매핑합니다. 베이스(base) – 세그먼트가 메모리에 위치한 시작 물리 주소를 포함합니다. 리미트(limit) – 세그먼트의 길이를 지정합니다.

segment-table base register (STBR):메모리 내 세그먼트 테이블의 위치 segment-table length register (STLR):프로그램이 사용하는 세그먼트의 수 (세그먼트 번호 s가 유효하려면 s < STLR 이어야 함)

cpu가 instruction을 가지고 오기 위해서는 2번의 메인 메모리 엑세스가 필요하다

1) segment table로 가서 해당 offset이 segment 범위 안에 있는 지 체크한다. 없으면 에러 발생(다른 공간의 정보를 엑세스 하려고 한 것이라서) 2) offset에다가 base address를 더해 물리주소를 구한다.

segmentation를 하는 가장 큰 이유는 보호(protection), 공유(sharing)

1) 보호가 되는 부분들은 같은 segment안에 같은 protection(보호, 권한?) 설정 가능 2) 공유가 되는 라이브러리를 한 segment 안에 넣을 수 있음 (관리 편리)

세그먼트 테이블의 각 항목과 관련된 보호 기능: 유효화 비트(validation bit) = 0 <--잘못된 세그먼트 읽기/쓰기/실행 권한

Paging

외부 단편화의 해결방법으로 , 메모리 공간을 일정한 페이지 단위로 나눠 주소를 불연속적으로 할당하는 메모리 관리 구조

segmentation 외부 단편화 발생, 길이가 달라서 table 안에 시작주소와 limit를 가져야 하기 때문에 메모리를 더 차지함 paging은 외부 단편화 발생안 함, 주소 결정 쉽다.

page(페이지): 가상메모리를 일정한 크기로 나눈 블록 frame(프레임) : 물리메모리를 일정한 크기로 나눈 블록 페이지와 프레임의 크기는 같음 -> 프레임에 대응되는 페이지 찾기 쉬움

논리 주소를 물리주소로 바꿔서 데이터를 가져오기 위해서 2번의 메인 메모리 access필요 1)page table를 이용해 물리주소 파악 2)해당 물리주소로 부터 데이터 가져오기

주소 전환 체계

페이지와 프레임의 대응도는 '페이지 테이블'에 저장되어 있다. 페이지 테이블: context switch가 일어날때마다 내용 바뀌어야 함

페이지 번호(p) – 페이지 테이블의 인덱스 페이지 오프셋(d) – 페이지 내의 특정 위치를 결정

paging

내부 단편화 계산 페이지 크기: 2,048 바이트 프로세스 크기: 72,766 바이트인 경우 72,766 ÷ 2,048 = 35.5 페이지, 따라서 36 페이지가 필요합니다. (35 페이지는 전체 2,048 바이트로 채워지고, 나머지 1 페이지는 일부만 사용됩니다) 마지막 페이지에서 남는 공간: 2,048 바이트 - 1,086 바이트 = 962 바이트 따라서 내부 단편화는 962바이트

최악의 경우 단편화 = 페이지 크기 – 1 바이트

평균적으로 단편화는 = 1/2 페이지 크기(페이지 크기의 절반)

작은 페이지 크기: 장점: 단편화를 줄임 단점: 페이지 테이블 항목이 많아져 추가적인 메모리 오버헤드가 발생 입출력 속도 떨어짐(많은 i/o를 발생시키게 됨)

큰 페이지 크기: 장점: 페이지 테이블 항목을 줄여 메모리 오버헤드를 줄임, 입출력 속도 빨라짐(적은 i/o)발생 단점: 단편화가 더 많이 발생

free-frame 리스트가 있으면 각각의 프로세스 페이지를 메모리로 옮기는 데 시간 절약됨

Page table

메인 메모리에 저장되어있음 Page-table base register (PTBR): 페이지 테이블의 위치 Page-table length register (PTLR):는 페이지의 수

데이터에 접근하기위해 두 번의 메모리 접근이 필요

1) 페이지 테이블에 접근해 물리주소 알기 2) 물리주소에 접근해 실제 데이터나 명령어를 가져옴 성능저하 발생 가능

이 문제를 해결하기 위해 'TLB (Translation Look-aside Buffer)' 사용 논리주소를 물리주소로 변환하는 속도를 높이기 위한 page table cash TLB는 페이지 테이블의 일부를 빠르게 검색하여 페이지 번호를 프레임 번호로 변환합니다. associative memory라고도함

메모리 접근 속도를 향상, 두 번의 메모리 접근을 하나로 줄여 시스템 성능을 향상

context switch시 마다 TLB를 바꾸지 않기 위해서 TLB 각 항목에 주소공간 식별자address-space identifiers (ASIDs)지정 TLB 미스 시 값이 다음 번에 더 빠른 액세스를 위해 TLB에 로드됩니다

TLB는 사이즈가 작아서 자주 교체해야함 최근 사용된 항목, 중요한 코드 등은 wired-down 고정해둠

TLB – 병렬 검색 주소번역(p,d)

p가 TLB에 있는 경우(TLB hit) 프레임 번호를 가져오고 그렇지 않으면(TLB miss) 메모리의 페이지 테이블에서 프레임 넘버 가져온다.

일어나지 않을 일을 하염없이 기다리는 상태

<시스템 모델>

시스템은 자원(CPU 사이클, 메모리 공간, I/O 장치 등)을 포함한다.

프로세스의 자원사용순서 1)request(요청) 2)use(사용) 3)release(방출)

<deadlock(교착상태)가 발생하는 조건(이유)>

1)mutual exclusion(상호배제) : 한 번에 한 프로세스만 자원을 사용하는 경우 2)hold and wait(점유 그리고 대기): 프로세스가 자원을 가지고 있는 상태에서 또 다른 자원을 기다리는 것 3)no preemtive(비선점적):선점이면 뺏을 수 있는 데 그렇지 못하니까 , 프로세스가 완료된 후에 리소스를 자발적으로 해제함 4)circular wait(순환 대기):P0은 P1이 가진 자원 P1은 P2가 가진 자원을 기다리는 ~ Pn은 P0이 가진 자원을 기다리는 순환대기가 일어날때

<자원 할당 그래프>

request(요청) edge : Pi -> Rj assignment(할당) edge : Rj -> Pi if(사이클이 없다) deaklock 발생 x else if(사이클이 있다){ if(자원이 하나다)deadlock 발생 o else if(자원이 여러개다) deadlock 발생 o/x }

<deadlock을 다루는 방법>

1)deadlock prevention(교착상태 예방) 2)deadlock avoidence(교착상태 회피) unix에서는 교착상태(deadlock)를 그냥 무시, 대부분 user 프로그램에서 발생하기 때문

<deadlock prevention(교착상태 예방)>

deadlock을 실행시키는 4가지 조건 부정 1)mutual exclusion(상호배제)는 부정불가(공유 가능한 자원에서는 부정 불가, 공유 불가능한 리소스에서는 유지 되어야함!)

2)hold and wait(점유 그리고 대기) : (1)자기가 필요한 모든 자원을 한꺼번에 요청, (기아상태 발생) (2)프로세스가 어떤 자원도 가지지 않았을 때 프로세스 시작 (자원 활용도 떨어짐) 3)no preemtive(비선점) : 내가 필요한 자원을 가질 수 없는 상태인 경우에 내가 가지고 있는 모든 자원을 방출한다. 자원을 다시 한 번 모두 요청한다. 조건: 복원이 가능한 자원인 경우에 사용가능 4)circular wait(순환대기): 자원(프로세스x)에게 순번을 정한다. 자원의 순번이 증가하는 순서로 요청한다. 문제점: 동적으로 lock의 순번이 정해지는 경우 deadlock 회피 불가능 이 예시에서 교차로 실행될 때 deadlock이 발생한다.

<deadlock avoidance(회피)>

요청을 받고 simulation을 돌려보고 circular wait(순환대기)(unsafe상태)가 발생할 거 같으면 받아들이지 않음

• deadlock을 회피하기 위해서는 몇 가지 사전 정보가 있어야 함 1) 프로세스가 필요한 자원의 최대개수 2) 현재 시스템에 남아있는 자원의 개수 3) 각각의 프로세스가 현재 가지고 있는 자원의 개수

<안전상태란? >

Pi가 요구하는 자원들이 현재 사용가능한 자원들과 Pj(j<i)가 가지고 있는 자원들로 충족되는 상태

즉, 1)Pi의 자원 요구가 즉시 충족되지 않으면, Pi는 모든 Pj가 완료될 때까지 대기할 수 있습니다. 2)Pj가 완료되면, Pi는 필요한 자원을 얻고, 실행하고, 할당된 자원을 반환하고, 종료할 수 있습니다. 3)Pi가 종료되면, Pi+1은 필요한 자원을 얻고 실행할 수 있습니다.

if(시스템이 safe state(안전상태)인 경우)- deadlock 없음 else if(시스템이 safe state(안전상태)가 아닌경우){ deadlock 발생 할 가능성 }

• avoidance(회피) -> 시스템이 unsafe상태로 가지 않도록 해준다.

  <avoidance(회피) 알고리즘>

  리소스가 단일 인스턴스인 경우: resource-allocation graph(자원 할당 그래프) 리소스가 다중 인스턴스인 경우: banker’s algorithm

<자원할당 그래프>

• claim edge(예약 엣지): 자원이 요청될 가능성이 있지만 아직 요청하진 않는 경우 점선으로 나타냄
• request edge(요청 엣지): 자원 요청 엣지
• assignment edge(할당 엣지): 자원이 할당된 상태를 나타내는 엣지

claim edge에서 request edge로: 프로세스가 자원 요청 request edge에서 assignment edge로: 프로세스에 자원 할당 assignment edge에서 claim edge로: 자원이 해제되고 요청될 가능성이 있는 상태로 감 *모든 자원은 시스템에서 사전에 청구되어야함 자원할당 그래프로 시뮬레이션을 해보고 circular- wait가 나타나면 요청을 받아들이지 않는다. 즉, 요청 엣지(request edge)를 할당 엣지(assignment edge)로 전환해도 사이클이 발생하지 않는 경우에만 요청허용가능

<banker's Algorithm(알고리즘)>

사용할 자원은 사전에 청구해야함 프로세스가 자원을 요청하면 기다려야할 수 있다. 프로세스는 자원을 제한된 시간 내에 반환해야 한다.

banker's 알고리즘 구조:

n:프로세스의 수 m:자원 타입의 수

1)Available :길이가 m인 벡터 ex) Available[j]=k인 경우 Rj의 인스턴스를 k개 사용할 수 있음

2)Max : nxm행렬 ex)Max[i,j]=k Pi가 Rj를 최대 k개 필요로 한다.

3)Allocation : nxm행렬 ex)Allocation[i,j]=k Pi에게 Rj가 k개 할당되었음을 의미

4)Need : nxm행렬 ex)Need[i,j]=k; Pi가 작업을 완료하기 위해 추가적으로 필요한 Rj의 개수가 k임을 의미 so Need[i,j]=Max[i,j]-Allocation[i,j]

<안전한 banker's 알고리즘>

1) 변수 초기화 work와 finish를 m과 n의 벡터로 초기화 Work=available로 초기화 (현재 사용가능한 자원을 나타냄) Finish[i]=false로 초기화(i는 0~n-1)(프로세스의 완료여부 나타냄)

2)다음을 충족시키는 프로세스i 찾기 (a) Finish[i]=false (b)need(i)<=work (현재 사용가능한 자원이 need를 충족시키는 지 확인) 충족시키는 i가 없으면 4번으로 가기

3)작업 수행 후 work=work + Allocation[i] (프로세스 i에 할당된 자원을 work에 더함) Finish[i] = true(프로세스 i를 완료 상태로 설정) 2번으로 가기

4)안전 상태 확인 모든 i에 대해 Finish[i]=true이면, 시스템은 안전 상태에 있음

<프로세스 i의 자원요청 알고리즘>

1)request(i)<=need(i)일 경우 2번으로 넘어감 (요청된 자원이 추가적으로 필요한 자원(need)을 넘는 지 확인) - 넘으면 에러발생

2)request(i)<=available일 경우 3번으로 넘어감 (요청된 자원이 현재 사용할 수 있는 자원(available)을 넘는 지 확인) - 넘으면 대기 해야함

3)요청된 자원을 가상으로 할당 (a) available= available-request(i) (b) allocation(i)=allocation(i)+request(i) (c) need(i)=need(i)-request(i)

if(안전 상태){자원을 pi에 할당) else if(안전상태가 아니라면){pi를 대기시키고 자원을 원상태로 복구}

<banker 알고리즘의 예시>

위의 예시에서 P1 Request (1,0,2)한 경우

<deadlock detection(감지)>

(a) 시스템이 교착상태로 가도록 허용 (b) 감지 알고리즘(Detection algorithm) (c) deadlock 복구(recovery)

<자원이 단일 인스턴스인 경우>

wait-for 그래프 유지 ex) P(i)->P(j) wait-for 그래프? 자원할당 그래프에서 자원을 뺀 형태, 프로세스의 관계를 그린 그래프 그래프에서 사이클을 찾는 알고리즘(n^2의 연산순서 필요(n은 정점 수)) 주기적으로 호출

<리소스 유형의 사례(인스턴스)>

a) Available : m길이의 벡터는 각 유형의 사용 가능한 리소스 수를 나타냄 b) Allocation: nxm 행렬의 각 프로세스에 할당된 각 유형의 리소스 수를 정의 c) Request: nxm 행렬은 각 프로세스의 현재 유형을 나타냄 ex)request[i][j]=k <- 프로세스 P(i)가 자원 R(j)을 k개 요청함

<Detection(감지) 알고리즘>

1) 변수 초기화 work와 finish를 m과 n의 벡터로 초기화 Work=available로 초기화 (현재 사용가능한 자원을 나타냄) 모든 i에 대해 Allocation이 0인 경우 Finish[i]=true로 초기화, 그 외인 경우 Finish[i]=false로 초기화

2)다음을 충족시키는 프로세스i 찾기 (a) Finish[i]=false (b)Request(i)<= work 충족시키는 i가 없으면 4번으로 가기

3)작업 수행 후 (a)work=work + Allocation[i] (프로세스 i에 할당된 자원을 work에 더함) (b)Finish[i] = true(프로세스 i를 완료 상태로 설정) 2번으로 가기

4)deadlock 확인 Finish[i]=False인 i가 있다면 시스템은 deadlock 상태임 추가로 Finish[i]=False인 경우 P(i)가 deadlock상태

알고리즘에서 시스템이 교착 상태에 있는지 여부를 감지하려면 O(m x n^2)개의 연산 순서가 필요합니다

<감지(detection) 알고리즘 예시>

<detection 알고리즘 사용>

호출하는 시기와 빈도 a) 교착상태가 발생할 가능성이 얼마나 되는 지 b) 얼마나 많은 프로세스를 rollback 해야하는 지 -> 분리된 사이클마나 하나씩

탐지 알고리즘이 임의로 호출되면 어떤 프로세스가 교착상태를 야기했는 지 알기 어려움

< Recovery from Deadlock(교착상태 복구)>

1) 프로세스 종료(termination) 2) 자원 선점(preemtion)

<Process Termination(프로세스 종료)>

교착사이클이 없어질 때까지 한번에 하나씩 교착상태인 모든 프로세스 중단

<어떤 순서로 프로세스를 중단(abort)하는 가에 고려할 점>

1) 프로세스의 우선순위(낮은 친구 먼저) 2) 프로세스가 얼만큼 실행되고 얼만큼 남았는지 (막 시작한 프로세스 abort) 3) 프로세스가 사용한 자원의 수(자원의 수가 적은 프로세스 abort) 4) 프로세스 완료까지 얼만큼의 자원이 더 필요한가 5) 종료해야 할 프로세스 수(적은 수의 프로세스가 종료되는 것이 좋음) 6) 프로세스는 대화형(interect)인지, 배치(batch)인지?

< Resource Preemption(자원 선점)시 고려해야할 점>

1)희생자(victim) 선정: 비용 최소화 고려 2)rollback: checkpoint까지 돌아가 프로세스 다시 시작 3)starvation: 항상 동일한 프로세스를 희생자로 선택할 수 있기 때문에 롤백 횟수도 고려할 수 있음

<고전적인 동기화문제>

1)bounded - buffer 문제(producer와 consumer 문제) 2)readers and writers 문제 3)식사하는 철학자들 문제

<producer와 consumer 문제>

semaphore mutex(1로 초기화, 0과 1가능) - 이진 세마포어 semaphore full(0으로 초기화)(n개 버퍼인 경우 n까지 가능) - counting semaphore(무제한) semaphore empty(1로 초기화)(n개 버퍼인 경우 n까지 가능) - counting semaphore

full- 몇 개의 공간이 차있냐 empty - 몇 개의 공간이 비어있냐 wait(mutex)와 wait(full,empty) 순서가 바뀌면 consumer도 멈추고 produmer도 멈추는 deadlock 발생함

<readers와 writers 문제>

reader:데이터 읽기만 가능(데이터 수정없음) writer:데이터 읽기와 쓰기 가능 즉, writer는 한 명만 reader는 여러명 접근 가능

즉, reader들이 데이터를 읽는 동안에 writer가 접근하지 못 하도록, writer가 데이터를 수정하는 동안 reader이 접근하지 못 하도록 해주는 동기화 기법

공유되는 데이터 1)데이터 2)semaphore rw_mutex(1로 초기화)(writer가 데이터를 수정하는 것을 제한하는 세마포어) 3)semaphore mutex(1으로 초기화)(reader의 처음과 끝을 알려주는 세마포어) 4)정수 read_count(0으로 초기화) (reader의 수)

<readers 와 writers 문제 변형>

변형1)writer가 쓰기 권한을 얻기 전이라면 어떤 reader도 기다리지 않음 reader가 계속 생기면 writer는 계속 기다려야 하는 starvation 문제 발생 변형 2) writer가 준비가 되면 가능한 빨리 쓰기 작업 수행 writer가 계속 생기면 reader는 계속 기다려야 하는 starvation 문제 발생 두 가지 모두 starvation 일으킬 수 있음

<식사하는 철학자 문제>

다섯 명의 철학자가 원탁에 앉아 있고, 각자의 앞에는 스파게티가 있고 양옆에 포크가 하나씩 있다. 그리고 각각의 철학자는 다른 철학자에게 말을 할 수 없다. 이때 철학자가 스파게티를 먹기 위해서는 양 옆의 포크를 동시에 들어야 한다. 이때 각각의 철학자가 왼쪽의 포크를 들고 그 다음 오른쪽의 포크를 들어서 스파게티를 먹는 알고리즘을 가지고 있으면, 다섯 철학자는 동시에 왼쪽의 포크를 들 수 있으나 오른쪽의 포크는 이미 가져가진 상태이기 때문에 다섯 명 모두가 무한정 서로를 기다리는 교착 상태(deadlock)에 빠지게 될 수 있다.

해결방안:

1) 식사를 하는 철학자의 수를 제한하자(5명 이하) 2) 왼쪽과 오른쪽을 다 집어야지 식사를 할 수 있게 만들어줌 (누군가는 한 쪽 젓가락을 오래 기다리는 starvation 일어날 수 있음)

race condition(경쟁상태)

공유데이터를 쓸 때 프로세스가 어떤 순서로 처리하냐에 따라서 결과가 달라지는 것을 "경쟁상태"라고 함. 즉, 임계구역에 동시에 접근하여 자원의 일관성이 깨지는 것 ex)프로세스 A는 값을 1만큼 증가시키고 프로세스 B는 값을 1만큼 감사시킬때 두 개의 프로세스가 동시에 공유 데이터를 읽고 실행시키면 값이 달라질 수 있다.

critical section(임계구역)

임계구역 : 프로세스가 공유할 수 있는 구역(데이터, 프로그램 등) Critical Section Problem은 여러 프로세스가 공유 자원에 대한 임계 영역(critical section)에 접근하는 것을 조절하기 위한 프로세스 동기화 문제입니다.

상호배제(mutual exclusion)

• 임계구역에 한 번에 한 프로세스씩 들어가는 것

<임계구역 문제 해결>

1)상호배제(mutaul exclution) - 임계구역에 진입한 프로세스가 있으면 다른 프로세스들이 들어갈 수 없다. 2)실행(process) - 임계구역에 진입한 프로세스가 없으면 들어가려는 프로세스는 임계구역에 들어갈 수 있어야 한다. 3)유한대기(bounded waiting) - 프로세스는 언젠가는 임계구역에 들어갈 수 있어야 한다. 무한대기 x

경쟁상태 예시)producer와 consumer>

producer consumer

Race condition- 경쟁상태

임계영역 문제해결을 위한 프로토폴(데이터교환방식을 정의하는 규칙체계)

entry section- 임계영역 진입하기 전 허가를 기다리는 구간 critical section - 임계영역 exit section - 다른 프로세스에게 임계영역을 넘겨줄 차례임을 알림 remainder section- 임계영역 이후의 작업

critical section- 임계구역

<커널이 선제적인지?>

선점적(preemtive) – 커널 모드에서 실행할 때 프로세스를 선점할 수 있습니다. (임계구역 문제 발생 - 메모리안의 프로세스가 커널을 공유하기 때문) 비선점적(non-preemtive) – 커널 모드를 종료하거나 자발적으로 CPU를 양도하는 방법으로 실행됩니다.

• 경쟁상태로부터 자유로움

<피터슨 해결방식(peterson's solution)>

• 소프트웨어에 의해 동기화 시켜주는 방법 2개의 변수를 공유: 1)int turn : 임계구역에 들어갈 차례를 나타냄(실제로 누구차례인지) 2)boolean flag[2] : 임계구역에 들어갈 준비가 되었는 지를 나타냄(들어가고 싶어! 알리기) ex)flag[i]=true인 경우 Pi가 준비가 되었음을 나타냄

(while(flag[j]&&turn==j)여기 부분은 cpu가 대기상태에 있는 게 아니라 running 상태) 임계구역(CS) 3가지 조건 [상호배제(flag[j]=false이거나 turn=i인 경우),실행,유한반복] 만족

but 3개 이상의 프로세스에서 올바르게 작동하기 어렵다, 오버헤드 발생 이를 해결하기 위한 하드웨어적 동기화 방법이 있음 일단 ,locking 방법을 이용하는 것이 base임

uniprocessor(단일프로세서) - 인터럽트를 비활성화함으로써 임계영역보호 (cpu가 다른 프로세스로 가려면 인터럽트가 발생해야 하는 데 인터럽트를 막았기 때문에 다른 프로세스로 갈 수 없음)

but 이 방법은 multiprocessor에선 비효율적임 (1)문제가 생기면 인터럽트를 발생시켜 해결해야하는 데 그러지 못해서 cpu는 멈춰있게 됨 (2)인터럽트를 걸어놔도 다른 cpu는 여전히 임계구역 진입가능(즉, 같은 cpu에서 동작하는 프로세스 사이에서만 동기화가 이루어짐)

so 현대에는 원자적(atomic: non-interrputible(인터럽트에 의해 중단되지 않는))하드웨어 구조 제공

원자적 하드웨어 명령어란? 실행되는 동작이 중간에 다른 작업에 의해 중단되지 않고 완전히 실행되는 특성을 가짐 그래서 인터럽트 비활성화가 필요하지 않기때문에 성능저하 없이 임계영역 보호가능

<동기화 하드웨어 lock 명령어를 사용하는 법(소프트웨어처럼 보이지만 사실 하드웨어)>

1)test-and-set

(1)원자적으로 실행 (2)전달된 파라피터의 원래값 반환 (3)파라미터의 값을 true도 설정 공유 변수 lock의 초기값은 false -(ture를 다시 true로 만드는 과정이 많으면 오버헤드 발생 so compare and swap를 적용해볼 수 있음)

2)compare-and-swap

(1)원자적으로 실행 (2)전달된 파라피터의 원래값 반환 (3)변수 value를 파라미터 new_value로 설정하되 value==expected인 경우에서 이루어짐. 공유 변수 lock의 초기값은 0

test_and_set을 이용한 상호배제, 유한대기(여러 프로세스인 경우)

이런 하드웨어 동기화들: 장점: 속도가 빠르지만 단점: (1)busy waiting(바쁜 대기) 문제가 있음 (2)임계구역에 못 들어가는 deadlock(교착상태), starvation(기아)문제 발생 문제 발생 *차이점 참고: 기아문제: 언젠가는 일어나지만 그 때가 언제인지 모르거나 매우 늦음 교착상태: 영원히 안 일어남 (임계구역에 들어간 친구가 무한 루프를 돌면 다른 프로세스들도 무한루프를 돌게 됨)

위는 어플리케이션 개발자가 접근할 수 없기때문에 임계구역 문제를 해결하기 위해 소프트웨어 방식을 만들었다

<뮤텍스락(Mutex Locks)>

: 상호배제를 위한 소프트웨어 lock 동기화 도구 acquire()(lock 획득)과 release()(lock 반환)를 이용하여 임계구역 보호 ->lock을 사용할 수 있는 지를 나타내는 부울변수 available사용 ->하드웨어 atomic(원자적) 구조를 이용하여 구현 그러나 busy waiting(바쁜 대기) 발생 이러한 lock을 spinlock이라고 함 ->임계구역이 작을 때 많이 사용됨

<busy waiting, spin lock>

lock상태를 주기적으로 무한루프 돌며 확인하는 거 available 초기값 - true

<세마포어(Semaphore)> - mutex보다 조금 더 정교

세마포어? 공유 자원에 1개 이상의 스레드 또는 프로세스 가 접근할 수 있으며 "접근 스레드나 프로세스의 수"에 한계를 두는 방식 정수 변수 - semaphore S 사용(S= 공유자원의 수) 2개의 분리할 수 없는 atomic(원자)연산을 통해서만 접근 가능 ->wait(), signal() (원래는 P(),V()라고 불림)

<세마포어 사용>

Counting semaphore(세마포어 계수): 제한되지 않은 범위에 있을 수 있는 정수 Binary semaphore(이진 세마포어): 정수값의 범위는 0~1(뮤텍스 자물쇠와 동일) ex)세마포어를 사용한 실행 순서 동기화 세마포어의 변수를 0으로 두고 먼저 실행할 프로세스 뒤에 signal 함수를 붙이고 실행할 프로세스 뒤에 wait 함수를 붙이면 된다.

<세마포어 구현>

2개 이상의 프로세스가 동시에 wait()나 signal()함수를 호출하면 문제가 생길 수 있음 상호배제가 필요함으로 wait()와 signal()함수는 임계구역에 있음..? 그래서 busy waiting(바쁜 대기)이 필요함 ->실행코드 짧을 땐 busy waiting이 유리 (더 빠르게 실행) ->빠르게 실행되어야 할 경우 유리 ->임계 구역이 조금 적용된다면 little busy waiting 어플리케이션이 임계구역에서 많은 시간을 할애하기 때문에 좋은 방법이 아님

<바쁜 대기 없이 세모파어 구현>

busy waiting,spin lock : 무한루프 통해 공유자원의 수(임계구역에 접근가능한 프로세스의 수)를 확인하는 거 해결 방법 : 1)사용할 수 있는 자원이 없는 경우 대기 상태(block함수)로 만듦(프로세스를 대기큐에 삽입) 2) 사용할 수 있는 자원이 생겼을 경우 준비상태(wake up 함수)로 만듦 (대기큐에서 하나의 프로세스를 제거하여 준비큐에 삽입) ->cpu 효율도 좋음

*대기 큐에는 2가지 데이터 항목이 있음 1)정수타입의 값 2)다음 기록을 가리키는 포인터

deadlock

대기 상태로 들어간 프로세스들이 실행 상태로 변경될 수 없을 때의 상황을 교착상태 (서로 상대방의 작업이 끝나길 기다리는 경우)

starvation - 무기한 차단

프로세스가 무한정으로 차단되어 있는 상태를 나타냅니다. 한 프로세스가 계속해서 필요한 자원을 얻지 못하고 계속해서 차단되는 것을 의미합니다.

우선순위 역전

우선순위가 높은 프로세스가 우선순위가 낮은 프로세스에 의해 cpu를 선점당해서 임계구역에 못 들어가는 현상, 해결방안 : 우선순위 상속 프로토콜(기법) ex)S,M,L이 있는 경우 임시적으로 우선순위가 낮은 프로세스(S)를 cs에서 빠져나올 때까지 우선순위가 높은 프로세스(L)만큼 높여준다.

<세마포어의 잘못된 사용>

signal (mutex) …. wait (mutex) 모든 프로세스가 임계구역에 들어가는 no 상호배제(mutual exclusion) 문제 발생 wait (mutex) … wait (mutex) 계속 기다리는 deadlock 발생 wait(mutex)와 signal(mutex) 중 하나가 생략되거나 둘다 생략된 경우 ->deadlock과 starvation 가능

<모니터>

모니터 내에서는 하나의 프로세스만 활성화할 수 있음 x,y는 모니터 안에서의 조건(condition) 변수

• x.wait - 프로세스가 x.signal()을 호출할 때까지 일시 중단됨.

• x.signal() - x.wait()를 호출한 프로세스 중 하나를 재개, 프로세스가 없다면 영향을 미치지 않음

  선택사항

  ex) 프로세스Q가 x.wait에 의해 중단되고 프로세스P는 x.signal()을 발생시킨 경우 1) Signal and wait – P는 Q가 모니터를 떠나거나 다른 조건을 기다릴 때까지 대기 2) Signal and continue – Q는 P가 모니터를 떠나거나 다른 조건을 기다릴 때까지 대기

• P가 나머지를 실행하면서 Q를 block시켰던 조건이 다시 발생하면 Q는 깨어나지 못 함 모두 장단점이 있기 때문에 언어에 따라 다름 이렇땐 P가 signal 이후에 바로 모니터를 빠져나옴, Q가 마저 수행하고 나오면 그때 P가 다시 들어감

• 버퍼가 꽉찬 경우 x.wait - 프로듀서 x.signal - 컨슈머

• 버퍼가 빈 경우 x.wait - 컨슈머 x.signal - 프로듀서

block된 프로세스(Q)가 x.wait부름 , x.signal(P)은 block된 프로세스를 깨운 경우

<모니터 안에서의 프로세스 재개(resume)> ex)조건 x에서의 여러 프로세스가 대기큐에 있을 때 x.signal()이 발생하면 어떤 프로세스를 시작해야 하나? FCFS방식이 적합하지 않을 때가 많음 so x.wait(c)구조를 제공해서 (c는 우선순위) 우선순위가 높은 순대로 실행

1)message passing:

프로세스 간에 메세지를 전달하여 데이터를 교환하는 방식이다. 동기화 : 공유되는 메모리가 없기 때문에 동기화 필요없음 데이터양: 적은 데이터 간단하게 처리가능 커널간섭: 커널 간섭이 높아서 오버헤드 큼 분산 시스템인 경우 편리

2)shared memory

여러 프로세스가 동일한 메모리 공간을 공유하여 데이터를 교환하는 방식 동기화: user가 동기화해주어야함 데이터양: 많은 양을 보낼 수 있음 커널 간섭: 커널 간섭적음 캐시의 일관성을 유지해야함

2. preemptive와 nonpreemptive scheduling 방식을 비교,설명하시오

비선점 스케줄링(nonpreemptive): 프로세스가 자발적으로 cpu를 양도하는 것 ex)시스템콜, i/o 요청장치 선점 스케줄링(preemptive): CPU를 강제적으로 다른 프로세스에 할당, 프로세스의 우선순위 허용 낮은 우선순위를 가진 프로세스보다 높은 우선순위를 가진 프로세스가 CPU를 선점하는 방식 ex)할당된 cpu시간이 끝나면 다른 프로세스에 할당

1)실행 상태에서 대기상태로 전환될 때 i/o인터럽트 nonpreemtive 2) 실행 상태에서 준비상태로 전환될때 자기한테 할당된 시간이 끝났을 때 preemtive 3)대기 상태에서 준비로 전혼될때 i/0가 끝나고 지금실행중인 프로세스가 끝나면 강제적으로 일어남 preemtive 4)종료 nonpreemtive

차이: preemptive 스케줄링은 우선순위가 높은 프로세스가 실행 중인 동안 다른 프로세스가 그 실행을 중단할 수 있지만, nonpreemptive 스케줄링은 한 번 시작된 프로세스가 CPU를 해제할 때까지 실행된다.  

3.FCFS, SJF, SRTF(Shortest-Remaining-Time-First), Priority, RR, Multilevel Queue, Multilevel Feedback Queue scheduling 방식을 각각 설명

first-come-first-served(FCFS) 스케줄링(nonpreemtive)

프로세스가 도착한 순서대로 진행하는 스케줄링 호위효과 발생: 긴 프로세스에 의해 기다리는 시간이 길어짐

Shortest-job-first(SJF) 스케줄링(nonpreemtive)(우선순위 스케줄링의 일종)

최소 평균 대기시간을 제공하는 가장 수행 시간이 짧은 job부터 수행하는 스케줄링 (어떤 게 수행시간이 짧은 지 알기 어려움) (preemtive)한 SJF 스케줄링 수행시간이 짧은 job이 나타나면 CPU를 그 job에게 양도하는 스케줄링

<Priority 스케줄링>(우선순위 스케줄링)

(nonpreemtive) 우선순위가 높은 순대로 수행 (preemtive) 우선순위가 높은 job이 나타나면 cpu를 그 job에게 양도 문제 :(starvation)기아 - 낮은 우선순위가 실행되지 않을 수 있음 해결 :aging(노화)- 시간이 지날수록 프로세스의 우선순위를 높여주는 방법

<RR(roundrobin)>

일정 시간동안 순서대로 cpu를 할당하는 스케줄러(time slice, time 퀀텀) 일정 시간이 지나고 다시 실행이 덜 끝났으면 ready 큐의 끝으로 감 q가 너무 길어지면: 총 대기시간이 길어진다(FIFO) q가 너무 짧으면:오버헤드 발생(문맥교환시간보다 길어야함) SJT에 비해 총 처리시간이 길지만 응답시간이 짧음

<multilevel 큐 스케줄링>

각각의 프로세스를 특성에 맞게 서로 다른 ready큐에 지정하는 것(큐끼리의 이동 불가)

foreground에서는 상호작용(interactive)을 해야하는 프로세스를 rr스케줄링을 통해처리한다. (응답시간이 빠르고 cpu벌스가 짧은) background에서는 일괄처리(batch)를 해야하는 프로세스를 fcfs스케줄링을 통해 처리한다. (총처리량이 많고 긴 시간을 필요로 하는)

큐를 스케줄링 하는 법 1)fixed priority scheduling (고정된 우선순위 스케줄링) foreground에 서비스를 먼저 실행하고 background의 서비스를 실행한다. 2)time slice 각 큐에 time을 적절한 비율로 할당해야한다.(foreground 80%, background 20%)

<multilevel feedback 큐>

멀티레벨 피드백 큐는 멀티레벨 큐랑 동일하나 프로세스가 하나의 큐에서 다른 큐로 이동 가능하다는 점이 다르다. (aging을 통해 이동가능)

다중 피드백 큐스케줄러는 다음과 같은 매개변수로 정의됩니다: 1)큐의 개수 정하기 2)큐마다의 스케줄링 알고리즘 지정 3) 프로세스를 업그레이드 시킬 때 사용하는 방식 4) 프로세스를 다운그레이드 시킬 때 사용하는 방식 5)프로세스가 들어오면 어떤 큐에 넣을 지 지정