Coding 공부

자바스크립트 typeof는 런타임 중에 에러를 체크한다.

타입스크립트는 타입을 컴파일 중에 체크를 해 에러를 미리 방지해준다.

DP 문제 테이블 방식은 2종류

dp[a][b] = a번의 횟수와 b의 높이가 남았을때의 최저 시도횟수

dp[a][b] = min(dp[a][b], 1 + max(dp[a-1][t-1], dp[a][b-t]))

1~b 사이에서 떨어드렸을 때, 깨지는 경우와 안깨지는 경우의 최악의 경우 max값을 구하고, 거기에 +1을 해준다.

횟수가 1회 남았을시에는 무조건 높이만큼의 횟수가 필요하니 그에 맞게 초기화

 횟수와 상관없이 1층만 남았을때에는 1회로 끝낼수 있으니 그걸로 초기화

다른 dp식 cozyyg 님의 코드를 보고 복기한거 틀릴 수 도 있음

dp[x][y] = x번 던질 기회가 남았을때 y번 시도해서 알 수 있는 유리가 깨지는 최소 높이

dp[x][y] = dp[x][y-1] + dp[x-1][y-1] + 1

y-1번을 시도했을때 x번 던질기회가 남았을때의 값과 ( 즉 깨지지 않았을때와) y-1번을 시도해서 x-1번 던질 기회가 남았을때(깨졌을때를 하면) 이 때의 최소높이는  이 두값을 더하고 + 1을 해준다.

두번째는 제대로 해석했는지는 모르겠다. 

동기식 입출력과 비동기식 입출력

• 동기식 입출력
  • 프로세스가 입출력이 진행될때, instruction이 실행이 안될때
  • I/O 요청 후 입출력 작업이 완료된 후에야 제어가 사용자 프로그램에 넘어감
  • 구현 방법1
    • I/O 끝날때까지 CPU를 낭비시킴
    • 매시점 하나의 I/O만 일어날수 있음
  • 구현 방법2
    • I/O가 완료될 때까지 해당 프로그램에게서 CPU를 빼앗음
    • I/O 처리를 기다리는 줄에 그 프로그램을 줄 세움
    • 다른 프로그램에게 CPU를 줌
• 비동기식 입출력
  • 프로세스가 입출력이 진행될때 instruction이 실행이 될 수 있을때
  • I/O 가 시작된 후 입출력 작업이 끝나기를 기다리지 않고 제어가 사용자 프로그램에 즉시 넘어감
• 두 종류 모두 I/O의 완료는 인터럽트로 알려줌

Thread

• Thread is basic unit of CPU utilization
• 프로세스에서 CPU의 수행단위
• Thread의 구성
  • program counter
  • register set
  • stack space
• Thread가 동료 thread와 공유하는 부분(=task)
  • code section
  • data section
  • OS resources
• 전통적인 개념의 heavyweight process는 하나의 thread를 가지고 있는 task로 볼 수 있다.

• Process 하나에 프로세스 실행단위를 여러개를 두는게 Thread, 각 Thread마다 Program Counter와 register를 별도로 유지
• Thread는 Stack은 별도, Process가 사용하는 state(상태), 자원은 공유하지만, PC와 register는 별도로 유지
• 다중 스레드로 구성된 태스크 구조에서는 하나의 서버스레드가 blocked(waiting) 상태인 동안에도 동일한 태스크 내의 다른 스레드가 실행되어 빠른 처리를 할 수 있다.
• 동일한 일을 수행하는 다중 스레드가 협력하여 높은 처리율과 성능 향상을 얻을 수 있다.
• 스레드를 사용하면 병렬성을 높일 수 있다.(CPU가 여러개일때 가능)

• 프로세스는 한개이기 때문에 PCB는 1개이고, Thread마다 별도의 PC와 Register를 따로 가지고 있다.

• 스레드의 장점
  • 응답성 : Responsiveness
  • 리소스 공유 : Resource Sharing
  • 경제성 : Economy → createing & CPU switching thread
    • Solaris의 경우 2가지 overhead가 각각 30배, 5배
  • Utilization of MP Architectures
    • each thread may be running in parallel on diffrent processor

Implementation of Treads

• Kernal Threads
  • 커널 스레드는 운영체제 커널이 스레드가 여러개인 것을 인지하고 있고, 스레드 변환시, CPU 스케쥴링과 컨텍스트 스위칭에 의해 작동된다.
    • Windows 95/98/NT
    • Solaris
    • Digital UNIX, Mach
• User Threads
  • 라이브러리로 지원되는 스레드
  • 프로세스 내에 스레드가 여러개인걸 운영체제가 모르는 상황
  • 구현상의 제약점이 있다.

프로세스의 개념

• Process is a program in execution

• 프로세스의 문맥(context)

  • 프로그램의 코드가 어디까지 실행을 했는가, data의 변수가 어떻게 되었는가? Register에 어떤 값을 넣어놓고, instruction을 어디까지 실행을 해야했는가에 대한 모든 요소를 문맥이라 한다.
  • CPU의 수행상태를 나타내는 하드웨어 문맥
    • Program Counter
    • 각종 register
  • 프로세스의 주소공간
    • code,data,stack
  • 프로세스 관련 커널 자료구조
    • PCB(Process Control Block) - 운영체제는 프로그램이 실행될때마다, 프로그램을 컨트롤 하기 위한 1개의 PCB block이 생성된다.
    • Kernal stack - 각 프로세스의 코드를 실행 중에, 시스템콜이 일어났을때, 해당 프로세스만의 커널 스택

• Time sharing, Multi Process이기 때문에, 현재 실행중인 프로세스가 다른 프로세스에게 넘겨줄때, 현재의 작업현황을 백업을 해놔야, 다음 실행때, 이어서 작업이 가능하다.

프로세스의 상태(Process State)

• 프로세스는 상태가 변경되며 수행한다.

  • Running

    • CPU를 잡고 instruction을 수행중인 상태

  • Reday

    • CPU를 기다리는 상태(메모리 등 다른 조건을 모두 만족하고 있는상태)

  • Blocked(wait, sleep)

    • CPU를 주어도, 당장 instruction을 수행할 수 없는 상태
    • Process 자신이 요청한 event(I/O)가 즉시 만족되지않아 이를 기다리는 상태( 디스크에서 file을 읽어와야하는 경우 )

  • New : 프로세스가 생성중인 상태

  • Terminated : 수행이 끝난 상태

  • CPU의 Redey Queue에 대기를 한다. 그러다가 CPU에서 Process가 동작을 하다가, I/O 작업이 있을때, Disk Queue에서 대기를 하면서 Process의 상태를 blocked(wait/sleep) 상태로 바뀌어서 들어간다.

  • 이러한 큐들은 Kenal Address space의 자료구조로 있고, 프로세스의 상태를 조정하고, 위치에 따라 queue에 넣어준다.

    Process Control Block(PCB)

- 운영체제가 각 프로세스를 관리하기 위해 프로세스당 유지하는 정보
- OS가 관리상 사용하는 정보
    - Process state, Process ID
    - scheduling information, priority
- CPU 수행 관련 하드웨어 값
    - Program counter, registers
- 메모리 관련
    - Code, data, stack의 위치정복
- 파일 관련
    - Open file descriptors

문맥 교환(Context Switch)

• CPU를 한 프로세스에서 다른 프로세스로 넘겨주는 과정
• CPU가 다른 프로세스에게 넘어갈때 운영체제는 다음을 수행
  • CPU를 내어주는 프로세스의 상태를 그 프로세스의 PCB에 저장
  • CPU를 새롭게 얻는 프로세스의 상태를 PCB에서 읽어옴

• System call이나 Interrupt 발생시 반드시 context switch가 일어나는 것은 아님

• System call이나 interrupt 발생시 Kernal mode로 변환이 일어나지만, 이 것을 Context switch를 의미하지 않고, 사용자 프로세스가 변환이 일어나는 것이 Context switch라고 한다.
• 운영체제로 변환이 일어날때에도 PCB에 저장을 하기 하지만, Context switch가 일어나는 경우보다 부담이 덜하다. ( cache memory flush : 프로세스가 달라지면, 캐쉬 메모리를 다 지워버리는 것을 의미)

프로세스를 스케쥴링하기 위한 큐

• Job queue
  • 현재 시스템 내에 있는 모든 프로세스의 집합
• Ready queue
  • 현재 메모리 내에 있으면서 CPU를 잡아서 실행되기를 기다리는 프로세스의 집합
• Device queues
  • I/O device의 처리를 기다리는 프로세스의 집합
• 프로세스들은 각 큐들을 오가며 수행된다.
• Linked List (head, tail)

• 인터럽트일때 ready queue에 대기를 하는것을 아니다.

스케줄러

• Long-term-scheduler(장기 스케쥴러 or job scheduler)
  • 시작 프로세스 중 어떤 것들을 ready queue로 보낼지 결정
    • 메모리가 생성 시, memory에 올라가는걸 허락
  • 프로세스에 memory을 주는 문제
  • degree of Multiprogramming을 제어
    • 메모리에 프로세스의 수를 제어
  • time sharing system에는 보통 장기 스케쥴러가 없음(무조건 ready)
    • 우리가 사용하는 대부분의 시스템에서는 장기 스케쥴러가 없음
• Short-term scheduler(단기 스케쥴러 or CPu scheduler)
  • 어떤 프로세스를 다음번에 running 시킬지 결정
  • 프로세스에 CPU를 주는 문제
  • 빨라야함(ms 단위)
• Medium Term Scheduler(중기 스케줄러 or Swapper)
  • 여유 공간 마련을 위해 프로세스를 통째로 메모리에서 디스크로 쫒아냄
  • 프로세스에게서 memory를 뺏는 문제
  • degree of Multiprogramming을 제어
    • 메모리에 동시에 올라간 프로그램 수가 많으면, 프로세스를 뺏는다.
  • 요즘 컴퓨터에서 쓰이는 방법

프로세스의 상태 2(현대 운영체제)

• Running , Ready, Blocked은 동일
• Suspended(stopped) : 중기 스케줄러 때문에 생긴 개념
  • 외부적인 이유로 프로세스 수행이 정지된 상태
  • 프로세스는 통째로 디스크에서 swap out 된다.
    • 사용자가 프로그램을 일시정지시킨 경우(break key)
    • 시스템이 여러이유로 프로세스를 잠시 중단시킴
• Blocked는 자신이 요청한 event가 만족되면 Ready로 바뀜
• Suspended는 외부에서 resume 해주어야 Active

컴퓨터 시스템 구조

• CPU는 Program Counter 라는 레지스터가 가리키는 메모리 주소의 instruction의 일만 진행
• CPU는 interrupt line을 instruction을 실행전 매번 확인을 후, interrupt이 들어오면, 운영체제로 권한이 바뀜
• I/O에 접근하는 모든 권한은 mode bit이 0일때에만 가능
• 인터럽트는 하드웨어 인터럽트, 소프트웨어인터럽트가 있다
  • 하드웨어는 I/O가 요청하는 인터럽트
  • 소프트웨어 인터럽트는 트랩이라고 하며, Exception이거나 system call이 있다.

동기식 입출력과 비동기식 입출력

• 동기식 입출력(synchronous I/O)

  • I/O 요청 후 입출력 작업이 완료된 후에야 제어가 사용자 프로그램에 넘어감
  • 구현방법 1
    • I/O가 끝날 때까지 CPU를 낭비시킴
    • 매시점 하나의 I/O만 일어날 수 있음
  • 구현방법2
    • I/O가 완료될때까지 해당 프로그램에게서 CPU를 빼앗음
    • I/O 처리가 기다리는 줄에 그 프로그램을 줄 세움
    • 다른 프로그램에게 CPU를 줌

• 비동기식 입출력

  • I/O가 시작된 후 입출력 작업이 끝나기를 기다리지 않고 제어가 사용자 프로그램에 즉시 넘어감

• 두 경우 모두 I/O의 완료는 인터럽트로 알려줌

DMA(Direct Memory Access) Controller

• DMA는 CPU말고도 메모리에 접근할수 있는 콘트롤러
• DMA는 I/O의 데이터를 메모리에 카피를 해서 올려놓고, 어느 정도 모이면 인터럽트를 걸기
• 빠른 입출력 장치를 메모리에 가까운 속도로 처리하기 위해 사용
• CPU의 중재 없이 device controller가 device의 buffer storage의 내용을 메모리에 block단위로 직접 전송
• 바이트 단위가 아니라, block 단위로 인터럽트 발생시킴

서로 다른 입출력 명령어

• I/O를 수행하는 special instruction에 의해
  • 메모리에 접근하는 address가 따로있고, device address가 따로 있는 방식
• Memory Mapped I/O에 의해
  • 구분없이 Memory address로 위치로 구분할때

저장장치 계층

• 위로 갈수록 Speed가 빨라지고, Cost가 비싸지고, 위로 갈수록 용량이 적고, 휘발성의 차이
• Executable은 CPU가 직접적으로 접근이 가능한 저장장치, byte 단위로 접근 가능
• 하드디스크는 섹터단위로 접근

프로그램의 실행(메모리 load)

• 프로그램을 실행하실 그 프로그램의 독자적인 Address space가 생긴다.
• code,data,stack 이 생긴다.
  • code : 기계어 코드
  • data : 전역변수
  • stack : 함수를 호출하거나 리턴할때 쓰는 용도
• 프로그램의 모든 메모리를 전부 올리는게 아닌, 필요한 부분들만 올린다.
• 디스크의 swap area : 현재는 쓰지 않지만 나중에 필요할지 모르는 메모리들을 적재시켜놓는다.
• swap area는 메모리의 연장 용도
• address translation : 하드웨어의 도움을 받아서, 프로세스의 address space의 상대적인 주소에서, 실제 물리적인 메모리의 주소의 위치로 변화시켜주는 역할

커널 주소 공간의 내용

• 시스템콜, 인터럽트 처리 코드
• 자원 관리를 위한 코드
• 편리한 서비스 제공을 위한 코드
• 각 프로세스들을 관리하기 위한 자료구조도 저장되어 있는 상태
  • Process Control Block
• 사용자 프로그램마다, 독립적인 커널스택을 보유중

사용자 프로그램이 사용하는 함수

• 함수(function)
  • 사용자 정의 함수
    • 자신의 프로그램에서 정의한 함수
  • 라이브러리 함수
    • 자신의 프로그램에서 정의하지 않고, 갖다 쓴 함수
    • 자신의 프로그램의 실행 파일에 포함되어 있다.
  • 커널 함수
    • 운영체제 프로그램의 함수
    • 커널 함수의 호출 = 시스템 콜

1. ts에 대한 타입은 type이나 interface를 통해 지정이 가능하다.

2. 만약 객체의 프로퍼티가 나중에 존재하거나 그럴때에는 선택적 프로퍼티인 ?을 넣어서 선언을 해준다.

3. 배열은 타입[] 으로 선언을 해준다.

4. Element의 subset이 HTMLElement이다.

5. 함수의 리턴값이 여러종류일 때 제너릭을 이용해서, 문제를 해결할 수 있다.

6. Map의 get은 선언한 타입이거나 undefined가 올 수있다. 그러니 널병합연산자로 undefined를 제거해줄수 있다.(부정확)

7. interface는 extends을 통해 확장이 가능하고, 이것은 type일때에는 &와 비슷하다.

8. interface는 여러번 정의가 가능하고, 그럴때마다 프로퍼티가 병합이 된다.

컴퓨터 시스템 구조

• 각각의 io device들은 디바이스들을 조정하는 device controller가 작업을 해준다.
• 디바이스 콘트롤러들도 작업공간이 필요한데, local buffer라 이야기한다.
• cpu 내에는 memory보다 빠른 register라는 저장공간이 있다.
• mode bit은 Cpu에서 실행중인 명령어가 사용자프로그램인지, 운영체제인지 구분해주는 것이다.
• interrupt line : cpu의 실행 중인 명령을 멈추는 입력신호가 있는지 확인하기 위한거(지금 이해한거)
  • ex ) i/o에서 오는 신호가 왔을때
  • timer에서 지정된 시간을 썼다고 왔을때
• time : 특정 프로그램이 CPU를 독점하는것을 막기 위한 하드웨어
• 사용자 프로그램은 I/O에 직접적으로 instrunction을 할 수 없고, 운영체제에게 위임을 한다.
  • 보안상의 이유와 다른이유 때문에 사용자프로그램이 직접 요청을 금지시켰다.
• 키보드 입력이 사용자 프로그램이 있다고 하면, 이 프로그램은 운영체제에 키보드 입력이 필요하다고, 요청을 보내고, 운영체제는 키보드 입력을 받을 수 있도록 작업을 한다.
• 작업을 요청을 한뒤 이 프로그램은 키보드 입력이 들어올때까지는 다음 작업을 수행할 수 없으므로, 다른 사용자프로그램에게 제어권을 넘겨준다.
• 그러다가, 키보드에서 입력이 들어오게 되면 interrupt line을 통해 cpu에 알려주게 되고, CPU에서는 다른 프로그램이 실행중이더라도 인터럽트가 들어왔기 때문에, 잠시 프로그램 실행을 멈추고, 제어권을 운영체제가 가지고 와, 키보드의 입력을 카피해서 키보드입력을 요구했던 프로그램에게 카피를 해준 뒤, 보통은 인터럽트를 당한 프로그램에게 제어권을 넘겨준다.

Mode bit

• mode bit은 0일때에는 모니터모드(커널모드) 1일때에는 사용자모드(사용자 프로그램 수행)
• 보안을 해칠 수 있는 중요한 멍령은 모니터모드에서만 수행가능
• interrupt나 Exception 발생시 하드웨어가 mode bit을 0으로 바꿈
• 사용자 프로그램에게 CPU를 넘기기전 mode bit을 1로 세팅
• 사용자가 프로그램의 잘못된 수행으로 다른 프로그램 및 운영체제에 피해가 가지 않기 위한 보호장치

Timer

• 정해진 시간이 흐른 뒤 운영체제에게 제어권이 넘어가도록 인터럽트 발생
• 타이머는 매 클럭 1틱마다 1씩 감소
• 타이머 값이 0이되면 타이머 인터럽트 발생
• CPU가 특정프로그램이 독점하는 것으로부터 보호
• 타이머는 timer sharing을 구현하기 위해 이용이 되고, 현재시간을 계산하기위해서도 사용한다.

Device Controller

• I/O device controller
  • 해당 i/o 장치유형을 관리하기 위한 일종의 작은 CPU
  • 제어 정보를 위해 control register, status register를 가짐
    • 이 register는 CPU에서 해야할 작업들에 대한 내용이 담기는 것
  • local buffer를 가짐
    • I/O의 실행결과에 대한 데이터들을 저장하거나 출력을 위한 데이터를 저장하는 저장소
• I/O는 device와 locl buffer 사이에 일어남
• Device controller는 I/O가 끝났을 경우 interrupt로 CPU에 그 사실을 알림
• device driver : OS 코드 중 각 장치별 처리루틴 software
• device controller : 각 장치를 통제하는 일종의 작은 CPU hardware

DMA Controller

• direct memory access controller
• 메모리에 직접적으로 접근할 수 있는 컨트롤러
• I/O 장치의 빈번한 인터럽트를 줄여주기 위한 장치
• I/O 장치의 저장된 데이터를 메모리에 직접 적재를 해주고, 모와서 CPU에 알려주는 역할

입출력의 수행

• 모든 입출력 명령은 특권 명령
• 사용자 프로그램이 I/O을 하는법
  • 시스템 콜
    • 사용자 프로그램이 운영체제에게 I/O 요청을 하는 거
    • 일반적인 함수는 사용자프로그램이 자기가 할당된 메모리 내에서 주소를 바꿔가면서 실행이 되지만, I/O 요청은 사용자 프로그램 메모리를 벗어난 OS의 메모리에 요청을 보내야하기 때문에 직접적으로 점프를 하는것이 불가능
    • 그렇기 때문에 사용자프로그램은 소프트웨어적으로, CPU에게 I/O 요청이 있음을 interrupt신호를 보냄
    • 이 interrupt 신호를 받은 CPU은 interrupt가 왔기 때문에 mode bit을 0으로 전환 후 OS모드 실행
  • trap을 사용하여 인터럽트 벡터의 특정위치로 이동
  • 제어권이 인터럽트 벡터가 가리키는 인터럽트 서비스 루틴으로 이동
  • 올바른 I/O 요청인지 확인후 I/O 수행
  • I/O 완료시 제어권을 시스템콜 다음명령으로 옮김

인터럽트

• 인터럽트 당한시점의 레지스터와 program counter를 save 한 후 CPU의 제어를 인터럽트 처리 루틴에 넘긴다.
• 넓은의미
  • interrupt (하드웨어 인터럽트 )
  • trap(소프트웨어 인터럽트)
    • 프로그램이 오류를 범한 경우 (Exception)
    • 프로그램이 커널 함수를 호출하는 경우 (System call)
• 인터럽트 벡터
  • 해당 인터럽트의 처리 루틴 주소를 가지고 있음
• 인터럽트 처리루틴 ( 인터럽트 서비스 루틴, 인터럽트 핸들러)
  • 해당 인터럽트를 처리하는 커널 함수

시스템 콜

• 사용자 프로그램이 운영체제의 서비스를 받기 위해 커널 함수를 호출 하는 것

import sys
from math import ceil

def input():
    return sys.stdin.readline().rstrip()


N,AC,AP,BC,BP = map(int,input().split())

if AP*BC < BP*AC:
    AC,AP,BC,BP = BC,BP,AC,AP


answer = float('inf')

for A_COUNT in range(BC):
    B_COUNT = ceil((N-A_COUNT*AC)/BC)
    isover = False
    if B_COUNT<0:
        B_COUNT = 0
        isover = True
    answer = min(answer, A_COUNT*AP + B_COUNT*BP)
    if isover:
        break

print(answer)

헷갈려서 어려웠던 문제

최소공배수를 이용해서 풀어야하는 문제이다.

가성비가 좋은 것을 B로 시작하는것을 두고

가성비가 안 좋은 것을 A라고 햇을시,

AB개만큼 구매를 한다고 했을시에는 무조건 B를 A개 사는것이 이득이다.

즉 이말은 A를 B개 미만으로 사는것이 장미를 최소한의 값으로 구매하는것임을 인지하고,

A묶음의 장미를 B번 사는 것 미만으로 샀을때

장미의 값을 계산을 해주면 되는 문제이다.

문제를 풀때 a,b가 헷갈려서 너무 어려웠던 문제였다. 조심해서 풀자.