기능이 바뀐거는 fix, 단순 구조가 바뀐거는 refactor

• 16바이트 ~ 20바이트의 URL-safe base64 encoding 진행한 값 권장

• 웹 인증에서 패스워드는 큰 위협
• 보안성, 개인정보, 편의성 측면 때문에 계속해서 사용되어 왔음
  • 그러면서 SSO를 이용해 편의성을 높이거나 브라우저 메타데이터를 활용하여 의심스러운 로그인을 감지하는 기법들 등장
• FIDO2표준(패스키: 패스워드리스)의 도입으로 생체정보나 PIN을 통해 공개키 기반 인증이 가능해짐
  • 그러나 이로인해 접근권한 상실 가능성 증대
• 클라우드 저장소, 이메일 서비스에 E2EE 도입중
  • 데이터 보안은 강화되지만 복구성 측면에서 클라이언트의 부담 증대(트레이드 오프)

• 해당 논문에서 수행한 일

1. 현대 웹 인증 및 복구 메커니즘을 체계화하고, 특히 E2EE 기반 인증의 보안·프라이버시·사용성·복구 가능성을 분석
2. 2024년 기준 미국 내 인기 웹사이트에서의 패스워드리스 인증 도입 현황을 조사하고, E2EE 클라우드/이메일/메신저 서비스들의 인증 및 복구 방식을 심층 분석
   • 특히 복구 메커니즘의 보안이 종종 취약점이 되는 점을 지적하며, 사용자가 직접 복구 키를 저장해야 하는 방식이 오히려 E2EE의 채택을 저해할 수 있음을 강조
   • 신뢰할 수 있는 연락처 인증(trusted contacts) 등 일부 오래된 인증 방식이 E2EE 복구에서는 재조명될 필요가 있음을 제안

웹 인증 및 복구의 현황

• 우리는 현대의 인증 방식을 사용되는 맥락에 따라 크게 두 가지 범주로 나눈다:
  1. 기본(primary) 인증 방식
  2. 보조(secondary) 인증 방식

     기본 인증 메커니즘은 신원 확인을 위한 첫 번째이자 (종종 유일한) 단계로 사용 반면, 보조 인증 메커니즘은 기본 인증이 성공적으로 완료된 후에만 작동되는 방식

주요 인증 메커니즘

1) 비밀번호

• 비밀번호의 보안성과 사용성 문제는 너무나 많음

• 수십 년간의 학술 연구 결과에 따르면,

  1. 사용자는 비밀번호를 자주 잊어버리고,
  2. 쉽게 추측 가능한 비밀번호를 사용하며,
  3. 여러 계정에서 같은 비밀번호를 재사용하는 경향이 있고,
  4. 비밀번호가 유출되거나 재사용되었다는 알림을 받아도 비밀번호를 바꾸지 않는 경우가 많음

• 하지만 오늘날의 위협 환경에서는,비밀번호 강도를 높이더라도 피싱 공격, 대규모 데이터 유출로부터 사용자를 충분히 보호할 수 없음

• 최근 사용자의 자격증명이 유출되었는지 확인할 수 있는 DB가 존재하고, 업계에서는 암호 기반 자동 알림 시스템도 도입 중

• 예를 들어, Meta의 Private Data Lookup(PDL) 도구는 Private Set Intersection(사적인 교집합 계산)을 통해 사용자의 비밀번호가 유출된 비밀번호 목록에 포함되어 있는지 서버 측에서 확인해줌

• 그러나,학계에서는 이러한 알림의 실질적인 효과가 제한적이라는 점을 여러 차례 입증함

  • 경고를 받은 사용자 중 실제로 비밀번호를 바꾸는 비율은 약 25% 정도에 불과함

이처럼, 비밀번호 기반 인증은 보안성과 사용성 사이의 근본적인 긴장을 피할 수 없기 때문에, 점점 더 많은 전문가들이 비밀번호를 "레거시 인증 메커니즘", 즉 시대에 뒤떨어진 방식으로 간주 중임

비밀번호 관리자(Password Manager)

• 많은 자격 증명 정보를 보다 쉽게 관리할 수 있도록 돕기 위한 대응 전략 중 하나는, 사용자에게 비밀번호 관리자(Password Manager)사용을 권장하는 것

• 기술 커뮤니티에서는 비밀번호 관리자를 보안상 이유로 선호하는데, 이를 사용하면 고복잡도(높은 엔트로피)의 비밀번호를 쉽게 사용할 수 있고, 모든 자격 증명을 기억할 필요가 없어지기 때문

• 그러나 학술 연구에서는, 사용자가 비밀번호 관리자를 사용하는 주된 이유는 보안이 아니라 편의성이라는 점이 밝혀짐

• 심지어 일부 사용자들은, 민감한 계정의 자격 증명은 비밀번호 관리자에 저장하지 않고, 덜 민감한 계정에만 활용하는 경향을 보임

• 또한 비밀번호 관리자에 접근해야하는 마스터키는 기억해야함

실제로는, 사용자들은 비밀번호 관리자의 보안 기능을 최대한 활용하지 않고,자동 완성용으로 단순하고 약한(low-entropy) 비밀번호만 저장하는 데 그치는 경우가 많음 -> "보안성" 보다 "편의성" 용도로 씀

SSO(Single Sign On)

• 싱글 사인온(SSO)은 연합 로그인(federated login) 기술로, OAuth와 OpenID Connect 같은 접근 위임 프로토콜을 통해, 사용자 인증 책임을 하나의 주요 제공자(예: Google, Apple)에 중앙 집중시키는 방식

• 하지만 SSO의 도입은 다음과 같은 이유들로 인해 제한적이었음

  1. 개인정보 보호에 대한 우려: 사용자 인증 시 빅테크 기업과 데이터가 공유된다는 점에 대한 합리적인 우려
     2. 기술에 대한 신뢰 부족: 근본 기술에 대한 불신으로 인해 도입을 꺼리는 사례들

• 실제로 과거 연구에서는 민감한 계정일수록 SSO를 사용하지 않는 경향이 있다는 점도 확인

• 보안 측면에서도,SSO의 기반 프로토콜 자체에 존재하는 보안 취약점, 서비스 구현 과정에서 발생하는 취약점이 학술 연구에서 많이 보고됨

• 심지어 현실에서는, OAuth 액세스 토큰을 수집하는 허니팟(honeypot) 웹사이트를 운영하는 사이버 범죄 조직들도 발견된 바 있음

• 이러한 개별적인 보안/프라이버시 문제 외에도,SSO 방식은 구조적으로 단일 실패 지점(Single Point of Failure)을 가지기 때문에,공격자에게 매우 매력적인 목표가 되기도 함

• 단일 실패 지점(Single Point of Failure, SPOF): 시스템 구성 요소 중 하나라도 실패하면 전체 시스템이 작동을 멈추게 되는 구조적인 약점

2)Device-Bound Credentials

• 하드웨어 토큰과 스마트폰 내 보안 하드웨어 칩의 보급이 늘어남에 따라, 단 하나의 강력한 하드웨어 기반 요소(사용자의 스마트폰)만으로도 인증이 가능해짐

• 이를 통해 서비스 제공자들은 일상적인 인증 절차에서 비밀번호를 완전히 제거 가능해짐

• 장치 결합 자격 증명은 공개키 암호화 방식을 사용

• 스마트폰의 보안 하드웨어 모듈이 각 웹 계정마다 고유한 키쌍을 생성하고, 개인키(private key)는 하드웨어 모듈에 안전하게 저장하며, 공개키(public key)는 웹 서버에 전달합니다. 웹 서비스에 로그인할 때 사용자는 지문·PIN·패턴 등 평소 사용하는 디바이스 잠금 해제 수단으로만 로컬 디바이스 인증을 거치면 되므로, 이 방식을 흔히 ‘패스워드리스(passwordless)’ 인증이라고 함

• 장치 결합 자격 증명의 주된 이점은 피싱 공격 및 대규모 계정 탈취 위험을 크게 줄인다는 점

• 각 계정마다 고유한 키쌍이 생성되므로, 인증 과정에서 디바이스는 해당 개인키를 사용해 서버가 보낸 챌린지(challenge)에 서명하고, 이를 통해 본인 소유임을 증명함.

• 또한, 인증기는 원래 등록된 웹 서비스에만 반응하도록 설계되어 있어, 악성 사이트의 인증 요청에는 서명하지 않습니다.

• 반면, 단점은 자격 증명의 보안이 곧 디바이스 보안에 달려 있다는 것임.

• 디바이스가 탈취·침해되면 모든 서비스에 대한 접근 권한이 위험해질 수 있음.

• 이를 방지하기 위해 스마트폰 제조사들은 패스키 사용 시마다 생체 인증을 요구하거나, 디바이스 잠금 해제 시도를 일정 횟수 이상 실패하면 잠금 속도를 늦추는 등 다양한 보안 조치를 도입하고 있지만, 구체적인 보호 수준은 플랫폼과 사용자 설정에 따라 달라짐.

• FIDO2 자격 증명이 처음부터 장치 결합 전용으로 설계되었기 때문에, 디바이스 분실 시 복구 방안은 여전히 큰 문제.

• 패스키(passkey)는 여러 디바이스 간 동기화가 가능하지만, 모든 디바이스를 잃어버리면 모든 패스키도 함께 사라짐 -> 이거를 클라우드로 커버침

• 디바이스는 자주 분실·훼손·업그레이드로 교체되며, 여행 중 노트북을 놓고 왔거나 단 한 대의 FIDO 호환 기기만 소지하고 있을 수도 있음.

  이 복구 문제를 해결하기 위한 업계의 합의는 "패스키"

패스키

• Passkeys(패스키): FIDO2 기반의 패스워드리스 인증 방식을
• 사용 편의성을 높이고 패스키 분실 위험을 줄이기 위해, 주요 운영체제 제공업체들은 패스워드리스 자격 증명을 각자의 클라우드 백업 서비스에 자동 동기화하도록 구현
• 클라우드 백업 복구 절차는 Apple과 Google 모두 비슷한데, 먼저 클라우드 서비스(예: Google 계정 또는 iCloud)에 로그인한 뒤, 스마트폰의 잠금 해제 코드를 입력해 자격 증명 백업에 접근
• 이처럼 클라우드 동기화는 사용자가 복구 가능성을 기대하는 데 필수적이지만, 동시에 패스키의 실제 보안 수준을 클라우드 계정(및 백엔드 HSM 보안)에 종속시킴
• 운영체제의 패스키 인증 프로세스 외에도, FIDO2 표준은 사용자가 FIDO2 패스키로 인증을 완료한 이후에 도메인이 추가적인 인증 단계를 구현할 수 있도록 허용 ex> 웹 서비스와 클라이언트는 선택적인 WebAuthn 확장 기능을 사용하여 추가적인 디바이스 바인딩 키(device-bound key)를 인증 과정에 포함시킬 수 있음 -> 이를 통해 웹 서비스는 예를 들어 사용자가 새로운 기기에서 로그인하는지 감지 가능
• 또한 FIDO2는 디바이스 간 인증(cross-device authentication)도 지원함. ex> 패스키를 지원하지 않는 노트북 같은 새로운 기기에서의 인증 시도는 유효한 패스키를 보유한 다른 디바이스로 블루투스를 통해 전달(tunneled)되며, 이때 Client to Authenticator Protocol(CTAP)이 사용

패스키 인증 흐름(Challenge Response with 서명)

1. 등록(Enrollment)

• 디바이스(스마트폰 등)의 SE/TEE에서 웹사이트별 공개·개인키 쌍 생성
• 개인키(패스키)는 디바이스 보안 저장소에만 보관, 공개키는 서버에 전송·등록

2. 로그인 요청 & 챌린지

• 클라이언트가 로그인 시도 → 서버가 논스(nonce) 챌린지를 생성해 전송

3. 사용자 인증 및 서명

• 디바이스 잠금 해제(PIN·생체 등) → 개인키로 챌린지 서명

4. 검증 & 로그인

• 서버가 등록된 공개키로 서명 검증 → 일치하면 로그인 성공

패스키 복구 흐름(E2EE)

1. 새 기기에서 복구 시작

• FIDO2/WebAuthn 지원 기기 준비 → iCloud/Google 계정 로그인(2FA 포함)

2. 클라우드 HSM 언랩(unwrap)

• 클라우드 HSM 안에 저장된 “백업용 대칭키”로 암호화된 개인키 데이터 언랩

3. 재래핑(Re-envelope) & 전송

• HSM이 복호화된 개인키를 선택된 기기의 퍼블릭 래핑 키로 즉시 재암호화(envelope)
• 래핑된 암호문만 TLS 채널로 새 기기 SE/TEE에 전달
• 퍼블릭 래핑키(HSM <-> 디바이스 TEE)간 E2EE 통신에 사용됨

4. 디바이스 언랩 & 저장

• 새 기기는 TEE/SE에 있는 프라이빗 래핑 키로만 암호문을 풀어 개인키를 안전 보관

5. 복구 완료

• 복원된 개인키로 웹사이트에 인증 시도 → 정상 작동 확인

패스키(passkey) 채택을 방해하는 잔존 문제

1. 자격 증명 공유(Credential Sharing)

   자격 증명 공유가 가장 빈번하게 발생하는 직장 환경에서는, 원격 근무의 확산으로 인해 사용자가 물리적으로 가까이 있지 않은 경우가 많아, 패스워드처럼 간단하게 문자나 메신저로 공유할 수 있는 방식이 여전히 유리하게 느껴짐

2. 자격 증명 철회(Credential Revocation)

   FIDO2 표준은 자격 증명의 전역 철회(global revocation) 문제를 적절히 다루지 못하고 있음 현재 표준은 웹 서비스가 사용자에게 특정 인증기의 공개키를 서버에서 제거하는 방식으로 접근 권한을 철회하는 기능을 제공하도록 요구하고 있지만, 이는 사용자가 각 웹사이트마다 개별적으로 수행해야 하는 불편함이 있음

3. 자격 증명 접근성(Credential Availability)

   패스키(passkey)는 보통 기기의 보안 저장소(secure element)에 저장되고, 기기 자체를 통해 인증하기에 그 기기를 가진 사람은 인증된 사용자처럼 행동할 수 있음 예를 들어 친구한테 사진 보여주려고 핸드폰을 넘겼는데, 그 친구가 다른 앱으로 들어가서 내 계정이나 메일을 본다거나, 로그인 상태인 웹사이트를 들어가서 뭘 본다거나 하는 일이 생길 수 있음

3) Social Authentication (사회적 인증)

• 사회적 인증 및 복구(social authentication and recovery)는 계정 소유자가 하나 이상의 복구 연락처(또는 ‘신뢰인(trustee)’)를 지정하여, 이들이 계정 접근 권한을 회복하는 데 도움을 주는 방식
• 이 방식은 모든 기기와 비밀번호를 분실하거나 기억하지 못하는 등의 현실적인 재난 상황을 확실하게 처리할 수 있는 유일한 복구 시나리오
• 이 개념은 2006년 RSA의 Brainard 등[53]이 처음 제안했으며, 현실의 신뢰 관계를 활용해 다른 사람이 사용자를 대신해 신원을 보증(vouch)하는 방식
• 당시 Brainard 등은 기업의 비밀번호 재설정 인력에 드는 재정적 비용을 줄이는 방법으로 이 개념을 제시했지만, 오늘날에는 수동 복구 과정에서 사용자의 신원을 확인하는 것이 어렵고, 또한 종단 간 암호화(E2EE) 서비스처럼 서비스 제공자가 사용자를 재인증할 수 없는 경우도 있기 때문에, 사회적 복구는 매우 중요한 대안으로 부각

단일복구연락처(Single Recovery Contact)

• 가장 단순한 형태의 사회적 복구 방식은 하나의 복구 연락처(보통은 가까운 지인)를 지정하는 것
• 예를 들어, Apple이 2022년에 도입한 iCloud 백업 복구 시스템은 이 아이디어를 반영
• Apple의 복구 방식에서는 복구 연락처가 되는 다른 iCloud 사용자가 짧은 코드를 생성해 원래 사용자(Alice)에게 전송함으로써 계정 복구를 가능하게 함

처음생각

1. 리스트를 n개 만들고 거기다가 append 하자
2. 문제 발생 파이썬의 리스트는 스택의 성질을 갖는다. 따라서 n=4의 경우 [1], [2, 9], [3, 8], [4, 5, 6, 7]까지(한바퀴)는 잘 채워지지만 그 다음에 [1], [2, 9], [3, 8, 10], [4, 5, 6, 7] 이렇게 채워지게 됨 -> 순서가 안맞는다.

두번째 든 생각

1. 0으로 위치가 정해진 배열을 선언하자. (n+1) * (n+1)
2. dx, dy로 탐색하자. state=0 : 밑으로 내려가는거 state=1 : 오른쪽으로 가는거 state=2 : 위로 가는거

def solution(n):
    answer = []
    candidates=[[0]*(n+1) for _ in range(n+1)]
    state=0
    dx=[1, 0, -1]
    dy=[0, 1, 0]
    x, y = 1, 1;
    data=1
    start_index=1
    for i in range(n, 0, -1):
        if state==0:
            for j in range(i):
                candidates[x][y]=data
                x += dx[state]
                y += dy[state]
                data+=1
            x-=dx[state]
            data-=1
            state=1

        elif state==1:
            candidates[x][y]=data
            for j in range(i):
                x += dx[state]
                y += dy[state]
                data+=1
                candidates[x][y]=data
            state=2

        else:
            for j in range(i):
                x += dx[state]
                y += dy[state]
                data+=1
                candidates[x][y] = data
            start_index+=1
            x+=1
            y=start_index
            state=0
            data+=1
    for cs in candidates:
        for c in cs:
            if c!=0:
                answer.append(c)

통과했지만 너무 더러움

개수만큼 만든 풀이

def solution(n):
    # 각 행의 길이가 1, 2, …, n 인 삼각형 리스트 생성
    triangle = [[0] * (i + 1) for i in range(n)]
    num = 1
    x, y = -1, 0  # 첫 이동 전에 위치 지정
    # 한 사이클마다 아래, 오른쪽, 좌상 이동을 하며 채워나감
    for i in range(n, 0, -3):
        # 1) 아래로 i칸 이동
        for _ in range(i):
            x += 1
            triangle[x][y] = num
            num += 1

        # 2) 오른쪽으로 (i - 1)칸 이동
        for _ in range(i - 1):
            y += 1
            triangle[x][y] = num
            num += 1

        # 3) 좌상(대각선 위)으로 (i - 2)칸 이동
        for _ in range(i - 2):
            x -= 1
            y -= 1
            triangle[x][y] = num
            num += 1

    # 삼각형 리스트를 1차원 리스트로 평탄화하여 반환
    return [value for row in triangle for value in row]

알고보면 쉽다...

• 한 사이클에 3변을 만들어버린다.
• 개수만큼 만들어도 마지막 변 만들때 x-=1, y-=1해버리면 규칙에 맞음
• 시작을 -1로 해도 됨...

1) 매핑

1. 문자열 길이 똑같은거
2. 불량이 * 거나 같으면

-> 불량사용자에 매핑됨

2) 조합

매핑될 수 있는 모든 경우의 수를 구하라

처음생각했던 방식

• 딕셔너리 만들어서 조합 수학으로 계산하려고 함

• 키가 중복되는 이슈 -> banned_id는 중복가능
• 숫자만으로는 계산식 만들기 어려움

새로운방식

1) n=1~8 -> 엄청난힌트

-> 순열(permutations) -> 모든 순열 만들어서 검사

2) 검사식

def check(user, banned):
    index=0
    flag=1
    if len(user)!=len(banned):
        flag=0
    else:
        while index < len(banned):
            if user[index]!=banned[index] and banned[index]!="*":
                flag=0
                break
            index+=1

    if flag==0:
        return False
    else:
        return True

index 증가시키면서 *도 아니고 같지 않으면 break 시킴

3) 중복처리

예를 들어 위의 경우 permutations 함수를 돌렸을때 (frodo, crodo, abc123, frodoc) 순열도 나올 수 있고 (frodo, crodo, frodoc, abc123) 순열도 나올 수 있다. 또한 이 2개 모두 검사식을 통과해서 둘다 count될 수 있음. 그러나 banned_id에 매핑되는 모든 조합을 계산하는 거라 이거는 중복임.

def solution(user_id, banned_id):
    answer = 1
    ps = list(permutations(user_id, len(banned_id)))
    value=[]
    for p in ps:
        temp=0
        i=0
        while i < len(banned_id):
            if check(p[i], banned_id[i]):
                temp+=1
            i+=1
        if temp==len(banned_id) and set(p) not in value:
            value.append(set(p))
    return len(value)

이때 순열의 중복이 있는지 검산할때는 set()으로 만들어서 중복을 검산한다.

• 즉 여러 가지로 분열된 순열을 하나의 공통된 값으로 모은다. (frodo, fradi, crodo, abc123) (fradi, frodo, crodo, abc123) 모두 (frodo, fradi, crodo, abc123)으로 고정됨

부모: 추천인 부모에게 10% 상납, 90%는 내가 가짐

• 특수조건

1. 10% 계산시 원단위에서 절삭(버림)
2. 10% 계산한 금액이 1원미만인 경우에는 상납안하고 걍 내가 다 가짐

밑에서 부터 위까지 탐색하면서 업데이트 -> DFS 생각하고 문제 시작 DFS는 자료구조를 잘 만드는게 중요 90%는 곱하는게 아니라 전체크기에서 10%를 절삭시킨값(정수)을 빼는 것임

자료구조

• seller와 amount가 짝궁 ex> young이 12*100 = 1200 판매힘 올림

• enroll과 referral이 짝궁 ex> john과 mary 부모는 루트("-"), edward의 부모는 mary
• result는? enroll과 짝궁

풀이

1) 탐색하기 위한 해시 생성

for i in range(0, len(enroll)):
        key_matching[enroll[i]]=i

이름을 키로하고 인덱스를 값으로 해서, 이름을 가지고 인덱스를 찾도록 enroll과 result는 짝궁임 근데 둘다 기준을 인덱스값으로 하니깐...

• enroll[0] -> john
• result[0] -> john의 돈

2) Seller 하나씩 for문 돌려서 업데이트 시작

result=[0]*(len(enroll))    
    for i in range(0, len(seller)):
        now_amount = amount[i]*100
        result = dfs(key_matching, enroll, referral, seller[i], now_amount, result)

3) DFS

def dfs(key_matching, enroll, referral, name, now_amount, result):
    index = key_matching[name]
    if int(now_amount*0.1)<1:
        result[index]+=int(now_amount)
        return result
    else:
        result[index]+=int(now_amount)-int(now_amount*0.1)

    if referral[index]=="-":
        return result
    else:
        return dfs(key_matching, enroll, referral, referral[index], int(now_amount*0.1), result)

1. 이름으로 index를 뽑는다.
2. 만약 현재가격의 10%가 1보다 작으면, 그냥 그대로(100%) 더해줌
3. 아니면 90%를 더해줌
4. 만약 부모가 루트("-")면 dfs 종료(return)
5. 일반적 부모면 바로 여전히 dfs 탐색 가. 이제 name에 부모의 name 들어감

    -> referral[index]

   나. 현재 가격도 10%곱한값이 인자로 들어감

• 요약

1. 사람의 수 N과 파티의 수 M이 주어짐
2. 진실을 아는 사람의 수와 번호가 주어짐
3. M개의 줄에 각 파티마다 오는 사람의 수와 번호가 주어짐

풀이

1. 유니온 파인드 생각

• 뒤에 입력되어도 진실을 안다는게 전파 되어야함

• = 같은 그룹으로 만든다 = 순서보다 같은 그룹에 속하는지...

2. Parent 리스트 생성 + 초기전파

 known_num, known_p = known_p[0], known_p[1:]
    for p in known_p:
        parent[p] = known_p[0]

입력받은 값 중에 제일 작은값으로 초기전파 시킴

3. 파티 입력 받을 때마다 Union(전파)

parties=[]
    for i in range(m):
        party = list(map(int, input().split()))
        party_num, party = party[0], party[1:]
        for i in range(party_num-1):
            union(party[i], party[i+1])
        parties.append(party)

예를 들어 4 1 2 5 6 입력했다면 union(4, 1) union(1, 2) union(2, 5) union(5, 6) 이렇게 한다.

4. 이제 union시킨 parent를 가지고 허풍 떨지 말지 결정

1) 최적화 전

answer=0
    for p in parties:
        count=0
        for person in p:
            if find(person)==find(known_p[0]):
                break
            else:
                count+=1
        if count==len(p):         
            answer+=1
    print(answer)      

• 양쪽에 find를 씌우는 이유는 나중에 union 할때 초기값보다 더 작은 집합과 union 되면 그 값이 되기 때문.. 따라서 find 씌워주어야 한다. 예를 들어 초기값이 3인덱스의 3하나인데 나중에 3과 2가 union이 될 수 있기 떄문임

• 결국 부모를 찾아나간다.

• 마지막 확인때 find는 거의 국룰...

2) 최적화 후

answer=0
    for p in parties:
        if find(p[0])==find(known_p[0]):
            continue    
        answer+=1
    print(answer) 

사실 생각해보면 이미 같은 집합끼리는 union 시켰기 때문에 첫번째 값만 확인하면 됨

이론적 설명

• 유니온: 특정 2개의 노드를 연결해 1개의 집합으로 묶는 것

• 파인드: 두 노드가 같은 집합인지를 확인

코드적 설명

• 유니온: 각 노드가 속한 집합을 1개로 합침

• 파인드: 해당 집합을 대표 노드를 반환

구현방법

1) 1차원 리스트로 각 노드를 표현(연결X인 상태)

연결이 안되어 있는 상태이기에 각 노드는 그룹을 형성하지 않음 -> 자기자신이 대표 노드임

2) find 후, union수행

1. 합치려는 노드들을 find로 대표 노드 찾는다.

-> find(1)=1, find(4)=4 -> find 수행시 재귀를 통해 최상단의 부모를 찾는다.(대표값과 노드가 같을 때까지)

• find는 경로 압축의 효과가 있다.(한번만 이동하면 바로 대표값을 찾음)
  

2. 찾은 대표노드 중 작은값으로 union한다.

-> 1로 union을 진행한다.

1) DFS와 그래프로 생각

결국 n-1개의 간선을 줬다는거랑 똑같음.... 따라서 그래프의 개념으로 생각해 볼 수 있다. 또한 그렇다는 것은 a -> b -> c 이렇게 탐색해 나갈 수 있다는 것이고 이는 DFS를 이용하여 계속해서 비율을 구해나가면 된다.

• Q: 그런데 정수로 안나누어 떨어질 수도 있지 않나? A: 그렇기 때문에 처음 탐색하는 노드를 모든 비율의 최소공배수로 둔다. 이러면 어떤 비율이든 나누어 떨어질 수 있다. ex> p,q의 비율 값들이 1,3,7,5로 주어진다면 105가 초기 시작 노드값이 된다.

n = int(input())
graph=[[] for _ in range(n)]
new_graph = [0] * (n)
visited = [False]*(n)
update = 1
for i in range(n-1):
    a, b, p, q = map(int, input().split())
    graph[a].append((b, p, q))
    graph[b].append((a, q, p))
    update *= (p*q) // gcd(p,q)

또한 그래프 자료형은 투플 자료형으로 (다음노드인덱스, p, q) 로 만든다. 만약 방향이 반대라면 (다음노드인덱스, q, p)로 만든다. -> 그래프는 양방향이기 때문

def dfs(node):
    for i in graph[node]:
        if visited[i[0]]==False:
            new_graph[i[0]] = new_graph[node] * i[2] // i[1]
            visited[i[0]]=True
            dfs(i[0])
    return

2) 새로운 비율들의 최대공약수로 나누어 줌

new_graph[0] = update
visited[0]=True
dfs(0)
mgcd = new_graph[0]
for i in range(1, n):
    mgcd = gcd(new_graph[i], mgcd)

for i in range(0, len(new_graph)):
    new_graph[i] = int(new_graph[i] // mgcd)
print(*new_graph)

이제 만들어진 new_graph라는 비율에 각각의 값을 최대공약수로 나누어 주어 이 비율을 만족하는 최소량을 구한다.

3) 애먹었던점

부동소수점 이슈..... 만일 확실히 정수로 나누어떨어지는 값이라는 것을 알고있다면 그냥 안전하게 "//" 사용하자!

처음 생각했던 프로세스

1. 범위 소수 -> 에라토스테네스의 체 이용해서 소수만 추리기
2. 체에서 소수인거 골라서 제곱시켜서 체크표시해서 count

문제발생

메모리 초과문제 발생

total=[]
for i in range(2, b+1):
    if field[i]==True:
        n=2
        value=0
        while value<=b:
            value = i**n
            if value not in total and value<=b:
                n+=1
                total.append(value)
            else:
                break
print(len(total))

1. 중복이 일어날것이라 생각해고 total 배열을 만들었음(X)

-> 중복이 일어나지 않음(몇개 예시로 써보면 감옴...) 2. 따라서 그냥 count만 하면됨

해결

count=0
for i in range(2, b+1):
    if field[i]==True:
        value= i*i
        while value<=b:
            if value >= a:
                count+=1
            value *=i

추가로 고민해본것

파이썬은 int형의 오버플로우가 나지 않는다.. 그러나 다른 언어는 내가 자료형을 직접 정해서 선언해야함 이때 N제곱한 것이 int의 범위를 초과한다면...? 오버플로우가 날것이다 아마도... 어떻게 해결해야 할까?

total=0
for i in range(2, len(field)):
    if field[i]==True:
        temp = i
        while i<= b/temp:
            if i >= a/temp:
                total+=1
            temp = temp*i

• 해결방안

  범위의 양쪽을 나눠준다.... ex> a<x<b에서 x의 2의 범위를 원하면 a와 b에 x를 나누어 주어서 이 범위에 맞는지 확인하는 것... x의 3의 범위는 a/x < x< b/x에서 또다시 a/x/x < x < b/x/x가 만족하는지 확인하고 이런식...

자신보다 작은 2개의 자연수를 곱해 만들 수 없는 1보다 큰 자연수 = 1과 자기 자신 외에 약수가 존재하지 않는 수

1. 소수 검사 방법

1) 딱 하나를 검사할 때

import math

def is_Prime(n):
    for i in range(2, int(math.sqrt(n))+1):
        if n%i==0:
            return False
    return True

Q: 왜 범위에 루트를 씌웠는가? A: 우리는 약수가 있는지 없는지를 판단하는게 메인이다. 그리고 약수라는 것은 쌍으로 존재하는데 그 쌍의 반만 검사해도 충분하기 때문이다.

2) 소수의 집합을 구할때 (에라토스테네스의 체)

1) 구하고자 하는 소수의 범위만큼 1차원 리스트를 생성 2) 2부터 시작하여 자신을 제외한 배수들을 지워나간다

핵심은 이미 지운거의 배수들은 지우지 않고 continue 한다는 것!! 이것을 통해 시간 복잡도를 O(N^2)에서 O(Nlog(logN))까지 줄일 수 있음

import math
n = int(input())
num = [True]*(n+1)
num[0] = False
num[1]= = False

for i in range(2, int(math.sqrt(n))+1):
    if num[i] == False:
        continue
    for j in range(i*2, n+1, i):
        num[j] = False

해당 코드는 num의 인덱스가 소수가 되고, 값은 True:소수/False:소수X가 됨. 계속 배수들을 지워서 소수가 아닌것들을 쳐내어 유용하게 쓸 수 있는 자료형(에라토스테네스의 체)를 만든다.

2. 소수 응용 문제(제곱수)

1) 각 소수당 제곱수 검사시 중복발생 X

소수의 제곱을 검사할 때 서로 겹치는 것은 없다. 검사1: 2, 4, 8, 16, 32 ... 검사2: 3, 9, 27

2) 제곱수의 key = a< x< b에서 a,b를 줄이는 것

제곱수 연산을 해나가게 되면 값이 너무 커진다. 오버플로우 가능성도 존재... 양변을 줄여나가는 것이 key가 됨... a/x < x < b/x 만족? a/x/x < x < b/x/x 만족? ...

정수론

1. 오일러 피(서로소 개수)

오일러 피 함수 P[N]의 정의는 1부터 N까지 범위에서 N과 서로소인 자연수의 개수를 뜻한다. -> "N과의 최대공약수가 1뿐임"

# GCD(n,k) = 1
import math
import sys
input = sys.stdin.readline

n = int(input())
result=n

for i in range(2, int(math.sqrt(n)+1)):
    if n %i==0:
        result -= result/i
        while n%i==0:
            n/=i
if n > 1:
    result = result - (result/n)
print(int(result))

1. i로 나누어서 이 값을 빼준다.

-> 공통된 약수의 개수를 줄인다. 2. N을 i와 공통된 약수가 없개 충분히 줄여준다.(while n%i==0) -> N이 줄어들어서 for문 조건에서 가변적임 3. for문 종료시 N이 1보다 크다면 마지막 소인수가 남았다는 뜻 한번더 연산해준다

2. 유클리드 호제법(최대공약수, 최소공배수 간단하게 풀 수 있음)

두 수의 최대 공약수를 구하는 알고리즘 소인수 분해 보다 더 간단함

• 주요 Point는 mod 연산을 이용한다는 것....

def gcd(a, b):
    if b==0:
        return a
    else:
        return gcd(b, a%b)

• a랑 b의 순서는 상관없음 why? 3 % 4해도 다시 재귀로 들어갈때 (4 % 3)으로 알아서 바뀜

• 그렇다면 최소공배수는 어떻게? 두수의 곱을 최대공약수로 나누어 주면 됨 따라서 유클리드 호제법으로 최소공배수까지 쉽게 구할 수 있음

3. 확장 유클리드 호제법

유클리드 호제법 -> 두 수의 최대공약수 확장 유클리드 호제법 -> 방정식의 해 구하기

ax + by = c(a, b, c, x, y는 정수)

• 위 방정식은 c % gcd(a,b) = 0인 경우에만 정수해를 가짐 = c가 a와 b의 최대공약수의 배수인 경우에만 정수해를 가짐

ex> 5x+9y=2를 만족하는 x와 y 구하기

• 먼저 확인해야할것 = 2가 gcd(5,9)의 배수인지

• 배수가 맞다! 따라서 5x + 9y = 최대공약수 를 가지고 확장 유클리드 진행 가능

• 여기서는 최대공약수가 1이다.

최종 답은 X=2, Y=-1 이것을 식(5x+9y=1)에 대입해보자! 맞아 떨어진다. 이제 이 최대공약수의 배수인 2에 맞아 떨어져야 하므로 답에 2씩 곱한다 따라서 정답은 X=4, Y=-2이다.

처음 생각한 전략

1) 소수판별 데이터 만들기: 에라토스테네스의 체 100만개 만들기 2) 팰린드롬 판별: 소수조건 만족하는거는 list로 변경해서 reverse()시켜서 비교

# 소수&팰린드롬
import math
import sys
input = sys.stdin.readline
def check(data):
    v1 = list(str(data))
    v2 = v1.copy()
    v2.reverse()
    if v1==v2:
        return True
    else:
        return False
m = 1000001
n = int(input())
prime=[True]*(m)
prime[0]=False
prime[1]=False
for i in range(2, int(math.sqrt(m))+1):
    if prime[i]==False:
        continue
    for j in range(2*i, m, i):
        prime[j] = False

for i in range(n, m):
    if prime[i]==True:
        if check(i):
            print(i)
            break

But 문제 발생 Where?

어떤 수 N(1<=N<=1,000,000)이라 백만이 N이 되면 백만이 넘어가는 소수값이 팰린드롬이 되어야 하는데 검사를 백만까지만 해서 아무것도 출력이 안됨

해결방법

자료형을 200만까지 늘렸다.

m = 2000000

최적화(투 포인터 활용)

reverse()시켜서 비교하면 O(n) + O(n) 즉 O(n)만큼으 시간복잡도가 걸린다. 그러나 투포인터를 활용하면,

1) 공간복잡도 절약: 새로운 reverse 자료형 안만들어도됨 2) 시간복잡도 절약: 반만 비교하면됨(n/2) + 밖에서부터 안쪽으로 비교하다가 한번이라도 아니면 중간에 멈춤 O(n)이어도 이정도까지 절약 가능...

# 소수&팰린드롬
import math
import sys
input = sys.stdin.readline
def check(data):
    v1 = list(str(data))
    answer = True
    start_point=0
    end_point = len(v1)-1
    while start_point<end_point:
        if v1[start_point] != v1[end_point]:
            answer = False
            break
        start_point+=1
        end_point-=1

    return answer
m = 2000000
n = int(input())
prime=[True]*(m)
prime[0]=False
prime[1]=False
for i in range(2, int(math.sqrt(m))+1):
    if prime[i]==False:
        continue
    for j in range(2*i, m, i):
        prime[j] = False

for i in range(n, m):
    if prime[i]==True:
        if check(i):
            print(i)
            break

1. Logical Block

• 디스크를 논리적으로 바라보는 단위이다.

• Logical Block은 디스크의 외부 컴퓨터 호스트가 디스크에 접근할 때 사용되는 단위로, 마치 1차원 배열처럼 구성되어 있다.
• 디스크는 논리적 블록 단위로 접근되며, 컴퓨터는 "몇 번째 블록을 읽어라"라는 식으로 디스크와 상호작용한다.

2. Sector

• 디스크를 물리적으로 관리하는 최소 단위이다.

• Sector는 Logical Block이 실제로 저장되는 물리적 공간에 해당한다.
• 디스크의 Sector는 일련의 동심 원으로 구성된 트랙(Track) 위에 배치되며, 각 트랙은 실린더(Cylinder)로 구성됩니다.
• Sector 0은 최외곽 실린더의 첫 트랙에 있는 첫 번째 섹터를 의미합니다.

Disk Management

1. Physical Formatting(Low-level formatting)

• Physical Formatting은 디스크를 처음 만들 때 수행하는 과정으로, 디스크를 섹터 단위로 나누는 작업이다.

• 이 과정은 공장에서 수행되며, 디스크가 물리적 섹터로 분할되어 디스크 컨트롤러가 읽고 쓸 수 있도록 준비된다.
• 각 섹터에는 논리적 블록 외에도 헤더(header)와 트레일러(trailer) 같은 부가 정보가 저장된다.

• 헤더와 트레일러는 섹터 번호, 오류 검출 및 수정 코드(ECC) 등 디스크 컨트롤러가 직접 접근하고 운영하는 정보가 포함된다.

2. Partitioning

• Partitioning은 Physical Formatting 이후에 수행되는 단계로, 섹터 영역들을 묶어서 하나의 독립적인 디스크로 만들어주는 작업이다.

• 이를 통해 Logical Disk가 생성되며, 예를 들어 하나의 HDD를 C 드라이브와 D 드라이브로 나눌 수 있다.
• 운영 체제는 이러한 논리적 디스크에 접근하여 독립적인 디스크로 간주하고 사용한다.
• 각 파티션은 파일 시스템용으로도 사용될 수 있고, 스왑 영역(Swap Area) 용도로도 사용할 수 있다.

3. Logical Formatting

• Logical Formatting은 파티션에 파일 시스템을 설치하는 과정이다.

• 예를 들어, FAT, NTFS, ext4와 같은 파일 시스템을 파티션에 설치한다.

• 이를 통해 데이터가 저장될 수 있도록 파일 시스템의 구조가 만들어지고, 파일 및 디렉터리의 관리가 가능하다.

4. Booting

Booting은 디스크에 설치된 운영 체제가 메모리에 올라와 실행되는 과정이다.

• 부팅 과정은 다음과 같은 단계로 구성된다: 1) ROM에 저장된 "small boot strap loader"가 실행된다. ROM: 비휘발성 메모리로, 컴퓨터가 켜질 때 가장 먼저 실행되는 프로그램이다. 2) 부트스트랩 로더는 HDD의 0번 섹터(부트 블록)를 메모리에 올리고 실행한다.

• 부트 블록은 디스크의 첫 번째 섹터로, 운영 체제를 부팅하기 위한 초기 코드를 포함하고 있다. 3) 부트 블록의 코드가 실행되면, 운영 체제 커널의 위치를 찾고, 해당 커널을 메모리에 로드하여 실행한다. 4) 커널이 메모리에 로드되면, 운영 체제가 초기화되고 시스템이 완전히 부팅된다.

디스크 스케줄링

Access time의 구성

1) Seek time

디스크 헤드가 1) 해당 실린더로 움직이는데 걸리는 시간 + 2) 해당트랙까지 움직이는데 걸리는 시간

• 트랙: 통조림 파인애플
• 실린더: 통조림 파인애플 쌓인거

2) Rotational latency

원판이 회전해서 섹터 위치가 디스크 헤드한테 가는데 걸리는 시간

3) Transfer time

굉장히 적은 시간이다. 실제로 헤드가 데이터를 읽고 쓰고 하는 시간이다. (실제 데이터의 전송시간)

Disk bandwidth(디스크 성능)

단위 시간당 디스크로 전송된 바이트의 수 가능한 seek time을 줄이는게 좋다.

Disk scheduling

seek time을 최소화 하는것이 목표이다. 즉 Disk bandwidth를 높여보자!

Disk Scheduling Algorithm

1) FCFS(First Come First Service)

2) SSTF(Shortest Seek Time First)

현재 헤드위치에서 제일 가까운 요청을 먼저 처리한다.

Starvation 문제: 큐에 멀리 있는 애들 차례 오려고 했는데 가까운 애들이 또 왕창 들어오면 헤드가 멀리 있는 애는 처리하지 않는다.

3) SCAN(엘리베이터 알고리즘)

53 -> 37 -> 14 -> 0 -> 65 -> 67 -> 98 -> 122 -> 124 -> 183

• 디스크 헤드는 항상 가장 안쪽위치에서 바깥쪾 위치로 이동하면서 가는 길목에 요청이 들어와 있으면 처리하고 지나간다.

• 제일 바깥쪽까지 나가고 방향 바꾸어서 다시 가장 바깥쪽에서 안쪽으로 들어오면서 가는 길목에 요청이 있으면 처리하고 지나간다.(반복)

• starvation문제가 발생하지 않고 디스크의 총 이동거리도 낮다.

그러나 실린더의 위치에 따라 대기 시간이 다르다는 문제점이 있다.

1) 가운데 부분은 기다리는 시간의 예상 기대치가 짧다. 2) 가장자리 지역은 기다리는 시간의 예상 기대치가 길다.

4) C-SCAN(단 방향)

53 -> 65 -> 67 -> 98 -> 122 -> 124 -> 183 -> 199 -> 0 -> 14 -> 37

디스크 헤드가 가장 안쪽에서 바깥쪽 위치로 이동하면서 요청을 처리한다. 그러나 가장 바깥쪽에서 안쪽으로 이동할때는 큐에 들어온 요청을 처리하지 않고 헤드가 이동만 한다. -> 이동거리는 좀 늘어나지만, SCAN보다 균일한 대기시간을 제공한다.

5) Other

가. N-SCAN

디스크 헤드가 이동하면서 현재 출발하면서 이미 큐에 들어와 있는거는 이번에 지나가면서 처리하고, 지나가는 도중에 들어오는 것들은 다음번에 처리한다.

나. Look(SCAN + a) and C-Look(C-SCAN + a)

디스크헤드가 안쪽에서 바깥쪽으로 이동하다가 그 방향에 더이상의 요청이 없으면 거기서 바로 방향을 바꾼다.

디스크 스케줄링 알고리즘의 결정

현대 디스크 시스템에서는 SCAN기반 알고리즘을 많이 쓴다.

• File을 할당하는 방법도 디스크 스케줄링에 영향을 준다.

• ex> 연속할당하면 연속된 실린더 위치에 있어서 더 이동거리 줄일 수 있다.

디스크 스케줄링 알고리즘은 OS 커널의 내부모듈과는 별도로 만들어서 필요할때 다른 알고리즘으로 교체에서 쓸 수 있게 하는 것이 바람직하다.(파일 할당에 따라 달라지기 때문이다.)

Swap-Space Management

디스크를 사용하는 2가지 이유(보조기억장치)

1) 메모리의 휘발성: 파일 시스템은 비휘발성 사용해야함 2) 프로그램을 실행하기 위한 메모리 공간의 부족: Swap Space

Swap Space

물리적인 Disk를 파티셔닝 해서 논리적 Disk를 만들 수 있다.(OS는 이를 서로 다르게 구분함)

• 공간 효율성보다 속도 효율성을 우선시한다. 그 이유는 프로세스가 끝나면 Swap Area의 내용은 어차피 다 사라져버린다.
• Seek time을 줄이기 위해 단위가 매우크다(킬로바이트)

RAID(Redundant Array of Indepenent Disks)

여러개의 디스크를 묶어서 사용한다.(중복저장, 분산저장)

RAID의 사용목적

1) 디스크 처리속도 향상

여러 디스크에 데이터가 중복저장되어 있으면 호스트 컴퓨터에서 데이터를 읽어오라고 디스크에 요청시, 여러 군대에서 동시에 조금씩 조금씩 읽어올 수가 있다(병렬적으로 읽어옴) 이러면 서로 협력하기 때문에 더 빠르다.

2) 신뢰성 향상

중복 저장하면 디스크 하나가 failure발생하더라도 멀쩡한 디스크에서 데이터를 읽어올 수 있기 때문에 신뢰성을 높일 수 있다.(Mirroring, Shadowing)

Parity

단순한 중복 저장이 아니라 일부 디스크에 parity를 저장하여 공간의 효율성을 높일 수 있다.

• Parity를 통해 중복저장의 정도를 낮게 할 수 있다. 즉 오류가 생겼는지를 알아내고 복구할 수 있을 정도의 중복저장만 아주 간략하게 한다.

P = C1 ⊕ C2 ⊕ C3 이 상황에서 C2가 소실되면 C2 = p ⊕ C1 ⊕ C3 로 다시 복구할 수 있다.

1. File

일반적으로 비휘발성의 보조기억장치에 저장(HDD) OS는 다양한 저장장치를 file이라는 동일한 논리적 단위로 볼 수 있게 해줌

• 연산: create, read, write, reposition(iseek), delete, open, close

2. File attribute(파일의 메타데이터)

파일 자체의 내용이 아니라 파일을 관리하기 위한 각종 정보들 ex> 파일 이름, 유형, 저장된 위치, 파일 사이즈, 접근권한(읽기/쓰기/실행), 시간(생성/변경/사용) 소유자 등

3. File System

1) OS에서 파일을 관리하는 부분 2) 파일 및 파일의 메타데이터, 디렉터리 정보등을 관리 3) 파일의 저장방법 결정 4) 파일 보호 등

Directory and Logical Disk

1. 디렉토리

파일의 메타데이터 중 일부를 보관하고 있는 특별한 파일 연산 -> search for a file, traverse the file system

2. 파티션(=Logical Disk)

OS가 보는 디스크 = 논리적 디스크(파티션) -> 물리적 디스크를 파티션으로 구성한 뒤 각각의 파티션에 file system을 깔거나 Swapping 등 다른 용도로 사용할 수 있다.

Open()

Open()시 파일의 메타데이터가 메모리로 올라온다.

Open("/a/b/c")를 하면

1) 시스템콜(I/O가 일어난다. 2) CPU 제어권이 OS로 넘어가고 사용자 메모리 영역에서 커널 메모리 영역으로 넘어간다. 3) OS는 이미 root의 메타데이터를 알고있다. 4) root의 content에서 a의 메타데이터를 찾아내고 이를 메모리에 올린다. 5) a의 메타데이터를 기반으로 a의 content를 찾고 b의 메타데이터를 찾는다. 6) b의 메타데이터를 기반으로 b의 content를 찾는다.

File Protection

각 파일에 대해 누구에게 어떤 유형의 접근 (read/write/execution)을 허락할 것인가?

접근제어방법

1) Access Control Matrix

• ACL: 파일별로 누구에게 어떤 접근 권한이 있는지

• Capability: 사용자별로 자신이 접근권한을 가진 파일 및 해당권한 표시 그러나 sparse matrix의 문제점을 가진다.

2) Grouping(지금 쓰는 방식)

rwx | r-- | r-- 전체 user를 owner, group, public 3개의 그룹으로 구분

3) Password

파일마다 password를 두는 방법 (디렉터리 파일에 두는 방법도 가능) 모든 접근권한마다 다른 password를 두면 관리와 암기에 대한 문제가 존재한다.

File System의 Mounting

Q: 만약 다른 파티션에 설치되어 있는 파일 시스템 접근시 어떻게? A: 마운팅한다.

Access Methods

1) 순차접근

카세트 테이프에 다시 듣고 싶은 부분이 있으면 되감아야한다. (A -> B -> C)

2) 직접접근

LP 레코드판과 같이 접근 (특정위치에 바로 접근이 가능하다) (A -> C)

파일을 디스크에 할당하는 방법

디스크에 파일 저장시 동일 크기의 섹터(블록) 단위로 저장한다.

1) 연속할당(Contiguous Allocation) 2) 연결할당(Linked Allocation) 3) 인덱스를 이용한 할당(Indexed Allocation)

1. 연속할당

1) 장점

가. 빠른 I/O이다. 한번의 seek로 많이 얻어온다. 나. 직접접근이 가능하다.

2) 단점

가. 외부조각 문제 발생(비어있어도 못들어간다) 나. 파일의 크기가 바뀌면(커지면) 제약이 있다. ex> 3block -> 5block 되면 뒤에거를 침해하게 된다. 다. 만약 미리 hole을 만들어서 할당자리 만들어 놓으면 내부조각문제가 발생한다. (할당해 놓았는데 아무도 안쓰는...)

2. 연결할당

연속적이 아니라 빈위치면 아무곳이나 들어간다.

1) 장점

외부조각이 발생하지 않는다.

2) 단점

가. 직접접근이 아니라 순차접근이다. 따라서 앞부분 다 탐색해야한다(카세트) 나. Reliability 문제가 있다. 중간에 하나 bad sector 되면 포인터가 유실된다. 다음 위치는 모조리 접근이 불가능 하다. 다. 한 섹터의 들어갈 내용이 포인터 저장(4 byte) 때문에 두 섹터에 저장된다.(공간효율성이 좋지 않다)

** FAT(File Allocation Table)를 통해 포인터를 별도위 위치에 보관하여 Reliability와 공간효율성 문제를 하결할 수 있다. **

3. 인덱스를 이용한 할당

1) 장점

가. 외부조각 발생X 나. 직접 접근 가능하다.

2) 단점

가. 너무 작은 파일이어도 블록이 2개 필요하다.(인덱스 블록, 실제데이터 저장 블록): 공간낭비 나. 너무 큰 파일은 하나의 block으로 인덱스를 저장하기에 부족하다. -> 해결방안

1) linked scheme: 인덱스 블록에 실제 파일의 위치를 적다가 결국 이 파일의 크기를 커버못하면 마지막에 또 다른 인덱스 블록을 가리키게 한다. 2) multi-level index: 인덱스 블록의 인덱스가 파일의 위치를 직접 가리키는 것이 아니라 또 다른 인덱스를 가리키게 한다. (2번 거침)

Unix의 파일 시스템 구조

1) Boot block: 어떤 파일 시스템이든 boot block이 맨 앞에 나온다.(약속) -> 전원키면 부팅한다. 즉 Boot block(부팅에 필요한 정보)을 메모리에 올린다. Boot block이 시키는 대로 하면 이 파일 시스템에서 OS 커널의 위치가 어디인지 찾아서 그것을 메모리에 올려서 부팅이 이루어진다.
2) Super block: 파일 시스템에 관한 총체적인 정보를 담고 있다. -> 어디가 먼 블록이고, 어디가 파일이 저장되어 있는지 등
3) Inode block: 파일의 메타 데이터를 가진다. -> 파일 하나당 하나의 Inode가 할당되며, 파일의 위치, 파일 크기, 파일의 소유자, 권한, 마지막 접근 시간, 마지막 수정 시간 등의 정보를 포함한다.
4) Data block: 실제 파일 데이터가 저장되는 블록이다. -> ex> Directory 파일의 경우 file 이름 : inode 번호 이렇게 가진다.

FAT File System(윈도우즈)

1) FAT: 파일의 메타데이터의 일부를 가진다.(특히 위치 정보를 담고 있는 테이블) 2) Data block: 똑같이 실제 파일 데이터가 저장되는 블록이다. 파일 시스템은 여러 클러스터로 나누어져 있으며, 각 클러스터는 일정 크기의 데이터 블록을 가진다. -> ex> Directory 파일의 경우 file 이름: 접근 권한, 소유주 등 모든 메타 데이터를 디렉터리가 가진다. 이를 통해 각 파일이 어떤 클러스터에 저장되어 있는지 FAT와 함께 관리한다.

• 직접 접근이 가능하다 (FAT이 작은 테이블임, 메모리에 올리면 쭉 따라간다) Data block가 FAT를 분리하였다. (FAT이 중요해서 2copy 이상 저장함)

비어있는 Blck 관리 방안

1. Bit map or Bit vector

각각의 Block 별로 번호가 있으면 유닉스의 경우 super block에다가 비트를 두어서 사용중인지 비어있는지 0과 1로 표시한다. 비트맵의 크기는 블록의 개수만큼 구성한다.

2. Linked list

비어있는 Block들을 연결한다. 장점: 공간의 낭비가 없다. 단점: 연속적인 빈 공간을 찾기 어렵다.

3. Grouping

처음에 비어있는 위치가 인덱스 역할을 한다. 하나의 Free Block에 비어있는 여러 Block의 인덱스를 저장한다.

4. Counting

연속적인 빈 Block을 찾기에 효과적이다.

1) 빈블록의 첫번째 위치, 2) 거기서 부터 몇개가 빈 블록인지...

디렉토리 구현(Directory Implementation)

1. 선형 리스트(Linear list)

file 이름: x바이트 file size: n바이트 즉 메타 데이터 크기는 고정 되어 있다. 구현은 간단하다 그러나 디렉터리 내에 파일이 있는지 찾기 위해서는 linear search가 필요하다.

2. 해시 테이블(Hash Table)

순차 탐색이 필요 없다. 파일 이름에 해시함수 적용하고 그 결과 엔트리를 찾는다. ex> F(ccc) -> 3 (3번 엔트리 씀) 그러나 Hash Collection 발생시 문제가 생긴다.

3. File의 메타데이터 보관 위치

1) 디렉터리 내에 직접 보관 2) 디렉터리에는 포인터를 두고 다른 곳에 보관(inode, FAT)

4. Long File name의 지원

파일 이름을 특정 byte수로 제한하는 것은 비효율적

길어서 정해진 엔트리 수 벗어나면 포인터를 두어서 맨 끝에서부터 파일 이름이 거꾸로 저장되도록 한다.

VFS and NFS

1. VFS(Virtual File System)

파일 시스템별로 서로 다른 종류의 System Call 쓰면 사용자가 혼란온다. VFS인터페이스를 두어서 동일한 시스템 콜 인터페이스(API)를 통해 접근할 수 있도록 해주는 OS 계층이다.

2. NFS(Network File System)

분산 시스템에서는 네트워크를 통해 파일이 공유될 수 있다. 즉 파일 시스템이 로컬 strage에 저장될 수도 있지만 원격에 저장된 파일시스템에 내가 접근할 수도 있다.

Page 캐시와 Buffer 캐시

1. Page 캐시

물리적인 메모리에 있는 프레임들을 페이지 케시라고 부른다. 파일을 읽거나 쓸 때, 데이터를 디스크에서 직접 읽는 대신, 해당 파일의 일부 또는 전체를 메모리에 로드하고 이를 캐시로 사용한다. 이렇게 하면 디스크 I/O를 줄일 수 있고, 캐시된 데이터를 더 빠르게 액세스할 수 있다. 디스크는 물리적으로 느리기 때문에, 디스크 접근 대신 메모리에서 데이터를 읽어오는 것이 성능상 훨씬 유리하다. -> Swap area보다 빠르다.

2. Memory-Mapped I/O

파일의 일부 또는 전체를 물리 메모리의 특정 주소에 직접 매핑하여, 파일의 데이터에 접근할 때 파일을 읽거나 쓰는 System Call(read, write)을 사용하지 않고, 메모리 접근처럼 처리하는 방식이다. -> 즉, 메모리에 파일의 데이터를 매핑해 두고, 프로그램은 이 매핑된 메모리를 접근하여 파일의 데이터를 읽거나 쓴다.

3. Buffer 캐시

파일에 대한 데이터를 사용자가 요청시 디스크에서 읽어서 사용자에게 전달하는 것이 아니라 OS가 읽어온 내용을 자기의 영역 중 일부에 저장해놓고 나중에 같은 요청 발생시 디스크까지 가지 않고 Buffer 캐시에서 바로 읽어준다.

4. Unified Buffer 캐시

최근의 OS는 Page 캐시와 Buffer 캐시를 같이 쓴다.

1) 메모리 내의 캐시 영역: 그림의 왼쪽 부분은 운영 체제의 메모리 영역을 나타낸다. 이 영역에는 Page Cache와 Buffer Cache가 통합된 형태로 데이터가 저장된다.
2) 파일 시스템의 데이터 블록: 그림의 오른쪽 부분은 파일 시스템의 데이터 블록을 나타낸다. 여기에는 파일이 저장된 데이터 블록이 있으며, 운영 체제는 필요한 데이터를 이 블록에서 읽어와 캐시에 저장한다.
3) 통합된 캐시 관리: Unified Buffer 캐시는 Page Cache와 Buffer Cache를 통합하여 관리하며, 캐시의 내용이 동일한 파일 시스템 데이터 블록을 가리키도록 한다. 이를 통해 메모리 사용 효율성과 성능을 향상시킨다.

Unified Buffer Cache or Not?

1. Unified Buffer Cache를 이용하지 않는 File I/O

1) read/write I/O

• read 또는 write system call이 사용자 프로그램으로부터 들어오면, 운영 체제(OS)는 디스크에 있는 파일 데이터를 사용자에게 전달해야 한다.

• 이를 위해 OS는 파일 시스템에서 요청된 파일의 내용을 디스크에서 읽어와 OS의 Buffer 캐시(Buffer Cache)에 저장한다.
• 이후, 사용자 프로그램에게 데이터를 전달할 때는 OS의 Buffer 캐시에서 사용자 프로그램의 메모리 영역(사용자 페이지)로 데이터를 복사(Copy) 한다.

2) Memory Mapped I/O

• Memory-Mapped I/O는 파일의 데이터를 메모리에 직접 매핑(Mapping)하여 파일 내용을 메모리처럼 읽고 쓸 수 있게 하는 방식이다.

• 이 방식은 사용자가 mmap system call을 호출하여 자신의 프로세스 주소 공간의 일부를 파일에 매핑한다.
• 매핑이 완료되면, OS는 디스크에 있는 파일의 일부 내용을 Buffer 캐시에 읽어오고, 이를 Page 캐시(Page Cache)에 복사한다.
• 사용자 프로그램은 자신의 주소 공간에 매핑된 메모리 영역에 대해 직접 메모리 접근(읽기/쓰기)하듯이 파일 데이터를 접근할 수 있다. 이 때, 파일의 데이터가 이미 Page 캐시에 존재한다면, 사용자 프로그램은 데이터를 메모리에 접근하듯이 빠르게 읽거나 쓸 수 있다.
• 만약 사용자가 매핑만 해놓고 데이터를 아직 메모리에 읽어오지 않았다면, 메모리 접근 시 페이지 폴트(Page Fault)가 발생한다.

2. Unified Buffer Cache를 이용하는 File I/O

Unified Buffer Cache를 사용하면 운영 체제(OS)는 파일 I/O와 메모리 관리의 효율성을 높이기 위해 Page 캐시와 Buffer 캐시를 통합하여 관리한다. 이 접근 방식은 파일의 데이터를 관리하는 데 필요한 중복을 줄이고, 메모리 사용의 일관성과 효율성을 높인다.

1) read/write I/O

• Unified Buffer Cache를 사용하는 경우, OS는 Page 캐시와 Buffer 캐시를 따로 나누지 않고, 필요에 따라 같은 메모리 공간(Page 캐시)을 사용한다.

• 사용자 프로그램이 read 또는 write system call을 호출하면, OS는 CPU의 제어를 가져와서 데이터를 처리한다.
• 파일의 내용이 이미 메모리에 올라와 있는 경우에 OS는 Page 캐시에서 해당 내용을 사용자 프로그램의 주소 공간으로 복사하여 사용자에게 전달한다.
• 파일의 내용이 메모리에 올라와 있지 않은 경우에 OS는 디스크의 파일 시스템에서 해당 데이터를 읽어와 Page 캐시에 저장한 후, 이를 사용자 프로그램의 주소 공간으로 복사하여 전달한다.

• 결과적으로, 파일 데이터는 Page 캐시에서만 관리되며, Buffer 캐시와 Page 캐시의 중복이 없어집니다.

2) Memory Mapped I/O

• 사용자 프로그램이 mmap system call을 호출하여, 자신의 주소 공간의 일부를 파일에 매핑한다. 이 때, Page 캐시가 사용자 프로그램의 주소 공간에 직접 매핑된다. 즉, 파일의 데이터를 별도로 Buffer 캐시에 복사하지 않고, Page 캐시 자체가 사용자 프로세스의 가상 주소 공간에 논리적으로 매핑된다.

• Page 캐시가 사용자 프로그램의 메모리 주소에 직접 연결되므로, 사용자 프로그램은 파일 데이터를 메모리처럼 읽고 쓸 수 있다.
• 버퍼 캐시와 페이지 캐시가 분리되지 않고, Page 캐시가 공유되는 방식이기 때문에, 중복된 데이터 복사 과정이 제거된다.
• 파일의 내용을 읽거나 쓰는 경우, 데이터가 이미 메모리에 존재하면 메모리 접근 속도로 빠르게 접근할 수 있다.

프로그램의 실행

1) 파일 시스템에서 파일이 실행이 되면 프로세스가 되고 이 프로세스는 각자 virtual memory를 가진다. 2) 각자 지닌 virtual memory는 주소변환해주는 HW(MMU)로 인해 당장 필요한 부분만 물리 메모리(RAM)에 올라간다. 나머지는 Swap area로 올라간다.

• 코드 부분은 물리메모리에 올라갔다가 쫓겨날때 swap area로 가지 않는다.

• 코드 부분은 read only로 이미 실행파일 형태로 저장되어 있다.

• 코드 부분은 이미 파일 시스템에 있기 때문에 swap area로 내리지 않고, 필요 없으면 물리적 메모리에서 지운다. 나중에 필요하면 파일 시스템에서 가져온다.

프로그램 실행(Memory Mapped I/O)

가상주소의 것을 물리메모리에다가 매핑해서 쓴다. (그 내용이 곧 이 내용)

• 프로그램이 실행되다가 데이터 파일을 쓰고 싶다.(Memory Mapped I/O 형태로)

1) 프로그램이 OS에게 이 데이터 파일의 일부를 내 주소공간 일부에다가 매핑해줘 라고 System Call을 한다. 2) 프로그램이 매핑된 가상 메모리 영역에 접근하려고 시도하지만, 그 내용이 실제로 물리 메모리에 아직 로드되지 않은 경우 페이지 폴트(Page Fault)가 발생힌다. 이때 CPU 제어권이 OS에게 넘어간다. OS는 페이지 폴트를 처리하기 위해 디스크에서 해당 파일의 필요한 데이터 페이지를 읽어와 물리 메모리에 올린다. 3) 가상의 페이지가 물리적 메모리의 페이지로 매핑이 된다. 4) OS는 가상 메모리의 페이지와 물리 메모리의 페이지 프레임을 연결하여 매핑한다. 이제 가상 주소 공간에서의 메모리 접근은 물리 메모리의 실제 데이터 위치를 참조하게 된다. 이 매핑이 완료되면, 프로그램은 메모리 주소를 통해 OS의 도움없이 파일 데이터를 직접 접근할 수 있다. 5) 나중에 물리메모리의 검정색 부분이 쫓겨날때는 swap area로 가는게 아니라 Memory Mapped 파일이기 때문에 파일에다가 수정된 내용을 써주고 쫓아낸다. 6) 다른 프로그램도 동일한 파일, 동일 데이터에 대해 Memory Mapped I/O 호출이 가능하다. 그럴시 물리메모리의 검정색 부분이 공유된다.

프로그램 실행(read write I/O)

파일에 대해 read/write system call을 해서 사용할 수 도 있다.

• 이 경우에 프로그램 A가 원하는 파일의 특정 내용을 달라고 OS에게 System Call을 한다.
• 이 system call을 통해 프로그램 A는 OS에게 "이 파일의 특정 데이터를 나에게 전달해달라"거나 "이 데이터를 파일에 써달라"는 요청을 한다.
• OS는 요청을 받으면 해당 파일의 데이터를 확인하기 위해 Unified Buffer Cache를 확인한다. Unified Buffer Cache는 Page 캐시와 Buffer 캐시가 통합된 형태로 관리되는 캐시이다. 즉, 물리 메모리에 있는 페이지 캐시가 버퍼 캐시의 역할도 겸하고 있다.
• 검정색 부분은 해당 파일의 데이터가 이미 물리 메모리(Page 캐시) 내에 올라와 있는 상태를 의미한다.
• 파일의 특정 내용이 이미 Page 캐시(버퍼 캐시)로 메모리에 로드되어 있는 경우(검정색 부분이 있는 경우)에 OS는 해당 데이터를 Page 캐시에서 읽어와 사용자 프로그램의 메모리 공간으로 복사(Copy) 한다.
• 파일의 내용이 아직 메모리에 올라와 있지 않은 경우에 OS는 디스크에서 해당 파일의 데이터를 읽어와 Unified Buffer Cache에 저장한다. 데이터를 Page 캐시로 메모리에 로드한 후, 사용자 프로그램의 메모리 공간으로 복사(Copy)하여 전달한다.

즉 OS가 사용자 프로그램 A에게 필요한 데이터를 메모리에 로드하고 이를 복사하여 전달하면, 프로그램 A는 해당 데이터를 사용할 수 있게 된다.

결론

1. Memory Mapped I/O

장점: 빠르고 효율적인 접근 -> 직접 메모리 접근:

• Memory Mapped I/O를 사용하면, 파일의 데이터가 물리 메모리에 로드된 후에는 System Call 없이 프로그램이 직접 메모리 접근을 통해 데이터를 읽고 쓸 수 있다.

• 파일의 데이터를 메모리에 매핑하고 나면, 프로그램이 CPU를 가지면서 메모리 접근처럼 빠르게 파일 데이터를 처리할 수 있습니다. 이로 인해 I/O 작업 속도가 매우 빨라진다.
• Memory Mapped I/O는 파일 데이터를 메모리에 매핑할 때, 해당 데이터가 메모리에 이미 올라와 있다면 추가적인 메모리 복사(copy) 작업 없이 사용할 수 있다.
• 파일의 내용을 프로세스의 가상 메모리 주소 공간에 직접 매핑하므로, 변경된 내용은 가상 메모리와 물리 메모리 간에 바로 전달된다.
• 이는 read/write I/O 방식에서 발생하는 메모리 복사 오버헤드가 제거되어 효율성이 증가한다.
• 파일 데이터가 이미 메모리에 존재한다면, OS의 추가적인 개입 없이 프로그램이 직접 데이터를 읽고 쓸 수 있다.
• 페이지가 메모리에 없는 경우에만 페이지 폴트가 발생하여 OS가 필요한 데이터를 메모리에 로드하는 방식이므로, system call 호출 횟수가 줄어들어 성능이 향상된다.

2. read/write I/O

• read/write I/O 방식에서는 파일 데이터가 OS의 Buffer Cache에서 사용자 메모리로 복사되어 전달된다.

• 프로그램이 데이터를 읽거나 쓰기 위해 매번 시스템 콜을 통해 OS에 요청하고, OS는 해당 데이터를 캐시에서 복사하여 전달하기 때문에, 프로그램 간의 데이터 일관성 문제가 없다.
• 각 프로그램이 파일의 데이터에 대한 독립적인 복사본을 가지므로, 프로그램 간 충돌이나 일관성 문제가 발생하지 않는다.

3. 결론

Memory Mapped I/O는 파일 데이터가 메모리에 올라와 있는 경우 빠르고 효율적으로 접근할 수 있고, 메모리 복사 오버헤드가 없어서 성능이 뛰어나다. 그러나 여러 프로그램이 같은 메모리 영역을 공유할 때 데이터 일관성 문제가 발생할 수 있어 이를 주의해야 한다.

read/write I/O 방식은 시스템 콜을 통해 데이터를 복사하여 전달하므로 데이터 일관성 문제가 없다. 하지만 메모리 복사로 인한 오버헤드가 발생할 수 있으며, 성능 측면에서는 Memory Mapped I/O보다 느릴 수 있다.

따라서, 사용할 I/O 방식은 파일 접근의 특성과 애플리케이션의 요구 사항에 따라 결정해야 한다. 데이터 일관성이 중요한 경우 read/write I/O를 사용하고, 성능이 중요한 경우 Memory Mapped I/O를 사용할 수 있다.

데이터 일관성 문제란?

데이터 일관성(Consistency) 문제란, 동일한 데이터를 여러 프로그램(프로세스)이 동시에 읽거나 쓸 때, 모든 프로그램이 동일한 최신 데이터를 볼 수 없을 때 발생하는 문제를 말한다. 이 문제는 Memory Mapped I/O를 사용할 때 더 두드러질 수 있습니다. 반면, read/write I/O 방식에서는 이러한 문제를 피할 수 있다.

예시를 통한 데이터 일관성 문제 설명

• 예시 시나리오: 두 개의 프로그램, 프로그램 A와 프로그램 B가 동일한 파일 data.txt를 사용하여 작업을 하고 있다고 가정한다. 이 파일은 숫자 100을 담고 있는 간단한 텍스트 파일이다.

프로그램 A와 프로그램 B는 각각 Memory Mapped I/O를 사용하여 이 파일의 데이터를 메모리에 매핑하여 사용한다. 프로그램 A는 파일의 숫자를 200으로 업데이트하고, 프로그램 B는 파일의 숫자를 읽어와 더한 다음(+300), 결과를 다시 파일에 쓰는 작업을 수행한다.

1) Memory Mapped I/O 방식에서의 데이터 일관성 문제

• Step 1: 프로그램 A와 B는 Memory Mapped I/O를 사용하여 data.txt를 메모리에 매핑한다.

  이 과정에서 파일 data.txt의 데이터(100)는 각 프로그램의 메모리에 매핑된다. 물리 메모리의 동일한 페이지가 매핑되어 프로그램 A와 B가 동일한 메모리 영역을 공유하게 된다.

• Step 2: 프로그램 A가 Memory Mapped I/O를 통해 파일의 내용을 100에서 200으로 변경한다.

  이때, 프로그램 A의 메모리 영역에서 값이 200으로 변경되고, 그 내용은 물리 메모리에 반영된다.

• Step 3: 프로그램 B가 같은 메모리 영역을 읽습니다.

  프로그램 B가 동일한 메모리 영역을 읽을 때, 프로그램 A의 변경이 이미 반영되어 있으면 값이 200으로 보이겠지만, 이 시점에서 B가 변경 전의 데이터를 읽고 있으면 값은 여전히 100으로 보일 수 있다. 만약 프로그램 B가 값이 100인 상태로 데이터를 가져와 작업(+300)을 한다면, B의 연산 결과는 500이 되어야 하지만, 잘못된 값 100에서 시작했기 때문에 400이 된다.

• Step 4: 프로그램 B가 그 값을 다시 메모리에 쓰면, 메모리에는 값이 400이 저장된다.

  프로그램 A가 200으로 변경한 내용이 무시되었고, 결과적으로 데이터의 일관성이 깨지는 문제가 발생한다.

2) read/write I/O 방식에서의 데이터 일관성 보장

• Step 1: 프로그램 A와 B는 파일 data.txt를 read/write I/O 방식으로 접근한다.

  프로그램 A가 read 시스템 콜을 통해 파일을 읽어와서 자신의 사용자 메모리 공간에 복사한 후, 값을 100에서 200으로 업데이트한다. 프로그램 A는 write 시스템 콜을 통해 변경된 데이터를 OS의 버퍼 캐시에 기록하고, 이 데이터는 OS가 관리하는 버퍼에 저장된다.

• Step 2: 프로그램 B가 read 시스템 콜을 통해 파일의 데이터를 읽습니다.

  프로그램 B의 요청은 OS가 관리하는 버퍼 캐시에서 처리되므로, 프로그램 A가 파일을 수정하여 OS에 반영한 최신 데이터(200)를 가져온다. 프로그램 B는 200이라는 최신 값을 사용하여 연산(+300)을 수행하고, 결과를 write 시스템 콜을 통해 파일에 기록합니다. 이 경우, 프로그램 B가 최신 값을 가져왔기 때문에 최종 결과는 일관성 있는 데이터 500이 됩니다.

• 왜 데이터 일관성 문제가 발생하는가?

  Memory Mapped I/O 방식에서 데이터 일관성 문제가 발생하는 이유는 물리 메모리의 동일한 부분을 여러 프로그램이 동시에 공유하여 사용하는 경우, 변경된 내용을 서로 알지 못하는 상황이 발생할 수 있기 때문이다. 반면 read/write I/O 방식에서는 모든 데이터 접근이 OS를 통해 이루어지며, OS가 일관성을 유지하는 역할을 수행한다. ** OS가 이를 순차적으로 처리하면서 데이터의 일관성을 유지한다.** 모든 파일의 읽기/쓰기 요청이 OS의 버퍼 캐시를 통해 이루어지기 때문에, 변경된 데이터는 항상 OS의 버퍼 캐시에 반영되고, 다른 프로그램이 최신 데이터를 읽어올 수 있다.

요청시 메모리에 올리는 것이다. 즉 프로그램이 실제로 필요로 할때 페이지를 메모리에 로드하는 방식이다.

1) I/O 양의 감소 2) Memory 사용량 감소 3) 빠른 응답시간 4) 더 많은 사용자 수용

Valid/Invalid Bit를 사용한다.

• Valid Bit: 페이지가 실제 물리 메모리에 있음을 나타냄
• Invalid Bit: 페이지가 물리적인 메모리에 안올라와 있고 Backing Store에 내려가 있는 경우이다. 혹은 사용되지 않는 주소 영역일 경우일 수 도 있다.

주소변환 하려고 봤는데 Invalid인 것들은 MMU가 Page Fault 발생시킨다. (어차피 물리메모리에 없다) Trap이 발생한다.

• Trap: Page Fault 발생하면 CPU 제어권이 OS에게 넘어감 이제 OS가 CPU를 가지게 되고 Page Fault 루틴을 처리하게 된다. 또한 DMA 컨트롤러가 Backing Store에서 페이지를 메모리에 올린다.

Free Frame이 없는 경우

Free frame이 없을 경우 운영체제(OS)는 새로운 페이지를 메모리에 올리기 위해 기존에 메모리에 있는 페이지 중 하나를 선택하여 쫓아내야 한다. 이를 페이지 교체(Page Replacement)라고 한다. 페이지 교체 과정은 다음과 같은 단계를 포함한다.

1. Page Replacement

1) 페이지 교체 결정:

OS는 새로운 페이지를 메모리에 올려야 할 때, 메모리에 빈 프레임이 없으면 어떤 페이지를 메모리에서 쫓아낼지를 결정한다. 이 결정은 페이지 교체 알고리즘에 따라 이루어진다.

2) 백업 필요 시 백킹 스토어로 쓰기:

만약 쫓아낼 페이지가 메모리에 올라온 이후에 쓰기 연산(write)이 발생해 변경된 내용이 있다면, 이 페이지의 내용을 백킹 스토어(예: 디스크)로 기록해야 한다. 이를 "dirty page"라고 하며, 변경된 페이지가 아니면 기록할 필요가 없다.

2. Relacement Algorithm

페이지 교체 알고리즘은 어떤 페이지를 쫓아내야 하는지를 결정하는 방식이다. 좋은 페이지 교체 알고리즘은 페이지 결함률(Page Fault Rate)이 낮게, 즉 가능한 한 0에 가깝게 유지하도록 설계되어야 한다.

• Page Fault: 프로그램이 실행 중에 필요한 페이지가 현재 메모리에 로드되어 있지 않음을 발견할 때 발생한다. 즉, CPU가 참조하고자 하는 메모리 페이지가 메모리에 없을 때 발생하는 것이다.

• 평가 페이지 결함률(Page Fault Rate): 주어진 페이지 참조 문자열(reference string)에 대해 페이지 결함이 얼마나 자주 발생하는지를 측정한다. 페이지 참조 문자열(Page Reference String): 시간 순서에 따라 페이지를 참조한 순서를 나열한 것이다. 예를 들어 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5라는 참조 문자열이 있을 때, 이는 특정 시간 동안 페이지 1, 2, 3, 4 등을 참조한 순서를 나타냅니다.

1) Optimal Algorithm

Page Fault를 가장 적게 하는 알고리즘이다. 가정: 미래에 참조될 Page들을 다 안다고 가정 가장 먼 미래에 찹조되는 Page를 교체한다.

2) FIFO Algorithm

먼저 들어온 것을 쫓아낸다. 프레임이 많아질수록 성능이 안좋아진다.(3프레임: 9page faults -> 4프레임: 10page faults)

3) LRU(Least Recently Used) Algorithm

제일 오래전에 사용된거를 쫓아낸다.

4) LFU(Least Frequently Used) Algorithm

참조 횟수가 가장 적은 페이지부터 쫓아냄

• 최저 참조 횟수인 페이지가 여러개 있는 경우 : 마지막 참조 시점이 오래된거부터 쫓아냄

• LRU vs LFU

1, 1, 1, 1, 2, 2, 3, 3, 2, 4, 5(현재)

1) LRU: 1번 OUT (가장 최근에 사용되지 않은거) 2) LFU: 4번 OUT (가장 사용률 적었던거)

• LRU vs LFU 구현

다양한 캐싱 환경

한정된 빠른 공간에 요청된 데이터를 저장해 두었다가 후속 요청시 캐쉬로부터 직접 서비스하는 방식이다.

Clock 알고리즘

LRU, LFU는 실제로 쓰지못한다. LRU와 근사한 알고리즘이다.

과정

중간중간에 CPU가 해당 페이지를 참조하면 HW가 이를 1로 설정한다.

1) 레퍼런스 비트가 0인 것을 찾을 때까지 포인터를 하나씩 앞으로 이동한다.(이동 중 1은 0으로 바꾼다)

2) 포인터가 이동하는 중에 레퍼런스 비트가 0인 것을 찾으면 그 페이지는 교체한다.

3) 1을 0으로 바꾸고, 한바퀴 돌아와서 0이면 그때에는 교체한다.

4) 자주 사용되는 페이지라면 Second Chance(한바퀴 돌아와서)가 올때 1이다.

1. 레퍼런스 비트가 0

시계바늘이 한바퀴 돌아오는 동안 이 페이지에 대한 참조가 없었다.(쫓아낸다)

2. 레퍼런스 비트가 1

시계바늘이 한바퀴 돌아오는 동안 적어도 한번의 참조는 있었다.

페이지 프레임 할당

각 프로세스에 얼마만큼 페이지 프레임을 할당할 것인가

1) Equal allocation: 모든 프로세스마다 똑같이 할당 2) Proportional allocation: 프로세스 크기에 비례하여 할당 3) Priority allocation: 프로세스의 priority에 따라 다르게 할당

Global vs Local Replacement

• Global replacement : 모든 페이지 프레임이 교체대상이 된다. 효율적일 수 있으나 스레싱 위험이 있다.
• Local replacement: 해당 프로세스에 할당된 페이지 프레임내에서만 교체를 수행한다. 안정적성능을 가지고 성능이 예측가능하다. 그러나 자원 충족이 어려울 수 있다.

Thrashing

프로세스의 원활한 수행에 필요한 최소한 페이지 프레임 수를 할당 받지 못하면 페이지 부재율이 크게 상승하여 CPU 이용률이 떨어진다. 이를 스레싱이라고 한다.

Page Fault가 전체적으로 많이 일어남 -> CPU가 인스트럭션 실행하려고 보면 그 페이지가 메모리에 없음 (I/O 해야함)

Working-set Model

적어도 프로그램들이 메모리에서 원활하게 실행되려면 어느정도의 메모리 페이지가 있어야 한다.

프로그램이 특정시간에는 특정 메모리 위치만 집중적으로 참조하는 특징이 있다. 이를 Locality of reference 라고한다.

이러한 Locality of reference에 기반하여 프로세스가 일정 시간 동안 한꺼번에 메모리에 올라와 있어야 하는 페이지의 집합을 워킹셋이라고 한다.

• working-set Model

  워킹셋 집합 전체가 메모리에 올라와 있을 수 있어야 수행이 된다. working set이 페이지 5개인데 메모리가 페이지에 3개의 공간밖에 못준다. 해당 프로세스는 모든 페이지를 반납하고 디스크로 SWAP OUT 된다.

Working-set 알고리즘

왼쪽을 보면 현재 시점에서 이 프로그램의 working set은 5개이다. working-set 알고리즘은 이 5개의 프레임을 이 프로그램에게 줄 수 있으면 {1, 2, 5, 6, 7}을 한꺼번에 메모리에 올린다. 아니면 전부다 디스크로 Swap Out 시키고 suspended 상태로 바꾼다.

PFF(Pafe-Fault Frequency) scheme

working set 수행하지 않고, 직접 page fault rate를 시스템에서 보고 결정한다. page fault rate의 상한과 하한값을 두고 프레임을 늘릴지 줄일지 결정한다.(page fault rate가 높다는 것은 필요한 페이지가 없다는 것을 의미한다 따라서 더 할당해줌) 만약 할당시키다가 빈 프레임이 없다면 일부 프로세스를 Swap OUt 한다.

• page size?: 메모리 크기가 커지면서 page size도 이제는 커지는게 트렌드 이다.

1) Logical 주소(Virtual 주소)

각 프로세스마다 0번지 부터 시작하는 논리주소 공간을 가짐(Virtual Memory) CPU가 보는 주소

주소변환 과정에 OS는 참여하지 않는다. 오직 하드웨어가 관여한다. 즉 여기에서 OS의 역할은 없다.

2) Physical 주소

메모리에 실제 올라가는 위치

주소바인딩

주소를 결정하는 것이다. Symbolic주소 -> Logical 주소 는 컴파일에서 이루어 진다. 그 후 Logical주소에서 Physical주소로 바뀌는 것이 바로 주소바인딩이다.

1) Compile time binding

논리주소 그대로

2) Load time binding

비어있는 곳 찾아서 할당

3) Run time binding

Load time binding처럼 처음에는 비어있는 곳에 할당했다가 실행 도중 이동이 가능하다. 이동할때는 MMU가 변환한다.

• CPU가 논리적 주소를 보는 이유는?

  물리적 메모리에 실행파일 코드 주소가 그대로 올라간다.(ex> Add 20, 30) CPU가 그 위치의 해당 논리주소에만 접근하면 MMU가 이거를 바꿔서 접근하게 해준다.

MMU(Memory Management Unit)

동적할당(Dynamic Loading)

그때그떄 루틴이 불려 질때마다 그 루틴을 메모리에 올림 생각보다 자주 사용되는 프로그램은 한정적임 (통째로 메모리에 올리면 비효율적임) OS가 라이브러리로 프로그래머가 동적할당 할 수 있게 도와줌

Overlays

메모리에 실제 필요한 부분만 올림 OS의 지원없이 프로그래머가 코딩을 통해 어디다 올릴지 짜야함

Swapping

프로세스를 일시적으로 메모리에서 HDD(Backing Store: swap area)로 쫓아냄

메모리에 너무 많은 프로그램이 올라와 있으면 시스템이 비효율적이 됨 따라서 중기 스케줄러가 일부 프로그램을 골라서 통째로 메모리에서 디스크로 쫓아냄

즉 CPU 수행가능성이 낮은 프로그램들을 골라서 메모리에서 HDD로 스왑 아웃 시킴

Swap Out을 당해도 물리메모리에 다시 Swap In 될때 원래주소로 가기 보다는 다른위치로도 비어있다면 갈 수 있게 해주는 Runtime binding이 사용되면 좋다.

Dynamilc Linking

1) Static Linking

라이브러리가 프로그램의 실행파일코드에 포함됨 ex> printf 프로그래밍 내가 만든 프로그램에 이미 printf의 코드가 포함되어 있다. 즉 내 프로그램 주소 공간에서 실행됨

2) Dynamic Linking

내 코드안에 라이브러리가 없지만 별도의 라이브러리 파일 위치를 찾을 수 있는 stub라는 작은 코드를 둠 -> 찾아서 필요하면 메모리에 올리고, 이미 올라와 있다면 그 주소로 가서 라이브러리를 실행함

Dynamic Storage-Allocation Problem

가장 적절한 hole을 찾아서 할당하는 것이다.

1) First-Fit

Hole 중에서 제일 먼저 찾아진 hole에다가 할당한다.

2) Best-Fit

Hole을 다 찾아본뒤 프로그램 크기와 가장 잘 맞는 hole에다가 프로그램을 올려놓는다.

3) Worst-Fit

가장큰 hole에 프로그램 할당 (어리석은 방법)

• Compaction

  외부조각으로 생기는 hole들을 한군대로 몰아서 아주 큰 hole을 만들어서 hole의 크기가 작아서 사용이 안되는 문제를 해결할 수 있다.

물리적 메모리 할당(Allocation of Physical Memory)

1. 연속할당

고정분할과 가변분할이 있다. 프로그램이 메모리에 올라갈 때 통째로 메모리에 올라간다.

고정분할은 분할 4개를 미리 나누어 놓는다 즉 융통성이 없다. 즉 뭔지도 모르고 나눠 놓았기 때문에 외부조각도 나오고 내부조각도 나온다. (공간 여분)

가변분할은 차곡차곡 공간에 프로그램을 올려놓는다. 그런데 B가 끝나고 D가 실행이 되면 B공간은 너무 작기 때문에 밑으로 들어가고 외부조각이 발생한다. 내부조각이 발생하지는 않는다.

2. 불연속할당(현재의 시스템)

프로그램마다 별도의 pagetable이 존재해야한다.

프로그램을 구성하는 주소공간을 잘개 쪼개서 일부는 이쪽 일부는 다른쪽에 할당한다.(여기저기 흩어져 있다.)

1) 페이징, 2) 세그멘테이션, 3) Paged Segmentation

즉 2번의 메모리 접근이 필요해진다.

1) pagetable을 참조하여 주소변환(MMU가 함) 2) 변환된 주소에 접근 따라서 속도향상을 위해 별도의 하드웨어인 TLB를 사용한다.

• 페이지 테이블과 MMU의 관계

  페이지 테이블은 메모리 관리에 필요한 주소 매핑 정보를 저장하는 데이터 구조이고, MMU는 이 페이지 테이블을 참조하여 실제 주소 변환 작업을 수행하는 하드웨어 장치이다. 즉, 페이지 테이블은 변환 정보를 제공하고, MMU는 그 정보를 사용하여 주소 변환을 실제로 수행한다.

• 사용되는 레지스터 1) page-table base register(PTBR): 메모리상에서 Pagetable이 어디에 있는지 그 시작위치 2) page-table length register(PTLR): 페이지 테이블의 길이

TLB

1) TLB 참조

자주쓰는 주소를 pagenumber, framenumber를 매핑하여 캐시형태로 두고 있다. p라는 페이지에 대한 주소 변환정보가 TLB에 있는지 확인하려면 전부 찾아봐야함! 만약 없으면 일반적인 방식으로 전환한다. 문맥교환시 비워진다. 프로세스마다 다른 TLB를 가진다.

2) Page 테이블 참조

페이지 테이블 접근해서 메인 메모리에서의 시작주소를 GET한다. (1번 접근) 페이지 테이블에서 얻은 주소로 물리메모리에 접근하여 데이터를 얻는다.(2번 접근)

결론 Page 테이블은 실제 RAM(물리적 메모리)에 있기 때문에 이거에 접근하는거보다 캐시를 두어서 캐시 장치(TLB)에 먼저 접근해서 속도를 높인다.

2단계 페이지 테이블

실제로 안쓰는 곳이 많음에도 페이지 테이블은 똑같이 만들어진다. 즉 공간 낭비가 심하다. 따라서 Outer테이블을 하나 더만들어서 거기서 실제로 쓰는 공간만 매핑(페이지 테이블)하겠다라는 것이다.

현재의 컴퓨터는 메모리 주소체계가 매우크다(64비트)

결론: 전체 주소공간 중 생당부분은 실제로 사용하지 않기에 바깥쪽 페이지 테이블에 NULL을 넣는다. 따라서 실제 값이 있는 부분만 안쪽 테이블이 만들어진다. 논리메모리 주소크기 = 바깥쪽 페이지 테이블 크기(그러나 NULL이 삽입)

• 그러면 계속 테이블을 만들어서 공간을 줄일 수 있지 않을까?

  실제로 Multilevel Paging and Performance 를 통해 outer 테이블을 여러개 만들 수 있지만 테이블을 거치는 시간때문에 성능에 문제가 발생한다.

valid(v) / invalid(i)

프로그램이 0번, 7번 사용안하지만 페이지 테이블은 프로그램의 주소공간이 가질 수 있는 최대 사이즈 만큼 엔트리가 생긴다. 이를 i로 표기한다.

Memory Protection

페이지 테이블 각 엔트리마다 아래의 bit를 둔다.

1) Protection bit

어떤 연산에 대한 접근 권한 (page에 대한 접근 권한: read/write/read-only)

2) Valid/Invalid bit

valid: 해당 주소의 frame에 그 프로세스를 구성하는 유효한 내용이 있음(접근 허용) invalid: 해당 주소의 frame에 유효한 내용이 없음을 뜻함(접근 불허) -> 프로세스가 그 주소 부분을 사용하지 않음, 해당 페이지가 메모리에 올라와 있지 않고 SWAP AREA에 있는 경우

Inverted Page Table

지금까지의 문제는 Pagae Table의 용량이다. Inverted Page 테이블은 엔트리가 물리적메모리의 페이지 프레임 개수만큼 존재한다. 이제 진짜로 올라와 있는거만 페이지 테이블에 존재한다.

• 페이지 테이블은 프로그램의 주소공간이 가질 수 있는 최대 사이즈 만큼 엔트리가 생긴다

1) 어떤 프로세스의 p인지 전수조사(pid를 도입)

2) 찾은 위치의 인덱스를 구한다.(f)

3) f랑 d로 실제 데이터 접근한다.

그러나 전수조사 덕에 시간적인 오버헤드가 존재한다.

Shared Page

아래한글을 3개의 프로그램으로 돌리고 있다. 프로그램의 코드 부분은 3개의 프로세스가 똑같이 쓰면 된다. 공유할 수 있는것은 같은 프레임에 Mapping 시킨다(Shared Code)

• 그러나 2가지 조건이 필요하다 1) read only로 하여야 함 2) 동일한 logical 주소에 위치하여야 함

Segmentation

의미 단위로 쪼갠다 Code, Data, Stack 부분이 하나씩의 세그먼트로 형성된다.

1) Segmentation 변환

의미 단위로 일할 경우 세그멘테이션이 효과적임, sharing에 효과적, 보안에 효과적 그러나 Segment의 길이가 각각 다르므로 allocation 문제가 발생 first fit / best fit 등의 기법을 써야한다.

2) 필요한 레지스터

가. Segment-table base register(STBR)

물리적 메모리에서의 segment table의 위치

나. Segment-table length register(STLR)

프로그램이 사용하는 Segment의 수

3) Sharing of Segments

4) Segmentation with Paging

세그먼트 하나가 여러개의 페이지로 구성(크기가 달라져서 생기는 allocation 문제 해결) 즉 세그먼트 당 페이지 테이블이 존재한다.

결론: 세그먼트 테이블 해당하는 세그먼트 마다 표시함(의미단위) 물리적 메모리에 올라갈 떄는 페이지 단위(allocation 문제가 발생하지 않는다) 2가지 장점을 취한다.

교착상태 : 상대방이 가진 자원을 요구 그러나 상대방도 자기거 내놓지 않고 다른 상대방거를 요구한다.

• 데드락: 일련의 프로세스들이 서로가 가진 자원을 기다리면서 block된 상태
• 자원: HW, SW 등을 포함하는 개념 ex> I/O Device, CPU cycle, memory space, semaphore 등

1) 데드락 상황1(HW)

• 시스템에 2개의 tape drive가 있다.

• 프로세스가 하는 역할은 하나의 tape drive에서 읽어서 다른 tape drive에다가 copy하고싶음
• 2개의 프로세스가 각각 tape 2개를 점유해야함. 그러나 각각 하나의 tape drive를 보유한채 다른 하나를 기다리면 데드락 상태가 된다.

2) 데드락 상황2(SW)

P0는 B를 요청 P1은 A를 요청 그러나 이미 서로 가지고 있는 상태이다.

데드락 발생의 4가지 조건(전부만족)

1) 상호배제(Mutual exclusion)

독점적으로 씀, 매 순간 하나의 프로세스만이 자원을 사용할 수 있음 = 내가 가지고 있는 동안은 나 혼자 독점적으로 쓴다.

2) 비선점(No preemption)

프로세스는 자원을 스스로 내어놓을 뿐 강제로 빼앗기지 않음

3) 보유대기(Hold and Wait)

자원을 가진 프로세스가 다른 자원을 기다릴 때 보유자원을 놓지않고 계속 가지고 있음

4) 순환대기(Circular Wait)

자원을 기다리는 프로세스간에 사이클이 형성되어야 함

데드락의 처리방법

1) Deadlock Prevention(미리 막는다)

상호배제는 예방할 수 없다.

• 1> 그러나 비선점을 선점(preemption)으로 바꾸어 뺏어올 수 있게 하는 방식으로 예방이 가능하다.

• 2> 보유대기는 프로세스가 자원을 기다리고 있을때 자원을 가지고 있지 않게 해서 예방한다.

• 방법1: 프로세스 시작시 모든 필요한 자원을 할당받는다.(중간에 자원 요청할 필요 없음)

• 방법2: 자원있는 상태에서 요청시 내가 가진 자원은 모두 뱉어내고 다시 요청

• 3> 순환대기는 모든 자원마다 순서를 지정하는 방식으로 예방이 가능하다. (싸이클이 안생긴다)

미리막는 경우의 문제점은 자원이용률이 낮아지고 성능도 낮아진다는 것이다. 또한 Starvation의 문제가 나타날 수 있다 아직 생기지도 않을 데드락에 대해 제약조건을 너무 많이 단다.

2) Deadlock Avoidance

프로세스가 시작될때 이 프로세스가 평생 쓸 자원의 최대량을 미리 알고 있다고 가정하고 데드락을 피해간다. 어떤 프로세스가 자원요청시 내가 자원할당해주면 데드락이 생길 가능성이 있겠다 싶으면 자원의 여분이 있어도 주지 않는다.

가. 자원할당 그래프 알고리즘

자원의 인스턴스가 하나씩 밖에 없는 경우에 활용 가능하다.

• 점선: 이 프로세스가 적어도 평생의 한번은 이 자원을 사용할 일이 있다.

현재상태: R1이 P1에 할당된 상태이다. 이때 R1자원을 P2가 요청했지만 아직 할당을 못받았다.(이미 P1에 할당됨) 그 다음 P2가 R2를 요청한다. 만약 R2가 P2에게 가면 Cycle이 형성될 가능성이 존재한다. 따라서 Deadlock Avoidance가 동작한다면 R2를 P2에게 할당 하지 않는다.

나. Banker의 알고리즘

자원당 인스턴스가 여러개 있는경우에 활용이 가능하다.

3, 3, 2 는 모든 할당된 자원을 10 5 7에서 차감한 값이다.

포인트: Available로 Need를 커버할 수 있으면 받아들인다. 그 후 나에게 할당된 자원을 다시 반납한다. -> Available + Allocation 그리고 다음 프로세스로 들어간다.

3) Deadlock Detection

데드락의 예방이 아니라 발생시 감지하는것이다.

가. 자원의 인스턴스가 1개일때 데드락 찾기

자원을 전부 빼버린다. 그렇게 해서 데드락사이클을 찾는다.

각 노드 하나당 화살표가 최대 (n-1)개씩 있을 수 있기에 n*(n-1) O(n^2)만큼의 시간복잡도를 갖는다.

나. 자원의 인스턴스가 여러개일때 데드락 찾기

• 만약 P1이 요청시 데드락?

  낙관적으로 본다.

  1) P0는 요청하는 것이 없으므로 B1개를 반납한다. 2) P2는 요청하는 것이 없으므로 A 3개와 C 3개를 반납한다. 3) 그러면 A(3), B(1), C(3)개가 생겼고 P1의 요구인 A 2개와 C 2개를 들어줄 수 있다. 4) 또한 마찬가지로 P1역시 자원 다 쓰고 다시 반납할 것임을 가정한다.

• 만약 P2가 자원 C 1개를 요청하는 것으로 변경하면?

  데드락이다.

  1) P0만이 요청하는 것이 없으므로 B 1개를 반납한다. 2) B를 원하는 프로세스는 없음(그 다음 반납 없다) 3) 어떤 프로세스의 요청도 들어줄 수 없다.

4) Deadlock Recovery

가. 프로세스 종료

데드락에 연루된 프로세스들을 사살

1) 모든 프로세스를 한꺼번에 죽임 2) 하나씩 죽이면서 데드락 없어지는지 확인

나. 자원 선점(Resource Preemption)

데드락에 연루된 프로세스들로부터 자원을 뺏는 방법 -> 희생양(Victim)을 선정해서 자원을 뺏는다. -> 문제점: A의 자원을 뺏었는데 다른 프로세스가 갖기 전에 A가 그 자원 또 요청해서 다시 가져감. A가 다시 희생양이 됨(반복) Starvation 문제 발생 따라서 Victim의 패턴을 다르게 해줘야함.

5) Deadlock Ignorance (현재 OS들이 채택)

데드락이 일어나든 일어나지 않든 아무일도 안함 -> 프로세스 정지 상황이 일어난다. -> 사용자가 알아서 처리

• why? 1) 데드락을 안생기게 하는 방법이 자원을 비효율적으로 쓴다. 2) 데드락을 감지하는거도 시스템의 오버헤드가 크다.

1. Bounded-Buffer Problem

• Semaphore의 용도 1) Lock의 문제(생산자가 동시에 도착) 2) 가용자원의 개수세는 용도(버퍼의 유한함)

프로듀서는 버퍼에 데이터를 집어넣는다. 컨슈머는 버퍼의 데이터를 꺼내간다.

1) 생산자가 동시에 도착 -> Binary Semaphore(Lock/Unlock)

생산자가 둘이 동시에 도착하여 비어있는 버퍼를 보고, 생산자 둘이서 데이터 만들어서 버퍼에 넣는 경우 문제가 생김 이 경우 Lock을 걸어서 동시 접근을 막는다.

2) 버퍼의 유한함 -> Integer Semaphore(가용자원의 개수)

생산자들이 한꺼번에 도착해서 공유버퍼를 가득 채운다. (비어있는 버퍼가 나올때 까지 기다린다) 소비자들이 한꺼번에 와서 다 꺼내간다. (데이터가 있는 버퍼가 있을 때까지 기다린다)

Bounder-Buffer Problem 코드

• semaphore full: 내용이 들어있는 buffer의 개수를 세기위한 변수
• empty: 비어있는 buffer의 개수를 세기위한 변수
• mutex: Lock을 걸기위한 변수
• P(): 자원획득
• V(): 자원반납

P(empty)는 빈 버퍼의 개수를 확인한다(없으면 wait) P(full)는 데이터가 있는버퍼의 개수를 확인한다(없으면 wait) P(mutex)는 빈 버퍼를 획득하고 lock을 건다. V(full)은 내용이 들어있는 buffer변수를 1개 증가시킨다 V(empty)는 비어있는 buffer 변수를 1개 증가시킨다.

2. Readers-Writers Problem

프로세스는 2종류가 있다. 1) 공유데이터를 읽어가는 프로세스, 2) 공유데이터에 쓰는 프로세스

write는 동시에 여러명이 하면 안되지만 read는 여럿이 동시에 해도 synchronization에 아무런 문제가 생기지 않는다. 그러나 Read하러와서 Lock을 걸어 아무도 접근못하게 하면 비효율적이다.

1) shared data

int readcount;는 현재 공유데이터에 접근중이 Reader의 수이다.

2) synchronization variable

semaphore mutex=1 (Lock 용도: readcount변수 보호) db=1 (Lock 용도: db 보호)

오른쪽 Reader의 경우 최초의 Reader인 경우에 P(db)로 락을 걸어버린다. 그리고 다 읽고 마지막에 readcount가0이면 그제서야 V(db)로 락을 푼다.

위의 소스의 문제점은 Writer의 Starvation이다. Reader가 Lock을 걸어 놓은 상태에서 Writer가 먼저 와도 Reader가 후에 몇개씩 계속 도착하면 계속 기다려야 하기 때문이다.

3. Dining-Philosophers Problem

식사하는 철학자는 동기화 문제 중 하나로, 여러 프로세스가 공유 자원에 동시에 접근하려고 할 때 발생할 수 있는 교착 상태(Deadlock) 문제를 설명하는 고전적인 예이다.

이 문제는 N명의 철학자가 원형의 테이블에 앉아 있고, 각 철학자 사이에 하나의 젓가락이 놓여있으며, 철학자가 식사하려면 두 개의 젓가락(왼쪽과 오른쪽 젓가락)을 동시에 집어야만 하는 상황을 모델링한다.

semaphore chopstick[5];

do {
    P(chopstick[i]); // 왼쪽 젓가락 잡는 연산
    P(chopstick[(i + 1) % 5]); // 오른쪽 젓가락 잡는 연산
    ...
    eat(); // 양쪽 다 잡으면 밥먹는다
    ...
    V(chopstick[i]); // 왼쪽 젓가락 내려놓음
    V(chopstick[(i + 1) % 5]); // 오른쪽 젓가락 내려놓음
    ...
    think(); // 다시생각
    ...
} while (1);

문제점: Deadlock의 가능성이 있다. -> 모든 철학자 5명이 동시에 배가 고파서 왼쪽 젓가락을 잡음, 이러면 모든 철학자들이 본인이 밥을 먹고 배부를 때까지 놓지를 않음. 그러면 오른쪽 젓가락을 아무도 못잡음.

해결방법:

1) 4명의 철학자만이 테이블에 동시에 앉을 수 있도록 한다. 2) 젓가락을 2개 모두 집을 수 있을때에만 젓가락을 집을 수 있게 한다. 3) 비대칭: 짝수(홀수)철학자는 왼쪽(오른쪽) 젓가락부터 집도록한다. 짝수 -> 왼쪽(우선순위) 홀수 -> 오른쪽(우선순위) 즉 짝수는 왼쪽을 집을 수 있어야 권한이 생긴다.

Monitor

Semaphore의 문제점

1) 코딩하기 어려움 2) 정확성의 입증이 어려움 3) 자발적 협력이 필요함 4) 한번의 실수가 모든 시스템에 치명적 영향을 줌

Monitor

monitor monitor-name
{
    shared variable declarations
    procedure body p1(...){
        ...
    }
    ...
    {
        initialization code
    }

}

공유 데이터 접근하려면 monitor 내부의 procedure를 통해서만 가능하게한다. 내부의 procedure는 동시에 실행 안되도록 통제 권한을 준다. 즉 Lock을 걸 필요가 없어진다.

1) 모니터 내에서는 한번에 하나의 프로세스만이 활동가능 2) 프로그래머사 동기화 제약조건을 명시적으로 코딩할 필요 없다. 3) 프로세스가 모니터안에서 기다릴 수 있도록 하기 위해 condition변수 사용

• condition 변수는 wait와 signal 연산에 의해서만 접근가능 1) x.wait(): 기다리는 줄에 줄서서 기다림 2) x.signal(): 접근 다 하고 빠져나가면 signal 호출해서 기다리고 있는 프로세스를 동작하게끔 함

Bounded-Buffer Problem을 Monitor로 해결

1) 하나의 프로세스만 활성화 되기 때문에 entry queue가 줄서서 기다린다. 2) shared data는 x: 내용이 들어있는 buffer를 기다리는줄 y: 비어있는 buffer를 기다리는줄 로 나뉜다. 3) 이 기다리는 줄을 signal()을 통해 깨워준다.

Dining-Philoshphers Problem을 Monitor로 해결

1) 먼저 test로 젓가락을 잡을 수 있는지 테스트한다. 2) 만약 왼쪽 철학자가 밥을 먹지 않았고 본인이 배고프고 오른쪽 철학자도 밥을 먹지 않은 상태라면 먹는다.(잠들어 있으면 깨운다) 3) 만약 밥을 먹지 못한 상태라면 잠든다. 4) 인접한 철학자가 나 때문에 밥못먹고 잠들어 있으면 깨워주려고 test한다.

Semaphore S // 정수값, 자원의 개수

typedef struct{
    int value; // Semaphore
    struct process *L; // 프로세스 wait queue
}semaphore

1) P(S): lock을 건다.

while(S<=0) do no-op;
s--;

공유데이터를 획득하는 과정(줄어듬)

2) V(S): lock을 푼다.

s++;

공유데이터를 반납하는 과정

프로그래머가 Semaphores를 이용할 수 있다.

semaphore mutex;
do{
    p(mutex);
    critical section
    v(mutex);
    remainder section
}while(1);

busy-wait는 효율적이지 못하다. 이를 Block & Wakeup 방식으로 해결가능하다(=sleep lock)

Block/Wake up

1) Block

Semaphore를 획득할 수 없으면 그 프로세스를 Block 시킴

2) Wakeup(P)

누군가가 Semaphore를 쓰고 반납하면 Block된 프로세스 중 하나를 깨워서 Wakeup시킴

P(), V()의 구현

S.value와 프로세스의 관계

세마포어 S의 값인 S.value는 사용 가능한 자원의 개수를 나타냅니다. 이를 통해 자원을 관리하고, 프로세스들이 자원에 접근할 수 있는지 여부를 제어한다.

1) S.value > 0:

사용 가능한 자원이 S.value만큼 있다는 의미입니다. 즉, 여러 프로세스가 자원에 접근하려고 할 때 S.value가 1보다 크다면 자원이 충분히 있어서 기다릴 필요 없이 자원을 사용할 수 있다는 뜻이다.

2) S.value == 0:

모든 자원이 사용 중이라는 의미이다. 즉, 현재 자원을 사용할 수 있는 프로세스는 없으며, 새로운 프로세스는 자원이 해제될 때까지 기다려야 한다.

3) S.value < 0:

자원이 부족하여 대기 중인 프로세스가 있다는 의미이다. S.value가 -1이면 한 개의 프로세스가 자원을 기다리고 있고, -2이면 두 개의 프로세스가 기다리고 있다는 뜻이다.

1) P(S)

s.value--; // 자원요청하는 경우니 1개 감소
if(s.value<0){ // 이미 누가 가지고 가서 자원의 여분 없음
    add this process to S.L; // 리스트에다가 이 프로세스를 연결시킴
    block(); // block시킨다.
}

2) V(S)

s.value++; // 자원을 반환하는 경우니 1개 증가
if(s.value<=0){ // 만약 자원을 반환한 후에도 S.value가 0 이하라면, 여전히 대기 중인 프로세스가 있다는 의미

    remove a process P from S.L;
    wakeup(P); // 잠들어 있는 프로세스 하나를 Semaphore 리스트에서 하나 빼서 깨워줌 (대기 큐에서 빼버린다)
}

즉 <=0이라는 것은 대기상태에 놓인 프로세스가 있다는 뜻이기 때문에 한개를 깨워서 또 자원을 준다. (어차피 반납해서 최소 자원 1개는 있는 상태임)

Busy wait vs Block/Wake up

보통은 Block/Wake up이 효율적이다. CPU를 쓰면서 기다릴 필요 없이 자원을 누군가 가지고 있다고 하면 CPU반납하고 Blocked 된 상태로 돌아가는게 의미있게 이용가능하다.

그러나 overhead가 발생한다. 따라서 critical section의 길이가 짧은 경우에는 Busy/Wait를 하는 것이 나을 수도 있다.

Semaphore의 2종류

1) Counting Semaphore

도메인이 0이상인 임의의 정수값으로 주로 resource counting에 사용 ex> 5, 10(즉 자원의 개수가 여러개 있어서 여분이 있으면 가져다 쓸 수 있다)

2) Binary Semaphore(=mutex)

0또는 1값만 가질 수 있는 semaphore 주로 mutual exclusion(lock/unlock)에 사용 0: 사용중 1: 사용가능함

Deadlock and Starvation

1) Deadlock

둘 이상의 프로세스가 서로 상대방에 의해 충족될 수 있는 event를 무한히 기다리는 현상

P1의 P(S)를 하려고 보니 기다려야한다. P0의 P(Q)도 마찬가지이다. 서로의 것을 요구하다 보니 둘다 같이 대기 상태에 빠진다.

해결방법: 자원을 획득하는 순서를 똑같이 맞춰준다. 결국 P1은대기 P0는 제대로 수행될것이다.

2) Starvation

자원을 자기들끼리 공유하면서 다른 프로세스는 영원히 자기 차례가 오지 못하게 함 = 어떤 특정 친구가 영원히 자원을 얻지 못하고 무한히 기다려야 하는 상황 (어떻게 보면 데드락도 기아의 일종?)