https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRDL1aeugDFAUo

오래 걸렸다. 다른 풀이 방법은 없을까?

풀이

1. 지도에 BC 정보들을 표시

   ① bc index를 표시함

   ② 중복되는 지점은 + 로 연결해서 표시 ( 지도의 type : String )

2. A, B 움직이며 충전

   ① 이동한 위치를 + 를 기준하여 자름 ( 1+3 : 1번 bc , 3번 bc 겹치는 지점 )

   ② BC 선택권이 겹치지 않는 경우, A 선택권 중 가장 power 센것과 B 선택권 중 가장 power 센것 더함

   ③ BC 선택권이 겹치는 경우, 모든 경우 비교 ( A : 1 2 3 , B : 2 3 => 3*2 번의 비교 )

출처 : 이화여자대학교 반효경 (http://www.kocw.net/home/search/kemView.do?kemId=1046323)

Demand Paging

• 실제로 필요할 때 page를 메모리에 올리는 것

  • I/O양의 감소
  • Memory 사용량 감소
  • 빠른 응답 시간
  • 더 많은 사용자 수용

• Valid / Invalid bit의 사용

  • Valid
    • 사용되지 않는 주소 영역인 경우
    • 페이지가 물리적 메모리에 없는 경우
  • 처음에는 모든 page entry 가 invalid로 초기화
  • address translation 시에 invalid bit이 set되어 있으면 “page fault”
    • 요청한 페이지가 메모리에 없는 경우
    • 운영체제가 CPU를 가지고 fault난 페이지를 메모리에 올림

Page Fault

요청한 페이지가 메모리에 없는 경우입니다. page fault가 나면 운영체제는 fault난 페이지를 메모리에 올립니다.

• invalid page를 접근하면 MMU가 trap을 발생시키고 (page fault trap)
  • Kernel mode로 들어가서 page fault handler 가 invoke 됨
• 다음과 같은 순서로 page fault 를 처리
  • invalid reference? (eg. bad address, protection violation) => abort process
    • 잘못된 요청인지 아닌지 체크하는 것
  • get an empty page frame (replace : 없으면 뺏어온다)
  • 해당 페이지를 disk 에서 memory로 읽어온다
    • disk I/O가 끝나기까지 이 프로세스는 CPU를 preempt 당함 (block)
    • Dist read가 끝나면 page tables entry 기록, valid/invalid bit = “valid”
    • ready queue에 process를 insert -> dispatch later
  • 이 프로세스가 CPU를 잡고 다시 running
  • 아까 중단되었던 instruction 재개

Page Replacement

page fault 가 났을 때, 원하는 페이지를 backing area에서 가져오게 됩니다. 만약, 물리 메모리가 모두 사용중인 상황이라면, 페이지 교체가 일어나야합니다.

https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5VwAr6APYDFAWu

DFS 문제이다. 오래 걸렸다. 아직 DFS 실력이 부족하다.

DFS 메소드에 방문 체크 배열을 넘기고, 복사해서 사용하면 시간 초과가 발생한다.

풀이

• 각 방문 지점에서 할 것

  • 방문 체크
  • 현 위치 기준으로 대각선 네 방향 체크

• 원점으로 돌아왔을 때 사각형인지 확인하는 방법

  • 길이가 4이상

  • 방향 전환 횟수가 4 or 3

    • 방향 전환 횟수가 4 인 경우

      

    • 방향 전환 횟수가 3 인 경우

      

출처 : 이화여자대학교 반효경 (http://www.kocw.net/home/search/kemView.do?kemId=1046323)

Deadlock

일련의 프로세스들이 서로가 가진 자원을 기다리며 block된 상태

• 자원
  • 하드웨어, 소프트웨어 등을 포함하느 개념
  • ex) I/O device, CPU cycle, memory space, semaphore 등
• 예시
  • 시스템 2개의 tape drive가 있다
  • 프로세스 P1과 P2 각각이 하나의 tape drive 를 보유한 채 다른 하나를 기다리고 있음

Deadlock 발생의 4가지 조건

• Mutual Exlusioin
  • 매 순간 하나의 프로세스만이 자원을 사용할 수 있음
• No Preemption
  • 프로세스는 자원을 스스로 내어놓을 뿐 강제로 뺏기지 않음
• Hold and wiat
  • 자원을 가진 프로세스가 다른 자원을 기달리때 보유 자원을 놓지 않고 계속 가지고 있음
• Circular wait
  • 자워을 기다리는 프로세스 간에 사이클이 형성되어야 함
  • P0은 P1이 가진 자원을 기다림
  • P1은 P2가 가진 자원을 기다림 ..

자원 할당 그래프

• 자원에서 프로세스쪽으로 나가는 화살표

• 이 프로세스가 이 자원을 가지고 있다.

• 프로세스에서 자원쪽으로 나가는 화살표

  • 이 프로세스가 이 자원을 요청

• 자원 안에 동그라미

  • 자원 개수

• 그래프 안에 cycle이 없으면 deadlock이 아니다

• cycle이 있으면

  • 자원당 인스턴스가 하나밖에 없으면, 데드락
  • 자원의 인스턴스가 여러개면, 데드락수도 있고 아닐수도 있고

• 왼쪽은 데드락, 오른쪽은 데드락이 아님

Logical vs Physical Address

• Logical address (=virtual address)

  • 프로세스마다 독립적으로 가지는 주소 공간
  • 각 프로세스마다 0번지 부터 시작
  • CPU가 보는 주소는 logical address임

• physical address

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

• 주소바인딩 : 주소를 결정하는 것

  • Symbolic address ->Logical Address -> Physical address

Address Binding

컴파일 타임 바인딩이나 로드 타임 바인딩 모두 실행될때 물리주소가 결정되지만,

런타임 바인딩은 실행 이후에도 물리 주소가 바뀔 수 있다.

소스코드 : A위치에 있는 값과 B위치에 값을 더해서 A에 저장해라. C위치로 점프해라

• Compile time binding
  • 물리적 메모리 주소가 컴파일 시 알려짐
  • 시작 위치 변경시 재컴파일
  • 컴파일러는 절대코드(absolute code) 생성
• Load time binding
  • Loader의 책임 하에 물리적 주소 부여
  • 컴파일러가 재배치가능코드를 생성하는 경우 가능
• Execution time binding(run time binding)
  • 수행이 시작된 이후에도 프로세스의 메모리 상 위치를 옮길 수 있음
  • CPU가 주소를 참조할 때마다 binding을 점검
  • 하드웨어적인 자원이 필요 (base and limit registers, MMU)

Memory-Management Unit (MMU)

logical address를 physical address로 매핑해 주는 hardware device