https://curly-pufferfish-7ca.notion.site/SW-2cd6b65d5a698020a20af935434cbaec

Hybrid RAG 도입 전/후 비교

1. 개념적 비교

Before: Pure Vector RAG

• 검색 방식
  • Gemini text-embedding-004로 쿼리 임베딩 생성
  • ChromaDB market_prices 컬렉션에 대해 vector similarity 검색만 수행
  • distance(코사인 거리)에 따라 상위 top_k 결과를 그대로 사용
• 장점
  • 의미 기반 유사도 검색에 강함
  • 임베딩 모델만 잘 학습되어 있으면 자연어 쿼리에 유연하게 대응
• 단점
  • 숫자, 브랜드명, 기능명 같은 정확 키워드 매칭에 약함
  • 짧은 텍스트/희소 데이터에서 리콜이 떨어질 수 있음
  • 쿼리와 같은 단어를 포함하지 않아도 임베딩이 비슷하면 상위에 오를 수 있음

After: Hybrid RAG (Vector + Lexical Re-ranking)

• 검색 방식
  1. 기존처럼 벡터 검색으로 top_k * 3 개의 후보 문서 가져오기
  2. 각 후보에 대해:
     • vector_score = 1 - distance
     • lexical_score = 쿼리 토큰과 문서/메타데이터 토큰의 겹침 비율
     • hybrid_score = 0.6 * vector_score + 0.4 * lexical_score
  3. hybrid_score 기준으로 정렬 후 상위 top_k만 최종 결과로 사용
• 장점
  • 의미 기반 검색(벡터) + 정확 키워드 매칭(lexical)을 동시에 활용
  • 가격/페이지 수/브랜드명/기능명 등이 쿼리에 포함될 때 정확하게 매칭되는 문서에 가중치 부여
  • 짧은 설명이나 희소 데이터에서도 키워드 매칭으로 리콜 보강
• 단점/Trade-off
  • 후보 수(top_k * 3)를 늘려서 한 번 더 파이썬 레벨에서 재랭킹하므로 약간의 CPU 비용 증가
  • 아주 큰 컬렉션에서 candidate_k를 너무 키우면 속도에 영향이 있을 수 있음 (현재는 3배 수준으로 안전한 범위)

2. 코드 레벨 비교

Before: search_similar_deals (순수 벡터)

def search_similar_deals(self, query: str, category: Optional[str] = None, top_k: int = 5):
    # 1. 쿼리 임베딩 생성
    query_embedding = self.create_embedding(query)

    # 2. ChromaDB 검색 (카테고리 필터 적용)
    where_filter = {"category": category} if category else None

    results = self.collection.query(
        query_embeddings=[query_embedding],
        n_results=top_k,
        where=where_filter
    )

    # 3. 결과 포맷팅
    similar_deals = []
    if results['ids'] and len(results['ids'][0]) > 0:
        for i in range(len(results['ids'][0])):
            deal = {
                "id": results['ids'][0][i],
                "metadata": results['metadatas'][0][i],
                "distance": results['distances'][0][i],
                "document": results['documents'][0][i]
            }
            similar_deals.append(deal)

    return similar_deals

After: search_similar_deals (Hybrid: Vector + Lexical)

핵심 변화 포인트만 요약:

def search_similar_deals(self, query: str, category: Optional[str] = None, top_k: int = 5):
    # 1. 쿼리 임베딩 생성
    query_embedding = self.create_embedding(query)

    # 2. 1차 벡터 검색 (후속 재랭킹을 위해 top_k 보다 넉넉하게 가져옴)
    where_filter = {"category": category} if category else None
    candidate_k = max(top_k * 3, top_k)

    results = self.collection.query(
        query_embeddings=[query_embedding],
        n_results=candidate_k,
        where=where_filter
    )
    # 3. 질의/문서 토큰화 + lexical score 계산
    def normalize_text(text: str) -> List[str]:
        text = text.lower()
        text = re.sub(r"[^a-z0-9가-힣\s]", " ", text)
        tokens = [t for t in text.split() if len(t) > 1]
        return tokens
    query_tokens = set(normalize_text(query))
    def lexical_score(doc_text: str) -> float:
        if not query_tokens:
            return 0.0
        doc_tokens = set(normalize_text(doc_text))
        if not doc_tokens:
            return 0.0
        overlap = query_tokens & doc_tokens
        return len(overlap) / len(query_tokens)
    # 4. 벡터 스코어 + lexical 스코어 결합
    hybrid_candidates = []
    for i in range(len(ids)):
        ...
        vector_score = 1.0 - float(distance)
        combined_text = f\"{title} {category_text} {document[:1000]}\"
        lex_score = lexical_score(combined_text)
        hybrid_score = 0.6 * vector_score + 0.4 * lex_score
        hybrid_candidates.append({...})
    # 5. hybrid_score 기준 상위 top_k 선택
    hybrid_candidates.sort(key=lambda x: x[\"hybrid_score\"], reverse=True)
    top_candidates = hybrid_candidates[:top_k]
    ...
    return similar_deals

3. 기대 효과 (PPT용 Bullet Point)

Before (Pure Vector)

• 의미 기반 유사도에는 강하지만,
• 가격/페이지 수/기능명/브랜드명 같은 정확 키워드가 반영되지 않을 수 있음
• 짧은 텍스트나 희소한 데이터에서 리콜 부족 문제 발생 가능
• RAG 실패 시, 오케스트레이션 에이전트가 아무리 잘 짜여 있어도 후보군 자체가 부족해짐
• After (Hybrid Vector + Lexical)*
• 벡터 스코어 + 키워드 스코어를 결합해 더 안정적인 검색 결과 제공
• 쿼리 내부의 핵심 단어(예: "WordPress", "3 hours", "logo", "landing page")가 실제 문서/타이틀에 포함된 경우 우선순위 상승
• 짧은 설명/희소 데이터에서도 키워드 겹침으로 리콜 보강
• 오케스트레이션 에이전트가 선택할 수 있는 후보군 품질과 다양성이 상승 → 전체 체인 안정성 증가

4. 측정/비교 아이디어 (보고서용)

1. Top-k Precision
   • 특정 쿼리 셋(예: “워드프레스 수정 3시간”, “로고 디자인 패키지”, “당근마켓 아이폰 13 프로”)에 대해
   • 사람이 라벨링한 정답 거래들이 top-5 안에 포함되는 비율 비교
2. 클릭/선택 로그 기반 (실제 사용자 데이터 생긴 후)
   • 제안된 협상안들 중 실제로 선택된 옵션이
   • Hybrid RAG가 추천한 상위 후보에서 얼마나 자주 나오는지 측정
3. 실패 케이스 분석
   • “관련 거래 없음”으로 떨어졌던 케이스를 다시 돌려보고
   • Hybrid 적용 후 유사 사례가 새로 잡히는 비율 확인

5. 정리 문구 (한 줄 요약)

• Before: “의미 기반(Vector-only) RAG → 자연어는 잘 잡지만, 키워드/숫자/짧은 텍스트에 약함”
• After: “Hybrid RAG (Vector + Lexical Re-ranking) → 의미 + 키워드 둘 다 반영해, 오케스트레이션 에이전트가 믿고 쓸 수 있는 후보군 제공”

Hybrid RAG 도입 전/후 비교 정리

보고서/PPT에 바로 쓸 수 있도록, RAG 구조의 Before / After를 정리한 문서입니다.

1. 개념적 비교

Before: Pure Vector RAG

• 검색 방식
  • Gemini text-embedding-004로 쿼리 임베딩 생성
  • ChromaDB market_prices 컬렉션에 대해 vector similarity 검색만 수행
  • distance(코사인 거리)에 따라 상위 top_k 결과를 그대로 사용
• 장점
  • 의미 기반 유사도 검색에 강함
  • 임베딩 모델만 잘 학습되어 있으면 자연어 쿼리에 유연하게 대응
• 단점
  • 숫자, 브랜드명, 기능명 같은 정확 키워드 매칭에 약함
  • 짧은 텍스트/희소 데이터에서 리콜이 떨어질 수 있음
  • 쿼리와 같은 단어를 포함하지 않아도 임베딩이 비슷하면 상위에 오를 수 있음

After: Hybrid RAG (Vector + Lexical Re-ranking)

• 검색 방식
  1. 기존처럼 벡터 검색으로 top_k * 3 개의 후보 문서 가져오기
  2. 각 후보에 대해:
     • vector_score = 1 - distance
     • lexical_score = 쿼리 토큰과 문서/메타데이터 토큰의 겹침 비율
     • hybrid_score = 0.6 * vector_score + 0.4 * lexical_score
  3. hybrid_score 기준으로 정렬 후 상위 top_k만 최종 결과로 사용
• 장점
  • 의미 기반 검색(벡터) + 정확 키워드 매칭(lexical)을 동시에 활용
  • 가격/페이지 수/브랜드명/기능명 등이 쿼리에 포함될 때 정확하게 매칭되는 문서에 가중치 부여
  • 짧은 설명이나 희소 데이터에서도 키워드 매칭으로 리콜 보강
• 단점/Trade-off
  • 후보 수(top_k * 3)를 늘려서 한 번 더 파이썬 레벨에서 재랭킹하므로 약간의 CPU 비용 증가
  • 아주 큰 컬렉션에서 candidate_k를 너무 키우면 속도에 영향이 있을 수 있음 (현재는 3배 수준으로 안전한 범위)

2. 코드 레벨 비교

Before: search_similar_deals (순수 벡터)

def search_similar_deals(self, query: str, category: Optional[str] = None, top_k: int = 5):
    # 1. 쿼리 임베딩 생성
    query_embedding = self.create_embedding(query)

    # 2. ChromaDB 검색 (카테고리 필터 적용)
    where_filter = {"category": category} if category else None

    results = self.collection.query(
        query_embeddings=[query_embedding],
        n_results=top_k,
        where=where_filter
    )

    # 3. 결과 포맷팅
    similar_deals = []
    if results['ids'] and len(results['ids'][0]) > 0:
        for i in range(len(results['ids'][0])):
            deal = {
                "id": results['ids'][0][i],
                "metadata": results['metadatas'][0][i],
                "distance": results['distances'][0][i],
                "document": results['documents'][0][i]
            }
            similar_deals.append(deal)

    return similar_deals

After: search_similar_deals (Hybrid: Vector + Lexical)

핵심 변화 포인트만 요약:

def search_similar_deals(self, query: str, category: Optional[str] = None, top_k: int = 5):
    # 1. 쿼리 임베딩 생성
    query_embedding = self.create_embedding(query)

    # 2. 1차 벡터 검색 (후속 재랭킹을 위해 top_k 보다 넉넉하게 가져옴)
    where_filter = {"category": category} if category else None
    candidate_k = max(top_k * 3, top_k)

    results = self.collection.query(
        query_embeddings=[query_embedding],
        n_results=candidate_k,
        where=where_filter
    )
    # 3. 질의/문서 토큰화 + lexical score 계산
    def normalize_text(text: str) -> List[str]:
        text = text.lower()
        text = re.sub(r"[^a-z0-9가-힣\s]", " ", text)
        tokens = [t for t in text.split() if len(t) > 1]
        return tokens
    query_tokens = set(normalize_text(query))
    def lexical_score(doc_text: str) -> float:
        if not query_tokens:
            return 0.0
        doc_tokens = set(normalize_text(doc_text))
        if not doc_tokens:
            return 0.0
        overlap = query_tokens & doc_tokens
        return len(overlap) / len(query_tokens)
    # 4. 벡터 스코어 + lexical 스코어 결합
    hybrid_candidates = []
    for i in range(len(ids)):
        ...
        vector_score = 1.0 - float(distance)
        combined_text = f\"{title} {category_text} {document[:1000]}\"
        lex_score = lexical_score(combined_text)
        hybrid_score = 0.6 * vector_score + 0.4 * lex_score
        hybrid_candidates.append({...})
    # 5. hybrid_score 기준 상위 top_k 선택
    hybrid_candidates.sort(key=lambda x: x[\"hybrid_score\"], reverse=True)
    top_candidates = hybrid_candidates[:top_k]
    ...
    return similar_deals

3. 기대 효과 (PPT용 Bullet Point)

Before (Pure Vector)

• 의미 기반 유사도에는 강하지만,
• 가격/페이지 수/기능명/브랜드명 같은 정확 키워드가 반영되지 않을 수 있음
• 짧은 텍스트나 희소한 데이터에서 리콜 부족 문제 발생 가능
• RAG 실패 시, 오케스트레이션 에이전트가 아무리 잘 짜여 있어도 후보군 자체가 부족해짐
• After (Hybrid Vector + Lexical)*
• 벡터 스코어 + 키워드 스코어를 결합해 더 안정적인 검색 결과 제공
• 쿼리 내부의 핵심 단어(예: "WordPress", "3 hours", "logo", "landing page")가 실제 문서/타이틀에 포함된 경우 우선순위 상승
• 짧은 설명/희소 데이터에서도 키워드 겹침으로 리콜 보강
• 오케스트레이션 에이전트가 선택할 수 있는 후보군 품질과 다양성이 상승 → 전체 체인 안정성 증가

4. 측정/비교 아이디어 (보고서용)

1. Top-k Precision
   • 특정 쿼리 셋(예: “워드프레스 수정 3시간”, “로고 디자인 패키지”, “당근마켓 아이폰 13 프로”)에 대해
   • 사람이 라벨링한 정답 거래들이 top-5 안에 포함되는 비율 비교
2. 클릭/선택 로그 기반 (실제 사용자 데이터 생긴 후)
   • 제안된 협상안들 중 실제로 선택된 옵션이
   • Hybrid RAG가 추천한 상위 후보에서 얼마나 자주 나오는지 측정
3. 실패 케이스 분석
   • “관련 거래 없음”으로 떨어졌던 케이스를 다시 돌려보고
   • Hybrid 적용 후 유사 사례가 새로 잡히는 비율 확인

5. 정리 문구 (한 줄 요약)

• Before: “의미 기반(Vector-only) RAG → 자연어는 잘 잡지만, 키워드/숫자/짧은 텍스트에 약함”
• After: “Hybrid RAG (Vector + Lexical Re-ranking) → 의미 + 키워드 둘 다 반영해, 오케스트레이션 에이전트가 믿고 쓸 수 있는 후보군 제공”

표준 TSP: 다 돌고,다시 돌아오는 거

거리 계산: 매번 재귀에서 하는 것 보단 배열에 저장하고, 참조하는게 더 나음. (두 점 조합- for문으로 계산)

• 크기 주로 4를 곱해서 사용
• tree[N] ~ tree[2*N -1] : leaf node
• tree[1] ~ tree[N-1] : 중간 노드
• 리프 노드가 N부터 시작하므로, 트리의 구조는 여전히 1-based 인덱스처럼 동작.
• N이 홀수든 짝수든, 부모 인덱스 k에 대해 2k(짝수), 2k+1(홀수) 규칙은 변하지 않음.
• 1-based 트리에서 자식 쌍은 항상 2k와 2k+1.
• pos / 2로 부모를 찾고, pos ^ 1은 반대 자식을 정확히 가리킴.

  방법1: tree_size = N으로 두기

  #include <stdio.h>
  #include <string.h> //memset용
  #define NMAX 1000
  

int tsize = NMAX; int segTree[2 * NMAX]; int src[NMAX]; int N;

void update(int pos, int val) { pos += tsize; // 0번 -> tsize로 변환 segTree[pos] = val; while (pos > 1) { int par = pos / 2; int sibling = pos ^ 1; segTree[par] = segTree[sibling] + segTree[pos]; pos = par; } } //l번 index부터 r번 index까지의 구간합 int query(int l, int r) { int res = 0; l += tsize; r += tsize; while (l <= r) { //left가 홀수면? 오른쪽 자식 if (l % 2 == 1) { res += segTree[l]; l += 1; } //right가 짝수면? 왼쪽 자식 if (r % 2 == 0) { res += segTree[r]; r -= 1; } l /= 2; r /= 2; } return res; }

int main() { N = 10; tsize = N; for (int i = 0; i < N; ++i) src[i] = i; memset(segTree, 0, sizeof(segTree)); // N ~ 부터는 단말노드 for (int i = 0; i < N; ++i) { segTree[tsize + i] = src[i]; } //1 ~ N-1 까지는 구간합 노드들 for (int i = N - 1; i > 0; --i) { segTree[i] = segTree[i * 2] + segTree[i * 2 + 1]; }

int left = 3;
int right = 9;
printf("sum(%d ~ %d): %d\n",left, right, query(3, 9));
update(5, 5);
printf("sum(%d ~ %d): %d\n",left, right, query(3, 9));
return 0;

}

### 방법 2: 노드마다 구간 적기
```cpp
#include <stdio.h>
#include <cmath>
#include <vector>
using namespace std;
#define MAXN 100001
int src[MAXN];
/*
segment tree
    - 크기: 4*N, 2*N
    - 높이: ceiling(log2(N))
    - len : 1 << (h+1)
*/
int segTree[4 * MAXN]; //주로 4 곱해서 사용

//vector<int> src;
//vector<int> segTree;

int N;
//node마다 어떤 구간인지 알아야 하는 경우
//init
int init(int node, int start, int end) {
    //leaf node인 경우
    if (start == end) {
        return segTree[node] = src[start];
    }
    int mid = (start + end) / 2;
    int leftNode = node << 1; //node *2
    return segTree[node] = init(leftNode, start, mid) + init(leftNode+1, mid + 1, end);
}

//update: 해당 index의 값을 diff만큼 더하고 싶다.
void update(int node, int start, int end, int idx, int diff) {
    //범위 벗어나는 경우 pass
    if (idx < start || end < idx) return;

    segTree[node] += diff;
    //단말노드가 아니라면, 밑에 자식들까지 update 해줘야함.
    if (start != end) {
        int mid = (start + end) / 2;
        int leftNode = node << 1;
        update(leftNode, start, mid, idx, diff);
        update(leftNode + 1, mid + 1, end, idx, diff);
    }
}
//sum: [left, right] 구간의 합을 알고싶다.
int sum (int node, int start, int end, int left, int right) {
    //1. 해당 노드의 구간이 모두 벗어나는 경우
    if (right < start || end < left) return 0;
    //2. 해당 노드의 구간이 모두 포함되는 경우
    else if (left <= start && end <= right) {
        return segTree[node];
    }
    //3. 해당 노드의 구간이 포함하는 경우(관련 없는 구간 존재)
    //4. 해당 노드의 구간이 일부만 포함(관련 없는 구간 존재)
    int mid = (start + end) / 2;
    int leftNode = node << 1;
    return sum(leftNode, start, mid, left, right) + sum(leftNode + 1, mid + 1, end, left, right);

}

int main() {
    N = 10;
    //src.clear();
    //src.resize(N+1);
    //segTree.clear();
    //int h = ceil(log2(N));
    //segTree.resize((h+1) >>1);
    //segTree.resize(N * 4);
    for (int i = 1; i <= N; ++i) {
        src[i] = i;
    }
    init(1, 1, N); //root node부터 초기화

    int left = 3; int right = 9;
    printf("sum(%d ~ %d ): %d\n", left, right, sum(1, 1, N, left, right));

    update(1, 1, N, 5, 5);
    printf("sum(%d ~ %d ): %d\n", left, right, sum(1, 1, N, left, right));
    return 0;
}

Fenwick Tree(Binary Index Tree)

: 연속된 구간합 빠르게 구하기

• 항상 원소는 1부터!!!

• 자료구조 크기는 FenwickTree[src개수] -> O(n)

• Full binary tree(Segment tree의 진화형)

• 구간합 rangesum[i,j] = psum[0,j] - psum[0, i-1]

• 부분합 psum[0, j] = a[0] + a[1] ...

• 2의 승수 k : FenwickTree[k] = psum[1, k]

• 홀수 k : FenwickTree[k] = A[k]

• 그 외 k : FenwickTree[k] = A[k-1] + A[k]

• idx = idx + (idx & -idx) //뒤로 업데이트 해야하는 idx(증가)

• idx = idx - (idx & -idx) //앞으로 업데이트 해야하는 idx (감소)

연산

update(pos, val)

: pos위치에 val 값 업데이트

while(pos <= NMAX){
    FenwickTree[pos] += val;
    pos += (pos & -pos);
}

sum(r)

int sum = 0;
while(pos <= NMAX) {
    sum += Fenwick[pos];
    pos -= (pos & -pos);
}

x & -x : x의 마지막 1 비트 추출 x - (x&-x): x의 마지막 1부트 제거

• 무향 그래프

• 유향 그래프

• 가중치 그래프

• 사이클 없는 방향 그래프 (DAG) (사이클: 두개 이상의 노드를 거쳐서 되돌아 올 수 있는 구조)

  • 위상정렬 문제
  • 최장거리 구하기 : 가중치에 음수로 바꿔서 최단거리 문제(다익스트라) 로 구하기
  • 완전 그래프: 정점들에 대해 가능한 모든 간선들을 가진 그래프(간선 개수= nC2)

    그래프 표현

    인접 행렬

    100만 * 100만 = 1억 불가?

• 무향그래프는 대각선 대칭

• 행 기준: A행 ~ A에서 나가는 정점(진출차수)

• 열 기준: A열 ~ A로 들어오는 정점(진입차수)

  인접리스트

  vector<vector<>> : 일단 출발점으로부터 연결되는 것들만 노드 번호가 10, 100만개이면 일차원 배열 형태로 잡는다. 가중치가 들어온다면,

  간선 배열

  만약에 노드 개수가 10억개 이상이면, map 구조로 만듣다. map<노드번호, vector<pair<>>>

노드개수 1000개 이하 2차원 배열

노드개수 2차원 벡터

노드 개수가 10억이면 map<int, vector>>

깊이우선탐색(dfs)

선형구조: 순차 / 이진(sort 되어 있어야함) 비선형구조: bfs/dfs

노드 번호 주로 1부터

stack 방문 유무 vt[] stack 들어오면서 check: 절대 두번 들어오지 않음

1. 출발점을 stack이나 queue에 넣기
2. 무한루프(!stack.empty) : 연결되어 있고 사용하지 않은것들만 stack에 push stack 빠져가면서 check

너비우선탐색 (bfs)

배열기반 코드

#include <vector>
#include <stdio.h>
#include <iostream>
#include <stack>
#include <queue>
#define MAXN 1001
using namespace std;
int V, E;
int g[MAXN][MAXN];
void bfs(int start) {
    //visited input할 때 check
    queue<int> q; //노드 번호 저장
    vector<int> vt(V + 1); //true,false보다 int가 더빠르다.

    q.emplace(start);
    vt[start] = 1; //들어가면서 방문 선언!
    printf("[");
    while (!q.empty()) {
        int u = q.front(); s.pop();
        //u로부터 연결되어 있고, 사용하지 않은
        for (int i = 1; i <= V; ++i) {
            if (g[u][i] && !vt[i]) {
                vt[i] = 1;
                q.emplace(i);
            }
        }
        printf("%d ", u);
    }
    puts("]");
}
void dfs1(int start) {
    //visited input할 때 check
    stack<int> s; //노드 번호 저장
    vector<int> vt(V+1); //true,false보다 int가 더빠르다.

    s.emplace(start);
    vt[start] = 1; //들어가면서 방문 선언!
    printf("[");
    while (!s.empty()) {
        int u = s.top(); s.pop();
        //u로부터 연결되어 있고, 사용하지 않은
        for (int i = 1; i <= V; ++i) {
            if (g[u][i] && !vt[i]) {
                vt[i] = 1;
                s.emplace(i);
            }
        }
        printf("%d ", u);
    }
    puts("]");
}
void dfs2(int start) {
    //visited input할 때 check
    stack<int> s; //노드 번호 저장
    vector<int> vt(V + 1); //true,false보다 int가 더빠르다.

    s.emplace(start);

    printf("[");
    while (!s.empty()) {
        int u = s.top(); s.pop();
        //나올때 체크하는 방식이므로 stack에 두번 들어갈 수 있다.
        if (vt[u]) continue; //사용했으면 continue;

        vt[u] = 1; //나올때 방문 선언!
        //u로부터 연결되어 있고, 사용하지 않은
        for (int i = 1; i <= V; ++i) {
            if (g[u][i] && !vt[i]) {
                //vt[i] = 1;
                s.emplace(i);
            }
        }
        printf("%d ", u);
    }
    puts("]");
}

int vt[MAXN];
//깊이 우선 탐색을 재귀로 돌린 것 : backtracking
int dfs_rec(int start) {
    cout << start;
    vt[start] = 1;
    for (int i = 1; i <= V; ++i) {
        if (!vt[i] && g[start][i]) {
            dfs_rec(i);
        }
    }
}
int main() {
    int sn, en;

    freopen("input.txt", "r", stdin);
    scanf("&d %d", &V, &E);
    for(int i = 0 ; i < E ;++i){
        scanf("%d %d", &sn, &en);
        g[sn][en] = 1;
        g[en][sn] = 1;
    }
    return 0;
}
                         ```

unordered_map 사용

#include <vector>
#include <stdio.h>
#include <iostream>
#include <stack>
#include <queue>
#include <unordered_map>
#define MAXN 1001
using namespace std;
int V, E;
vector<vector<int>>g;
//unordered map : 십만개 - 우리가 아는 hash
unordered_map<int, vector<int>> gg;
void dfs(int start) {
    stack<int> s;
    vector<int> vt(V + 1);

    s.emplace(start);
    vt[start] = 1;
    printf("dfs: ");
    while(!s.empty()){
        int u = s.top(); s.pop();
        for (int& t : g[u]) {
            if (vt[t]) continue;
            s.emplace(t);
            vt[t] = 1;
        }
    }
}
int main() {
    int sn, en;

    freopen("input.txt", "r", stdin);
    scanf("&d %d", &V, &E);
    g.clear();
    g.resize(V + 1);
    for(int i = 0 ; i < E ;++i){
        scanf("%d %d", &sn, &en);
        g[sn].emplace_back(en);
        g[en].emplace_back(sn);
        gg[sn].emplace_back(en);
        gg[en].emplace_back(sn);
    }
    for (int i = 1; i <= V; ++i) {
        cout << i << " : ";
        for (int t : gg[i]) {
            cout << t << " ";
        }cout << "\n";
    }

    return 0;
}

  /*
7 14
1 2 3
1 3 5
2 3 1
2 4 2
2 5 4
3 2 3
3 4 4
3 6 6
4 5 7
4 6 2
5 6 4
5 7 5
6 5 3
6 7 8
*/
#include<stdio.h>
#include <queue>
#include <vector>
using namespace std;
vector<vector<pair<int,int>>> g;
//무향그래프
int V;

void bfs(int start) {
    //visit input check
    queue<int> q;
    vector<int> dist(V + 1, INT_MAX);
    vector<int> p(V + 1);
    dist[start] = 0;

    q.emplace(start);

    while (!q.empty()) {
        int u = q.front(); q.pop();

        for (auto& t : g[u]) {
            if (dist[t.first] > dist[u] + t.second) {
                dist[t.first] = dist[u] + t.second;
                q.emplace(t.first);
                p[t.first] = u;
            }
        }
    }

    printf("idx\t:\t[");
    for (int i = 1; i <= V; ++i) {
        printf("%d ", i);
    }puts("]");

    printf("dist\t:\t[");
    for (int i = 1; i <= V; ++i) {
        printf("%d ", dist[i]);
    }puts("]");
    printf("p\t:\t[");
    for (int i = 1; i <= V; ++i) {
        printf("%d ", p[i]);
    }puts("]");
}

int main() {
    freopen("input.txt", "r", stdin);
    int E;
    int sn, en, val;
    scanf("%d %d", &V, &E);
    g.clear();
    g.resize(V + 1);
    //pair f:nodeNum, s : time
    for (int i = 0; i < E; ++i) {
        scanf("%d %d %d", &sn, &en, &val);
        g[sn].emplace_back(en, val);
    }

#if 0
    for (int i = 1; i <= V; ++i) {
        printf("%d : ", i);
        for (auto& t : g[i]) {
            printf("(%d,%d) ", t.first, t.second);
        }
        puts("");
    }
#endif
    bfs(1);

    return 0;
}

문자 0을 기준으로 적으면 연산자, 크면 숫자로 인식

한글 한자 euc.kr - 2byte utf - 3byte

c

• 배열 : 마지막에 구분자 '\0' 방식 cpp : string
• 객체 : 길이 방식(start로부터 얼마나)

c계열: 컴파일러가 2바이트씩 읽어서 알아서 잘 해준다.

문자열 관련 headers #include : cpp string 객체 #include <string.h> : c의 string

atoi(문자열), atof: 표준함수 itoa: 비표준 리눅스, gcc에는 없음.

  #include <stdio.h>
//#include <string.h> // c 기반 문장려 : strlen 
#include <cstring> // string.h 확장버전
#include <cstdlib> //atoi, itoa(숫자 <-> 문자)
#include <iostream>
using namespace std;
int my_strlen(char* str) { //c는 1byte를 len 1로 생각(한글은 2byte)
    int len = 0;
    while (*str) { //현재 값을 찍을 때 * 사용, 마지막 문
        len++;
    }
    return len;
}
//long long - 64bit
//8, 10, 16 진법이 아닌 경우
void my_itoa(char* sNum, int val, int digit) {
    int idx = 0;
    if (val < 0) {
        sNum[0] = '-';
        idx++;
    }
    int iNum; char c;
    while (val) {
        iNum = iNum % digit;
        if (iNum < 10) { //0~9까지의 형태가 들어옴
            c = iNum + '0';
        }
        else {
            c = iNum + 'a' - 10;
        }
        char c = val % 10 + '0';
        sNum[idx++] = c;
        val = val / 10;
    }
    sNum[idx] = 0; //널문자 넣어주기
    //puts(sNum);
    //순서 반대로 바꿔줘야함(reverse)
    int len = idx / 2; //ex) len 4 -> 중앙 2 len 5 -> 중앙 2
    for (int i = 0; i < len; ++i) {
        char t = sNum[i];
        sNum[i] = sNum[idx - 1 -i]; //0번과 3번이랑 바꾸기
        sNum[idx - 1 - i] = t;
    }
}
void my_strcpy(char* dest, char* src) {
    while (*dest++ = *src++); //주소 복사시키고 ++로 이동
}
int main() {
    char buf3[100] = "123";
    char buf4[100];
    int iNum; double dNum = 1.234567;
    //scanf("%d", &iNum); //키보드로부터 읽어라
    sscanf(buf3, "%d", &iNum ); //배열로부터 읽어라
    cout << "iNum: " << iNum << "\n";
    sprintf(buf4, "%o", iNum); //배열에다가 뿌려라.
    puts(buf4);
    sprintf(buf4, "%x", iNum); //배열에다가 뿌려라.
    puts(buf4);
    sprintf(buf4, "%lf", dNum); //배열에다가 뿌려라.
    puts(buf4);
    char sNum[] = "123a";
    //숫자형 문자열 -> 숫자
    iNum = atoi(sNum); //"123"만 들어옴. 
    char buf2[100];
    itoa(iNum, buf2, 2);
    puts(buf2);

    char s[] = "hong";
    //string.h
    char s1[11] = "hong";
    char s2[11] = "aong";
    printf("len: %d\n", strlen(s1));
    //(a-b) > 0 : 1 : 앞선 문자열이 더 크다  / 0: 같다 / -1 : 뒤 문자열이 더 크다.
    printf("cmp: % d\n", strcmp(s2, s1));

    char buf[100] = "hong";
    //buf = s2 ; //error! (왜냐하면 buf는 배열이므로 주소를 바꿀 수 없음)
    strcpy(buf, s2); //초기화 다음 단계에서 어떤 문자열을 복사하려면 strcpy 사용해야함.
    strcat(buf, s2); //문자열 더하기

    char str1[11] = "hong"; //배열(배열 주소를 바꿀 수 없음: 상수)
    //char str2[11] = { 'h', 'o', 'n', 'g' };
    char str2[11]; 
    const char* str3 = "hong"; //포인터로 선언? 근데 이건 const이면,,, 바꿀 수없는거아님??

    str2[0] = 'h';
    str2[1] = 'o';
    str2[2] = '\0'; 
    printf("%s\n", str1);
    puts(str3);
    /*
        배열 
        - str1 = str2
        포인터는 자료형 동일하면 가능
        - str3 = str2 
    */
    return 0;
}

#include <stdio.h>
#include <string>
#include <iostream> //cin, cout

using namespace std;

int main() {
    string str;
    cin >> str;
    cout << "str: " << str << endl;

    //file 종류 지점: -1로 끝남(EOF)
    while (getchar() != 10); //10 : '\n' 개행 (input 버퍼 비우는 코드)(실무에서)
    getline(cin, str);//현위치부터 개행 진적까지 모든 문자열 받기
    //c: gets , cpp: getline  -> buffer 비우기 작업 필요? 출력문 버퍼 비우기 (fflush) 
    cout << "str: " << str << endl;
    return 0;
}

#include <stdio.h>
#include <string>
#include <iostream> //cin, cout

using namespace std;

int main() {
    string s = "abcdefghij";

    //string -> arry
    char str[] = "hong";

    string str1 = "hong";
    string str2("hong");
    string str3 = str1; //기존 문자열 대입도 가능
    string str4 = str; //배열구조 넘겨주면 string으로 바뀜 
    //나중에 배열로 사용하고 싶으면 string.c_str() 사용
    string str5(str);


    char buf[100];
    strcpy(buf, str1.c_str());
    printf("str: %s\n", str); //ok
    //printf("str1: %s\n", str1);//error!
    printf("str1 : %s\n", str1.c_str()); // string에서 c 기반 배열주소로 사용하고 싶을때
    cout << "str : " << str << endl;
    cout << "str1 : " << str1 << endl;
}

  #include <stdio.h>
#include <string>
#include <iostream> //cin, cout

using namespace std;

int main() {
    string str = "abcdefghijde";
    printf("str[1]: %c\n", str[1]); //이게 더 속도 빠름
    printf("str[1]: %c\n", str.at(1));
    int idx = str.find("de"); //0번째 부터 "de"가 나타나는 첫번째 위치를 알려줌.
    printf("idx : %d\n", idx);
    idx = str.find("de", 5); //5번째 부터 "de"가 나타나는 첫번째 위치를 알려줌.
    printf("idx : %d\n", idx);
    //값이 존재하지 않으면 -1 반환
    idx = str.rfind("de"); //n-1번째부터 거꾸로 찾기
    printf("idx : %d\n", idx, 5);//5번째부터 에서 거꾸로 찾기

}

#include <stdio.h>
#include <string>
#include <iostream> //cin, cout
#include <vector>

using namespace std;

int main() {
    //: 기준으로 split하기
    vector<int> idxs;
    string str = "aaa:bbb:ccc:ddd";
    int idx = 0;

    while (1) {
        idx = str.find(":", idx);
        if (idx == -1) {
            break;
        }
        idxs.emplace_back(idx);
        idx++;
    }
    for (int& i : idxs) {
        printf("%d ", i);
    }puts("");

    string subString = str.substr(4); //이 5번(idx)부터 끝까지
    cout << subString << endl;
    subString = str.substr(4,3); //이 5번(idx)부터 3(크기)
    cout << subString << endl;
    subString = str.substr(4, 10000); //크기 초과해도 오류 안남
    cout << subString << endl;

}

cpp 에는 string reverse함수가 없다! string +operator가 만들어져 있으므로 string 더하기 가능!

1) 괄호 검사

2) 문자열 계산기 sol1 - stack 중위 표현식 -> 후위 표현식으로 바꾸기 ex) a - b => a b -

stack : 나보다 서열이 낮을 때 까지 빼기

후위 문자열 배열: 피연산자 들어오기

so2 - 이진트리

3) dfs : 모든 경우의 수 - stack bfs : 단계별 검증 / 최단 경로 - queue

queue

원형큐

queue는 front에서 삭제하는 구조이므로, 선형큐으로 했을 때 메모리 부족 문제 발생 가능 => 실무에서 직접 구현할 땐 "원형큐"를 사용한다.

초기상태 : front = rear = 0 공백상태 : front = rear

6개 크기 -> 5개 자료 보관 rear = (r + 1) % N front = (f + 1) % N (rear+1) % n = front 이면, 다 찬 경우

연결큐

2) n번 독립시행확률: nCr * (성공확률)^r * (1-성공확률)^(n-r)

3) dp 4) %f: 여섯번째자리까지 = %.6f cout은 안됨

/*
5분에 하나의 가구
완제품: 결함X
두명 가구 장인 시합
각 장인 완제품 개수: 소수개수 인가

pa = (5분안 완제품 만들 확률)
pb = (5분안 완제품 만들 확률)

총 시간 90분 = 최소 2개 최대 36개
한 장인: 최소 0개 최대 18개
n: 18번 시도 , r: (0~18)중 소수가 아닌 수

적어도 둘 중 한명이라도 소수개 만들 확률 = 1 - (둘다 소수가 아닐 확률)

장인a: 18Cr * (pa)^r * (1-pa)^(18 - r)
장인b: 18Cr * (pb)^r * (1-pb)^(18 - r)
*/
#include<iostream>
#include<vector>
#include<algorithm>
#include<math.h>
#define NMAX 11
#define diff (1e-12)
using namespace std;
double pa; double pb;
vector<int> numbers = { 0, 1, 4, 6, 8, 9, 10, 12, 14, 15, 16, 18 };
int dp[19][19];
vector<int> comb(19);

int comb_cal(int n, int r) {
    if (r == 0 || n == r) return 1;
    //0이면
    if (!dp[n][r]) return dp[n][r] = comb_cal(n - 1, r) + comb_cal(n - 1, r - 1);
    return dp[n][r];
}
int main(int argc, char** argv)
{
    int test_case;
    int T;
    //freopen("input.txt", "r", stdin);
    cin >> T;

    //조합: 18C숫자 계산 미리 해두기
    for (int& r : numbers) {
        comb[r] = (comb_cal(18, r));
        //cout << comb[r] << endl;
    }
    for (test_case = 1; test_case <= T; ++test_case)
    {
        int a, b;
        cin >> a >> b;
        cout << "#" << test_case << " ";
        if ((!a) && (!b)) {
            printf("%.6lf\n", 0.0);
            continue;
        }
        pa = (double)a / 100; pb = (double)b / 100;
        double sum_a = 0;
        double sum_b = 0; 
        //cout << "pa: " << pa << " pb: " << pb << endl;
        if (pa == 0) {
            for (int& r : numbers) {

                sum_b += (comb[r] * pow(pb, r) * pow((1-pb), (18 - r)));
            }
            printf("%.6lf\n", (1 -  sum_b));
            continue;
        }
        else if (pb == 0) {
            for (int& r : numbers) {
                sum_a += (comb[r] * pow(pa, r) * pow((1-pa), (18 - r)));
            }
            printf("%.6lf\n", (1 - sum_a));
            continue;
        }
        else {
            for (int& r : numbers) {
                //cout << (comb[r] * (float)pow(pb, r) * (float)pow((1-pb), (18 - r))) << endl;
                sum_a += (comb[r] * (float)pow(pa, r) * (float)pow((1-pa), (18 - r)));
                sum_b += (comb[r] * (float)pow(pb, r) * (float)pow((1-pb), (18 - r)));
            }
            printf("%.6lf\n", (1 - (sum_a * sum_b)));
        }


    }
    return 0;//정상종료시 반드시 0을 리턴해야합니다.
}

입력값의 개수에 따라 달라짐.

1) 출발, 도착 선택, 모든 도시 여행

2) 3곳만 숙박비 선택(비용이 가장 적은 세개 구하기)

6C3 중 비용합 최소

3) 여행자 경비 한정적, 최대 개수 도시?

dp : 반복문 vs 재귀호출 -> 반복문 구조가 덜 메모리 사용하고, 더 빠르다. -> 그러나 tc마다 반복문 개수가 다를 때 재귀만 가능한 경우도 있다.

재귀호출

• stack 메모리 할당이 가능한 깊이를 확인 필요. (stack overflow)
• 탈출 조건, 유도된 수식

반복문

• 슬라이딩 윈도우(1억개 이상일 경우 메모리 초과 날 수 있음.)
• 피보나치: 모듈러 처리로 메모리 절약하는 방법.

**피보나치라고 문제에 나와있지 않더라도, 수식을 세워보니(경우의 수 세었을 때) 피보나치 계열일 수 있음!

최적부분구조 : 해결한 부분은 되돌아보지 않는 구조 중복부분구조 :

그 부분에서 최적값이 한개가 나오는데, 합쳐놓고 보니 오답이 나오는 구조 -> 탐욕알고리즘 완전 탐색으로 해결해야 한다! -> 항상 증명을 해야하거나, 알고 있는 경우 (다익스트라 최단경로 알고리즘, Prim 알고리즘)

ex) 최소 신장트리(minimum spanning tree)

• prim 알고리즘 ex) aaaabbcaaaaddd -> a4b2c1a4d3 run length 알고리즘? ex) 허프만 코딩 : 빈도수가 가장 많이 나온 것을 가장 적은 byte ? -> 허프만 트리

ex) 거스름돈 문제: 돈의 관계가 배수 관계가 성립하면 탐욕 알고리즘이지만, 그게 아닌 경우는 완전탐색을 해야한다. ex) 부정방정식(변수의 개수보다 방정식 개수가 적은 경우): 중복조합으로 짤 경우 시간이 너무 오래걸리므로 dp로 풀기

ex) knapsack Todo: 가방이 감당할 수 있는 무게, 가격의 총합 max

1) zero one knapsack : 모든 경우의 수

• 부분집합 이용해서 풀이(backtracking) or dp 알고리즘

• 종류: 보석의 개수가 무한개(동전알고리즘과 유사) / 한정적

  #include <iostream>
  #include <stdio.h>
  #define MAXN 31
  #define MAXW 1001
  using namespace std;
  //int j[][2] = { {0} , { 4, 40 }, {10, 50}, {20, 150} };
  int jw[MAXN] = { 0, 4, 10, 20 };
  int jp[MAXN] = { 0, 40, 50, 100 };
  int N, W;
  //knapsack1 - 보석이 무한개 : ans => 40 * 7
  //중복해서 사용하는 경우 => 1차원 배열 dp
  int dp1[MAXW];
  int knapsack1() {
    for (int i = 1; i <= W; ++i) { //경우 : 기준 가방
        for (int j = 1; j <= N; ++j) { //검증 : 보석
            //i: 현재 가방 무게 , j: 새로 담을 보석
            if (i >= jw[j]) {
                if (dp1[i] < dp1[i - jw[i]] + jp[j]) {
                    dp1[i] = dp1[i-jw[i]] + jp[j];
                }
            }
        }
    }
  
    return dp1[W];
  }
  

//knapsack2 - 보석이 한개 : ans => 20 , 10kg: 200만원 //중복해서 사용 못하는 경우 => 2차원배열 int dp2[MAXN][MAXW]; //보석이 기준 int knapsack2() { for (int i = 1; i <= N; ++i) { //경우 : 기준 보석 for (int j = 1; j <= W; ++j) { //검증 : 가방 //i: 현재 보석 가격 , j: 새로 담을 보석 dp2[i][j] = dp2[i - 1][j]; //복사시켜놔야 다음에 사용가능 if (i >= jw[j]) { if (dp2[i][j] < dp2[i - 1][j - jw[i]] + jp[i]) { //직전 데이터로부터 덜어내고 dp2[i][j] = dp2[i - 1][j - jw[i]] + jp[i]; } } } }

return dp2[N][W];

}

int main(int argc, char** argv) { W = 30; N = 3;

return 0;//정상종료시 반드시 0을 리턴해야합니다.

}

2) fraction knapsack : 탐욕 알고리즘


```cpp
#include <iostream>
#include <stdio.h>
#include <algorithm>
#define MAXN 31
#define MAXM 1001
int moneys[] = { 0, 1, 4, 6 };
int N; int MONEY;
using namespace std;

int dp[MAXM];
//최소 카운트를 세는 것! 
int getCnt() {
#if 0
    //최솟값 찾고 싶으므로, 무한대로 초기화
    for (int i = 1; i <= MONEY; ++i) { //0번지에는 0이여야함?
        dp[i] = 0x7fffffff;
    }
#endif 
    fill(dp + 1, dp + MONEY + 1, 0x7fffffff);

    for (int i = 1; i <= MONEY; ++i) {
        for (int j = 1; j <= N; ++j) {
            if (i >= moneys[j]) {
                if (dp[i] > dp[i - moneys[j]] + 1) {
                    dp[i] = dp[i - moneys[j]] + 1;
                }
            }
        }
    }

    return dp[MONEY];
}


int main(int argc, char** argv)
{
    N = 3; //돈의 종류 개수
    MONEY = 8; //돌려받으려는 값

    return 0;//정상종료시 반드시 0을 리턴해야합니다.
}

<이미 만들어진 코드들, 문제를 읽고 해당 알고리즘인지 파악하고, 구현> TSP LIS LCS MCM 동전 knapsack 피보나치

에라토스테네체의 체

1. 처음에 다 default true로 하기
2. i*i < n 인 i 까지 반복(sqrt(N))
3. %i == 0 이면 false로 바꾸기

현재 위치가 소수이면 primes vector 배열에 넣기 소수가 아닌 것들은 bool값 바꿔주기

10억 7은 int 안으로 들어올 수 있다. 그러나 곱하는 계산 과정 속에서 int 범위 넘을 수 있다. long long으로 사용해줘야한다!

그릐고 n을 나는 임시 변수로 저장하지 않아서 값이 바뀌었다. 그래서 제대로 된 답이 나오지 않았다. 변수를 그대로 사용할 때 뒤에서 다시 사용하면, 해당 값을 임시변수에 저장하여 사용하는 습관을 기르자.

#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <vector>

#define div (1000000007)
#define MAXN 100000
using namespace std;
bool isprime[MAXN + 1];
vector<int> primes;
int main(int argc, char** argv)
{
    int test_case;
    int T;
    freopen("input.txt", "r", stdin);
    cin >> T;
    //소수 전처리
    for (int i = 0; i <= MAXN; ++i) isprime[i] = 1; //모두 true로 초기화
    isprime[1] = false; isprime[0] = false;
    for (int i = 2; i * i <= MAXN; i++) {
        if (!isprime[i]) continue; //소수가 아니면 pass
        for (int j = i * i; j <= 100000; j += i) {
            isprime[j] = false;
        }
    }
    for (int i = 2; i <= MAXN; ++i) {
        if (isprime[i]) {
            primes.push_back(i);
        }
    }
    for (test_case = 1; test_case <= T; ++test_case)
    {
        int n, k;
        long long ans = 1;
        cin >> n >> k;
        //TODO: nCk 의 약수의 개수를 구하여라.
        //1. 소인수분해
        unordered_map <int, int> um; // 소수, 지수
        for (int prime : primes) {
            if (prime > n) break;
            int factor_cnt = 0;
            //n!
            int temp_n = n;
            while (temp_n) {
                temp_n /= prime;
                factor_cnt += temp_n;
            }
            //k!
            int temp_k = k;
            while (temp_k) {
                temp_k /= prime;
                factor_cnt -= temp_k;
            }
            //(n-k)!
            int temp_nk = n - k;
            while (temp_nk) {
                temp_nk /= prime;
                factor_cnt -= temp_nk;
            }

            if (factor_cnt > 0) {
                long long tmp = (factor_cnt + 1) % div;
                ans = (ans * tmp) % div;
            }
        }

        cout << "#" << test_case << " " << ans << "\n";
    }
    return 0;//정상종료시 반드시 0을 리턴해야합니다.
}

Procedural Statements (절차적 문장)

Procedural Statements는 순차적(Sequential)으로 실행되는 문장을 의미하며, 주로 always 블록 또는 initial 블록 내부에서 사용됩니다.

1. Procedural Blocks (절차적 블록)

Verilog에서는 프로시저 블록(Procedural Block)을 사용하여 논리 동작을 정의합니다. 대표적으로 다음과 같은 두 가지가 있습니다.

(1) initial 블록

• 시뮬레이션 시작 시 한 번만 실행되는 블록
• Testbench(테스트벤치)에서 주로 사용됨
• 합성(Synthesis) 불가

initial begin
    a = 0;
    #10 a = 1;  // 10ns 후 a를 1로 설정
end

(2) always 블록

• 특정 조건(Event)에 따라 반복 실행됨
• 하드웨어 설계에서 순차 논리(Flip-Flop, Latch 등) 및 조합 논리(Combinational Logic) 생성에 사용됨

always @(posedge clk) begin
    q <= d;  // clk의 rising edge마다 q에 d를 저장
end

2. Procedural Assignments (절차적 할당)

Procedural Block 내부에서 값을 할당하는 문장입니다.

(1) = (blocking assignment)

• 순차적으로 실행됨 (Blocking)
• 앞의 문장이 끝난 후 다음 문장이 실행됨

always @(posedge clk) begin
    a = b;   // b의 값을 a에 즉시 할당 (blocking)
    c = a;   // 위의 할당이 완료된 후 실행됨
end

(2) <= (non-blocking assignment)

• 동시에 실행됨 (Non-blocking)
• 모든 문장이 동시에 실행되므로 Register(레지스터) 동작을 표현하는 데 적합

always @(posedge clk) begin
    a <= b;   // b를 a에 비동기적으로 할당
    c <= a;   // 기존 a 값을 c에 할당 (이전 값이 유지됨)
end

3. Event Control (이벤트 제어)

Verilog에서는 특정 이벤트(Event)가 발생할 때 블록이 실행됩니다.

(1) 일반적인 이벤트 제어

• @() 구문을 사용하여 특정 신호 변화 시 블록을 실행

always @(clk)   // clk이 변할 때마다 실행
    q = d;

(2) Edge 트리거 이벤트 제어

• posedge : 상승 엣지(positive edge, 0 → 1)에서 실행
• negedge : 하강 엣지(negative edge, 1 → 0)에서 실행

always @(posedge clk)  // clk 상승 엣지에서 실행
    q <= d;

(3) 비동기(Asynchronous) 리셋을 포함한 이벤트 제어

• rst가 0이면 q를 0으로 초기화
• 그렇지 않으면 clk 상승 엣지에서 q에 d를 저장

always @(posedge clk or negedge rst) begin
    if (!rst) 
        q <= 0;  // rst가 0이면 q를 초기화
    else 
        q <= d;  // clk 상승 엣지에서 d를 저장
end

4. Procedural Statements (절차적 문장)

절차적 문장은 always 또는 initial 블록 내부에서 사용됩니다.

(1) If-Else 문

• 조건문을 사용하여 분기 처리
• 조건이 중복될 경우, 가장 먼저 참(true)이 되는 조건이 실행됨

always @(posedge clk) begin
    if (a > b) 
        result <= 1;
    else if (a == b) 
        result <= 0;
    else 
        result <= -1;
end

(2) Case 문

• 여러 개의 조건을 검사하는 경우 case 문 사용
• 기본적으로 case는 완전히 일치하는 경우만 실행됨

always @(posedge clk) begin
    case (sel)
        2'b00: out <= in0;
        2'b01: out <= in1;
        2'b10: out <= in2;
        2'b11: out <= in3;
    endcase
end

(3) casex 및 casez 문

• casex : x, z, ?를 Don't Care로 간주
• casez : z, ?만 Don't Care로 간주

casex (opcode)
    4'b1xxx: out = 4'b0001;  // MSB가 1이면 실행
    4'b01xx: out = 4'b0010;  // 상위 2비트가 01이면 실행
endcase

casez (opcode)
    4'b1zz0: out = 4'b1000;  // z는 무시됨
endcase

5. Loop Statements (반복문)

(1) repeat 문

• 지정한 횟수만큼 루프 실행

repeat (5) begin
    a = a + 1;  // a를 5번 증가
end

(2) while 문

• 조건이 참일 동안 루프 실행
• 합성(Synthesis) 불가능 → 시뮬레이션에서만 사용

while (a < 10) begin
    a = a + 1;
end

(3) forever 문

• 무한 반복 (종료 조건 없음)
• 하드웨어 합성 불가능 → 시뮬레이션에서만 사용

forever begin
    #10 clk = ~clk;  // 10ns마다 clk 반전
end

6. Fork-Join (병렬 실행)

Verilog는 기본적으로 begin...end를 사용하면 순차 실행하지만,
fork...join을 사용하면 동시에 실행(병렬 실행)됩니다.

fork
    #10 a = 1;
    #20 b = 2;
    #30 c = 3;
join

위 코드는 a, b, c가 동시에 변경됨 (비동기 실행).
만약 begin...end를 사용했다면 순차적으로 실행됩니다.

Letch (Edge Triggered):

• Letch는 엣지 트리거 방식을 사용합니다. 즉, 신호가 변화하는 순간에 동작합니다.
• 입력 신호의 변화(엣지)에 의해 동작을 시작하는 메모리 요소를 나타냅니다.
• 일반적으로 순차 회로에서 사용됩니다.

FF (Flip-Flop) (Level Triggered):

• FF는 레벨 트리거 방식을 사용합니다. 즉, 특정 레벨이 유지되는 동안 동작합니다.
• 일반적으로 레벨 감지 방식으로, 지속적인 신호 상태에 따라 동작합니다.

Logic Value (4-Value Logic System)

Verilog는 4-Value Logic System을 지원하며, 이는 디지털 회로의 신호 값을 표현하는 다양한 상태를 포함합니다.

각 Logic 값의 의미

• 0: false, ground, low, VSS, negative assertion (부정적인 신호 또는 낮은 전압)
• 1: true, high, Power, VDD, VCC, positive assertion (긍정적인 신호 또는 높은 전압)
• x: bus 충돌(unknown state) 또는 미초기화된 상태. 이 값은 여러 신호가 동시에 충돌할 때 나타날 수 있습니다.
• z: High Impedance (Hi-Z) 상태를 나타냅니다. 이는 세트되지 않거나 연결되지 않은 상태로, 일반적으로 Tri-state 버퍼에서 사용됩니다.

1. Data Types

Nets

• Nets는 회로의 물리적 연결을 나타냅니다. 예를 들어, wire는 물리적인 연결을 의미하며, 신호가 흐를 수 있는 경로를 정의합니다.
• wire, tri, supply1, supply0, wand, wor, triand 등 여러 가지 타입이 있으며, 주로 연결된 신호를 표현할 때 사용됩니다.

Register

• Register는 추상적인 저장 요소입니다. reg, integer, real, time 등 다양한 데이터 타입이 포함될 수 있습니다.

• 순차 회로에서 값을 저장하는 데 사용됩니다. 예를 들어 플립플롭(FF)나 레지스터는 상태를 유지해야 할 때 사용됩니다.

  중요: FF나 letch는 단순히 하드웨어에서 상태를 저장하는 요소에 해당합니다. 이를 구체적으로 표현하는 것이 reg, integer, real 등이죠.

Parameter

• Parameters는 런타임 상수로, 하드웨어 설계에서 유동적인 상수값을 정의하는 데 사용됩니다. 예를 들어, parameter WIDTH = 8;와 같이 상수 값을 정의할 수 있습니다.
• module parameter는 각 인스턴스별로 #() 또는 defparam으로 오버라이드(값을 변경)할 수 있습니다.

Concept of Type

타입 개념

• Verilog에서는 각 변수의 타입을 명시적으로 지정할 수 있습니다. 예를 들어 wire나 reg와 같은 기본 타입이 있습니다.
  • Procedural assignment는 reg 타입에만 가능합니다. 이는 프로시저적 할당 방식으로 값이 변경되는 경우에 사용됩니다.
  • Default는 보통 wire 타입입니다. 이는 기본적으로 물리적인 신호를 나타내는 데 사용됩니다.

Vectors

Vectors

• Vectors는 여러 비트로 구성된 신호를 나타냅니다. 예를 들어, reg [7:0] data;는 8비트 레지스터를 의미합니다.

• 비트 벡터는 [msb:lsb]로 표현되며, 크기 조정을 할 때 주의해야 합니다.

  크기 조정(Truncation & Padding)

  • Source가 더 크면: 더 작은 신호가 오른쪽에서 잘라지며(트렁케이션) 전달됩니다.
  • Source가 더 작으면: 패딩을 통해 왼쪽에서 0으로 채워집니다.

Literal Values

• Verilog에서 상수값을 표현할 때 4'b1001, 8'd255와 같은 literal 값을 사용합니다.
• 형식: [size]'[base][value]
  • 예: 4'b1001 = 4비트 바이너리 1001
  • 4'd9 = 10진수 9
  • 5'o11 = 8진수 11

Automatic Extension of Literals

• Verilog에서는 상수값을 확장할 때 MSB(최상위 비트)가 x나 z일 경우, 자동으로 확장이 될 수 있습니다.

Net Types

Nets

• Nets는 회로의 물리적 연결을 정의하며, 기본적으로 wire 타입으로 설정됩니다.
• wire 외에도 다양한 전달 타입이 존재합니다:
  • supply1, supply0: 전원 공급용 신호
  • tri: 트라이 상태 (Hi-Z 상태) 신호
  • wand, wor: AND/OR 결과로서의 연산 신호

Logic Conflict

• Continuous assignment에서 충돌이 발생할 수 있습니다. 예를 들어 wire로 선언된 신호는 여러 드라이버가 있을 경우 x 값이 될 수 있습니다.

Register Types

Register Types

• reg: unsigned, 사용자가 정의한 폭을 가진 4-상태 (0, 1, x, z) 값을 가질 수 있습니다.
• integer: signed, 32비트 크기의 4-상태 값을 가질 수 있습니다.
• 실수 타입: real, time, realtime 등 다양한 데이터 타입을 사용할 수 있습니다.

Choosing the Correct Data Type

• input port: 무조건 net type으로 선언해야 합니다. (데이터가 외부에서 들어오기 때문)
• output port: reg 또는 net type으로 선언할 수 있습니다. (값을 외부로 내보내는 신호)
• inout port: 무조건 net type으로 선언합니다. (입출력 모두 가능한 포트)

Parameter

Module Parameters

• Module parameters는 각 인스턴스에 대한 상수를 정의합니다.
• 예를 들어, 인스턴스를 만들 때 parameter WIDTH=8;과 같이 특정 값들을 설정하고, 이를 #()를 통해 오버라이드할 수 있습니다.

Local Parameters

• Local parameters는 모듈 내에서만 사용되는 상수입니다.
• Override할 수 없으며 상수 값으로 고정되어 있습니다.

Arrays

• Verilog에서는 다차원 배열을 설정할 수 있습니다. 예를 들어 reg [7:0] data[0:99];는 100개의 8비트 배열을 정의하는 방식입니다.

2. Operators

arithmetic bitwise logical: operand reduction by a single bit operation *reduction unary reduction operators : 결과 1, 0, x shift relational == : logical equality operator ===: case equality operator conditional triset, mux 구현할 때 사용 ?: concatenation replication

알겠습니다! 이번에는 Verilog에서 사용되는 다양한 연산자(Operators)에 대해 자세히 설명하겠습니다. 각 연산자의 종류와 특징을 설명하고, 어떻게 사용되는지 구체적인 예시를 추가하여 정리해 드리겠습니다.

2. Operators

1. Arithmetic Operators (산술 연산자)

산술 연산자는 수학적 계산을 수행하는 데 사용됩니다.

예시:

reg [3:0] a, b, sum;
a = 4'b0011;  // 3
b = 4'b0101;  // 5
sum = a + b;  // 8 (4'b1000)

2. Bitwise Operators (비트 단위 연산자)

비트 단위 연산자는 각 비트에 대해 연산을 수행합니다. 이러한 연산자는 wire 타입과 같이 net type에 사용됩니다.

예시:

reg [3:0] a, b, result;
a = 4'b1101;  // 13
b = 4'b1011;  // 11
result = a & b;  // 4'b1001 (AND 연산)
result = a | b;  // 4'b1111 (OR 연산)
result = a ^ b;  // 4'b0110 (XOR 연산)

3. Logical Operators (논리 연산자)

논리 연산자는 boolean 값을 처리하는 데 사용됩니다.

예시:

reg a, b, result;
a = 1'b1;  // true
b = 1'b0;  // false
result = a && b;  // 1'b0 (AND 연산)
result = a || b;  // 1'b1 (OR 연산)

4. Reduction Operators (축소 연산자)

축소 연산자는 벡터의 모든 비트를 하나의 값으로 축소하는 데 사용됩니다. 주로 wire 타입에 사용됩니다.

예시:

reg [3:0] a;
a = 4'b1011;  // 4비트 벡터
wire and_result;
assign and_result = &a;  // AND 축소 -> 1'b0

5. Conditional (삼항) Operator

조건부 연산자는 if-else 구문처럼 작동하지만, 한 줄로 간단하게 표현할 수 있습니다. if else 문 대신에 사용도 가능하다.

예시:

reg [3:0] a, b, c, result;
a = 4'b1100;
b = 4'b1010;
c = 4'b0110;
result = (a == 4'b1100) ? b : c;  // 4'b1010 (a가 참이면 b)

6. Concatenation Operator (연결 연산자)

연결 연산자는 여러 비트나 벡터를 합치는 데 사용됩니다.

예시:

reg [3:0] a, b, result;
a = 4'b1100;
b = 4'b1010;
result = {a, b};  // 8비트 벡터: 4'b11001010

7. Replication Operator (복제 연산자)

복제 연산자는 하나의 값을 여러 번 반복하여 벡터로 만드는 데 사용됩니다.

예시:

reg [3:0] a, result;
a = 4'b1010;
result = {3{a}};  // 12비트 벡터: 4'b101010101010

좋아요! 추가적으로 Shift 연산자, 관계 연산자, 논리/케이스 동등 연산자에 대해 설명하겠습니다.

8. Shift Operators (시프트 연산자)

Shift 연산자는 비트를 왼쪽 또는 오른쪽으로 이동하는 데 사용됩니다.

논리 시프트 vs. 산술 시프트 차이점

• 논리 시프트(<<, >>): 비어 있는 자리를 0으로 채운다.
• 산술 시프트(<<<, >>>): 오른쪽 시프트 시 부호 비트를 유지한다.

예제

reg [7:0] a, b;
a = 8'b00001111;  // 15
b = a << 2;       // 8'b00111100 (왼쪽으로 2비트 이동, 60)
b = a >> 2;       // 8'b00000011 (오른쪽으로 2비트 이동, 3)

산술 시프트 예제

reg signed [7:0] c;
c = -8'sd4;        // 8'b11111100 (-4)
c = c >>> 1;       // 8'b11111110 (-2) (MSB 유지)

9. Relational Operators (관계 연산자)

관계 연산자는 두 값 간의 크기 비교를 수행합니다. 결과는 1(true) 또는 0(false)이 됩니다.

예제

reg [3:0] a, b;
a = 4'b1010;  // 10
b = 4'b0101;  // 5
if (a > b)    // 10 > 5 → 참 (1)
    $display("a가 b보다 크다");

10. Equality Operators (동등 연산자)

논리 동등 연산 (==, !=)

• == : 두 값이 같으면 1을 반환 (논리적 동등)
• != : 두 값이 다르면 1을 반환 (논리적 비동등)

예제

reg [3:0] a, b;
a = 4'b1010;  // 10
b = 4'b1010;  // 10
if (a == b)   // 참 (1)
    $display("a와 b는 같다");

⚠ 주의: x 또는 z가 포함된 값을 비교하면 결과가 X가 될 수도 있음.

Case Equality Operators (===, !==)

• === : 두 값이 모든 비트가 완전히 같아야 1을 반환 (비교할 때 x와 z도 고려)
• !== : 두 값이 하나라도 다르면 1을 반환 (비교할 때 x와 z도 고려)

논리 동등(==) vs. 케이스 동등(===) 비교

예제

reg [3:0] a, b;
a = 4'b10xx;
b = 4'b1010;

if (a == b)   // 결과: X (논리 비교)
    $display("a와 b는 같다");

if (a === b)  // 결과: 0 (모든 비트 다 비교)
    $display("a와 b는 완전히 같다");
else
    $display("a와 b는 다르다");

Operator Precedence

외우기 힘드니 괄호를 사용하자

mux.v

`timescale 1 ns / 1 ns
//port 
module mux
(
 output reg y ,
 input wire s ,
 input wire i1 ,
 input wire i0
);

 always @ (s or i1 or i0)
  if (s == 1)
   y = i1 ;
  else
   y = i0 ;

endmodule
~

mux_test.v

`resetall
//`include "defines.inc"
`timescale 1 ns / 1 ns

module mux_test;

  wire  y ;
  reg   i0 ;
  reg   i1 ;
  reg   s ;

//MUX instance([module name] [instance name]
 mux  mux1(
        y,
        s,
        i1,
        i0
        );
 task display ;
  begin
   $display
   (
    "time=%0d" , $time, " ns"
  , " s=", s
  , " i1=", i1
  , " i0=", i0
  , " y=", y
  );
  end
 endtask

 initial
  begin
  s = 0 ; i1 = 0; i0 = 1 ; #10 ; display;
  s = 0 ; i1 = 1; i0 = 0 ; #10 ; display;
  s = 1 ; i1 = 0; i0 = 1 ; #10 ; display;
  s = 1 ; i1 = 1; i0 = 0 ; #10 ; display;
 end

endmodule

xmvlog

xmelab

xmelab -access RWC top (gui 접근 설정)

xmsim

xmsim -gui -run mux_test

Multicore: Multiple CPU cores are packed onto a single chip. -> using threads (to run in parallel) -> How to schedule jobs on multiple CPUS(or cores)?

Single CPU with Cache

• Cache:
  • small, fast, popular data의 copy들을 가진다.
  • temporal & spatial 지역성 활용
• Main memory: 모든 데이터를 저장, slower than cache

Cache Coherence(캐시일관성)

:여러 캐시들이 동일한 메모리 위치에 대한 데이터를 보유할 때, 각 캐시가 최신의 일관된 데이터를 유지하도록 보장하는 메커니즘

• how?: 여러개 프로세스들이 메모래에 갱신할 때 항상 공유되도록 한다.(bus snooping)
• 캐시는 자신과 메모리르 ㄹ연결하는 버스의 통신상황 계속 모니터링, 캐시 변경 발생시
  • invalidate protocol: 해당 데이터의 복사본을 무효화 시킨다.
  • update protocol : 해당 데이터의 모든 복사본도 업데이트 한다.

    Synchronization

• lock(&m), unlock(&m) 필요
• ex) list에서 원소 제거하는 과정: critical section 임.
• fine grained 하게 최대한 작게 임계구간 잡아야함.
• locking 많이 -> concurrency 감소 = 성능 감소

  Cache Affinity (Processor Affinity)

  : 프로세스가 다음에 실행될 때 동일한 CPU에서 실행되는 것이 유리하다.
  • 왜냐하면, 해당 CPU 캐시에 일부 정보(state)가 이미 존재하고 있기 때무에 더 빨리 실행될 것이기 때문이다.

    Single Queue Multiprocessor Scheduling(SQMS)

• 모든 job들이 single queue에 scheduled.
• 각 CPU는 global shared queue를 보고 다음 job을 고른다.
• 문제:
  • 작업이 너무 자주 서로 다른 큐로 이동한다.(스케쥴링 효율저하)(cache affinity저하)
  • 공유되는 큐를 사용하므로 locking 형식 필요 -> 확장성(scalability)이 떨어진다.

    Scheduling Example with Cache affinity

• Preserving affinity: E 제외 다른 process들은 움직이지 않음.
• 구현 복잡

  Multi-Queque Multiprocessor Scheduling(MQMS)

• 단일 queue 문제로 인해, MQMS는 큐도 여러개이다!(CPU 마다 각자 큐 가짐)
  • 각 큐는 RR 혹은 다른 스케쥴링 알아서...
• job은 하나의 scheduling queue에 고정.
  • data sharing과 동기화 문제 방지한다.
  • CPU 개수가 증가할수록, 큐도 증가하기 때문이다.
• 장점: 나은 scability, cache affinity

  문제: Load Imbalance issue

• 여러개 큐를 사용하므로 load imbalance issue 발생...
• 그런데 만약 C가 끝나면 , A가 B,D보다 2배의 CPU 차지
• 심지어 만야 A가 끝나면, CPU0은 놀게 된다.

  해결: Migration(job 옮기기)

  : 작업을 한 CPU에서 다른 CPU로 이주시키기
• 그러나 한번의 이주만으로는 문제 해결 안됨. 지속적 이주가 필요하다

Migration 필요 여부 결정 how? Work Stealing

• job의 개수가 낮은 큐: source queue
• 다른 target queue들에 훨씬 많은 수의 작업이 있는지 가끔씩 검사한다.
• target queue가 source queue보다 훨씬 많이 차있으면, source queue가 작업을 가져온다.
• 문제:
  • 큐 자주 검사 -> overhead 발생 -> 확장성 저하
  • 큐 자주 검사 안하면 -> load imbalance 문제 해결 못함.

9. Fair share scheduler

• CPU time의 일정 비율대로 각 job이 할당 받는 것이 보장됨.
• = Proportional Share(비례배분!)
• turnaround time 과 response time은 optimized 되지 않음
• ex ) Lottery scheduling / Stride scheduling / Completely Fair schedulig(Nice,vruntime, timeslice, red-black tree)

  9.1 Lottery scheduling

  Basic Concept-추첨권이 당신의 지분이다.

  Tickets: 하나의 process가 받는 resource의 비율 단위

• tickets의 비율이 시스템 리소스의 할당 비율
• process가 가진 티켓 수에 따라 해당 자원을 나눠가짐.
• ex) 프로세스 A가 75개의 티켓을 가지고 있으면, CPU 시간의 75%
• 프로세스 B가 25개의 티켓을 가지고 있으면, CPU 시간의 25%를 차지하도록 목표한다.

방법 초 간단.

• 스케줄러는 winnig ticket을 뽑는다.(난수)
  • 해당 process를 로드하고, run 한다.

    Example

• 해당 job들이 더 길게 경쟁할 수록, 그들이 기대하던 percentage와 가까워진다. 만약에 job들의 실행수가 적으면, 비율대로 실행이 안될 수도 있다.
• 무작위성을 기반으로 하므로, 원하는 비율을 정확히 보장하지느 않는다. 장시간 실행하면 원하는 비율 달성 가능성 높아진다.
• 처음엔 랜덤한 결과로 보이지만, 시간이 지날수록 각 프로세스가 받은 티켓 수에 비례하여 자원을 사용하는 비율이 점차 목표 비율(75% vs 25%)에 가까워짐.
• turnaround, response time 최적화 x
• short ,long job 고려 x

  9.2 Ticket Mechanisms

  1) Ticket Currency(티켓 통화)

  : 사용자가 각 프로세스나 작업에 자신만의 방식으로 티켓을 할당하고, 시스템이 이를 전역 티켓 수(Global currency)로 변환하는 방식
• A1: 100 * (500/1000)
• A2: 100 * (500/1000)
• B1: 100 * (10/10)

  2) Ticket transfer(티켓 양도)

  : 자기가 당장 자원이 필요하지 않으면,** 일시적으로** 다른 프로세스에게 티켓 나눠주기
• ex) client가 server에게 ticket transefer(나중에 환수)

  3) Ticket Inflation(티켓 인플레이션)

  : 자기 소유 티켓의 수를 임시적으로 증가시키거나 감소시키기
• 만약 특정 프로세스가 더 많은 CPU 시간을 필요하면, 티켓수를 스스로 일시적으로 증가 시킨다.

  9.3 Implementation

• 프로세스 및 티켓:
  • Job A는 100개의 티켓
  • Job B는 50개의 티켓
  • Job C는 250개의 티켓
  • 총 티켓 수는 400개야 (100 + 50 + 250).
• 목록 순서: 프로세스는 티켓 수에 따라 연결 리스트로 관리됨.
• 코드 설명:
  • 랜덤 티켓 추출 (getrandom 함수): getrandom(0, totaltickets)에서** 0과 총 티켓 수(400) 사이에서 무작위로 티켓 번호가 선택**됨. 예를 들어, 150번 티켓이 선택될 수 있어.
  • 반복문 (while 루프): 선택된 티켓 번호에 해당하는 프로세스를 찾기 위해 리스트를 순차적으로 탐색함.
    • counter는 현재까지 확인한 티켓 수를 누적.
    • 현재 프로세스의 티켓 수를 counter에 더하고, counter가 winner 값(랜덤으로 선택된 티켓 번호)을 초과하면 그 프로세스가 선택됨.
    • 예를 들어, winner가 123이라면 Job A와 Job B를 합쳐 150(즉, Job B가 포함된 시점) Job B가 선택됨.
• 주의: 최악의 경우 리스트 끝까지 탐색해야 하는 상황이 있을 수 있음. Job C가 선택되려면 끝까지 가야 함. -> 정렬: 티켓 수에 따라 미리 프로세스가 내림차순 정렬하기(이 작업은 한 번만 처리되는 오버헤드임)

  9.4 Lottery Fairness Study

  U: unfairness metric = (first job completed 시간) / (second job completed 시간)

  • 실행시간(run time): A : 10, B : 10
  • 끝난시간(finish time): A : 10, B : 20
  • U = 1.0 / 2.0 = 0.5
  • U가 1에 가까울 수록 fair하다.(거의 동시에 끝난다)

    Lottery scheduler 문제: Fairness Problem

• 각 job들이 모두 같은 티켓 가지고 있는 예시이다.
• job length가 짧은 처음에는 unfair 할 수 있으나, 길어질수록 fair함.

  작업 길이가 그리 길지 않을 때, 평균 불공정성(average unfairness)이 상당히 심각할 수 있다.

9.5 Solution: Deterministic Approach: Stride Scheduling

: 무작위성을 이용하면 단순하게는 가능하지만 정확한 비율 보장을 못하므로 결정론적으로!! : 우선순위가 높으면 -> 티켓 많음 -> 보폭 적음 -> 조금씩 진행 되므로, 강강약약인 OS는 기회를 더 줌. : pass value(+=stride)가 가장 적은 process를 schedule시킨다.

Stride of each process

• (large number) / (the number of tickets of the process)
• 자신이 가지고 있는 추첨권 수에 반비례
• Example: large number = 10,000
  • Process A has 100 tickets -> stride of A is 100
  • Process B has 50 tickets -> stride of B is 200

    Counter(=passvalue)

    : 각 process마다 0에서 시작하여 run할때마다, 각 프로세스의 stride를 더한다. : 얼마나 CPU를 사용하였는지 추적 용도

    Stride Scheduling Example(imp)

    Problem1: 각 process마다 pass value를 유지해야한다.

    Problem2: 새로운 job이 pass value 0으로 새로 들어오면, 기존 다른 어떤 process 보다 pass value가 작으므로, CPU를 독점할 것이다.

    Stride Scheduling vs Lottery Scheduling

• stride scheduling: fairness 보장(짧은 길이의 job이더라도)
• lottery scheduling: no per process-state (overhead x)

9.7 The Linux Completely Fair Scheduling(CFS)

• non-fixed timeslice
  • CPU의 사용 비율로 할당
• priority - nice value 사용
  • 덜 nice 할수록, 우선순위 높아지게 weight 크다.
  • 더 nice 일수록, 우선순위 낮아지게 weight 작다.
• efficient data structure
  • use red-black tree(효율적인 검색, 삽입, 삭제)

    1) (basic) Virtual runtime(vruntime)

    • 프로세스가 실제로 실행된 시간(프로세스마다 별도 관리)
    • vruntime이 가장 낮은 프로세스를 스케쥴러가 선택한다.
    • CPU 자원의 공정한 배분을 도와준다.
    • process가 얼마만큼 CPU 썼는지 추적한다.

      2) Sched_latency(지연시간)

    • 스케줄러가 프로세스에게 CPU를 할당하기 위한 기본적인 지연 시간을 의미해. 일반적으로 이 값은 48밀리세컨드(millisecond)로 설정
    • 공정하게 CPU 자원을 할당받을 수 있도록 타임슬라이스가 결정되며, 프로세스 수가 많아질수록 각 프로세스가 받을 수 있는 CPU 시간은 줄어듦

      3) (basic) Time Slice = sched_latency / (실행 중인 프로세스의 수)

      Example

• timeslice = 48/4=12ms -> 48/2 = 24ms
• min_granularity: CPU 프로세스에 할당되는 최소 타임슬라이스
  • 만약에 time slice가 6ms보다 작으면 그냥 6ms 보장
  • 왜냐하면, 프로세스 수가 많을 경우, 스케줄러는 각 프로세스의 상태를 관리하고 CPU를 할당하기 위해 지속적으로 작업해야한다. 이때 너무 짧은 타임슬라이스를 설정하면 스케줄링에 소요되는 오버헤드가 증가한다.
  • 이거 때문에 완전 complete fairness를 보장하는 건 아님...

4) Weight-Nice Value

Nice Value

• CFS가 priority을 조정할 수 있게 한다.
• Nice vlaue: -20 ~ 19 정수
  • -20: 가장 높은 우선순위 (덜 나이스 할수록 더 많이 CPU 할당)
  • +19: 가장 낮은 우선순위 (더 나이스 할수록 덜 CPU 할당)
• nice value # weight (mapping)
  • nice 낮을 수록, weight 높다.

    5) Weighting=가중치 (Niceness)

    (new) Timeslice with weight

    
• 프로세스의 우선순위 차이까지도 고려한 timeslice이다.

(new) Vruntime with weight

: vruntime += nicevalue의 중간값 weight(0) / 내 weight * runtime

• 실행시간 누적하는 것 뿐만 아니라 우선순위 차이까지도 고려한다.
• weight 높을수록, vruntime 작아져서 먼저 실행된다.(stride로 나누듯이 weight로 나누기)

---> 가중치 표의 장점은 nice값의 차이가 유지되면, CPU 배분 비율도 유지된다.

Structure of ready queue: Red-Black Tree

• balanced binary tree
• ordering : O(logn)
• 최소 vruntime process을 효율적으로 찾을 수 있다.
• 오직 running(runnable O, sleep X, blocked X)중인 process들만 tree에 있다.

I/O(blocked) and Sleeping(semaphore, api) Process ?

• 문제: process가 sleep 하는 동안은 vruntime이 증가하지 않아, 매우 작아집니다. 매우 작아진 프로세스가 다시 CPU 사용하게 되면, CPU를 독점하여 과도하게 차지할 수 있습니다.
• 해결: 프로세스가 다시 깨어날 때, 해당 프로세스의 vruntime을 현재 트리에서 발견된 최솟값으로 설정합니다.
• 그러나, Process that sleep for short periods of time frequently do not ever get their fair share of the CPU.(왜??)

FIFO algorithm

• convoy effect(tractor가 길을 다 막는다) -> low CPU 와 device utilization

  SJF(Shortest Job First) scheduling algorithm

• *평균 turnaround time(terminate-arrival)을 줄인다. *
• 평균 waiting time(start-arrival)을 줄인다.
• job length를 미리 알 수 있는가? 항상 좋은가?

  RR scheduling algorithm

• response time 줄인다.(각 프로세스마다 정해진 타임 퀀텀 동안 번갈아가며 CPU 할당)
• turnaround time을 줄이지는 못한다.

  Need a new algorithm for

• optimize turnaround time -> run shortest job first
• minimize response time -> use Round Robin to 가능한 많은 job 실행 (반응성=first run - arrival)
• Learn from the past to predict the future without prior knowledge of job length

8. Scheduling: Multi-Level Feedback Queue(MLFQ)

8.1 Basic Rules

• 다른 priority level들로 구성된 queues들을 가진다.
• 하나의 job은 하나의 queue에서 실행된다.

  Rule 1: 다른 큐끼리) higher queue에 있는 job이 우선적으로 실행된다.

  Rule 2: 같은 큐끼리) Round Robin 스케쥴링을 사용하여 실행한다.(정해진 타임 퀀텀 끝나면 다른 job)

• 작업의 관찰된 행동에 따라 우선순위를 조정합니다.
  • 작업이 반복적으로 CPU를 포기하고 입출력(I/O)을 기다리면, 우선순위를 높게 유지해.
  • 반면, 작업이 오랜 시간 동안 CPU를 집중적으로 사용하면, 그 작업의 우선순위를 낮춘다.

8.2 How to Change Priority

Rule 3: 처음에 system에 job이 들어올 때, 가장 높은 priority queue에 위치한다.

Rule 4a: 실행중에 모든 time slice를 사용하면, 해당 job이 priority는 감소한다.

Rule 4b: 모든 time slice을 사용하기 전에 job이 CPU를 놓으면, 계속 해당 priority level을 유지한다.

--> 이러한 방식으로 Shortest Job First에 근사한다. 왜냐하면, 4a: CPU을 집중적으로 사용하는, 오래 걸리는 job이므로 우선순위를 낮추어 나중에 실행하게 한다. 4b: CPU를 조금 쓰고 스스로 놓는 경우, short job이므로 높은 우선순위 유지 -> turnaround time 평균 줄이기, fairness 추가(?) -> 낮은 우선순위 계속 실행 못할 수도 있으므로 priority boost 추후 사용

Example 1: 한개의 긴 실행시간 가진 작업

처음 시스템에 들어올 때 가장 높은 우선순위 큐에 위치하지만, 10ms 안에 CPU를 놓지 않으므로 계속해서 더 낮은 priority 큐로 강등된다.

Example 2: 짧은 작업과 함께 가장 먼저 시스템에 들어온 A는 가장 priority 높은 Q2에서 시작하지만, 앞선 예시와 같은 이유로 강등된다. 그후 B가 들어오고 B도 20ms 동안 실행하므로 강등된다. 그렇지만 A보다는 높아서 먼저 실행된다.

Example 2: 입출력 작업 B는 CPU를 매우 짧게 사용하여, 10ms안에 스스로 놓기 때문에 강등되지 않고 I/O 작업을 수행한다. 그리고 CPU는 B의 I/O 작업이 끝나고 나서 (B가 ready queue로 들어가므로) 다시 또 짧은 job인 B가 실행 될 수 있도록 한다.

-> 세 경우 모두 작업이 짧은 작언인지 긴 작업인지 알 수 없어도 먼저 짧다고 가정 후 우선순위를 조정하며 SJF 에 근사한다.

Problems with the Basic MLFQ

1) Starvation

• interactive(대화형) jobs들이 많으면, 계속 해당 job들만 실행되므로, long running job들이 CPU를 할당 받지 못한다.

  2) Game the scheduler

• 만약, time slice의 99%만 사용하고, I/O operation 을 수행하는 job이 있다고 가정하자. 이 job은 time slice를 다 사용하기 거의 직전에 스스로 CPU를 놓으므로 계속 높은 priority을 유지한다. 그렇지만 계속해서 CPU를 거의 다 사용하여 독점현상이 발생한다.

  3) A program may change its behavior over time

• CPU bound process였다가 I/O bound process로 바뀔 수도 있다. 이때 다시 우선순위가 높아지는 mechanism이 필요하다.

  P2-Solution: Better Accounting

  Rule 4: 한 작업이 주어진 레벨(우선순위 큐)에서 할당된 시간(time allotment)을 모두 사용하면, (몇 번이나 CPU를 포기했는지에 상관없이), 그 작업의 우선순위가 낮아진다(즉, 큐에서 아래로 이동한다). 입출력 중점 대화형 작업을 빨리 실행시킨다.

  이 규칙은 작업이 특정 우선순위 큐에서 CPU 시간(time allotment)을 다 소모하면, 더 낮은 우선순위로 이동하게 된다.

P1,P3-Solution: The Priority Boost

Rule 5: some time period S 이후엔, 모든 job들을 가장 높은 우선순위 큐로 옮긴다.

Tuning MLFQ And Other Issues

-> Lower Priority, Longer Quanta

• 우선순위가 높은 큐 -> short time slice
• 우선순위가 낮은 큐 -> long time slice

  The Solaris MLFQ Implementation

• 60개 queue를 가진다.
• 낮은 우선순위 : 수백 milliseconds
• 높은 우선순위 : 20msec(빨리 빨리 response time 반응성)
• 1s 마다 우선순위 boost!

--> 프로세스의 CPU 사용에 대한 이전 지식이 필요하지 않는다.

fork()

• 자식 process 생성
• 부모의 address space copy

  wait() or waitpid()

• child와 parent 간의 dependency 생성(deterministic)
• reaping a child process
• 자식 process가 종료되면, exit(status)을 report 하도록 한다.
• 자식의 exit status는 process table에 저장되고, process table의 entry는 parent process 가 wait call을 invoke 한 뒤 해제된다.
• wait()가 호출되면 부모 프로세스는 자식의 종료 상태를 받아들이고, 그 후 자식 프로세스의 프로세스 테이블 항목(PCB)은 운영체제에 의해 할당 해제됩니다. 이를 통해 좀비 프로세스(종료 후 아직 reaping 되지 않은 자식)가 정리되고, 프로세스 테이블에 남은 항목이 제거됩니다. (자식 프로세스에 대한 모든 참조가 삭제됨을 의미합니다.)

  Zombie Process

• process 실행은 다 완수했지만, process table에 남아있는 process
• 부모는 executing, while child is dead.

  Orphan Process

• parent가 wait 하지 않은 상태로 죽었는데, 실행중인 child process
• init process가 새로운 부모가 되고, wait call을 호출한다.
• 본래 부모는 dead, while child is executing

Does fork() immediately copy the entire process heap in Linux? - NO

Copy-On-Write 방식 사용

• 기본 동작:
  • fork()를 호출하면 부모 프로세스의 메모리 공간(코드, 데이터, 힙 등)을 자식 프로세스와 공유합니다.
  • 하지만 실제로는 메모리를 복사하지 않고, 두 프로세스가 같은 메모리 페이지를 참조합니다.
• 메모리 페이지 수정 시점:
  • 부모 프로세스나 자식 프로세스 중 하나가 메모리를 수정하려고 할 때, 해당 페이지가 복사됩니다.
  • 최초로 수정하려는 시점에만 복사가 이루어지며, 이때 각 프로세스는 독립적인 메모리 공간을 갖게 됩니다.

exec()

: running a new program

• parent 코드 말고 다른 코드 실행하고 싶어!
• 운영체제는 새로운 프로그램(바이너리 이미지)을 메모리에 로드하고, 새 프로그램을 위한 스택 및 힙을 초기화합니다.
• 인자: (실행할 바이너리 파일의 경로, 해당 프로그램에 전달할 인자 배열 argv)
• 1번) 현재 프로세스의 내용을 지우고 2번)새로운 프로그램의 내용을 메모리에 로드하여 새로운 프로그램을 실행시키는 역할을 합니다.(pid는 유지)(현재 실행중인 process 덮어씌우기)
• return 값 없다.
• ex)

• kernel에서 제공하는 API를 가지고 process 실행

• fork 와 exec 구분하는 이유?

• 실행 전에 I/O redirection 또는 pipe를 중간에 사용하려고

• I/O redirection : 앞의 outcome이 stdout이 아니라 뒤에 있는 파일로 가도록해준다.

• pipe: 앞의 outcome이 뒤의 입력으로 가도록 해준다. 서로 address 공간이 달라서 원래는 접근이 불가능하지만, OS가 Inter Process Communication을 제공한다. (I/O redirection, pipe)

I/O redirection

: 전자의 output을 capture하여 후자의 input으로 send한다.

File Descriptor and File Descriptor Table

• process가 생성되면, process의 file descriptor array를 만든다.
• STDIN, STDOUT, STDERR는 초기화 되어있다.
• File Descriptor -> File Struct(각 struct마다 offset 존재)
• ex) read 시스템 콜 하게되면, kernel이 해당 fd가 가리키는 struct의 offset을 읽고 buffer에 복사한다.
• ex) write 시스템 콜 하게되면, kernel이 buffer에 있는 내용을 해당 fd가 가리키는 struct의 offset에 이어서 쓴다.

File Descriptor and System Calls

• open(): 새로운 파일을 열 때, 운영체제는 새로운 파일 객체를 할당하고, 이를 가리키는 FD를 생성합니다. 이 파일 디스크립터는 파일 디스크립터 테이블에서 사용 가능한 가장 작은 번호를 할당받습니다.
• close():
  • 파일 디스크립터 fd가 더 이상 사용되지 않도록 해제합니다.
  • 해당 파일 디스크립터와 연결된 파일 객체가 더 이상 어떤 파일 디스크립터에서도 참조되지 않으면, 그 파일 객체도 메모리에서 해제됩니다.
• fork():
  • 부모의 fd table을 자식에게 copy합니다.(file struct 공유)
• exec():
  • 프로세스가 파일 디스크립터 테이블을 유지한다.

    Pipe: '|'

    : 한 process의 output이 STDOUT이 다른 process의 STDIN으로 들어간다.

Duplication of FD using dup()

fd = dup(n) system call : file descriptor table의 빈 곳을 찾아 n을 복사한다.

pipe()

: 커널에서 관리되는 특수한 파일(kernel buffer을 읽고 쓰는 fd)로, 두 개의 파일 디스크립터를 통해 프로세스 간에 데이터를 전달할 수 있습니다. 이 파일 디스크립터들은 읽기와 쓰기를 위한 각각의 끝을 나타냅니다.

• 파이프(pipe)는 단방향(unidirectional) 통신(FIFO queue)을 위해 사용됩니다.
• 한 쪽에서는 데이터를 쓰고, 다른 쪽에서는 그 데이터를 읽을 수 있습니다.
• No structured communication: 데이터의 크기나 송신자/수신자 정보를 알 수 없습니다.
• 파이프의 접근 방식은 파일 디스크립터(file descriptor)를 통해 이루어집니다.
• 파이프는 두 개의 파일 디스크립터로 구성됩니다:

  p[0]: 읽기 끝 (read end)

  • 다른 프로세스는 p[0]을 통해 데이터를 읽습니다.
  • 만약 읽을 데이터가 없으면, 읽기 프로세스는 차단(block)되어 대기 상태가 됩니다.
  • 즉, 버퍼에 데이터가 쌓일 때까지 읽는 프로세스는 기다리게 됩니다.

    p[1]: 쓰기 끝 (write end)

  • 한 프로세스가 p[1]을 통해 데이터를 쓰면, 그 데이터는 커널에서 관리하는 버퍼에 저장됩니다.

Pipe Used by Commands

e.g., > ps-aux | grep root | tail

Anonymous Pipe

int pipe(int filesdes[2]) : 프로세스가 파이프를 만들지만 실제로 누가 쓰고 읽는지 알 수 없다. 부모 process 는 fd[0]을 통해 읽고, fd[1]에다가 쓴다. 만약 fork를 하는 경우, 동일한 fd table 공유, 즉 동일한 pipe 공유 child process는 fd[0]을 통해 읽고, fd]1]에다가 쓴다. 따라서 parent의 close(fd[0]), child의 close(fd[1]) 하면 메모리 누수를 막는다.

한계

두 개 프로세스가 커뮤니케이트 할 땐 좋지만,

• 한개의 process가 communicate 끝난 다음에 다른 process가 communicate할 수 있다.
• 그리고 process가 여러개인 경우 누가 읽고 쓰는지 모른다.

Named Pipe(FIFO)

• child-parent가 아닌 여러 process가 공유할 수 있게 해주는 pipe
• mkfifo or mknod 명령어를 통해 생성된다.
  • int mkfif (const char *paht, mode_T, mode);
  • file이라는 path를 통해서 kernel buffer을 연결 할 수 있게 만들어준다.
  • file path가 곧 kernel buffer에 대한 이름이다. ex)
  • Write-Only without O_NONBLOCK(O_WRONLY): 파일을 쓰기 전용으로 열겠다.
  • 읽기 프로세스가 대기 중인 경우: 쓰기 작업이 즉시 완료됩니다.
  • 읽기 프로세스가 없는 경우: 쓰기 작업은 블로킹 상태가 되어 대기하게 됩니다.
  • nmyfifo라는 kernel buffer가 할당됨
  • unlink() file-system call: 실제 file object delete하는 역할